Lecture 11 - 해시 테이블

---

해시 테이블

원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조이다.

트리에서도 값에 의해 위치가 달라지는 것 같지만 그것은 트리를 사람이 이해하기 쉽게 그렸을 때의 위치이며 메모리 상에서의 위치는 키 값에 따라 달라지는 것이 아니다.

평균 상수 시간에 삽입, 삭제, 검색이 가능하여 매우 빠른 응답을 요하는 응용에 유용하다. 예를 들면 119 긴급구조 호출과 호출번호 관련 정보 검색, 주민등록 시스템 등 에서 이용된다.

다만 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않는다. 따라서 sorting같은 과정보다는 다순한 삽입 검색등의 과정에 적합한 자료구조이다.

 

위와 같이 검색키를 통해 주소계산을 하고 constant time으로 테이블에 값이 존재하는지 검색한다.

 

크기 13인 해시 테이블에 5개의 값이 입력된 예시를 보자. 해시 테이블에 원소가 차 있는 비율은 적재율이라고 하며 해시 테이블의 성능에 큰 영향을 끼친다. 다음 예시는 적재율 = 5/13 인 상황이다.

해시함수 h(x) = x mod 13를 기반으로 테이블에 원소를 채웠음을 알 수 있다.

---

해시 함수

해시 함수는 임의의 키 값을 입력받은 후 일정한 구간 내의 값(해시 테이블 상의 주소)으로 변환 하는 역할을 수행한다.

아래의 두 가지 성질을 만족하여야 한다.

1.입력 원소가 해시 테이블 전체에 골고루 저장될 수 있도록 해야 함
2.계산이 간단해야 함

첫 번째 조건이 굉장히 중요하며, 만약 서로 다른 키 값들에 대해서 같은 주소값을 반환하게 되면 충돌이 발생하여 해시 테이블의 성능이 저하된다.

 

간단한 예시를 보자 우선 다음은 나누기 방법(Division method)이다.

ℎ(𝑥) = 𝑥 mod 𝑚

간단하고 직관적임을 알 수 있다.

 

다음은 곱하기 방법(Multiplication method)이다.

나누기 방법은 큰 수를 해시 테이블 크기 범위 내로 들어오도록 축소시키지만, 곱하기 방법은 입 력값을 0과 1 사이의 소수로 대응시킨 다음 𝑚을 곱하여 0과 𝑚 − 1 사이로 팽창시킨다. 해시 함수의 특성을 결정하는 0 < 𝐴 < 1인 𝐴를 미리 준비하여야 한다. 과정은 아래와 같다.

1. 𝑥에 𝐴를 곱한 다음 소수부만을 취함

2. 𝑚을 곱하고 정수부만을 취함

3. ℎ(𝑥) = 𝑚(𝑥𝐴 mod 1)

𝑚 값은 어떻게 잡아도 성능에 큰 영향이 없고, 𝐴 값에 따라 해시 값 분포가 달라진다.

---

Collision

해시 테이블의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것이다.

위에서 보았던 해시테이블을 예시로 들어보면 다음과 같은 상황이다.

---

이를 해결하는 방법은 체이닝(Chaining)과 개방주소 방법(Open Addressing)이 있다.

 

우선 체이닝 방식은 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트(linked list)로 관리하는 것이다. 그러나 해시 테이블 외에 추가적인 메모리가 필요하여 메모리차원에서 불리한 해결책이다. 장점으로는 간단하고 적재율이 1이 넘어가도 작동에는 문제 없다는 것이다.

아래와 같이 해시 테이블이 구성된다. 안정성은 높지만 그 효율성은 상황에 따라 크게 낮아진다.

다음은 개방주소 방법(Open Addressing)이다. 충돌이 일어나더라도 어떻게든 주어진 테이블 공간 내에서 해결하기 위해 다른 해시값을 도출하는 것이다. 충돌을 할 때 마다 해시 함수가 조금씩 바뀌어서 새로운 해시 함수로 새로운 값을 부여해준다. (h0(x), h1(x), h2(x)...)

이 방법은 해시 테이블 외에 추가적인 메모리가 필요하지 않다는 장점이 있다.

---

대표적으로는 선형 조사, 이차원 조사, 더블 해싱 이 세가지 방법이 있다.

 

선형 조사는 충돌이 발생하면 다음 칸으로 계속 이동하여 빈 칸이 생기면 입력하는 방식이다. 굉장히 직관적이라고 볼 수 있다. 빈 칸이 나올때까지 없다면 테이블 내에 해당 키 값은 없는 상태이다.

다만 선형 조사는 특정 영역에 원소가 몰리는 1차군집에 취약하다.

---

이차원 조사(Quadratic Probing)는 충돌이 생길 때 마다 건너뛰는 칸의 개수를 2차함수로 계산하는 방식이다.

위 예시는 𝑐1 = 1, 𝑐2 = 0으로써 처음 충돌할 때는 1칸 이동, 그럼에도 충돌이 있으면 4칸 이동, 또 충돌이 있다면 9칸 이동과 같은 방식으로 빠르게 처음의 해시 영역을 벗어나는 방식을 이용한다. 이때 이차원 조사는 테이블 내의 인접 구간에 값들이 몰려있는 1차군집은 빠르게 벗어나지만, 여러 키 값들이 동일한 초기 해시 함수값을 갖게되는 2차군집에는 취약하다.

---

마지막으로 더블 해싱(Double Hashing)은 두 개의 해시 함수를 사용해서 해시 값을 계산하며, 충돌이 발생할 때 마다 두 번째 해시 함수값 을 더하여 충돌 지역을 벗어나는 방법이다.

ℎ(𝑥)에 대해 두 키 값의 해시 값이 같더라도 𝑓(𝑥)에 대해서까지 해시 값이 같을 확률은 낮다. 아래 예시에서는 13과 11의 공배수인 키 값이 등장하면 선형 조사 방식으로 충돌을 해결하게 된다. 다만 𝑓(𝑥)에서의 +1 항이 없으면 13과 11의 공배수에 대해선 충돌 해결 방법이 없다.

---