Hash Collision, 해시 충돌시 해결방법

해시 충돌이 일어났을 경우 해결하는 방법은 크게두 가지가 있습니다.

1. 체이닝(Close Addressing)

해시 충돌이 발생하면 키에 해당하는 데이터들을 연결하는 방식입니다.

 

1) 연결 리스트를 사용하는 방식(Linked List)

• 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision이 발생하면 해당 bucket의 list에 추가하는 방식이다.
• 삭제 또는 삽입이 간단하다.
• 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다.

2) Tree를 사용하는 방식 (Red-Black Tree)

 

트리를 사용하는 방식은 메모리 사용량이 많다.

 

 

2. 개방 주소법(Open Addressing)

해시 충돌이 일어나면 다른 버킷에 데이터를 저장하는 방식입니다.

 

1) 선형탐색

 

해시 충돌시 다음 버킷에 저장하는 방법

 

 

2) 제곱 탐색

 

해시 충돌시 제곱만큼 건너뛴 버킷에 데이터를 저장하는 방법

 

 

3) 이중 해시

 

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

 

 

장점 :

• 체이닝처럼 포인터가 필요 없고, 지정한 메모리 외에 추가적인 공간이 필요 없습니다.
• 삽입 삭제시 오버헤드가 적습니다.

단점 :

• 최악의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있습니다.
• 특정 위치에만 데이터가 몰리는 현상이 나타날 수 있습니다.