[자료구조] 맵, 해시 테이블

맵

맵은 원소를 저장하고 키를 이용하여 빠르게 찾을 수 있도록 한다. 엔트리라 불리는 키-값 쌍(k, v)을 저장한다. 맵 ADT에서 각 키는 유일하여 키와 값의 연관은 매핑을 정의한다. 가장 높은 수준의 일반화를 위해, 맵에 저장된 키와 값은 어떠한 객체타입도 가능하다. 키는 일종의 위치 역할을 하는 객체이다.

맵은 객체에 연관된 키가 그 자료구조에서 객체의 위치를 결정하기 때문에 연관된 저장소(associative stores) 또는 연관된 컨테이너(associative container)라고 불리기도 한다.

 

엔트리와 구성 패턴

엔트리는 구성 패턴(Composition Pattern)이라 불리는 객체지향 설계 패턴의 한 예로 다른 객체들로 구성된 단일 객체를 정의한다. 쌍은 가장 간단한 구성이다. 두 객체가 하나의 쌍 객체로 합쳐진다!

이러한 개념의 구현을 위해 두 개의 멤버 변수를 저장하는 클래스를 정의하고, 그 변수들에 접근하고 수정할 수 있는 함수를 제공한다.

template <typename K, typename V>
class Entry {				// (키, 값) 쌍
public:
    Entry(Const K& k = K(), const V& v = V())
     : _key(k), _value(v) {}
    const K& key() const { return _key; }	// 키를 반환
    const V& value() const { return _value; }	// 값을 반환
    void setKey(const K& k) { _key = k; }	// 키 수정
    void setValue(const V& v) { _value = v; }	// 값 수정
private:
    K _key;					// 키
    V _value;				// 값
}

 

맵 ADT

맵 반복자 p가 주어졌으면, 연관된 엔트리는 p를 디레퍼런스(= *p)하여 접근할 수 있고 개별 키와 값은 p->key()와 p->value()를 이용하여 접근할 수 있다. 객체가 맵에 존재하지 않는 것을 나타내기 위해 end라 불리는 특수한 센티널(sentinal) 반복자가 정의되었다고 가정한다. 지금까지 사용했던 것과 마찬가지로 이 센티널은 맵의 마지막 원소의 바로 뒤에 위치한 가상 원소를 가리킨다.

• size(): M에 있는 엔트리의 개수를 반환
• empty(): M이 비어있으면 true, 아니면 false
• find(k): 만약 M이 엔트리 e = (k, v), 즉 키가 k와 같은 엔트리를 포함하면 이 엔트리를 가리키는 반복자 p를 반환하고 그렇지 않으면 특수 반복자 end를 반환한다.
• put(k, v): 만약 M이 키가 k와 같은 엔트리를 포함하지 않으면 M에 엔트리 (k, v)를 추가한다. k와 같은 엔트리가 존재한다면 기존 엔트리 값을 v로 대체한다. 삽입되었거나 수정된 엔트리에 대한 반복자를 반환한다.
• erase(k): 키가 k와 같은 엔트리를 삭제한다.
• erase(p): 반복자 p가 가리키는 엔트리를 M에서 삭제한다.
• begin(): M의 첫 번째 엔트리에 대한 반복자를 반환한다.
• end(): 맵의 마지막 원소 바로 뒤의 위치에 대한 반복자를 반환한다.

STL map 클래스

map<string, int> myMap;						// (string, int) 맵
map<string, int>::iterator p;				// 맵에 대한 반복자
myMap.insert(pair<string, int>("Rob", 28));	// ("Rob", 28) 삽입
myMap["Joe"] = 38;							// ("Joe", 38) 삽입
myMap["Joe"] = 50;							// ("Joe", 50)으로 수정
myMap["Sue"] = 75;							// ("Sue", 75) 삽입
p = myMap.find("Joe");						// *p = ("Joe", 50)
myMap.erase(p);								// ("Joe", 50) 삭제
myMap.erase("Sue");							// ("Sue", 75) 삭제
p = myMap.find("Joe");
if (p == myMap.end()) cout << "nonexistent\n";	// Joe가 존재하지 않는다면 nonexistent 출력
for (p == myMap.begin(); p != myMap.end(); p++) {	// 모든 엔트리를 출력
    cout << "(" << p->first << "," << p->second << ")\n";	// (키, 쌍) 형태로 출력
}

