11. Hash Tables

많은 프로그램들에 필요한 동적 집합은 INSERT, SEARCH, DELETE만 지원하면 충분하다. 해시 테이블은 이를 지원하기 위한 효과적인 자료구조이다. 해시 테이블에서의 탐색은 최악의 경우 \Theta(n)이지만 웬만한 경우 평균 탐색 시간은 O(1)이다. 해시 테이블은 배열의 직접 주소 접근 특성을 일반화한 것이다. 이는 평균 O(1) 시간 안에 접근을 가능하게 해준다.

11.1. Direct-address tables

키들의 집합이 작을 때는 직접 주소를 가져오는 것이 간단하면서 잘 동작하는 방법이다. 키가 U = \{0, \cdots, m - 1 \}에서 추출될 때 직접 주소 테이블 T[0, \cdots, m - 1]의 각 슬롯이 각각 키에 대응하게 된다. 이 때 동작들의 구현은 간단하다. 각각은 O(1)의 수행 시간을 가진다.

DIRECT-ADDRESS-SEARCH(T, k)
return T[k]
DIRECT-ADDRESS-INSERT(T, x)
T[x.key] = x
DIRECT-ADDRESS-DELETE(T, x)
T[x.key] = NIL

어떤 어플리케이션에서는 직접 주소 테이블 자체가 동적 집합의 원소의 포인터 대신 원소 자체를 저장해 공간을 절약하기도 한다. 이 때에는 빈 슬롯을 나타내기 위한 특별한 키를 사용한다. 이 때 테이블 내에서의 오브젝트의 인덱스를 갖고 있으면 키를 갖고 있는 것과 마찬가지이므로 오브젝트의 키를 따로 저장할 필요도 없다. 그러나 이 때는 빈 슬롯을 나타내기 위한 방법이 필요하다.

11.2. Hash tables

직접 주소 테이블의 단점은 가능한 키의 가짓수가 많으면 가능한 전체 키의 집합을 테이블로 만드는 것은 비실용적이고 메모리의 낭비가 될 수 있다는 점이다. 또한 실제 저장된 키의 수는 훨씬 적을 수 있다. 이 때는 해시 테이블이 훨씬 더 적은 메모리를 차지한다. 이 경우 저장된 키의 갯수가 K일 때 \Theta(\lvert K \rvert)의 메모리를 차지하면서 평균 접근 시간 O(1)의 장점은 그대로 유지하게 된다. 이것은 평균 접근 시간이지 최악의 접근 시간이 아님에 유의하라.

해시 테이블에서 키 k를 가진 원소는 해시 함수 h : U \to \{0, \cdots, m - 1\}에 의해 해시되어 해시 테이블 T[0, \cdots, m-1]로 매핑되어 해시값 h(k)에 저장된다. 이 때 두 키가 같은 슬롯에 해싱되는 충돌이 일어날 수 있는데, 이를 피하거나 해결하는 것이 이상적이다. 키의 갯수가 해시값의 갯수보다 많기 때문에 충돌을 완전히 방지하는 것은 불가능하므로, 결정론적이지만 무작위에 가까운 좋은 해시 함수로 충돌을 최소화한 뒤에 발생하는 충돌을 해결하는 방식을 쓴다.

Collision resolution by chaining

연결법에서는 같은 슬롯으로 해시되는 모든 원소를 같은 연결 리스트에 배치한다. 이 때 딕셔너리 동작들은 다음과 같이 구현된다.

CHAINED-HASH-INSERT(T, x)
insert x at the head of list T[h(x.key)]
CHAINED-HASH-SEARCH(T, k)
search for an element with key k in list T[h(k)]
CHAINED-HASH-DELETE(T, x)
delete x from the list T[h(x.key)]

