해시 함수 및 테이블 크기 2^p

Question

해시 테이블 버켓 인덱스를 키의 해시 코드에서 계산할 때 버킷 배열의 크기가 클수록 나눗셈 (모듈러) 후에 나머지를 사용하지 않는 이유는 무엇입니까? 2의 거듭 제곱인가?

Answer 1

해시를 계산할 때 값의 전체 범위에서 좋은 값으로 물건을 저렴하게 넣을 수있는 정보를 원합니다. 해시 테이블에 저장할 항목이 많지 않으면 (32 억 개 이상) 32 비트 부호없는 정수가 일반적으로 좋습니다.

해시 코드를 실제로 관심이있는 버킷 색인으로 변환 중입니다. 버킷 수 n이 2의 거듭 제곱이면 해쉬 코드 h와 (n -1), 결과는 h mod n과 같습니다.

이 문제가 발생할 수있는 이유는 AND 연산이 단순히 해시 코드에서 상위 수준 비트 인 비트를 삭제하기 때문입니다. 이것은 다른 것들에 따라 좋거나 나쁠 수 있습니다. 한편으로는 AND보다 훨씬 빠르며 (왜냐하면 2 버켓의 힘을 사용하는 것을 선택하는 일반적인 이유이기도하지만) 반면에 빈약 한 해시 함수는 하위 비트에서 열악한 엔트로피 : 즉, 해시되는 데이터가 변경 될 때 하위 비트가 많이 변경되지 않습니다.

Answer 2

표 크기를 m = 2^p라고합시다. k를 키로 둡니다. 그러면 k mod m을 할 때마다 k의 이진 표현의 마지막 p 비트 만 얻습니다. 따라서 마지막 p 비트가 동일한 여러 키를 입력하면 해시 함수는 모든 키가 테이블의 동일한 슬롯에 해시됨에 따라 매우 잘 수행됩니다. 따라서, 2의 힘을 피하십시오