[자료구조/C++] 해시 테이블(hash table)과 체이닝(chaining) - vector와 list로 구현

[ 1 ] 해시 테이블(hash table)이 필요한 이유

옥스포드 영어 사전에는 약 170,000개의 단어가 수록되어 있다고 한다. 이 사전에서 하나의 단어를 탐색하는데 시간 복잡도가 O(n)인 선형 탐색을 활용한다면 오랜 시간이 걸릴 것이다.

이를 해결하기 위해 AVL Tree나 Red-Black Tree처럼 트리의 높이를 O(log n)으로 유지하는 자료구조를 활용한다면 선형 탐색보다 그 검색 시간을 유의미하게 줄일 수 있을 것이다.

하지만, 데이터의 수가 증가하거나 탐색 횟수가 크게 증가할 경우 O(log n)의 속도도 만족스럽지 못할 수도 있기 때문에 우리는 더욱 효율적인 데이터 저장 - 탐색을 위한 자료구조를 떠올려야 한다.

 

이때 해시 테이블(hash table)이 효율적이고 효과적인 자료구조로써 활용될 수 있다.

 

[ 2 ] 기본 내용

[ 2 - 1 ] 기본 구조 - hashing과 hash function

출처 - 위키백과

해시 테이블은 기본적으로 entry 라고 불리는 (key, value)를 저장하는 자료구조이며, 이는 전에 포스팅했던 map과 유사하다.

위의 그림은 다음과 같이 동작한다.

 

 (1) 위는 크기가 16인 hash table이다.

 (2) ("John Smith", "521-1234")라는 (key, value)쌍이 해당 hash table로 들어왔을 때, 우선 key값인 John Smith를 hash function에 넣어 고유한 숫자 값(=해시 값)을 뽑아낸다.

 (3) 위 예제에서 John Smith의 해시 값은 2로 계산되었으므로 buckets[2]에 value 값인 "521-1234"를 저장한다.

 (4) 나머지 (key, value)도 (1) ~  (3)의 과정을 통해 hash table에 추가한다.

 

위와 같은 hash table이 완성된 후 "John Smith"를 검색할 때 우리는 모든 buckets을 선형으로 탐색할 필요없이 "John Smith"를 hash function에 넣어 해시 값을 계산한 후 buckets[해시 값]을 확인만 하면 된다. 즉, 데이터 탐색의 평균적인 시간복잡도가 O(1)인 것이다.

 

- hashing: 위 과정에서 각 데이터를 고유한 숫자 값(=해시 값)으로 표현하고, 그 값을 통해 나중에 데이터의 유무를 확인하거나 해당 숫자에 대응하는 원본 데이터를 추출하는 작업

- hash function: hashing의 과정에서 주어진 데이터로부터 고유한 숫자 값(=해시 값)을 계산하는 함수

 

hash function이 도대체 무엇이길래 key에 따른 고유값을 뽑아낼 수 있는 것이지? 의문일 수도 있다. hash function의 종류는 다양하고, key의 데이터 타입에 따라 구현 방법이 달라질 수 있으니 상황에 맞게 구현(or 구글에 검색)하도록 하자.

가장 간단한 hash function으로는 모듈로 함수가 있으며 보통 [key % size(hash table의 크기)]로 구현한다.

 

 

[ 2 - 3 ] 충돌(collision)

하지만, hash table에서는 충돌(collision)이라는 문제가 발생할 수 있다. 충돌은 서로 다른 데이터에 대해 같은 해시 값을 반환했을 때 나타나는 문제이다. 

만약, 위 예시에서 ("Coha", "521-0000")라는 (key, value)값이 들어왔는데, hash function이 "Coha"의 해시 값으로 2를 반환했다고 가정해보자. 이미 "John Smith"의 해시 값도 2로 계산되어 buckets[2]에 ("John Smith", "521-1234")이 저장되어 있는 상황이다. 이러한 충돌을 대비할 전략을 갖추지 않고, 충돌이 발생했을 때 기존 키를 덮어쓰는 방식으로 최근에 추가된 키만 저장한다면 위의 hash table의 buckets[2]에는 ("John Smith", "521-1234")는 사라지고 ("Coha", "521-0000")만이 남을 것이다.

즉, 충돌로 인해 데이터의 손실 및 모든 키를 저장할 수 없는 문제가 발생한다.

 

 

[ 2 - 4 ] 충돌을 피하는 방법 1 - 체이닝(chaining)

이러한 충돌을 피하기 위해 체이닝(chaining)이라는 기법을 활용할 수 있다. 체이닝은 hash table의 bucket에 하나의 값만 저장하는 것이 아니라 연결 리스트를 활용하여 여러 개의 값을 저장할 수 있도록 한다. 

chaining 예시

