완벽한 해시 함수?

Question

위키 피 디아에서 pigeonhole principle을 읽는 동안 "가능한 키 수가 배열의 인덱스 수를 초과하기 때문에 해시 테이블에서 충돌이 불가피합니다. 해킹 알고리즘은 아무리 똑똑해도 충돌을 피할 수 없습니다" . 그러나 정확하게 이것을하는 gperf가 아닙니까?

계몽하십시오.

Answer 1

gperf은 미리 정의 된 문자열 목록에 따라 해시 함수와 해시 테이블을 만듭니다.

따라서 gperf은 충분한 가능성이 있도록 충분히 긴 해시를 만듭니다.
위와 같은 가능한 모든 키를 알고있는 경우에만 할 수 있습니다. 위키피디아의 항목에 설명이없는 가정이며, "비 상수"해시 테이블과 관련이 있습니다.

Answer 2

gperf의 웹 사이트에서 "지정된 문자열 목록의 경우 해시 함수와 해시 테이블을 생성합니다 ..."- 즉 함수를 준비하기 위해 이전에 모든 문자열을 알아야한다는 것을 의미합니다. 충돌없이.

일반적인 프로그래밍 언어에서 사용하는 일반적인 해시 함수는 입력으로 차례대로 문자열을 처리 할 수 ​​있으므로 목록이 동시에 제공되지 않으므로 충돌을 일으킬 수 있습니다.