확장 가능 해시로 비어있는 버킷을 만드는 방법

Question

필자는 종이에 확장 가능한 해싱을하는 방법을 알고 있지만 비어있는 버킷을 만드는 방법을 알지 못합니다.

확장 가능 해시에서 비어있는 버킷이 생성되게하려면 어떻게해야합니까? 간단한 예를 보여줄 수 있습니까?

Answer 1

해시 함수 h(x)이 h(x) = x이고 각 버킷이 두 가지를 포함 할 수 있다고 가정합니다.

해시 디렉토리의 인덱스와 마찬가지로 해시 코드의 최하위 비트를 최상위 비트와 반대로 사용합니다.

기본적으로 빈 버킷을 얻으려면 공백이없는 버킷에 무언가를 배치하여 해시 테이블을 두 배로 만들려고하지만 두 배가 실패하기를 원합니다.

그럼 삽입하겠습니다.

먼저, h(0) = 0 및 0 % 2 = 0부터 첫 번째 버킷에 넣어야합니다.

다음에 4를 입력하십시오. h(4) = 4 및 4 % 2 = 0부터 첫 번째 버켓에 들어가야합니다.

이제 버켓은 버킷에 두 가지만 저장할 수 있으므로 8을 삽입하면 테이블 크기가 두 배로 증가해야합니다. 따라서 전역 해시 수준은 1에서 2으로 증가합니다. 다른 변경 사항에는 새로운 세 번째 버킷과 두 번째 버킷을 가리키는 네 번째 해시 인덱스가 포함됩니다.

불행히도 다시 해싱 프로세스가 h(x) % 4이고 모든 숫자가 (의도적으로) 4의 배수이기 때문에 첫 번째 버킷은 너무 채워져 있고 세 번째 버킷은 비어 있습니다. 이것은 해시 테이블을 두 배로 늘려서 해결됩니다.