p->first, p->second로 키와 value를 참조할 수 있다.

 

Simple List-Based Map 구현

맵을 구현하는 간단한 방법은 이중 링크드 리스트로 구현된 리스트 L에 n개의 엔트리를 저장하는 것이다. 기본적인 함수들 find(k), put(k, v), erase(k)를 수행하기 위해서는 키 k를 찾으며 L을 스캔하면 된다.

Algorithm find(k):
    input: 키 k
    output: L에서 키 k를 갖는 엔트리의 위치, 또는 L에 키 k가 없으면 end
    for each position p in [L.begin(), L.end()) do
    	if p.key() = k then
        	return p
     return end		k와 같은 키를 갖는 엔트리가 없다
     
 Algorithm put(k, v):
     input: 키-값 쌍 (k, v)
     output: 삽입/수정된 엔트리의 위치
     for each position p in [L.begin(), L.end()) do
     	if p.key() = k then
        	*p <- (k, v)
            return p
     p <- L.insertBack((k, v))
     n <- n + 1
     return p
     
Algorithm erase(k):
    input: 키 k
    output: 없음
    for each position p in [L.begin(), L.end()) do
    	if p.key() = k then
        	L.erase(p)
            n <- n - 1	엔트리의 개수를 하나 감소시킴

list-based 맵은 간단하지만 매우 작은 맵에서만 효율적이다. 모든 주요 함수들이 n개의 엔트리를 갖는 맵에서 실행시간이 O(n)이다(최악의 경우 전체 리스트를 검색해야 하기 때문에). 따라서 훨씬 빠른 다른 것이 필요하다!!

 

해시 테이블(Hash Tables)

맵을 구현하는 가장 효율적인 방법 중 하나이다. 해시 테이블을 사용할 경우 맵 연산의 실행시간은 최악의 경우 O(n)이지만, 평균 O(1) 시간에 실행할 수 있다. 버켓 배열과 해시 함수가 해시 테이블의 두 개의 주요 구성원소이다!!!

출처: https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94

버켓(bucket) 배열

해시 테이블을 위한 버켓 배열은 크기가 N인 배열 A이다. 여기서 A의 각 셀을 키-원소 쌍을 저장하는 컨테이너 "버켓"으로 생각하고 정수 N은 배열의 용량(capacity)이다. 만약 키들이 [0, N-1] 범위에 잘 분포된 정수라면 버켓 배열만으로 충분하다. 키 k를 갖는 원소 e는 버켓 A[k]에 삽입된다. 

만약 키가 [0, N-1] 범위에 있는 유일한 정수라면 각  버켓은 최대 하나의 엔트리를 저장한다. 따라서 버켓 배열의 검색, 삽입, 삭제는 최악의 경우 O(1) 시간이 소요된다. 충돌에 대한 걱정을 할 필요가 없다!!! 하지만 여기에는 두 가지 단점이 있다. 첫 번째는 O(N) 공간을 사용한다는 것이다. N이 실제 맵에 존재하는 엔트리의 개수 n에 비해 너무 크다면 이 구현 방법은 공간을 낭비하는 것이다. 두 번째는 버켓 배열에서 키들이 [0, N-1] 범위에 있는 유일한 정수여아 하는데 이 경우는 별로 흔하지 않다. 이러한 단점들 때문에 키를 [0, N-1] 범위 안에 정수로 변환하는 매핑과 함께 버켓 배열을 사용한다!!

 

해시 함수(Hash Function)

해시 함수라고 불리는 h 함수는 맵의 각 키 k를 [0, N-1] 범위의 정수로 변환하는데, 여기서 N은 이 테이블을 위한 버켓 배열의 용량이다. 해시 함수가 있으면 임의의 키에 대해 버켓 배열 방법을 적용할 수 있다. 키 k 대신 키의 해시 함수값 h(k)를 버켓 배열 A의 인덱스로 사용한다!!! 즉, 엔트리 (k, v)를 버켓 A[h(k)]에 저장한다.

