2.2.6 딕셔너리

해시맵 혹은 키/값으로도 알려진 딕셔너리(dictionary)는 가장 유용하고 많이 사용되는 데이터 구조 중 하나이다. 우리는 이 데이터 구조의 능력을 당연하게 여기는 경향이 있다. 딕셔너리는 키와 값을 저장할 수 있는 컨테이너이다. O(1) 복잡도의 상수 시간 안에 키를 사용하여 값을 검색할 수 있다. 즉, 데이터 검색 속도가 매우 빠르다. 왜 이렇게 빠를까? 숨겨진 비밀이 뭘까?

비밀은 단어 해시에 있다. 해싱이란 임의의 데이터에서 숫자 하나를 생성하는 것을 의미하는 용어이다. 생성된 숫자는 결정론적이어야 한다. 즉, 동일한 데이터는 동일한 숫자를 생성해야 하지만, 반드시 고유한 값을 생성할 필요는 없다. 해시 값을 계산하는 방법은 여러 가지다. 일부 객체를 해싱하는 로직은 GetHashCode에 구현되어 있다.

해시는 언제나 동일한 값을 가지므로 검색할 때 사용하면 좋다. 예를 들어 해시 값이 모두 있는 배열일 경우 배열 인덱스를 사용하여 해당 값을 검색할 수 있다. 하지만 이러한 배열은 모든 int가 4바이트를 차지하고 약 40억 개 정도의 값을 가질 수 있기 때문에 생성된 딕셔너리마다 약 16기가바이트가 필요할 것이다.