작성: 조민성 (슈어소프트테크  SW시험자동화연구소 책임)

원문: http://preshing.com/20110504/hash-collision-probabilities/

작성일 : 2014년 6월 12일

hash값의 크기에 따른 충돌 가능성

확률에 기반하여 ID를 부여하는 모든 구조를 사용할때 다뤄야하는 데이터의 크기에 따라 충돌 가능성이 얼마나 되는지 찾아보던 중에..

좋은 자료가 있어서 공유 합니다.

간단히 요약하면, 32비트 길이의 해쉬값을 사용하는 경우 9292개의 데이터 요소를 다루게 되면 100번에 한번 꼴로 충돌이 일어 납니다.

포커에서 풀 하우스가 나올 확률보다 6배나 높습니다.

즉 왠만하면 32비트 길이 해쉬는 사용하면 안되는 겁니다.

대강 생각해서 32비트 정수 범위인 4억분에 1정도라고 생각하는것 보다는 훨씬더 적은 데이터 에서도 충돌을 눈으로 목격 할 수가 있는 겁니다.

64비트 길이의 해쉬에서는 192만 개의 데이터를 다루게 되면 천만번에 한번 꼴로 충돌이 일어 납니다.

(실생활에서 비슷한 경우가 로또 1등 확률 정도가 된다고 합니다.)

물론 분포도가 좋지 않은 해쉬함수를 사용하는 경우에는 여기서 언급하는것 보다 훨씬 적은 데이터 에서도 높은 충돌을 보일수 있습니다. MD5 등의 검증된 해쉬 함수를 쓰는게 좋겠죠.