Hash 충돌 회피 방법은 무엇이 있을까?

Open Address

데이터를 삽입하려는 해시 버킷이 이미 사용중인 경우라면 다른 해시 버킷에 데이터를 삽입하는 방법이다. 데이터를 찾을때는 Linear Probing, Quadratic Probing 등의 방법을 이용한다.

Separate Chaning에 비해 캐시 효율이 높다는 장점이 있어 데이터 개수가 적다면 효율이 좋다. 그렇지만 배열의 크기가 커진다면 캐시 효율이 낮아지기 때문에 장점이 사라진다.

데이터를 삭제할때 효율적이지 못하다는 단점이 있다.

저장된 데이터가 많아진다면 Separate Chaining 보다 느려진다는 단점이 있다. 해시 버킷을 채운 밀도가 높을수록 충돌이 발생할 확률이 높기 때문이다.

 

선형탐사 : 해시 충돌시 다음 버킷에 저장하는 방법이다.

이차 방정식 탐사 : 2차 방정식을 이용해 위치를 구해 저장하는 방법

제곱 탐사 : 해시 충돌시 제곱만큼 건너뛴 버킷에 저장하는 방법이다.

이중해시 : 해시 충돌시 다른 해시함수를 이용해 한번 더 적용한 결과를 저장한다.

 

Close Address(Chaning)

다른 버킷을 이용하는 것이 아니라 연속적으로 묶어서 처리하는 방법으로 충돌을 회피한다.

리스트 혹은 트리를 이용하여 구현한다.

메모리를 더 사용한다는 단점이 존재한다.

 

Separate Chaining : 버킷에 LinkedList에 대한 주소를 가지고 있는 방식이다.

동일 index으로 인한 충돌이 일어난다면 LinkedList에 노드를 추가하여 해결한다.

 

 

출처 : https://d2.naver.com/helloworld/831311