과연 닷넷 라이브러리의 dictionary , hashtable, hashset의 해시 정밀도는 얼마나 될까요…?
기본 GetHashCode는 Int32 범위였던걸로 기억중입니다.
그리고, IEquatable 또는 거기서 구현된 Equals를 이용해서 Key를 비교할 텐데,
그렇다면 단지 Hash를 이용한 비교는 얼추 비슷한 대부분의 값을 걸러내는 데에만 사용하고 땡일까요?
제 얕은 지식에 의하면 hash의 값은 중복 가능성이 있다고 알고 있습니다.
그리고 닷넷의 dictionary는 bucket 단위로 한번 더 구분을 하는 걸로 알고 있는데요,
평소 사용하는 수준에선 (거의) 그럴 일 없겠지만
아주 낮은 확률으로나마 중복 확률이 있다고 하면 찝찝하다는 생각이 들었습니다.
왠지 이렇게 생각해보니 또 보안적인 이슈도 있을 수 있겠다는 두루뭉술한 생각도 드네요.
관련 정보를 얻을수 있는 방법 또는
혹여나 제가 실험해볼수 있는 힌트가 있다면 부탁드립니다.
SHA-1은 암호학적 해시 알고리즘으로, 많은 언어에서 해시테이블 등에서 활용하기 위해 객체마다 구현하도록 하는 해시 코드와는 쓰임도 평가 기준도 다릅니다. 일례로 SHA-1은 160비트 공간을 쓰지만 .NET의 Object.GetHashCode() 메서드는 32비트 공간을 씁니다. 암호학적 해시 알고리즘이야 해시 결과로부터 입력값을 예측 수 없게 하는 것이나 현실에서 해시 충돌이 일어나지 않도록 하는 것이 아주 중요한 요건이지만, 해시테이블에서의 해시 함수는 충돌 가능성을 열어두고 쓰는 것입니다.
말씀하신 것처럼 다른 객체여도 해시 코드가 같으면 한 통에 담게 되어 있고, 그 안에서 결국 Object.Equals(Object) 내지는 IEquatable<T>.Equals(T) 메서드를 연달아 호출하며 완전히 일치하는 객체를 찾게 되어 있습니다. (물론 한 통에 객체가 하나만 있는 겨우에는 그럴 필요 없음.) 이는 그냥 해시테이블이라는 자료 구조가 원래 그렇게 만들어진 것으로 크게 이상하게 볼 것은 아닙니다. 요는 동등 비교를 아예 안 하겠다는 게 아니라 비싼 동등 비교를 덜 하고 찾겠다는 데에 있기 때문입니다.
마지막으로 해시 코드의 충돌 가능성은 Dictionary<TKey, TValue> 같은 컨테이너 구현보다는 각 TKey 자료형의 GetHashCode() 메서드의 구현에 따라 달라질 것으로 보입니다. 극단적으로는 32비트 내에 표현 가능한 정보만 담는 객체는 충돌 가능성이 아예 없게 해시 코드를 만들 수 있습니다. Int32 같은 자료형은 스스로를 그대로 해시 코드로 써도 될테니까요.