위와 같이 연결리스트를 활용하면 충돌이 발생하더라도 데이터 손실없이 모든 값을 저장할 수 있다.

 

이는 C++에서 vector와 list를 활용하여 구현할 수 있다.

(해당 예시는 value값 없이 정수 key값만 저장하는 매우 단순한 hash table이다!)

 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

class hash_map{
private:
    vector<list<int>> data;

public:
    hash_map(unsigned int n)
    {
        data.resize(n);
    }
}

우선, hash_map 클래스를 만들고 데이터를 담을 vector<list<int>> data와 data의 크기를 n으로 설정하는 생성자를 구현한다. 해당 예시에서 hash function은 입력된 정수값을 n으로 모듈로 연산을 하는, 매우 간단한 함수로 구현했다.

 

hash_map의 추상자료형은 전에 포스팅한 map과 거의 비슷한 search, insert, delete이다.

 

 (1) search

 

    bool search(unsigned int value)
    {
        int n = data.size();
        auto& entries = data[value % n];
        return (find(entries.begin(), entries.end(), value) != entries.end());
    }

data[value % n]으로 해당 해시 값을 가진 list로 이동한 후 <algorithm>에 내장된 find()함수로 list에 해당 value가 존재하는지 확인할 수 있도록 구현했다.

 

 

 (2) insert

 

    void insert(unsigned int value)
    {
        if(search(value))
        {
            cout << "이미 존재하는 값입니다." << endl;
            return;
        }
        else
        {
            int n = data.size();
            data[value % n].push_back(value);
            cout << value << "을 삽입했습니다." << endl;
            return;
        }
    }

 값의 중복을 방지하기 위해 search 함수를 활용하여 이미 hash table에 존재하는 값이라면 저장하지 않도록 구현했다.

 

 

 (3) delete

 

    void delete_entry(unsigned int value)
    {
        int n = data.size();
        auto& entries = data[value % n];
        auto it = find(entries.begin(), entries.end(), value);
        
        if(it != entries.end())
        {
            entries.erase(it);
            cout << value << "을 삭제했습니다." << endl;
        }
        else
        {
            cout << "존재하지 않는 값입니다." << endl;
        }
    }

 

※ 위 예제는 load factor를 고려하지 않은 매우 단순한 예제이므로 main()함수를 만들어 직접 다루어 보면서 참고만 하자! 또한, vector와 list container를 알고 있다고 가정했다.

 

 

[ 2 - 5 ] 체이닝(chaining)의 시간복잡도와 부하율(load factor)

체이닝을 활용한 hash table에서 insert는 항상 O(1)의 시간복잡도를 가진다. 하지만, 모든 키가 같은 해시 값을 가지게 되는 경우는 어떠한가? 즉, n개의 키가 버킷 내부 하나의 연결리스트에만 전부 저장된 것이다. 그러므로 이때의 search는 연결리스트에서 선형 검색을 수행하는 것과 같으므로 O(n)의 시간복잡도를 가지게 된다.

 

hash table이 저장할 키 개수에 비해 크기가 작으면 충돌이 많이 발생하게 되어 연결리스트는 평균적으로 더 길어지고, 반대로 크기가 너무 큰 hash table은 실제 데이터가 듬성듬성 저장되므로 메모리 낭비가 발생할 수 있다. 

그러므로 우리는 '부하율(load factor)'를 고려하며 hash table의 크기를 적절히 조절해야 한다.

 

- load factor = 전체 키 개수 / hash table의 크기

 

즉, load factor은 hash table에서 각각의 연결리스트에 저장되는 키의 평균 개수를 의미한다. 

- 전체 키 개수 = hash table의 크기라면 load factor = 1이다. 이는 매우 이상적인 상태이며 모든 연산이 O(1)에 가깝고, 메모리 낭비가 적다.

- load factor < 1 이라면 메모리 낭비가 발생하고 있다는 것을 의미

- load factor > 1 이라면 연결리스트의 평균 길이가 1보다 크다는 것을 의미하고, 이는 search가 느리게 동작할 수 있음을 의미한다.

 

그러므로 load factor = 1에 가깝도록 유지하는 것이 이상적이며, 실제로 이상적인 load factor를 유지하기 위해 해시 함수를 변경하는 등의 rehashing을 진행하는 hash table도 존재한다.

 

※ 하지만, 크기가 7인 hash table의 모든 키(7개)가 하나의 연결리스트에 저장되어 있다고 가정하라! 이 경우에는 load factor = 1인데, search의 시간복잡도는 O(n)이다. 그러므로 load factor에만 집중해야 하는 것이 아니라, 최대한 key를 분산할 수 있는 hash function을 구현하는 것도 중요함을 의미한다!

 

 

+ 추가) 다음에는 충돌을 피하는 다른 방법인 '열린 주소 지정(open addressing)'에 대해 포스팅하도록 하겠다!