"MOD PRIME"유형의 해시 함수를 사용하는 것 이상을 고려하지 않았으며 반환 된 해시 값을 사용하여 값을 저장하는 방법으로 다소 혼란 스럽습니다. HashMap.해시 테이블 - 해시 값을 인덱스에 매핑
키가 64 비트 int (long long int) 인 HashMap을 구현하고 싶습니다. 긴 정수를 반환하는 해시 함수가 있습니다. 문제는이 반환 된 해시 값을 사용하여 테이블 인덱스를 결정하는 가장 좋은 방법은 무엇입니까? 내 테이블은 해시 값의 범위보다 분명 작을 것입니다.
최적의 테이블 크기를 선택하기위한 지침이 있습니까? 또는 해시 값을 테이블 크기에 매핑하는 가장 좋은 방법은 무엇입니까?
감사합니다.
어떤 시점에서 테이블의 크기를 조정해야합니다. 사용하는 방법에 따라 크기 변경 및 복사 작업 중 모든 키를 다시 해시하거나 extendible hashing 또는 linear hashing과 같은 어떤 형태의 dynamic hashing을 사용해야합니다.
질문의 첫 번째 부분에 답하는 것과 마찬가지로 모듈로 소수를 사용 했으므로 모듈로 테이블 크기 해시 값을 사용하여 색인을 가져올 수 있어야합니다 (64 비트 int 크기가 2^16 인 테이블은 64 비트 해시의 16 개 최하위 비트 일뿐입니다. 테이블 크기는 모든 데이터와 여유 공간을 보유 할만큼 큰 크기를 선택합니다 (실제로 0.75의 값이 사용됩니다). 삽입물이 많을 것으로 예상되는 경우 더 많은 헤드 룸을 제공해야합니다. 그렇지 않으면 항상 테이블의 크기가 조정됩니다. 위에서 언급 한 동적 해싱 알고리즘을 사용하면 모든 크기 조정 작업이 시간이 지남에 따라 상환되므로 필요하지 않습니다.
또한 해시 테이블의 동일한 해시 된 위치에있는 동일한 버킷 (해시 함수 merely tells you where to start looking)에 두 개의 항목을 저장할 수 있습니다. 따라서 실제로는 해시 테이블의 각 위치에 항목 배열이 있어야합니다. open addressing을 사용하여 해시 충돌을 처리하면이 문제를 피할 수 있습니다.
물론 다른 해시 함수를 선택하면 더 잘할 수 있습니다. 귀하의 목표는 dynamic perfect hashing 또는 universal hashing과 같은 것을 사용하여 테이블의 각 크기에 대해 perfect hash function (재사용시 재연 마할 수있는 경우) 일 것입니다.