삽입의 최악 수행 시간은 O(1)인데, 삽입되는 원소가 테이블 내 존재하지 않는다고 가정하기 때문이다. 필요하다면 이에 대한 체크를 할 수 있다. 탐색의 최악 수행 시간은 리스트의 길이에 비례한다. 연결 리스트가 이중 연결 리스트일 경우 삭제의 수행 시간은 O(1)이 된다.

Analysis of hashing with chaining

연결 해싱법의 검색 성능은 얼마나 될까? n개의 원소를 m개의 슬롯에 저장하는 해시 테이블 T에 대해 부하 인자 \alpha = \frac{n}{m}으로 정의하자. 최악의 경우에는 모든 키가 같은 슬롯에 해싱되어 길이 n의 리스트를 만드는 것인데, 이 경우 탐색의 수행 시간은 \Theta(n)에 해시 함수 계산에 쓰는 시간까지 추가되어 장점이 없다. 해싱의 평균 수행 시간은 해시 함수가 원소를 슬롯들에 얼마나 잘 분배하느냐에 달려 있다. 해시 함수가 슬롯들 각각에 균일하게 분배할 때 이를 단순 균등 해싱이라 하자. 이 때 해시 함수를 계산하는 데 걸리는 시간은 O(1)로 가정하여, 키 k를 탐색하는 데 걸리는 시간은 각 해시값의 슬롯의 길이에 선형으로 비례한다고 하자. 이 경우 탐색 동작의 기대 수행 시간은 어떻게 되는가? 키 k가 테이블에 없는 경우와 있는 경우 둘로 나눠서 분석해 보도록 하자.

Theorem. 연결 해싱법을 차용한 해시테이블에서, 단순 균등 해싱을 가정하면 키가 테이블에 없는 경우 평균 수행 시간은 \Theta(1 + \alpha)이다.

Theorem. 연결 해싱법을 차용한 해시테이블에서, 단순 균등 해싱을 가정하면 키가 테이블에 있는 경우 평균 수행 시간은 \Theta(1 + \alpha)이다.

이것은 무엇을 뜻하는가? 해시 테이블 슬롯의 수가 테이블 내 원소의 수에 비례하면 \alpha = n/m = O(m)/m = O(1)이므로, 탐색의 평균 수행 시간도 O(1)이 된다. 따라서 이중 연결 리스트를 쓸 경우 삽입, 탐색, 삭제를 모두 평균 O(1) 시간에 지원할 수 있다.

11.3. Hash functions

좋은 해시 함수를 만드려면 어떻게 해야 할까?

What makes a good hash function?

좋은 해시 함수는 단순 균등 해싱에 가까운 해시 함수이다. 이 경우 모든 키가 다른 키들의 해시 분포에 상관없이 슬롯들에 균등히 분배된다. 실제로는 키들의 확률분포를 알기 쉽지 않기 때문에 이를 체크하기는 쉽지 않다. 또한, 키들이 독립적으로 샘플된다는 보장도 없다.

가끔은 키들의 분포를 알 수도 있다. 키들의 분포가 U \sim [0, 1)에서 i.i.d라면 해시 함수 h(k) = \lfloor km \rfloor는 단순 균등 해시 조건을 만족한다. 실제로는 잘 동작하는 해시 함수를 만들기 위해 휴리스틱한 접근법을 많이 쓴다. 이 때 키의 분포에 대한 정성적 접근이 도움이 될 수 있지만, 해시 함수에 대한 좋은 접근법은 어떤 데이터 패턴에 대해서도 독립적인 해시 함수를 만드는 것이다. 또한, 어떨 때는 단순 균등 해싱보다 더 강한 조건이 필요할 때도 있다.

Interpreting keys as natural numbers

대부분의 해시 함수는 키들을 자연수로 가정한다. 자연수가 아닐 경우엔 자연수로 변형해 표현한다.

11.3.1. The division method

