큰 숫자의 ConcurrentDictionary

Question

왜 ConcurrentDictionarygetOrAdd 방법은 항목 번호가 커짐에 따라 속도가 많이 느려지는지 궁금합니다.

3 개의 중첩 된 루프에서 호출하고 각 루프의 시간을 파일로 인쇄하면 각 루프의 실행 시간이 선형으로 늘어나고 왜 가장 좋은 루프가 있는지 알 수 있습니다. 같은 크기. 나는 그것이 ConcurrentDictionary의 문제라고 추측하고 있었다. 그러나 그것이 내가 여기에서 묻고있는 이유 다.

의견이 있으십니까?

Answer 1

충돌로 인한 것입니다. ConcurrentDictionary은 버킷 목록을 유지 관리하며 GetHashCode 메서드가 반환하는 결과는 항목이 배치 될 버킷을 결정합니다. 이상적으로 각 항목은 별도의 버킷에 있어야합니다. 그러나 실제로는 불가능합니다. GetHashCode이 2 개의 다른 키에 대해 동일한 값을 반환하면 충돌이 나타나고 더 많은 항목이 동일한 버킷에 배치됩니다.

각 설정에서 각 버킷은 연결된 목록으로 구현됩니다. 충돌이 감지 될 때마다 사전은 주어진 항목이 이미 있는지 확인하기 위해 링크 된 목록을 스캔해야합니다. 이 사전에 요소가 많을수록 링크 된 목록이 길어지고 반복되는 데 더 많은 시간이 소요됩니다.

그런데 표준 사전은 다른 방식으로 구현되지만 비슷한 방식으로 작동합니다. 두 데이터 구조의 내부 구조에 대한 좋은 설명은 찾을 수 있습니다 here