C# 또는 .NET 의 Dictionary<TKey,TValue> 또는 Hashtable의 정밀도가 얼마나 될까요?

지극히 개인적인 궁금증이 생겨서 질문드립니다.

과연 닷넷 라이브러리의 dictionary , hashtable, hashset의 해시 정밀도는 얼마나 될까요…?
기본 GetHashCode는 Int32 범위였던걸로 기억중입니다.
그리고, IEquatable 또는 거기서 구현된 Equals를 이용해서 Key를 비교할 텐데,
그렇다면 단지 Hash를 이용한 비교는 얼추 비슷한 대부분의 값을 걸러내는 데에만 사용하고 땡일까요?

제 얕은 지식에 의하면 hash의 값은 중복 가능성이 있다고 알고 있습니다.
그리고 닷넷의 dictionary는 bucket 단위로 한번 더 구분을 하는 걸로 알고 있는데요,
평소 사용하는 수준에선 (거의) 그럴 일 없겠지만
아주 낮은 확률으로나마 중복 확률이 있다고 하면 찝찝하다는 생각이 들었습니다.

왠지 이렇게 생각해보니 또 보안적인 이슈도 있을 수 있겠다는 두루뭉술한 생각도 드네요.

관련 정보를 얻을수 있는 방법 또는
혹여나 제가 실험해볼수 있는 힌트가 있다면 부탁드립니다. :pray:

좋아요 2

해시 정밀도라는게 사이즈를 말씀하시는걸까요??

좋아요 2

음… 아마 모든 데이터에 대해 유일한 값을 뽑아주는가? 인거 같습니당

좋아요 2

이걸로 내용이 보충이 될 지는 모르겠는데,
비교를 할 때 쓰이는 hash 값의 크기쯤 될 것 같습니다.
또는
@마수리 님께서 말씀해주신
어느 범위까지 유일한 값을 뽑을수 있을까 도 맞겠네요.

아무래도 해시 충돌을 방지하기 위한 여러 기술이 추가되어있을텐데,
이건 기업 영업비밀일까요?ㅎㅎ

좋아요 1

hash 값은 hash를 만든 알고리즘에 따라 크기?(길이)가 고정자리수로 정해져있습니다.

아마 해시 충돌에 대해서 궁금하신걸로 보이는데용

구글 연구팀이 SHA-1 알고리즘에 대해서 서로 다른 데이터가 같은 hash 값을 뽑아낼 수 있다는 것을 증명했습니다.

그래서 이걸 계기로 빅테크 기업이 더 정교한 hash 알고리즘을 사용하는 걸로 변경했다고 알고있습니다.

그리고 대중적인 SHA-256 알고리즘은 아직까지는 충돌이 증명되진 않았습니다.

이 자료구조들이 어떤 hash 알고리즘을 사용하는지 먼저 알아보고 그에대해 해시충돌을 검색해보시면 좋을 것 같습니다!

좋아요 4

맞는 말씀이십니다. MS doc을 봐도 어떤 알고리즘을 쓰는지는 안 알려준 것 같아서요.
제가 못 찾은 탓도 있을 테고…

좋아요 1

.net 프레임워크 소스에는 미리 정의된 소수 리스트가 있으며, 버킷 크기는 엘리먼트 개수에 따라 적절한 소수 값으로 정의 됩니다. 엘리먼트 개수가 달라진다고 바로 반영 되는 것은 아니고 확장될 때 새로운 소수를 찾아 버킷 개수를 늘려줍니다.

고로 해시 충돌은 발생되나 최소화할 수 있는 방안들이 마련되어 있다로 보면 될 것 같습니다.
그리고 닷넷 소스에서 소수 리스트를 참조하는 클래스들 보니 dictionary, hashtable이 있네요. 아마도 해시와 연관된 클래스들은 같은 방식을 취하는 것 같습니다.
image

설명대로 리사이즈하는 코드들도 있네요.


Insert 할때에도 충돌 개수가 일정수준을 넘어가면 늘려주네요. 코드상으로는 100개입니다.

해시코드 크기는 int형이네요.

닷넷코드입니다~
https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,312

좋아요 4

링크 감사합니다. mscorlib 뜯어놓은걸 보는 곳이 있었네요!
닷넷 github에도 비슷한게 있으려나…

좋아요 2

.net core 3.0 이후부터는 문자열 해시코드는 marvin32 알고리즘을 사용하고, hashtable이나 dictionary의 키로 사용하면 이 알고리즘으로 동작합니다.

이게 c로된 코드 같은데 어렵네요 ;;

좋아요 7

SHA-1은 암호학적 해시 알고리즘으로, 많은 언어에서 해시테이블 등에서 활용하기 위해 객체마다 구현하도록 하는 해시 코드와는 쓰임도 평가 기준도 다릅니다. 일례로 SHA-1은 160비트 공간을 쓰지만 .NET의 Object.GetHashCode() 메서드는 32비트 공간을 씁니다. 암호학적 해시 알고리즘이야 해시 결과로부터 입력값을 예측 수 없게 하는 것이나 현실에서 해시 충돌이 일어나지 않도록 하는 것이 아주 중요한 요건이지만, 해시테이블에서의 해시 함수는 충돌 가능성을 열어두고 쓰는 것입니다.

말씀하신 것처럼 다른 객체여도 해시 코드가 같으면 한 통에 담게 되어 있고, 그 안에서 결국 Object.Equals(Object) 내지는 IEquatable<T>.Equals(T) 메서드를 연달아 호출하며 완전히 일치하는 객체를 찾게 되어 있습니다. (물론 한 통에 객체가 하나만 있는 겨우에는 그럴 필요 없음.) 이는 그냥 해시테이블이라는 자료 구조가 원래 그렇게 만들어진 것으로 크게 이상하게 볼 것은 아닙니다. 요는 동등 비교를 아예 안 하겠다는 게 아니라 비싼 동등 비교를 덜 하고 찾겠다는 데에 있기 때문입니다.

마지막으로 해시 코드의 충돌 가능성은 Dictionary<TKey, TValue> 같은 컨테이너 구현보다는 각 TKey 자료형의 GetHashCode() 메서드의 구현에 따라 달라질 것으로 보입니다. 극단적으로는 32비트 내에 표현 가능한 정보만 담는 객체는 충돌 가능성이 아예 없게 해시 코드를 만들 수 있습니다. Int32 같은 자료형은 스스로를 그대로 해시 코드로 써도 될테니까요.

좋아요 7

친절하고 상세한 답변 감사합니다. 힌트가 많이된 것같습니다.
좀더 찾아보려 했는데 도움이 될 것 같습니다!

좋아요 1