일반적으로 간단한 해시 함수는 입력의 “구성 요소 부분”(문자열의 경우 문자)을 취하고 상수의 거듭 제곱을 곱한 다음 정수 유형으로 함께 추가하여 작동합니다. 예를 들어 문자열의 전형적인 (특히 좋지는 않지만) 해시는 다음과 같습니다.

(first char) + k * (second char) + k^2 * (third char) + ...

그런 다음 첫 번째 문자가 모두 같은 문자열 묶음이 공급되면 적어도 정수 유형이 오버플로 될 때까지 결과는 모두 동일한 모듈로 k가됩니다.

[예를 들어, Java의 문자열 hashCode는 이와 매우 유사합니다. k = 31로 문자를 역순으로 수행합니다. 따라서 같은 방식으로 끝나는 문자열간에 모듈로 31과 눈에 띄는 관계를 얻었고, 끝 근처를 제외하고는 같은 문자열 사이에서 모듈로 2 ^ 32의 눈에 띄는 관계를 얻습니다. 해시 테이블 동작을 심각하게 망칠 수는 없습니다.]

해시 테이블은 버킷 수에 대한 해시 계수를 가져와 작동합니다.

충돌이 해시 테이블의 효율성을 감소시키기 때문에 해시 테이블에서는 가능한 경우 충돌을 일으키지 않는 것이 중요합니다.

이제 누군가가 첫 번째 문자가 모두 같은 것처럼 항목 사이에 관계가있는 해시 테이블에 전체 값을 넣었다고 가정 해보십시오. 이것은 상당히 예측 가능한 사용 패턴이므로 너무 많은 충돌을 일으키기를 원하지 않습니다.

해시에 사용 된 상수와 버킷 수가 coprime 이면 “수학의 특성 때문에”수학 적인 경우 충돌이 최소화되는 경우 가 종종 있습니다. 그들이 coprime 이 아닌 경우충돌이 최소화되지 않은 입력 간에는 매우 간단한 관계가 있습니다. 모든 해시는 공통 계수와 동일한 모듈로 나오므로 공통 계수의 모듈로 값을 갖는 버킷의 1 / n 번째에 해당합니다. n 배 많은 충돌이 발생하는데, 여기서 n은 공통 요소입니다. n은 2 이상이므로 상당히 간단한 유스 케이스가 일반적인 경우보다 최소 두 배의 충돌을 생성하는 것은 허용되지 않습니다. 일부 사용자가 배포판을 버킷으로 나누려는 경우 간단한 예측 가능한 사용법이 아니라 이상한 사고가 되길 원합니다.

이제 해시 테이블 구현은 분명히 항목에 넣은 항목을 제어 할 수 없습니다. 그들은 그들이 관련되는 것을 막을 수 없습니다. 따라서 할 일은 상수와 버킷 수를 동일하게 유지하는 것입니다. 이렇게하면 작은 공통 요소와 관련하여 버킷의 계수를 결정하기 위해 “마지막”구성 요소에만 의존하지 않습니다. 내가 아는 한, 그들은 이것을 달성하기 위해 소수가 될 필요는 없으며 단지 coprime입니다.

그러나 해시 함수와 해시 테이블이 독립적으로 작성된 경우 해시 테이블은 해시 함수의 작동 방식을 모릅니다. 작은 요인으로 상수를 사용하고있을 수 있습니다. 운이 좋으면 완전히 다르게 작동하고 비선형적일 수 있습니다. 해시가 충분하면 모든 버킷 수는 괜찮습니다. 그러나 편집증 해시 테이블은 좋은 해시 기능을 가정 할 수 없으므로 소수의 버킷을 사용해야합니다. 마찬가지로 편집증 해시 함수는 큰 소수 상수를 사용해야하므로 누군가 상수와 공통 요소를 갖는 여러 버킷을 사용할 가능성을 줄입니다.

실제로 버킷 수로 2의 거듭 제곱을 사용하는 것이 일반적이라고 생각합니다. 이 방법은 편리하며 적절한 크기의 소수를 검색하거나 미리 선택하지 않아도됩니다. 따라서 승수도 사용하지 않는 해시 함수에 의존합니다. 일반적으로 안전한 가정입니다. 그러나 위와 같은 해시 함수를 기반으로 때때로 해시 동작이 잘못 발생할 수 있으며 주요 버킷 수는 더 도움이 될 수 있습니다.

“모든 것이 가장 중요하다”는 원칙을 고수하는 것은 해시 테이블에 대한 적절한 배포를 위해 충분하지만 필요한 조건은 아는 한입니다. 다른 사람이 동일한 규칙을 따랐다 고 가정 할 필요없이 모든 사람이 상호 운용 할 수 있습니다.

[편집 : 소수의 버킷을 사용해야하는 또 다른보다 전문적인 이유가 있습니다. 선형 프로빙과의 충돌을 처리하는 경우입니다. 그런 다음 해시 코드에서 보폭을 계산하고 해당 보폭이 버킷 수의 요인이되면 시작한 곳으로 돌아 가기 전에 (bucket_count / stride) 프로브 만 수행 할 수 있습니다. 가장 피해야 할 경우는 stride = 0입니다. 물론 특수 사례이어야하지만 작은 정수와 같은 특수 케이스 bucket_count / stride도 피하기 위해 bucket_count를 소수로 만들 수 있습니다. stride가 0이 아니라면 제공됩니다.]

---

답변