나눗셈법에서는 해시 함수가 나머지를 취해 h(k) = k \mathrm{mod} m이 된다. 이 때 m을 택할 때 특정한 값들은 피하는 것이 좋은데, m = 2^{p}같은 값들이다. 2의 승수에 가깝지 않은 소수 m을 택하는 것은 좋은 선택이다.

11.3.2. The multiplication method

곱셈법에서는 키 k를 상수 0 < A < 1로 곱하고 kA의 분수 부분을 택해, 해시 함수가 h(k) = \lfloor m (kA \mathrm{mod} 1) \rfloor가 된다. 곱셈법의 장점은 m을 택할 때 특정 값들을 피할 필요가 없다는 장점이 있다. 이 방법은 A를 아무거나 택해도 적절하게 동작하지만 다른 값보다 더 잘 동작하는 A값은 있다. A \simeq \frac{\sqrt{5} - 1}{2} 등이 그렇다.

11.3.3. Universal hashing

어떤 이가 키들이 전부 같은 슬롯에 해싱되게 키들을 삽입한다면, 해시 테이블의 성능은 매우 나빠질 것이다. 이를 방지하기 위해서는 저장될 키들에 독립적이고 무작위적이도록 해시 함수를 정해야 할 필요가 있다. 이를 보편적 해싱이라 한다. 이 경우 해시 함수는 동작 시마다 세심하게 선별된 함수들의 집합들 중 무작위로 선택된다.

\mathcal{H}를 키의 전역 집합 U로부터 범위 \{0, \cdots, m - 1\}로 매핑하는 해시 함수의 집합이라 하자. 임의의 키의 쌍 k, l \in U에 대해 h(k) = h(l)이 되는 해시 함수 h \in \mathcal{H}의 수가 최대 \frac{\lvert \mathcal{H} \rvert}{m}이면 이 해시 함수의 집합을 보편적이라 한다. 이 때, 함수들의 집합 중에서 해시 함수를 무작위로 선택했을 때 서로 다른 키에 대해 충돌이 발생할 확률은, 해시값이 독립적이고 무작위적으로 선택되었을 때 최대 \frac{1}{m}이 된다. 보편적 해시 함수의 평균적 성능을 분석해 보자.

Theorem. 보편적 해시 함수 집합 내의 해시 함수 h가 크기 m의 해시테이블 T에 원소 n개를 연결 해싱법으로 해싱한다고 하자. 키 k가 테이블에 없으면, 키가 해시되는 리스트의 기대 길이 \mathbb{E}[n_{h(k)}]는 최대 \alpha = \frac{n}{m}이다. 키 k가 테이블에 있으면, 키가 해시되는 리스트의 기대 길이는 최대 1 + \alpha이다.

Corollary. 보편적 해싱과 연결 해싱법을 사용했을 때, 크기 m의 해시테이블이 초기에 비어 있다고 가정하자. 임의의 일련의 INSERT, SEARCH, DELETE 동작 n번이 INSERT를 O(m)번 포함하고 있을 경우, 이 동작 전체를 수행하는 데는 \Theta(n) 시간이 걸린다.

Designing a universal class of hash functions

보편적 해시 함수 집합을 어떻게 만들까? 적당한 소수 p > m에 대해 a \in \mathbb{Z}_{p}^{\ast}, b \in \mathbb{Z}_{p}의 임의의 정수 쌍에 대해 해시 함수 h_{ab}(k) = ((ak + b) \mathrm{mod} p) \mathrm{mod} m로 정의한다면, 이 해시 함수들 p(p-1)개의 집합은 보편적 해시 함수 집합이 된다. 또한, m의 값에 제약이 없다는 장점도 있다.

Theorem. 위의 해시 함수들의 모임으로 정의되는 집합 \mathcal{H}_{pm}은 보편적 해시 함수 집합이다.

11.4. Open addressing