만약 두 개 이상의 키들이 같은 해시값을 가진다면(k1 != k2 && h(k1) == h(k2) 라면) 두 개 이상의 원소들이 A의 같은 버켓에 매핑되는 충돌(collision)이 발생할 수 있다!!! 해시 함수는 맵 내의 키들을 매핑하는 과정에서 충돌을 가능한 최소화해야 좋은 함수라고 할 수 있다. 해시 함수의 계산이 빠르고 쉬운 것 또한 바람직하다!!

해시 함수 h(k)의 계산을 두 단계로 나누어 생각한다. 해시 코드(hash code)라고 불리는 키 k를 정수로 바꾸는 과정과 압축 함수(compression function)라 불리는 해시 코드를 버켓 배열의 인덱스 범위([0, N-1])로 매핑하는 과정이다.

해시 함수의 두 단계: 해시 코드와 압축 함수

해시 코드(Hash Codes)

해시 함수의 첫 번째 단계는 맵의 임의의 키 k에 주어진 정수값을 할당하는 것이다. 키 k에게 할당된 정수값을 k에 대한 해시 코드라 한다!! 이 정수값은 [0, N-1] 범위에 있지 않아도 되고 음수값일 수도 있다. 키들에 주어진 해시 코드들은 가능한 충돌하지 않는 것이 바람직하다. 만약 키들의 해시 코드가 충돌하면 압축 함수도 충돌하게 된다. 또한 모든 키의 일관성을 위해 키 k에 주어진 해시 코드는 k와 같은 키의 해시 코드와 같아야 한다!!

 

압축 함수(Compression Functions)

키에 대한 해시 코드의 범위가 보통 버켓 배열 A의 인덱스 범위를 벗어나기 때문에, 키 k에 대한 해시 코드를 버켓 배열에 바로 사용하기는 적당하지 않다. 범위가 맞지 않는 해시 코드를 버켓 배열에 사용하면 out-of-bound 예외가 발생하게 된다. 따라서 객체 k에 대한 정수 해시 코드를 결정한 다음에도 그 정수를 범위 [0, N-1]으로 매핑하는 문제가 남아있다. 이러한 압축 단계는 해시 함수가 수행하는 두 번째 과정이다.

 

충돌-처리 기법(Collision-Handling Schemes)

해시 테이블의 핵심은 버켓 배열 A와 해시 함수 h를 사용하여 맵의 각 엔트리 (k, v)를 버켓 A[h(k)]에 저장하는 것이다. 하지만 두 개의 키 k1과 k2가 같은 해시값을 가지면(h(k1) == h(k2)) 충돌의 문제가 생긴다. 이러한 충돌 때문에 새 엔트리 (k, v)를 버켓 A[h(k)]에 직접 넣을 수가 없다. 

별도 체이닝(Seperate Chaining)

충돌을 해결하는 간단하면서 효과적인 방법은 각 버켓 A[i]에 리스트, 벡터, 또는 시퀀스 Si의 참조를 저장하는 것이다. 해시 함수가 버켓 A[i]로 매핑하는 모든 엔트리를 얘네들에 저장한다. 시퀀스 Si는 비정렬된 시퀀스 또는 로그 파일 방법으로 구현된 작은 맵을 생각할 수 있으며, h(k) = i인 모든 엔트리 (k, v)를 저장한다. 이러한 충돌 해결 방법을 별도 체이닝이라 한다. 각 비어 있지 않은 버켓을 이러한 로그 파일 방식에 의한 작은 맵으로 구현하였다고 가정하면 맵의 기본적인 연산들을 아래 코드로 수행할 수 있다.

Algorithm find(k):
    output: 맵에서 일치하는 엔트리의 위치, 또는 맵에 키 k가 없으면 end
    
    return A[h(k)].find(k)	find(k)를  A[h(k)]에 있는 list-based map에 위임

Algorithm put(k, v):
    p <- A[h(k)].put(k, v)	put을 A[h(k)]에 있는 list-based map에 위임
    n <- n + 1
    return p

Algorithm erase(k):
    output: 없음
    A[h(k)].erase(k)		erase를 A[h(k)]에 있는 list-based map에 위임
    n <- n - 1

