해시 충돌(Hash Collision)과 최적화 방법

해시 충돌

해시함수는 해시테이블의 키 값으로 레코드가 저장되어 있는 주소(또는 색인)을 산출하는 함수이다. 다른 내용의 데이터가 같은 키를 갖는 상황을 해시 충돌이라고 하는데, 같은 키 값이 생긴다는 것은 특정 키의 버켓에 데이터가 집중된다는 뜻이다. 따라서 빈번한 해시 충돌은 해시테이블의 성능을 저하시킨다.

 

해결 방법 1) 체이닝

버켓 내에 연결리스트를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터를 연결하는 방식이다. 복잡한 계산식을 사용할 필요가 없고, 삭제 또는 삽입이 용이하다.

 

해결 방법 2) 개방 주소법

체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려갈 수 있기 때문에 데이터의 주소값은 바뀌지 않는다. 그러나 개방 주소법은 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입한다. 대표적으로 다음과 같은 3가지 방법이 있다.

• 선형 탐색: 해시 충돌 시 다음 버켓이나 몇 개를 건너뛰어 데이터를 삽입
• 제곱 탐색: 해시 충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입한다.
• 이중 해시: 해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용한다.

개방주소법은 포인터가 필요없고, 추가적인 저장공간이 필요없다는 장점이 있다. 

 

참고

https://preamtree.tistory.com/20

https://javannspring.tistory.com/238