원인 : 해시함수의 입력값은 무한한반면 출력값의 가짓수는 유한하기에 발생이 일어난다.
이러한 충돌로 인해서 클러스터링(연속된 레코드에 데이터가 몰리는 현상) 이나 오버플로우( 버킷에 할당된 슬룻 수보다 많이 할당이 되어 더 이상 넣지 못하는 경우) 가 발생한다.
이와 같은 문제를 해결하기 위해서는 크게 3가지 방법이 있다.
첫번째는 체이닝이다.
<체이닝>
체이닝이란 버킷 내에 연결리스트를 할당하여 버킷에 데이터를 삽입하는 것이다. 그렇기에 버킷에 제한이 없어지므로 오버플로우를 방지할 수가 있다.
두번째는 개방 주소법이다.
개방 주소법에는 크게 선형 탐색, 2차 검색법, 이중 해시가 있다.
<선형 탐색>
선형탐색이란 해시가 충돌이 일어날 시 다음 버켓이나 혹은 몇 단계를 건너뛰어서 데이터를 삽입하는 것이다.
장점 : 구현이 간단함. 캐시의 효율이 높음.
단점 : 최악의 경우 해시테이블 전체를 모두 돌아야 함. 데이터의 클러스터링에 취약하다.
<2차 검색법>
2차 검색법은 선형 탐색과 달리 저장할 위치로부터 떨어진 영역을 차례대로 검색하여 처음으로 빈 영역에 키를 저장하는 방법이다.
장점 : 선형 검색법에서 발생하는 제1밀집문제를 제거
단점 : 같은 해시값의 키들로 인하여 제2밀집문제가 발생
캐시 효율과 클러스터링 방지 측면에서 선형 검색법과 이중해시의 중간에 있다.
<2중 해시>
2중 해시란 해시 충돌시 다른 함수를 한번 더 적용해서 키 값을 내는 것이다.
장점 : 클러스터링의 영향이 거의 없음.
단점 : 캐시 효율이 떨어짐, 연산량을 많이 요구함.
세번째는 리사이징이다.
리사이징은 말 그대로 새로운 배열에 기존 배열의 키를 다시 재 해싱하는 것이다.
단점 : 사이즈가 커짐, 알맞은 크기가 아닐 경우에 연속적으로 연산이 들어감.
장점 : 오버플로우 방지