[Algorithm] 해시 테이블

해시 테이블

먼저 배열에 대해 생각해보자.

배열은 컴퓨터 프로그래밍에 있어서 가장 근본이 되는 자료구조이다. 레지스터가 메모리 어드레싱을 통해 특정 번지의 값을 바로 참조해올 수 있는 것처럼, 배열도 특정 주소의 공간을 바로 참조해올 수 있다. 사실 이 특성은 굉장히 유용하게 활용될 수 있다.

특정 위치를 탐색비용 없이 참조해 올 수 있다는 것은,

어떤 데이터들을 저장할 때, 각 데이터가 저장될 위치를 결정할 수 있다고 가정했을 때,

아무런 탐색비용 없이 그 데이터를 저장하고 참조해올 수 있는 자료구조를 설계할 수 있다는 의미이다.

리스트와 같은 일반적인 컨테이너가 저장비용으로 O(1), 데이터 참조 비용으로 O(N) 인 것을 감안했을 때, 

저장비용 O(1), 참조비용 O(1)은 자료구조로서 엄청나게 효율적이라고 볼 수 있을 것이다.

 

예제를 하나 생각해보자.

a-z 까지의 알파벳으로 이루어진 문자열이 들어올 때, 각 알파벳들의 개수를 카운팅하려면 어떻게 해야할까?

위에서 생각해본 대로, 알파벳이라는 데이터를 통해 각 알파벳이 저장될 위치를 결정할 수 있다면 다음과 같은 알고리즘을 작성할 수 있을 것이다.

 

#include <string>
#include <iostream>

using namespace std;

int main()
{
    string text = "aaabbbcccadd";
    int cnt[26] = {};

    for (int i = 0; i < text.size(); ++i)
    {
        char alphabet = text[i];

        // 저장될 위치
        int index = alphabet - 'a';
        cnt[index] ++;
    }

    // 출력
    for (int i = 0; i < 26; ++i)
    {
        char alphabet = i + 'a';
        cout << alphabet << " : " << cnt[i] << endl;
    }

    return 0;
}

이 알고리즘에서는 index = alphabet - 'a'; 라는 부분을 통해 데이터가 저장될 위치를 계산해냈다.

이제 'd'의 개수를 알고싶다면, index = 'd' - 'a'를 통해 위치를 알아내고, 그 값을 참조해오면 될 것이다.

이처럼 데이터를 통해 데이터가 저장될 위치를 알아낼 수 있다면, 이는 배열의 주소참조라는 강점과 합쳐져서 엄청난 효율의 자료구조로서 활용될 수 있다. 그래서 이런 특성을 제대로 활용해보고자 탄생한 자료구조가 해시테이블이다.

 

이 예제는 굉장히 축소된 해시 예제이지만, 약식 해시테이블로서 코드를 다시 작성해볼 수 있다.

'a'와 같은 알파벳들은 데이터 그 자체로서, 해시테이블에 저장될 값(Value)와 대응된다.

알파벳의 아스키 값은 데이터의 고유한 식별값으로서, 키(Key)와 대응된다.

배열[26]은 해시 테이블의 저장공간으로서, 버킷(Bucket)과 대응된다.

alphabet - 'a'라는 계산식은 각 데이터가 저장될 위치를 결정하는 방법으로서, 해시 함수(Hash Function)에 대응된다.

hash function 통해 계산된 index는 실제 값이 bucket에 저장될 위치로서, 해시(Hashes)와 대응된다.

 

추가로, 구조체를 통해 value와 cnt를 묶어서 저장한다면 출력시 어떤 cnt가 어떤 알파벳에 대한것인지 알아낼 수 있기 때문에, hash function을 alphabet % BucketSize로 확장시킬 수 있다. 모듈러 연산으로 만들어진 index이기 때문에 오버플로우에 대해 안전하다.

#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

const int InValid = -1;
const int BucketSize = 26;

struct Value
{
    char alphabet;
    int cnt;
};

struct KeyValue
{
    KeyValue() :key(InValid), value() {}

    int key;
    Value value;
};

// overflow를 방지하기 위해 bucket_size로 모듈러 연산
int HashFunction(int key, int bucket_size)
{
    return key % bucket_size;
}

int main()
{
    string text = "aaabbbcccadd";
    KeyValue bucket[BucketSize] = {};

    for (int i = 0; i < text.size(); ++i)
    {
        char alphabet = text[i];
        int index = HashFunction((int)alphabet, BucketSize);

        bucket[index].key = (int)alphabet;
        bucket[index].value.alphabet = alphabet;
        bucket[index].value.cnt ++;
    }

    // 출력
    for (int i = 0; i < BucketSize; ++i)
    {
        if (bucket[i].key == InValid)
        {
            continue;
        }

        cout << bucket[i].value.alphabet << " : " << bucket[i].value.cnt << endl;
    }

    return 0;
}

 

 

하지만 제대로 된 해시 테이블이 되기 위해서는 건너야 할 과제가 아직 많이 남아있다.

만약 위 예제에서 소문자뿐만 아니라 대문자에 대해서도 처리해야한다는 추가 요구사항이 생겼다고 하면 어떻게 해결해야할까?? 현재 구조대로라면 bucket 공간보다 데이터 종류가 많기 때문에 비둘기집 원리에 의하여 반드시 겹치는 공간이 생기게 된다. 실제로 'u'와 'A'는 저장공간이 겹치게 된다. 이런 서로 다른 데이터에 대해 해시 함수가 동일한 출력값(저장 index)를 내는 문제를 해시 충돌이라한다.

 

