[알고리즘] 해시 충돌 해결 방법 | Hash Collision

Seperate Chaining

추가적인 공간을 활용해 충돌을 해결한다. seperate 뜻에 맞게 Linked-List를 사용한다.

보통 헤드에 삽입한다. (테일에 삽입하면 테일까지 가는 시간이 걸리기 때문)

최악의 경우 하나의 해시에 데이터가 몰리면, 조회할 때 Linked-list를 탐색하는 시간이 걸리게 된다.

 

 

Open Addressing

• Linear Probing

해시 충돌 발생 시 충돌이 발생하지 않을 때까지 해시를 linear 하게 탐색한다. 

단, clustering 군집현상이 발생할 수 있다.

 

 

• Quadratic Probing

충돌 발생 시 해싱 함수에 특정 연산을 더해 새로운 해시를 제작한다. 보통 제곱연산을 쓰는데 추가적인 상수곱이나 제곱연산이 가능하다.

 

사진을 예시로 3번째 값 hf_qp(506, i) = 11에서 (i는 충돌횟수)

i=0일 때 key가 1이므로 충돌이 발생한다.

i=1일 땐 11+1^2=12 해시가 2이므로 또 충돌이 발생한다.

i=2일 때 11+2^2=15 해시가 5이므로 충돌이 발생하지 않는다.

 

아무리 다른 key여도 해싱 함수가 같은 해시를 반환한다면, 아무리 i값을 증가시키더라도 계속 충돌을 발생시킨다.

 

• Double Probing

충돌이 일어나면 해싱함수를 다시 한 번 사용해 해시의 해시(?)를 구한다.

 

 

 

+)

JDK7 이전은 linked list로 seperate chaining을 사용

JDK8부터 linked list와 red-black tree를 혼용한 sperate chaining을 사용

 

https://www.youtube.com/watch?v=dKqv1mQotNU&ab_channel=%EC%89%AC%EC%9A%B4%EC%BD%94%EB%93%9C