Hash Table 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[Data Structures#Binary Search Tree|Data Structures]]

==개요==
해시 테이블(Hash Table)은 [[Data Structures#Dictionary|사전(Dictionary)]]을 구현하는 데에 매우 실용적인 자료 구조이다. 해시 테이블의 근본적인 아이디어는 배열에서 인덱스만 주어지면 이를 바탕으로 원하는 원소에 즉시 접근할 수 있다는 것이다. 이때 키(key)는 보통 정수(integer)가 아니므로, 임의의 키를 정수 인덱스로 바꾸는 해시 함수(hash function)를 구현하고 응용하는 것이 해시 테이블의 골자이다.

==Collisions==
[[파일:Figure 1. Chaining Hash Table.png|섬네일|Figure 1. Chaining Hash Table]]
충돌(Collision)이란 서로 다른 두 키가 동일한 해시 값에 매핑되는 현상이다. 충돌이 발생할 경우에는 해당 버킷 안에 여러 키가 모이게 된다. 이때 키들이 해시 함수에 의해 균등(uniformly)하게 버킷들에 분포된다면, 각 버킷에는 몇 안되는 원소들만 들어간다. 따라서 이 경우에는 각 버킷 내부의 작은 리스트만 탐색하면 되므로 여전히 효율적이다. Figure 1은 해시 테이블의 크기가 10인 자료구조에 키 55, 21, 2, 13, 34, 5, 8, 3 등이 해시 값에 따라 여러 버킷에 들어가 있는 것을 보여준다.

===Collision Resolution by Chaining===
Chaining은 충돌이 발생하였을 때 이를 해결하는 방법중 하나로, 각 버킷마다 [[Data Structures#Pointers and Linked Structures|연결 리스트(linked list)]]를 두어 충돌이 발생할 때마다 새 원소를 해당 버킷의 리스트에 추가하는 방식이다. 이는 구현이 단순하고 직관적이라는 장점이 존재하지만, 각 리스트가 포인터를 필요로 하므로 메모리 낭비가 발생한다는 단점이 있다.<ref>이는 해시 테이블 자체의 크기를 제한하기도 한다.</ref> Figure 1은 Chaining의 한 예시로, 버킷에 해당하는 키 값들이 포인터를 통해 연결되어 있다.

시간 복잡도는 삽입/삭제/탐색 연산이 모두 리스트에서 처리되므로 리스트 길이에 비례한다. 이때 리스트의 길이는 평균적으로 <math>n/m</math><ref>n은 키의 개수, m은 테이블의 크기를 의미한다.</ref>이므로 따라서 시간복잡도는 <math>O(n/m)</math>이다. 이때 <math>n/m</math>은 적재율(load factor)라고 불린다.

===Open Addressing===
[[파일:Figure 2. Sequential Open Address.png|섬네일|Figure 2. Sequential Open Address]]
Open addressing은 체이닝 대신 포인터를 쓰지 않고, 테이블 내부에서 다른 빈 공간을 찾아 저장하는 방식이다. 해당 방식은 원래의 해시 값이 가리키는 칸이 비어 있으면 삽입하고, 이미 차 있으면 다음 위치에 삽입하는 것을 시도하는 방식이다. 이때 충돌할 경우 다음 위치를 정하는 규칙은 아래와 같다:
* Sequentially: h,h+1,h+2,...
* Quadratically: h, h+1<sup>2</sup>, h+2<sup>2</sup>, h+3<sup>2</sup>, ...
* Linearly: h, h+k, h+2k, h+3k, ...
Figure 2는 linear probing 방식의 한 예시를 보여준다. 해당 방식은 별도의 포인터 저장이 불필요하다는 장점이 있지만, 원소들이 뭉쳐서 연속 구간을 차지하면(Primary Clustering) 탐색 성능이 저하된다는 단점이 있다. 또한 해당 방식은 원소를 삭제할 때 어려움을 겪는데, 이는 원소를 삭제할 때 단순히 해당 칸을 비워버리면 문제가 생기기 때문이다. 왜냐하면 삭제 이후 탐색 시 “그 원소가 충돌 때문에 다른 칸에 있는지” 구분이 불가능해져서<ref>probing chain이 끊기기 때문이다.</ref>, 일부 원소가 검색 불가능해지기 때문이다. 따라서 보통은 “삭제된 자리”를 특별한 마커(예: DELETED flag)로 표시해 해결한다.

==Hash Functions==
해시 함수(Hash function)의 가장 중요한 역할은 키(key) 를 정수(integer) 로 변환하는 것이다. 예를 들면 키가 "apple"일 때, 이를 어떤 정수값으로 바꾸는 것이다. 이때 좋은 해시 함수의 조건은 아래와 같다:
# 계산이 저렴해야 함(Is cheap to evaluate)<br>해시 함수가 복잡하면 해시 테이블을 쓰는 의미가 없으므로, 빠르고 단순하게 변환해야 한다.
# 모든 해시 테이블 슬롯을 고르게 사용(Tends to use all positions from 0 … M uniformly)<br>해시 테이블의 크기가 M이라면, 해시 함수의 결과로 인덱스 0부터 M-1까지 고르게 값이 나와야 충돌(collisions)이 줄어든다.
아래는 문자열 키를 정수로 바꾸는 어떤 해시 함수이다: 
 <math>h=\sum^{Key\,Length}_{i=0}128^i\times char(key[i])</math>
위와 같은 해시 함수의 결과로는 매우 큰 정수가 나올 수 있다. 만약 해시 함수의 결과가 1,928,374,982 같은 수라면, 해시 테이블 크기보다 훨씬 클 수 있다. 따라서 해당 결과를 테이블 크기에 맞게 줄이는 작업을 해야 한다. 이는 아래와 같은 방법을 사용한다.
 <math>h(k) = k\, mod\, M</math>
위에서 k는 해시 함수를 통해 1차적으로 얻은 큰 정수를 의미하며, M은 해시 테이블의 크기를 의미하며, 모듈러 연산을 통해 결과값이 항상 0~k-1 범위 내에 있도록 한다. 이때 M의 값은 2<sup>i</sup>-1<ref>i는 k를 이진수로 표현하였을 때 필요한 비트의 수를 의미하며, 2<sup>i</sup>-1은 i개의 비트로 만들 수 있는 가장 큰 수에 해당한다.</ref>에 너무 가깝지 않은 M은 큰 소수로 선택하는 것이 권장된다. 만약 M을 2의 거듭제곱수로 사용한다면, k를 이진수로 바꾸었을 때 하위 비트만을 이용하므로 충돌이 증가한다. 또한 M이 소수가 아니라면, 키 값이 특정 배수 패턴을 가질 때 특정 버킷들에 모이므로 충돌이 늘어난다.

예를 들어, 사회보장번호(SSN)의 앞 세 자리를 해시 키로 쓰는 경우는 나쁜 해시 함수이다. 그 이유는 사회보장번호 앞 세 자리는 지역이나 특정 규칙에 따라 배정되므로 값이 편향되어 있기 때문이다.<ref>주민등록번호의 경우에도 2020년 법 개정 이전에는 앞 여섯 자리는 성별과 출생 주소지 등에 대한 정보를 담고 있으므로 나쁜 해시 함수로 볼 수 있다.</ref> 하지만 SSN의 뒷 세 자리를 해시 키로 쓰는 경우는 좋은데, 마지막 세 자리는 지역과 상관없이 거의 무작위(random)로 배정되므로 훨씬 균일한 분포를 보이기 때문이다.

===The Birthday Paradox===
아무리 좋은 해시 함수를 사용하더라도 충돌은 피하기 힘들다. 그 이유는 birthday paradox 때문인데, 이는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50% 이상이 된다는 것이다. 이는 삽입할 때마다 충돌 확률은 누적되어 올라가기 때문이다. 해시 테이블의 크기가 m일 때 n개의 키를 삽입하면 아래와 같은 충돌 확률을 가진다: 
 <math>P(no collision) = \frac{m}{m} \times \frac{m-1}{m} \times \frac{m-2}{m} \times \cdots \times \frac{m-n+1}{m} = \prod^{n-1}_{i=0}\frac{m-i}{m}</math>

==각주==