이 문제를 해결하기 위한 가장 단순한 접근으로는 그냥 bucket size를 늘리는 것이다. 하지만 해시 함수로 만들어진 index의 분포가 어떤 형태로 나타날지 모르고, 데이터의 종류가 어떻게 들어올지 모르는 일반적인 상황에서 항상 충돌이 발생하지 않는 bucket size를 유지하는것은 너무 공간낭비이다. 그러므로 충돌을 피하기 위한 좀 더 다른 방법들이 필요할 것이다.

 

해시 충돌해결

개방 주소법 (Open Addressing)

개방 주소법은 새로운 버킷 인덱싱을 통해 충돌을 해소하는 방법이다.

그렇기 때문에, 버킷 크기가 들어올 수 있는 인풋 가지수보다 큰 경우에만 사용할 수 있는 충돌 해결방법이다.

만약 인풋 가지수가 버킷 사이즈보다 크다면, 비둘기집 원리에 의해 어떤 방법을 동원해서 새로운 인덱스를 만들더라도 충돌이 발생할 수 밖에 없다.

 

선형조사

충돌이 일어난 바로 뒷 자리에 값을 넣어준다.

예를 들어 i번째 위치가 이미 점유되어 있다면, i + 1위치에 값을 저장한다.

만약 i + 1 위치도 점유되어 있다면, i + 2 위치에 값을 저장한다.

데이터를 참조해오는 경우는 다시 i번째 위치를 해싱하고,

거기서부터 선형조사를 하며 데이터와 같은 값을 갖는 위치를 찾아 데이터를 참조해온다.

계산이 단순하다는 장점이 있지만, 테이블 내에 데이터가 특정 영역에 몰리는 현상이 발생할 수 있고,

그러한 이유로 검색에 시간이 많이 소요될 수 있다.

 

이차 조사법

근본적인 아이디어는 선형조사와 비슷하지만, 새로운 위치를 찾을 때 제곱수를 더해주는 형태로 하여 데이터가 좀 더 고르게 분포되도록 한다. 

i + 1, i + 4, i + 9 ...

하지만 역시 초반에 같은 해시값을 같는 데이터가 연속적으로 들어온다면, 빈 슬롯을 찾기 위해 접근하는 위치가 계속 동일하게 된다.

 

이중 해싱

이중 해싱은 두 개의 해시함수를 준비하여, 기본적으로는 첫번째 해시함수로 동작하도록 하고, 충돌이 발생한 경우 두 번째 해시함수가 동작하도록 한다. 실제로도 꽤 좋은 해결방법으로 사용되고 있다.

 

 

비개방 주소법 (Closed Addressing)

비개방 주소법은 충돌시 다른 인덱스를 찾지 않고, 자료구조적으로 충돌을 해소하는 방법이다.

그렇기 때문에 버킷 크기가 들어올 수 있는 인풋 가지수보다 작더라도 충돌을 해소할 수 있다. (물론 성능은 버킷을 늘리는게 좀 더 효율적일 것이다.)

 

체이닝

해시함수를 이용하여 bucket의 적절한 위치를 찾아 충돌을 피하는 방법도 있지만, 자료구조적으로 충돌문제를 해결하는 접근방법도 있다. 체이닝이라는 방법은 어떤 위치에서 충돌이 일어났을 경우 단순하게 그 위치 뒷부분에 데이터를 추가하는 것이다. 즉 모든 bucket의 item들은 리스트 형태로 되어있고, 충돌상황이 발생하면 리스트 뒤에 추가시켜 주는 것이다. 하지만 역시, 해시테이블이 채워질수록 리스트의 탐색비용이 커진다는 단점이 있다.

 

 

해시 테이블 구현 (약식)

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/3-HashCustom.cpp

insooneelife/AlgorithmTutorial

 

 

Key와 Hash를 혼동하지 않기

해시테이블에 대해 배울 때 항상 주의하여야 하는 부분이 있다. Key와 Hash는 엄연히 다른 것이라는걸 인지하여야 한다.

Key는 어떤 데이터를 위한 고유 식별자(Unique Identifier)로서, 단지 해시 테이블에서만 사용되는 개념이 아니다. 굉장히 다양한 자료구조에서 사용되고 있고, 컴퓨터공학의 다양한 개념에서도 사용되고, 심지어 현실에서도 사용되고 있는 개념이다. (주민등록번호, 군번, 전화번호 등등..)

반면 해시(Hashes)는 해시 함수를 통해 생성된 값으로, 해시 테이블 버킷 내의 데이터가 저장될 주소값이다.

그리고 해시 충돌에서 언급했듯이 해시 값은 서로 다른 데이터에 대해 동일한 값이 나올 수도 있는 반면  키는 서로다른 데이터라면 반드시 달라야만 한다. (키가 같다면 그것은 같은 데이터이다.)

보통 Key의 대한 개념을 명확하게 알지 못한 상태에서 Dictionary와 같은 잘 인터페이싱된 자료구조를 이용하며 Key를 알게 된 경우, 내부 bucket과 해시함수의 동작이 완벽하게 가려져 있기 때문에 Key와 Hash를 동일시하게 되는데, 그렇게 되면 해시 테이블을 사용하는데 있어서 많은 문제가 생길 것이다.

 

 

C++ Hash Table (unordered_map, unordered_set) 

C++에서는 STL을 통해 해시 테이블 컨테이너를 지원한다.

C++ unordered_map의 경우 삽입, 삭제, 참조 모두 O(1) 정도에 근사하게 동작한다.

하지만 string을 key로 하는 경우 equal 비교연산이나 hash function 에서 연산비용이 늘어나기 때문에, 

string이 길어진다면 조금 취약해질 수 있다.

 

사용 예제 1.

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/4-unordered_map.cpp

insooneelife/AlgorithmTutorial

 

 

사용 예제 2.

 

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/5-unordered_map-CustomKey.cpp

insooneelife/AlgorithmTutorial