키 k에 관련된 각각의 기본적인 맵 연산을 위해, A[h(k)]에 저장된 작은 시퀀스에 의한 맵의 연산을 이용한다. 따라서 put(k, v)는 이 리스트를 따라 k와 키가 같은 엔트리를 검색한다. 발견하면 값을 v로 교체하고, 그렇지 않으면 리스트의 끝에 (k, v)를 삽입한다. 비슷하게 find(k)는 리스트를 따라 검색하여 k와 같은 키를 갖는 엔트리를 찾거나 리스트의 끝에 도달한다. erase(k)는 유사한 검색을 실행한 후, 만약 엔트리를 발견하였다면 삭제한다.

맵이 n개의 엔트리를 사이즈 N인 버켓 배열에 저장하기 위해 좋은 해시 함수를 사용하고 있다고 가정하면, 각 버켓의 사이즈는 평균 n/N이 될 것이다. 해시 테이블의 적재율(load factor)로 불리는 이 값(λ로 표시)은 작은 것이 바람직하며, 가능하면 1보다 작아야 한다. 이 함수를 이용한 해시 테이블로 구현된 맵의 연산 find, put, erase의 예상 실행 시간은 O(⌈n/N⌉) 이다. 따라서 n이 O(N)인 경우 표준 맵 연산들의 예상 실행 시간은 O(1)이다.

크기가 13인 해시 테이블에 정수 키를 갖는 10개의 엔트리를 별도 체이닝 방법에 의해 충돌을 해결하여 저장한 예. 이 경우 압축 함수는 h(k) = k mod 13이다.

오픈 어드레싱(Open Addressing)

별도 체이닝은 맵 연산의 구현을 간단히 할 수 있는 등의 많은 장점을 가지고 있지만, 충돌하는 키들을 저장하기 위해 별도의 자료구조인 리스트가 필요하다는 단점이 있다. 공간이 충분하지 않은 경우에는 각 엔트리를 버켓에 직접 저장하는 방식(각 버켓은 최대 하나의 엔트리를 저장)을 사용할 수 있다. 이 방식은 별도의 자료구조를 사용하지 않아 공간을 절약할 수 있지만, 좀 더 복잡한 충돌 해결 방법이 필요하다. 이러한 방법을 전체적으로 오픈 어드레싱 기법이라고 하고, 이때 적재율은 항상 1보다 작아야 하고 엔트리들은 버켓 배열에 직접 저장된다.

선형 검사(Linear Probing)와 그 변형들

간단한 오픈 어드레싱 충돌-처리 기법이 선형 검사이다. 만약 엔트리 (k, v)를 삽입할 버켓 A[i](여기서 i == h(k))에 다른 엔트리가 이미 저장되어 있는 경우, 다음 버켓 A[(i+1) mod N]에 저장하는 방식이다. A[(i+1) mod N]에도 다른 엔트리가 이미 저장되어 있으면 A[(i+2) mod N]에 저장한다. 이런 방식으로 A에서 빈 버켓을 찾을 때 까지 계속 다음 버켓을 검사한다. 이렇게 해서 빈 버켓을 찾은 후에 엔트리(k, v)를 거기에 저장하면 된다.

충돌 해결을 위해 선형 검사를 사용하여 해시 테이블에 삽입하는 예. 여기서 압축 함수는 h(k) = k mod 11을 사용한다.

 

이 방법은 맵의 엔트리를 뭉치게 하여 연속적으로 저장하는 경향이 있으며 심지어 여러 키가 겹치기도 한다. 이러한 현상은 검색 시간을 현저히 떨어트린다.

제곱 검사(Quadratic Probing)

빈 버켓을 찾을 때 까지 연속적으로 A[(i + f(j)) mod N](여기서 j = 0, 1, 2, ... 이고 f(j) = j^2)를 검사한다. 제곱 검사 전략은 선형 검사에서 발생하는 뭉치는(clustering) 패턴을 피할 수 있다. 하지만 이 방법은 2차 클러스터링이라 불리는 채워진 셀들이 배열 내에서 정해진 패턴으로 "움직이는" 클러스터링을 발생시킨다. 만약 N을 소수로 하지 않으면 꽉 차지 않은 배열 A에서 빈 배열을 못 찾을 수도 있다. 또 N이 소수이더라도 버켓 배열이 반 이상 차있다면 또 빈 버켓을 찾지 못할 수 있다.

