[알고리즘-이론] 해시 테이블 (Hash Table)

---

해시 테이블

해시 테이블은 검색의 평균 시간 복잡도가 O(1)이 되는 검색에 최고의 알고리즘이다.

 

검색 트리는 원소가 저장될 자리가 이미 트리에 존재하는 원소와 비교하여 결정되는 반면, 해시 테이블은 원소가 저장될 자리에 값에 의해 결정되는 자료구조이다.

 

해시 테이블은 단계적으로

검색키 -> 주소 계산 -> 테이블 참조

 

의 흐름으로 검색이 이루어진다.

• 검색 키

  해시 함수 h(x) = x mod m에 의해 검색 키가 결정되고 x는 사용자 입력 값,(배열 값) m은 해시 테이블의 크기를 뜻한다.

• 주소 계산

  주소 계산은 검색 키를 통해서 x mod m을 실질적으로 행하는 과정이다.

• 테이블 참조

  검색 키를 통한 주소 계산이 이루어진 후 검색을 하는 단계이다. 원소가 저장될 자리가 값에 의해 결정되므로 평균 한 번의 검색으로도 참조가 가능하다.

 

해시 테이블에 원소가 차 있는 비율은 해시 테이블의 성능에 매우 중요한 영향을 미친다. 이 비율을 적재율이라고 하며 해시 테이블의 크기가 m이고, 저장된 원소의 총 수가 n이라면 적재율은 n/m 이다.

 

해시 테이블 예제

 

---

입력: 25, 13, 16, 15, 7 에서 해시 함수 h(x) = x mod 13을 함께 분석해보자.

• 검색 키: h(x) = x mod 13
• 해시 테이블의 크기 = 13

Round 1

• 25를 해시 함수로 돌렸을 때 나오는 값: 25 mod 13 = 12
• 테이블 열 12번째 Index에 추가

Round 2

• 13을 해시 함수로 돌렸을 때 나오는 값: 13 mod 13 = 0
• 테이블 열 0번째 Index에 추가

Round 3

• 16을 해시 함수로 돌렸을 때 나오는 값: 16 mod 13 = 3
• 테이블 열 3번째 Index에 추가

Round 4

• 15를 해시 함수로 돌렸을 때 나오는 값: 15 mod 13 = 2
• 테이블 열 2번째 Index에 추가

Round 5

• 7을 해시 함수로 돌렸을 때 나오는 값: 7 mod 13 = 7
• 테이블 열 7번째 Index에 추가

Round 6

• 완료!

해시 함수

---

해시 함수는 키 값을 입력으로 받아 해시 테이블상의 주소를 리턴한다고 했는데 해시 함수는 다음 두 가지 성질을 가지도록 만들어야 한다.

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

• 계산이 간단해야 한다.

첫 번째 성질이 가장 중요한데, 이 성질을 잘 만족해야 서로 다른 두 원소가 한 주소를 놓고 충돌할 확률이 작아지기 때문이다!!

해시 함수를 만드는 대표적인 방법

1. 나누기 방법

나누기 방법은 지금까지 맛보기로 수행했던 해시 함수의 검색 키와 동일한 구조이다.
h(x) = x mod m

• 해시 테이블의 크기 : m
• 해시 테이블의 크기 m : 2의 멱수에 가깝지 않은 소수로 구성되어야 한다.

2. 곱하기 방법

h(x) = m(xA mod 1)
해시 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 한 것이다.

1. 해시 테이블은 입력 값을 0과 1사이의 소수로 대응시킨다.

2. 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 확장시킨다.

이 방법에서 중요한 것은 해시 함수의 특성을 결정짓는 0 < A < 1 범위의 상수 A이다.

• 상수 A를 정한다. 이 때 상수 A의 범위는 0<A<1이다.
• 입력 x에 A를 곱한다.
• m을 곱한다.

결론: 나누기 방법은 구현하기 쉽지만 크기가 제한적인 테이블만 사용할 수 있는 반면 곱하기 방법은 제한적인 테이블만 사용하더라도 범위가 커지는 장범이 있다.

---

충돌 해결

해시 함수는 어떤 값에 모듈러 연산을 통해 값을 얻는다고 하였는데 만약 모듈러한 값이 같게 되면 즉 (13, 26, 39) 가 입력으로 들어왔다고 하면 모두 13을 키로 갖는 해시함수 x mod 13을 수행한 결과는 0이 되므로 같은 주소에 들어가려고 한다. 이를 충돌 이라고 한다.

충돌을 해결하는 방법에는 크게 두 가지 방법이 있다.

1. 체이닝 방법

같은 주소에 해싱되는 원소를 모두 모아 하나의 연결 리스트에 매달아서 관리.

해시 테이블의 크기가 m 이면 최대 m개의 연결 리스트가 존재함.

2. 개방 주소 방법

해시 테이블 시간 복잡도

해시 테이블은 해시 함수를 통해 실제 값을 갖는 테이블에 참조 하도록 설계가 되어있기 때문에 입력의 시간 복잡도는 O(1)이 된다.

해시 테이블의 특징

해시 테이블 자바 코드