개방 주소법에서는 각 원소가 해시 테이블을 점유한다. 즉, 테이블 항목 각각이 동적 집합의 원소를 포함하거나 NIL을 포함한다. 원소를 찾을 때는 해당 원소를 찾을 때까지 테이블 슬롯을 조사한다. 연결법과는 달리, 별도의 리스트나 원소들이 테이블 밖에 저장되지는 않는다. 즉, 개방 주소법에서는 해시 테이블이 더 이상 원소가 삽입될 수 없을 때까지 채워진다. 그러므로 개방 주소법에서는 \alpha가 절대 1을 넘을 수 없다.

개방 주소법의 장점은 포인터를 사용하지 않는다는 점이다. 그 대신에 조사할 슬롯들을 직접 계산할 수 있다. 포인터를 저장하지 않음으로써 메모리를 아낄 수 있고, 빠른 검색과 더 적은 충돌을 얻을 수 있다. 개방 주소법에서는 빈 슬롯이 발견될 때까지 연속적으로 해시 테이블을 검색한다. 이 검색의 대상이 되는 슬롯의 순열은 삽입되는 키에 의존한다. 이 때 해시 함수는 탐색 숫자를 두 번째 입력으로 받도록 확장된다. 즉, 해시 함수는 h : U \times \{0, \cdots m-1 \} \to \{0, \cdots m - 1\}로 확장된다. 개방 주소법에서는 모든 키 k에 대해 검색 수열 h(k, 0), \cdots, h(k, m-1)0, \cdots, m - 1의 순열이 됨을 보장해야 한다. 이 때 삽입 동작은 다음과 같이 구현된다.

HASH-INSERT(T, k)
i = 0
repeat
    j = h(k, i)
    if T[j] == NIL
        T[j] = k
        return j
    else
        i += 1
until i == m
error "hash table overflow"

키 k를 탐색할 때 검색되는 슬롯들의 순서는 키 k를 삽입할 때 검색되는 슬롯들의 순서와 같다. 그러므로 키 k가 삭제된 적이 없다면, 키 k를 탐색할 때 빈 슬롯을 찾는다면 해당 키를 찾지 못했음을 알게 된다.

HASH-SEARCH(T, k)
i = 0
repeat
    j = h(k, i)
    if T[j] == k
        return j
    i += 1
until T[j] == NIL or i == m
return NIL

개방 주소법에서의 삭제는 까다롭다. 슬롯 i에서 키를 삭제할 때 그냥 NIL을 저장하면 해당 슬롯을 쓰는 다른 키들을 검색할 수 없게 되므로 특별한 값 DELETED를 슬롯에 마킹해야 한다. 이 때 HASH-INSERT는 DELETED를 빈 슬롯으로 취급해야 하며, HASH-SEARCH는 따로 수정할 필요는 없다. 이렇게 되면 탐색 시간이 부하 인자 \alpha에 더 이상 의존하지 않게 되므로, 키들이 삭제됨을 가정한다면 연결법이 개방 주소법보다 더 보편적으로 쓰인다.

아래의 분석에서 우리는 균등 해싱을 가정한다. 이는 각각의 키의 검색 수열이 0, \cdots, m - 1 의 m!개의 순열 중에서 균등하게 선택됨을 의미한다. 이는 앞서 다룬 단순 균등 해싱의 일반화이다. 진짜 균등 해싱은 구현하기 까다롭지만, 적당한 근사는 가능하다.

자주 쓰이는 개방 주소법의 검색법은 3가지가 있다: 선형 검색법, 이차 검색법, 이중 해싱. 세 방법은 모두 각각의 키의 검색 수열이 0, \cdots, m - 1의 순열임을 보장하지만, 균등 해싱은 아니다. 이 중에서는 이중 해싱이 가장 좋은 성능을 낸다.

Linear probing

일반적 해시 함수 h’를 보조 해시 함수로 썼을 때, 선형 검색법은 해시 함수 h(k, i) = (h'(k) + i) \mathrm{mod} m을 쓴다. 키 k에 대해, 먼저 T[h'(k)]를 검색한 뒤, T[h'(k) + 1], 등등부터 T[m – 1]까지를 탐색한 뒤 다시 T[0]부터 T[h'(k) – 1]까지를 검색한다. 이 때 서로 다른 검색 순열은 총 m개뿐이다.

