Hash Collision 해시 충돌

정의

• 해시값을 이용하여 데이터를 저장할때 해시주소가 겹쳐 충돌하는 경우 생기는 문제
• Open Addressing / Separate Chaining 두가지 방법으로 해결을 한다
• Open Addressing
  • 저장하려는 데이터에 할당한 해시주소가 이미 존재한다면 다른 주소로 새롭게 할당하는 방식
• Separate Chaing
  • 해시 테이블의 구조를 변경하여 하나 이상의 키값을 저장할 수 있도록 만드는 방법
• Java에서는 Separate Chaing를 사용하여 해쉬 충돌을 해결

해시 충돌의 해결 방법

1. Chaning

해시 버킷내 링크드 리스트를 할당하여 버킷에 데이터를 삽입하다 해시 충돌이 발생하면 링크드 리스트로 데이터를 연결하는 방식

• 장점
  • 링크드 리스트 하나로 해결 가능하기에 복잡한 계산식을 사용할 필요가 없다.
  • 개방주소법의 선형탐색에 비해서 성능저하가 적다
  • 성능저하 참고 이미지

 

2. Open Addressing개방 주소법

1의 체이닝은 버킷이 꽉 차더라도 링크드리스트로 계속해서 늘려가기에 데이터의 주소값은 바뀌지 않는다.(Closed Addressing)

개방 주소법은 해시 충돌이 일어나는 경우 다른 버킷에 데이터를 삽입하는 방식을 말한다.

개방 주소법은 3가지 방식으로 나눌 수 있다.

1. 선형 탐색
   1. 해시 충돌시 다음 버킷, 혹은 몇개를 건너뛰어 데이터를 삽입한다
2. 제곱 탐색
   1. 해시 충돌시 제곱만큼 건너뛴 버킷에 데이터를 삽입한다(1, 4, 9 , 16)
3. 이중 해시
   1. 해시 충돌시 다른 해시함수를 한번 더 적용한 결과를 이용한다

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