이중 해싱(Double Hashing)

선형검사 방법이나 제곱 검사 방법에 의해 발생하는 클러스트링을 만들지 않는 오픈 어드레싱 전략이다. 이 방법에서는 보조 해시 함수 h'를 만들어 만약 키 k에 대한 버켓 A[i](i = h(k))가 이미 사용되고 있으면 버켓(A[(i + f(j)) mod N](여기서 j = 1, 2, 3, ... 이고 f(j) = j · h'(k))를 차례로 검사한다. 보조 해시 함수는 0이 되지 않아야 하며 일반적으로 h'(k) = q - (k mod q)를 사용한다. 여기서 q는 N보다 작은 소수이고 또한 N도 소수여야 한다. 보조 해시 함수를 결정하는 데 있어 클러스터링을 최대한 줄이도록 해야 한다.

이러한 오픈 어드레싱 방법은 별도 체이닝 방법보다 공간은 절약되지만 속도 면에서 반드시 빠르다는 것은 아니다. 만약 메모리 공간이 중요한 문제가 아니라면 별도 체이닝 방법이 적절하다!!

 

적재율과 재해싱(Load Factors and Rehashing)

위에서 설명한 모든 해시 테이블 체계에서 적재율 λ = n/N은 항상 1보다 작은 것이 바람직하다. 실험과 통계적인 분석에서 오픈 어드레싱은 λ<0.5이고 별도 체이닝에서는 λ<0.9인 것이 바람직하고 한다.

오픈 어드레싱에서 λ가 0.5를 넘어 증가하기 시작하여 1에 접근하기 시작하면서, 버켓 배열에서 엔트리들의 클러스터도 같이 증가하기 시작한다. 이러한 클러스터들은 검사 정책(probing strategy)들이 상당히 큰 시간 동안 버켓 배열을 여기저기 검색하도록 하는 원인이 된다. λ가 1에 가까워지면, 몇 개 남은 비어있는 셀 중 하나를 발견하기 전에 만나야 하는 버켓의 수가 선형일 것이기 때문에 모든 맵 연산은 선형의 실행시간을 갖는다.

새 테이블로의 재해싱(Rehashing into a New Table)

적재율 λ을 정해진 임계 값 이하로 유지하는 것이 중요하다. 만약 해시 테이블의 λ가 특정 임계값보다 상당히 높아지면, 보통 정해진 적재율 아래로 유지하기 위해 테이블 사이즈를 증가시키고 모든 객체를 새 테이블로 삽입한다. 새 테이블로 재해시할 경우, 새 테이블의 사이즈는 이전 사이즈보다 적어도 두 배 이상 되는 것이 좋다. 새로운 버켓 배열을 할당한 후에는 함께 사용할 해시 함수를 다시 정의해야 한다. 이렇게 새로운 해시 함수를 준비한다면, 이전 배열의 모든 엔트리를 새 해시 함수를 이용하여 새 배열로 삽입한다. 이러한 과정을 재해싱(rehashing)이라고 한다.

 

C++ 구현