선형 검색법은 구현하기 쉽지만, 주 클러스터링이라는 문제가 있다. 채워진 슬롯들이 더 많아질수록 평균 검색 시간은 늘어나게 된다.

Quadratic probing

이차 검색법은 h’가 보조 해시 함수이고 c_{1}, c_{2}가 보조 양수일 때 h(k, i) = (h'(k) + c_{1} i + c_{2} i^{2}) \mathrm{mod} m 형태의 해시 함수를 사용한다. 이는 최초 T[h'(k)]로부터 시작해서 이차 오프셋만큼의 위치를 검색해 나간다. 이는 선형 검색법보다 나은 성능을 보이지만 해시 테이블 전체를 쓰기 위해서는 c_{1}, c_{2}, m의 값들이 제약되어야 한다. 또한, 두 키의 최초 검색 위치가 같다면 검색 순열의 순서도 같다. 그러므로 이차 클러스터링이라는, 완화된 형태의 문제가 여전히 남는다. 이 경우에도 서로 다른 검색 순열은 총 m개뿐이다.

Double hashing

이중 해싱은 개방 주소법에서 택할 수 있는 가장 나은 방법들 중 하나로, 보조 해시 함수 h_{1}, h_{2}에 대해 h(k, i) = (h_{1}(k) + ih_{2}(k)) \mathrm{mod} m의 형태를 가진다. 선형 검색법이나 이차 검색법과는 다르게, 검색 순열은 키 k에 대해 초기값과 오프셋이라는 두 가지 방식으로 의존한다. 이 때 전체 해시 테이블이 선택되게 하기 위해서는 오프셋 해시 함수 h_{2}(k)은 반드시 해시 테이블 크기 m과 서로소여야 할 필요가 있다. 편리한 방법은 m을 2의 승수로, h_{2}를 홀수로 잡는 것이다. m을 소수로, h_{2}를 m보다 작은 정수로 잡는 방법도 있다. 이 때 이중 해싱은 \Theta(m^{2})개의 서로 다른 검색 순열을 제공하므로, 선형 검색법이나 이차 검색법보다 더 낫다. m의 경우 다른 값을 쓸 수도 있지만, 이 때 h_{2}를 효과적으로 정하기는 힘들어진다.

Analysis of open-address hashing

연결법 때와 똑같이, 개방 주소법에서의 분석도 해시 테이블의 부하 인자 \alpha = \frac{n}{m}에 대해 이루어진다. 하지만 개방 주소법에서는 \alpha \leq 1이라는 차이가 있다. 이 때에는 균등 해싱을 가정한다.

Theorem. 개방 주소법 해시 테이블에서 부하 인자 \alpha < 1일 때, 균등 해싱을 가정할 경우, 키가 테이블에 없을 때 검색되는 슬롯 수의 기대값은 최대 \frac{1}{1 - \alpha}이다.

이를 직관적으로 해석하면, 키가 테이블에 없을 때 첫 번째 슬롯을 검색하고, \alpha의 확률로 두 번째 슬롯을 검색하고 (그만큼의 확률로 슬롯이 점유되었을 것이므로), \alpha^{2}의 확률로 세 번째 슬롯을 검색하고, 이를 반복해 기대값이 \frac{1}{1-\alpha}이 되는 것이다.

Corollary. 개방 주소법 해시 테이블에서 균등 해싱을 가정할 경우, 원소를 삽입할 때 검색되는 슬롯 수의 기대값은 \frac{1}{1-\alpha}이다.

키가 테이블에 있을 때는 좀 더 복잡하다.

