데이터 구조의 오버플로 처리

새 쌍(키, 요소)에 대한 홈 버킷이 가득 찼을 때 오버플로가 발생합니다.

오버플로를 처리할 수 있습니다.

가득 차지 않은 버킷에 대해 체계적인 방식으로 해시 테이블을 검색합니다.

• 선형 탐색(선형 개방 주소 지정).
• 2차 프로빙.
• 무작위 조사.

각 버킷이 홈 버킷인 모든 쌍의 목록을 유지하도록 허용하여 오버플로를 제거합니다.

• 배열 선형 목록입니다.
• 체인.

모든 요소가 해시 테이블에 직접 저장되도록 개방형 주소 지정이 수행되므로 다양한 방법을 구현하여 충돌 해결을 시도합니다.

Linear Probing은 테이블의 다음 열린 슬롯에 데이터를 배치하여 충돌을 해결하기 위해 수행됩니다.

선형 프로빙의 성능

• 최악의 경우 찾기/삽입/삭제 시간은 θ(m)이며, 여기서 m은 테이블의 쌍 수로 처리됩니다.
• 모든 쌍이 동일한 클러스터에 있을 때 발생합니다.

선형 프로빙 문제

• 식별자는 함께 묶이는 경향이 있음
• 인접한 클러스터가 합쳐지는 경향이 있음
• 검색 시간 증가 또는 향상

2차 프로빙

선형 탐색은 버킷을 검색합니다(H(x)+i2)%b; H(x)는 x의 해시 함수를 나타냅니다.

2차 프로빙은 i의 2차 함수를 증분으로 구현합니다.

1<=i<=(b-1)/2

b는 4j+3 형식의 소수로 표시되고, j는 정수

무작위 조사

Random Probing은 임의의 숫자로 통합을 수행합니다.

H(x):= (H’(x) + S[i]) % b
S[i] is a table along with size b-1
S[i] is indicated as a random permutation of integers [1, b-1].