-1
왜 2의 제곱 수 또는 10의 소수 또는 소수가 좋은 해싱 함수가 될 수 없습니까? 우리가 해시 함수에 오버플로 레코드를 저장하려면 왜 해시 함수를 선택하는 것이 좋지 않습니까?해싱 Google 인터뷰
A
답변
4
해시 함수가 32 비트 부호없는 결과를 반환한다고 가정합니다. 여러분이하는 일은 효과적으로, index = hash & 0xFFF입니다. 해시 값의 상위 20 비트를 버립니다. 자, 해시가 인 경우, 실제로는이 좋고 나머지 12 비트는 나머지만큼 좋으므로 문제가되지 않습니다. 그러나 해시가 32 비트에 비해 꽤 좋지만 하단 12 비트가 의심스러운 경우 (예 : 문자열의 마지막 문자가 더 강하게 영향을받을 수 있음) ... 그러면 상위 20 개를 버리는 것을 후회할 수 있습니다 이 경우 홀수 계수를 선택하면 index = hash % modulus 결과는 해시의 모든 32 비트에 따라 다릅니다. 당신의 해시 모듈 M을 계산하고 인덱스가 hash % N으로 가지고가는 경우에
그래서, 더 일반적으로, 다음, 당신이 원하는 것은 당신의 M 및 N이 될 공동 프라임입니다. M (이것은 일반적으로) 2^m 경우 생성 index 하단 n 비트 해시 하단 n 비트 직선 복사본이기 때문에
다음 N=10^n 가난한 선택이다.
숫자 자체는 잘 숫자이며 해시 함수가 아닙니다. 컨텍스트를 더 제공 할 수 있습니까? 아마도 해시 함수에 대한 공식을 작성 하시겠습니까? – mvp
당신은 2와 10의 지수와 소수 (prime number)를 계수로 사용한다고 가정할까요? gcc의 구현은 소수 모듈을 사용합니다. 모듈러스는 필요한 버킷 수에 따라 간단히 증가합니다. – Pradhan
정확하게 맞습니다. 왜 해싱 함수의 계수로 2,10과 소수의 힘을 선택하는 것이 최고의 메모리 관리 결과를 얻지 못하는 것입니까? – Shrerocx