버킷 인스턴스에 대한 해시 키

Question

hash key --> bucket instance 매핑의 경우 어떤 알고리즘이 최상의 배포를 산출합니까?

즉, 해시 함수 (아마 SHA-1)가 있고 n 버킷이 있다고 가정 해 보겠습니다. 키를 버킷에 매핑하는 데 어떤 알고리즘을 사용해야합니까? 예 : 하위 비트, 상위 비트, 다른 것?

Answer 1

일반적으로 버킷 수를 사용하여 해시 값을 mod으로 설정하면됩니다. 드물지만 버킷 수가 2의 거듭 제곱이면 bitwise-and를 사용할 수 있습니다.

hash function에 위키 발췌 :

가

일반적인 솔루션은 매우 넓은 범위 (예를 들어, 0 ³² 2 - 1)과 고정 된 해시 함수를 계산하고, 그 결과에 나누어 n을 입력하고 부분의 나머지 부분을 사용하십시오. n 자체가 2의 거듭 제곱 인 경우비트 마스킹 및 비트 시프트로 수행 할 수 있습니다. 이 접근법을 사용할 때 해시 함수는 응용 프로그램에서 발생할 수있는 n에 대해 결과가 0과 n-1 사이에 균등하게 균일하도록 이되도록 선택해야합니다. 기능에 따라, 특정 n에 대해서만 나머지가 균일 할 수있다. 홀수 또는 소수.

Answer 2

SHA-1 및 기타 cryptographic hash functions은 이미 균등 분포로 모든 출력을 동일한 확률로 생성하는 것처럼 보이는 경향이 있습니다.

원하는 출력 범위에서 적절한 수의 비트를 선택하여 원하는 범위의 숫자를 지정하면됩니다.

공간에 대한 이해를 돕기 위해 해시 함수 및 해시 테이블에 대한 자료를 학습하여 요구 사항을 기반으로 정보에 입각 한 선택을 할 수 있습니다. Wikipedia 또는 CLR과 같은 알고리즘 텍스트 북에서 시작할 수 있습니다. 결국 Knuth으로 이동할 것입니다.