template <typename K, typename V, typename H>
class HashMap {
public:
    typedef Entry<const K, V> Entry;		// (key, value) pair
    class Iterator;							// 반복자(위치)
	HashMap(int capacity = 100)				// 생성자
    : n(0), B(capacity) {}
    int size() const {						// 엔트리 개수
    	return n;
    }
    bool empty() const {					// 맵이 비었는지
    	return size() == 0;
    }
    Iterator find(const K& k) {				// 키 k를 갖는 엔트리를 검색
    	Iterator p = finder(k);				// k를 찾는다
        if (endOfBkt(p))					// 못찾았나?
        	return end();					// 그럼 end 반복자 반환
        else
        	return p;						// 찾았으면 위치를 반환
    }
    Iterator put(const K& k, const V& v) {	// (k,v)를 삽입하거나 이미 키가 k인 엔트리가 존재한다면 (k, v)로 교체
    	Iterator p = finder(k);				// k를 검색
        if (endOfBkt(p)) {					// k가 없나
        	return inserter(p, Entry(k, v));	// 버켓 끝에 삽입
        }
        else {
        	p.ent->setValue(v);				// 있다면 k의 값을 v로 교체
            return p;
        }
    }
    void erase(const K& k) {				// 키 k를 갖는 엔트리 삭제
    	Iterator p = finder(k);				// k를 검색
        if (endOfBkt(p))					// 못찾았나?
        	throw NonexistentElement("Erase of nonexistent");	// 에러
        erase(p);							// 삭제
    }
    void erase(const Iterator& p) {			// p에 있는 엔트리 삭제
    	eraser(p);
    }
    Iterator begin() {						// 첫 번째 엔트리의 반복자
    	if (empty()) return end();			// 비어있으면 end반환
        BItor bkt = B.begin();				//그렇지 않으면 엔트리를 검색
        while (bkt->empty()) ++bkt;			// 비지 않는 버켓을 찾는다
        return Iterator(B, bkt, bkt->begin());	// 버켓의 first 반환
    Iterator end() {						// end 엔트리의 반복자
		return Iterator(B, B.end);
    }
protected:
    typedef std::list<Entry> Bucket;		// 엔트리들의 버켓
    typedef std::vector<Bucket> BktArray;	// 버켓 배열
    Iterator finder(const K& k) {			// 검색 편의 함수
    	int i = hash(k)%B.size();			// 해시 인덱스 i를 구함
        BItor bkt = B.begin() + i;			// i번째 버켓
        Iterator p(B, bkt, bkt->begin());	// i번째 버켓의 첫 엔트리
        while (!endOfBkt(p) && (*p).key() != k)		// k를 검색
        	nextEntry(p);
        return p;
    }
    Iterator inserter(const Iterator& p, const Entry& e) {	// 삽입 편의 함수
    	EItor ins = p.bkt->insert(p.ent, e);	// p 앞에 삽입
        n++;
        return Iterator(B, bkt, ins);			// 이 위치 반환
    }
    void eraser(const Iterator& p) {			// 삭제 편의 함수
    	p.bkt->erase(p.ent);					// 엔트리를 버켓에서 삭제
        n--;									// 엔트리의 개수를 감소
    }
    typedef typename BktArray::iterator BItor;	// 버켓 반복자
    typedef typename Bucket::iterator EItor;	// 엔트리 반복자
    static void nextEntry(Iterator& p) {		// 버켓의 다음 엔트리
    	++p.ent;
    }
    static bool endOfBkt(const Iterator& p) {	// 버켓의 끝인지
    	return p.ent == p.bkt->end();
    }
private:
    int n;									// 엔트리의 개수
    H hash;									// 해시 비교자
    BktArray B;								// 버켓 배열
public:
    class Iterator {						// 반복자
    private:
    	EItor ent;							// 엔트리
        BItor bkt;							// 버켓
        const BktArray* ba;					// 버켓 배열
    public:
        Iterator(const BktArray& a, const BItor& b, const EItor& q = EItor())
        : ent(q), bkt(b), ba(&a) {}
        Entry& operator*() const {			// 엔트리 반환
        	return *ent;
        }
        bool operator==(const Iterator& p) const {	// 반복자가 같은지
        	if (ba != p.ba || bkt != p.bkt) return false;	// ba 또는 bkt가 다른가
            else if (bkt == ba->end()) return true;	// 둘 다 end인가?
            else return (ent == p.ent);				// 엔트리가 같은지 확인
        }
        Iterator& operator++() {			// 다음 엔트리로 전진
       		++ent;
            if (endOfBkt(*this)) {			// 버켓의 끝인가?
            	++bkt;
                while (bkt != ba->end() && bkt->empty())	// 비지 않은 버켓을 검색
                	++bkt;
                if (bkt == ba->end()) return *this;			// 버켓 배열의 끝?
                ent = bkt->begin();
            }
            return *this;
        }   
        friend class HashMap;				// HashMap에 접근을 허용
    };
};

---

참고 문헌

[1] Michael T. Goodrich, Roberto Tamassia, Davaid M. Mount, C++로 구현하는 자료구조와 알고리즘, WILEY, 2013.