(블로그 이사하면서 옮겨진 글입니다)
C#의 Dictionary는 다른 언어의 Dictionary나 Hashmap처럼 Key를 통해서 O(1)에 가까운 시간에 Value를 얻어낼 수 있는 자료형이다.
많은 언어들이 그렇게 구현하는 것처럼, C#에서도 HashTable을 통해서 Dictionary를 구현한다(1). 이를 통해서 O(1) 시간에 Value의 위치를 특정할 수 있다. 또한 동일한 Key값이 이미 있는지를 체크하기 위해서 IEqualityComparer 인터페이스를 사용한다(1). 그리고 이 HashTable을 구현하는데 쓰이는 Hash Function은 GetHashCode함수를 사용한다(2).
여기까지가 공식문서에 쓰여있는 내용이다. 그렇기 때문에, 그 외의 세부 구현은 버전에따라 쉽게, 아무런 공지도 없이 바뀔 수 있다. 하지만 세부 구현 내용이 궁금해서 조금 더 찾아보다보니 (3)의 글을 발견했다. 요약하자면, Dictionary의 Add를 사용할 때 중복키 에러가 나오는 경우는 두개의 키 k1,k2에 대해서 k1.Equals(k2) == true만 만족하는 경우가 아니라, k1.GetHashCode() == k2.GetHashCode()까지 동시에 만족하는 경우이다.
생각해보면, 내가 대입하려는 키 k2에 대해서 k1.Equals(k2) == true가 성립하는 어떤 값 k1이 존재하는지를 알아내기 위해서는 모든 키에 대해서 Equals를 호출해보아야하는데 이는 Dictionary를 쓰는 이유를 훼손시킨다. 그러니 내가 Add를 하려는 곳에서 이미 Equals를 만족하는 키가 있는지만 체크를 해야하고, 내가 Add를 하려는 곳은 GetHashCode에 의해 결정되므로 위 두 조건이 만족되어야만 두개는 정말로 같은 키로 취급되는 것이다.
그리고 C# 버전이 2인 시절의 내용이라(현재 최신 버전은 10) 실제 세부구현이 이미 변경되었을 수도 있지만, MSDN에서 제공해주는 문서에 따르면 Dictionary의 Key Conflict는 linked list로 처리한다고 한다.(4)
(1) https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?redirectedfrom=MSDN&view=net-6.0
(2) https://docs.microsoft.com/en-us/dotnet/api/system.object.gethashcode?view=net-6.0#system-object-gethashcode
(3) https://stackoverflow.com/a/1407510
(4) https://docs.microsoft.com/en-us/previous-versions/ms379571(v=vs.80)?redirectedfrom=MSDN
