C# Dictionary의 성능에 대해서.

원문 https://stackoverflow.com/questions/3460729/is-there-a-limit-to-entries-in-a-dictionary

질문 : 3000개정도의 다른 데이터들이 있다. 그것을 구조체에 저장해서 관리하려고 한다.

 

그리고 나의 어플리케이션이 시작할 때 그 데이터들을 전부 Dictionary에 저장 해놓고 게임이 시작하기 전에 불러오려고 한다.

 

이것들의 성능이 궁금하다. 이정도의 데이터가 게임을 느리게 할 것인지? 

 

그리고 TryGetValue와 ContainsKey가 느린지?

 

 

 

답변 : 해쉬들이 잘 분포되어 있을때 그정도의 크기에서 TryGetValue와 ContainsKey는 꽤나 빠르다. 

 

Dictionary는 인덱스를 달 수 있는 버킷들(데이터를 담을 빈 공간)을 갖고있다. 

 

키를 이용해 값을 추가하거나 찾을 때 그것은 GetHashCode()를 이용해서 값을 반환한다. 

 

GetHashCode()에서는 버킷들의 수보다 적은 값이 나오도록 해쉬를 하고, 그것으로 관련된 버킷을 찾는다. 

 

버킷은 아마 비어 있거나 안에 여러 개의 아이템들이 있을것이다. Dictionary는 아이템들을 Equals()를 통해 비교한다.

 

찾고자 하는 버킷을 찾는 것은 O(1) 시간이 걸린다. 

 

그 다음에 같은 버킷 안에 들어있는 값들에 대해서 비교하는 것은 O(n)이 걸린다. 

 

여기서 O(n)은 Dictionary 모든 요소에 대한 것이 아니고 버킷 안에서 만이다.

 

일반적으로는 같은 버킷 안에 적은 수의 아이템들이 있을 것이다,

 

만약에 해쉬가 나쁘게 됐으면(중복이 많게) 같은 버킷 안에 많은 키값들이 있을 것이고 시간복잡도는 O(n)에 가까워질 것이다

 

최악의 경우는 List보다 나쁠 것이다, 왜냐하면 List역시 O(n)이지만 딕셔너리는 좀 더 큰 오버헤드를 갖고 있기 때문에.

이것이 의미하는게 걱정 할 만한일인가? 아니다, 심지어 상대적으로 원초적인 해시방법을 쓰더라도 좋은 결과를 얻을 것 이다.

 

만약에 키를 string으로 쓰고 있다면 충분하고도 남는다. 만약에 간단한 빌트인타입을 사용하고 있다면 그건 더 좋을 것이다.

 

 

만약에 딕셔너리 안에서 데이터를 찾는데 오래 걸린 다는 것을 발견 한다면, GetHashCode()하는 방법을 고치거나 IEqualityComparere(외부에서 GetHashCode(),Equals()를 정의)를 만들면 된다.

 

 

하여튼 3000개는 아무것도 아니고, 괜찮을 것이다.