뻐꾸기 해싱(Cuckoo hashing)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

뻐꾸기 해싱

• 크기가 같은 2개 이상의 해시 테이블을 사용한다.
• 각 테이블을 다른 해시 함수를 갖는다.
• 모든 원소는 테이블 어디든 저장될 수 있고 그 중 하나에 존재한다.
• 원소는 다른 테이블로 이동할 수 있다.

 

뻐꾸기 해싱에서의 삽입

1. 해시 테이블1에서 공간이 비어 있으면 삽입한다.
2. 비어 있지 않으면 기존 원소를 해시 테이블2로 이동한 후 삽입한다.
3. 기존 원소를 옮길 공간이 비어 있지 않으면 원래 있던 원소를 해시 테이블 1로 이동한 후 삽입한다.
4. 빈 공간이 발견되어 이동이 멈출 때까지 2부터 반복한다.
   여기서 루프가 발생할 수 있고 이때는 재해싱을 수행해야 한다.

 

뻐꾸기 해싱의 성능

• 검색, 삭제는 원소의 개수와 상관 없이 테이블의 개수만큼만 확인하면 되므로 O(1) 시간에 수행된다.
• 적절한 해시 함수를 사용한다면 대부분의 상황에서 O(1) 복잡도를 갖는 삽입이 가능하다.
• 높은 성능을 내기 위해서는 0.5 이하의 부하율(Load factor)을 유지해야 한다.

 

#include <iostream>
#include <vector>

using namespace std;

class hash_map
{
    vector<int> data1;
    vector<int> data2;
    int size;

public:
    hash_map(int n) : size(n), data1(vector<int>(n, -1)), data2(vector<int>(n, -1)) { }

    vector<int>::iterator lookup(int key)
    {
        int hs1 = hash1(key);
        int hs2;

        if (data1[hs1] == key)
        {
            cout << "1번 테이블에서 " << key << "을(를) 찾았습니다." << endl;

            return data1.begin() + hs1;
        }
        else if (data2[hs2 = hash2(key)] == key)
        {
            cout << "2번 테이블에서 " << key << "을(를) 찾았습니다." << endl;

            return data2.begin() + hs2;
        }

        return data2.end();
    }

    void erase(int key)
    {
        auto it = lookup(key);

        if (it != data2.end())
        {
            *it = -1;

            cout << key << "에 해당하는 원소를 삭제했습니다." << endl;
        }
        else
        {
            cout << key << "키를 찾지 못했습니다." << endl;
        }
    }

    void insert(int key)
    {
        insert_impl(key, 0, 1);
    }

    // 루프 검사를 위해 방문한 모든 값을 기억하는 것은 부담이 클 수 있으므로
    // 단순히 재귀 깊이가 테이블의 크기 이상이면 루프로 간주한다.
    // 이러한 구현은 괜찮은 성능을 낸다.
    void insert_impl(int key, int cnt, int table)
    {
        vector<int>& data = (table == 1) ? data1 : data2;
        int hs = (table == 1) ? hash1(key) : hash2(key);

        if (size <= cnt)
        {
            cout << key << " 삽입 시 루프 발생! 재해싱이 필요합니다!" << endl;

            return;
        }

        if (data[hs] == -1)
        {
            data[hs] = key;

            cout << table << "번 테이블에 " << key << " 삽입" << endl;
        }
        else
        {
            int old = data[hs];
            data[hs] = key;

            cout << table << "번 테이블에 " << key << " 삽입: 기존의 " << old << " 이동 -> ";

            insert_impl(old, ++cnt, (table == 1) ? 2 : 1);
        }
    }

    void print()
    {
        cout << "Index: ";
        for (int i = 0; i < size; ++i)
            cout << i << '\t';
        cout << endl;

        cout << "Data1: ";
        for (int e : data1)
            cout << e << '\t';
        cout << endl;

        cout << "Data2: ";
        for (int e : data2)
            cout << e << '\t';
        cout << endl;
    }

private:
    int hash1(int key) const
    {
        return key % size;
    }

    int hash2(int key) const
    {
        return (key / size) % size;
    }
};

void main()
{
    hash_map map(7);

    map.print();
    cout << endl;

    map.insert(10);
    map.insert(20);
    map.insert(30);
    cout << endl;

    map.insert(104);
    map.insert(2);
    map.insert(70);
    map.insert(9);
    map.insert(90);
    map.insert(2);
    map.insert(7);
    cout << endl;

    map.print();
    cout << endl;

    // 루프 발생!
    map.insert(14);
}

 

출력

Index: 0        1       2       3       4       5       6
Data1: -1       -1      -1      -1      -1      -1      -1
Data2: -1       -1      -1      -1      -1      -1      -1

1번 테이블에 10 삽입
1번 테이블에 20 삽입
1번 테이블에 30 삽입

1번 테이블에 104 삽입: 기존의 20 이동 -> 2번 테이블에 20 삽입
1번 테이블에 2 삽입: 기존의 30 이동 -> 2번 테이블에 30 삽입
1번 테이블에 70 삽입
1번 테이블에 9 삽입: 기존의 2 이동 -> 2번 테이블에 2 삽입
1번 테이블에 90 삽입: 기존의 104 이동 -> 2번 테이블에 104 삽입: 기존의 2 이동 -> 1번 테이블에 2 삽입: 기존의 9 이동 -> 2번 테이블에 9 삽입
1번 테이블에 2 삽입: 기존의 2 이동 -> 2번 테이블에 2 삽입: 기존의 104 이동 -> 1번 테이블에 104 삽입: 기존의 90 이동 -> 2번 테이블에 90 삽입
1번 테이블에 7 삽입: 기존의 70 이동 -> 2번 테이블에 70 삽입

Index: 0        1       2       3       4       5       6
Data1: 7        -1      2       10      -1      -1      104
Data2: 2        9       20      70      30      90      -1

1번 테이블에 14 삽입: 기존의 7 이동 -> 2번 테이블에 7 삽입: 기존의 9 이동 -> 1번 테이블에 9 삽입: 기존의 2 이동 -> 2번 테이블에 2 삽입: 기존의 2 이동 -> 1번 테이블에 2 삽입: 기존의 9 이동 -> 2번 테이블에 9 삽입: 기존의 7 이동 -> 1번 테이블에 7 삽입: 기존의 14 이동 -> 14 삽입 시 루프 발생! 재해싱이 필요합니다!