Theorem. 개방 주소법 해시 테이블에서 부하 인자 \alpha < 1일 때, 균등 해싱을 가정할 경우, 키가 테이블에 있을 때, 테이블 내 존재하는 키들이 검색될 확률이 동일하다면, 검색되는 슬롯 수의 기대값은 최대 \frac{1}{\alpha}\ln \frac{1}{1-\alpha}이다.

11.5. Perfect hashing

키들이 정적일 때, 즉 저장된 키들의 집합이 바뀌지 않을 때에는 최악 수행 시간도 좋게 할 수 있다. 최악 수행 시간이 O(1)인 해싱을 완벽 해싱이라 한다. 이를 위해서는 두 단계의 보편적 해싱을 해야 한다. 첫 번째 단계는 연결 해싱법과 같다. 단, 한 슬롯에 대해 연결 리스트를 사용하는 대신에 작은 이차 해시 테이블 S_{j}와 그에 연관된 해시 함수 h_{j}를 사용한다. 이차 해시 함수를 잘 선택하면, 두 번째 단계에서 충돌이 일어나지 않음을 보장할 수 있다. 이를 위해서는 해시 테이블 S_{j}의 크기 m_{j}가 해싱된 키들의 개수 n_{j}의 제곱이어야 한다. 이는 메모리 낭비를 가져온다고 생각될지 모르나 첫 번째 단계의 해시 함수를 잘 선택하면 전체 메모리 사용량을 O(n)으로 제한할 수 있다.

첫 번째 단계의 해시 함수는 \mathcal{H}_{pm}으로 정한다. 이 때 p는 임의의 키보다 큼이 보장되는 소수이다. 이 때 슬롯 j로 해싱된 키들은 두 번째 단계의 해시테이블에서 \mathcal{H}_{p, m_{j}}로부터 선택된 해시 함수 h_{j}를 통해 재해싱된다.

Theorem. 보편적 해시 함수들로부터 선택된 해시 함수 h로 n개의 키들을 m = n^{2} 크기의 해시테이블에 저장할 때, 충돌이 존재할 확률은 1/2 미만이다.

해싱되는 키들의 집합이 고정이라는 가정을 하고 있으므로, 몇 번 시도하면 충돌이 없는 해시 함수를 얻을 수 있다. n이 크면 해시 테이블의 크기가 지나치게 커지기 때문에, 첫 번째 단계의 해시테이블에서 키들을 m = n 슬롯으로 먼저 해시해 키들을 충돌이 없는 이차 해시 테이블로 분배한다. 이 때 첫 번째 단계의 해시 테이블에서 사용하는 메모리는 O(n)이다.

Theorem. 보편적 해시 함수들로부터 선택된 해시 함수 h로 n개의 키들을 m = n 크기의 해시테이블에 저장할 때, 슬롯 j에 해싱되는 키의 수가 n_{j}라면, \mathbb{E}[\sum_{j=0}^{m-1}n_{j}^{2}] < 2n 이 된다.

Corollary. 보편적 해시 함수들로부터 선택된 해시 함수 h로 n개의 키들을 m = n 크기의 해시 테이블에 저장하고, 슬롯 j에 해싱된 n_{j}개의 키들을 m_{j} = n_{j}^{2} 크기의 이차 해시 테이블에 저장할 때, 이차 해시 테이블이 사용하는 메모리의 전체 기대값은 2n 미만이다.

Corollary. 보편적 해시 함수들로부터 선택된 해시 함수 h로 n개의 키들을 m = n 크기의 해시 테이블에 저장하고, 슬롯 j에 해싱된 n_{j}개의 키들을 m_{j} = n_{j}^{2} 크기의 이차 해시 테이블에 저장할 때, 이차 해시 테이블이 메모리를 4n 이상 사용할 확률은 1/2 미만이다.

위의 결과들로부터, 키들이 고정되어 있다면 선형 메모리만 사용하는 완벽한 해싱 함수를 몇 번의 시도 안에 얻을 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중