Hashtables : 두 번째 해시 함수가 테이블 크기의 배수를 반환 할 때의 이중 해시

Question

이중 해싱을 통한 열린 주소 지정을 사용하여 C++에서 HashTable을 구현하고 있습니다. 내가 제대로이 부분을 구현 한 생각

indexInProbingSequence = (originalIndex + i * hashFunction2(key)) % tableSize 

:

나는 이중 해싱의 기본 원리가 있다는 것을 이해합니다. 이것은 숙제를위한 것이며 특정 코드 조각에 대한 조언을 구할 수없는 수업 정책이므로 저를 신뢰해야합니다.

문제점을 일으키는 것으로 보이는 이유 중 일부 키는 두 번째 해시 함수의 적용을받는 경우 (소수) 테이블 크기의 배수 인 값을 반환하는 경우가 종종 있습니다. 이러한 경우 프로빙 시퀀스의 모든 인덱스는 동일합니다. 예를 들면, :

originalIndex = 32 
hashFunction2(key) = 3035446 
tableSize = 211 

프로빙 시퀀스는 다음 등등

(32 + 1 * 3035446) % 211 == 32 
(32 + 2 * 3035446) % 211 == 32 

와.

무엇이 누락 되었습니까?

Answer 1

나는 당신이 무엇이든 놓친 적이 있다고 생각하지 않으며 특별히 hashFunction2(key) == 0 일 때 테이블 크기에 관계없이 문제가 발생한다고 생각합니다.

hashFunction2(key) 대신 (hashFunction2(key) % (tableSize - 1) + 1)을 사용하십시오. 스트라이드는 테이블 크기를 기준으로 링을 생성하는 것이 바람직합니다 (프로브가 결국 전체 테이블을 포함한다는 말투) 또는 적어도 큰 기간은 실패합니다. 테이블 크기가 소수이므로 0을 피해야한다는 것을 의미합니다.