[자료구조] 해시(Hash) 충돌이란?

Hash 충돌이란?

 해시함수의 입력값은 무한하지만, 출력값의 가짓수는 유한(출력값, 즉 키가 유한하지 않다면 해시기법을 사용하는 의미가 없다.)하므로 해시 충돌은 반드시 발생한다.(비둘기집 원리)

 

 

 

  위의 그림에서 Sandra Dee라는 사람의 연락처를 삽입하는 상황을 가정해보자. Sandra Dee라는 키는 John Smith라는 키와 결과값이 같다. 둘 사이에 충돌이 일어난 것이다. 그러자 충돌이 일어난 주소(혹은 색인)의 bucket에 레코드가 추가로 담긴 것을 확인할 수 있다. 만약에 해당 bucket에 충분한 공간이 없다면? 오버플로우가 발생한다.

 

 이러한 해시 충돌을 해결하는 방법에는 여러가지가 있다.

1. 체이닝(Chaining)

 버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식이다. 그림2를 다시보자, Sandra Dee라는 사람의 연락처를 삽입할 때, 충돌이 일어나니 버켓 내에서 연결리스트로 데이터를 연결하는 것을 확인할 수 있다. 

 

2. 개방 주소법(Open Addressing)

 체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다.(Closed Addressing) 하지만 개방 주소법의 경우에는 다르다. 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방 주소법이라고 한다. 개방 주소법은 대표적으로 3가지가 있다.

 

 

선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.

제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)

이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

 

 

개방 주소법에는 더 많은 방법들이 있다. 그리고 지금까지 다뤄본 해싱과 개념이 살짝 다른 '동적 해싱'도 있다. 사족으로 아래에 체이닝과 개방주소법의 비교를 추가하여 기재해봤다.

 

 

 

 

 

✨체이닝(Chaining)의 장점 

• 연결 리스트만 사용하면 된다. 즉, 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.
• 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생한다. (그림 3 참조)  
•  

✨개방주소법(Open Addressing)의 장점

•   체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.
•  삽입,삭제시 오버헤드가 적다.
•  저장할 데이터가 적을 때 더 유리하다.