해시 테이블 알고리즘

  해시 테이블 

해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조로 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다.

 

해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다.

 

※ 테이블의 모든 영역에 값을 적절하게 분배하지 못하는 경우 성능이 떨어질 수 있다.

 

해시 함수

해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다.

• 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
• 계산이 간단해야 한다.

 

만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때문에 입력된 데이터가 해시 테이블 전체에 골고루 나누어 저장되는 것이 상당히 중요하다.

 

해시 함수는 대표적으로 두 가지 방법이 존재한다.

• 나누기 방법 주어진 데이터를 해시 테이블의 크기로 나눈 나머지를 인덱스로 사용하는 방법
  • 해시 테이블의 크기는 2의 멱수(2ⁿ)에 가깝지 않은 소수(prime number)를 택하는 것이 좋다.
  • h(x) = x mod m
• 곱하기 방법 주어진 데이터를 0과 1 사이의 소수(decimal)로 대응시킨 뒤 해시 테이블의 크기를 곱하여 인덱스로 사용하는 방법
  • 데이터를 0과 1 사이의 값으로 만들 수 있는 상수 값을 미리 준비해야 한다.
  • 잘 동작하는 상수 값으로 (root 5 - 1) / 2 가 제안되어 있다.
  • h(x) = └m(xA mod 1)┘

 

※ 해시 함수가 테이블의 값을 분배하는 역할을 하므로 해시 테이블의 성능을 해시 함수가 결정한다고 할 수 있다.

 

해시 테이블 충돌 해결

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

 

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

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

 

쉽게 배우는 알고리즘 해시 테이블 그림 6-5, 6-7

 

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

 

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

 

쉽게 배우는 알고리즘 해시 테이블 그림 6-9

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

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