해싱 함수 충돌 해결 방법

- 클러스터링 (Clustering)

: 자료들이 해시 테이블에 고르게 분포되지 않고 특정 주소들 주위로 뭉치게 되는 현상

 

- 개방 주소 (Open Addressing)

> 조사법 (Probing)이라고도 함

> 주소가 비어있지 않으면 그 다음 주소를 확인하고 안비어 있으면 되풀이

 

1) 선형 조사법

-> 주소를 1씩 증가

2) 제곱 조사법

-> 주소를 조사 횟수의 제곱만큼씩 증가

3) 이중 해싱

-> 원래 해싱 함수와는 다른 추가적인 해싱 함수 이용

 

- 체이닝 (Chaining)

> 해시 테이블의 구조를 변경하여 각 주소(버킷)에 하나 이상의 검색 키 값이 저장될 수 있도록 함