해싱을 사용한 검색

Question

10 개의 버킷이있는 해시 테이블이 있고 S1 ~ S7 기호가 선형 프로빙을 사용하는 해싱 함수를 사용하여 초기 입력됩니다. 존재하지 않는 항목을 검색하는 데 필요한 최대 비교 수는 얼마입니까? - S7

1 - - - S1

2 - - 빈

3

IndexKEY

• 0 해싱 도면으로 설명 될 수있다 - - S4

,

• 4 - - 빈

• 6 - - - S2

• 5 - S5

• 7 - -

• 8

빈 - - S6

• 9 - - S3

S8 요소 (분명히 존재하지 않음)를 찾고 싶다고 가정 해 봅시다. S8에 대한 해시 함수를 계산하면 지수 8로 점프한다고 가정합니다. 선형 탐색을 통해 색인 8에서 요소를 찾지 못하면 다음 색인을 검사합니다 등등. Now, the number of comparisons should come out to be total length of the array because by linear probing it should try to look in every index ...하지만 실제 답변은 5입니다! : | 제발 누구나 설명!

Answer 1

선형 검사는 빈 해시 버킷에 도달 할 때까지 요소를 찾습니다. 이 경우 8, 9, 0, 1 및 2를 검사합니다. 버킷이 비어 있기 때문에 2시에 멈 춥니 다.

삭제는 버킷을 삭제 된 것으로 표시하지만 선형 프로브 체인이 끊어지는 것을 방지하는 특수한 "삭제 표시"값으로 바뀌어 처리됩니다. 따라서 선형 프로브는 빈 요소가있는 경우에도 올바르게 작동합니다.