알고리즘...94

해시 테이블 충돌 해결

원소를 저장하려고 할 때 이미 다른 원소가 저장되어 있는 경우 충돌이 발생하게 된다.

 

이를 해결하는 방법으로 다음과 같은 방법들을 사용한다.

• 체이닝 같은 주소로 해싱되는 원소를 연결 리스트로 관리, 적재율이 1을 넘을 수 있음
  • 검색, 추가, 삭제 시 해싱 후 연결 리스트를 통한 연산이 추가된다.
• 개방 주소 방법 어떻게든 주어진 해시 테이블 내에서 충돌을 관리, 적재율이 1을 넘을 수 없음
  • 선형 조사 충돌이 일어난 바로 직후를 확인하여 처리를 진행하는 방식
    • 특정 영역에 원소가 몰리는 경우 성능이 떨어진다.
  • 이차원 조사 충돌 직후의 위치를 보는 대신 이차 함수에 따라 검색 폭을 넓히면서 확인하는 방식
    • 여러 원소가 동일한 초기 해시 함숫값을 가지면 동일한 폭으로 검색하게 되므로 성능이 떨어진다.
  • 더블 해싱 두 개의 해시 함수를 사용하며 충돌이 생기는 경우 두 번째 해시 함숫값만큼 이동하는 방식
    • 두 번째 해시 함숫값이 해시 테이블 크기와 서로 소인수 값이어야 한다.
    • 권장되는 함숫값은 첫 번째 해시 함수를 h(x) = x mod m으로 잡고, 두 번째 해시 함수를 m 보다 조금 작은 소수 m'에 대해 f(x) = 1 + (x mod m')로 잡는 것이다.

 

적재율이 높아지면 효율이 급격히 떨어지므로 적당한 임계점을 설정 후 임계점을 넘는 시점에 해시 테이블의 크기를 두 배로 키우고 원소를 다시 해싱하는 것이 일반적이다.

 

※ 충돌이 일어난 뒤 특정 원소를 삭제한 경우 적절한 검색을 위해 삭제한 부분을 'Deleted' 등으로 표시한다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