[C++] 뻐꾸기 해싱(Cuckoo Hashing)

뻐꾸기 해싱(Cuckoo Hashing)

• 크기가 같은 2개의 해시 테이블을 사용함.
  • 각각의 해시 테이블은 서로 다른 해시 함수 를 가짐.
  • 모든 원소는 두 해시 테이블 중 하나에 있을 수 있음.
    • 위치는 해당 해시 테이블의 해시 함수 에 의해 결정됨.
• 뻐꾸기 해싱이 다른 해싱 기법과 다른 점
  • 원소가 두 해시 테이블 중 어디든 저장될 수 있음.
  • 원소가 나중에 다른 위치로 이동할 수 있음.
• 다른 해싱 방법에서는 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없음.
  • 그러나, 뻐꾸기 해싱 방법에서는 모든 원소가 2개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있음.
  • 더 나은 성능을 얻고, 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가 시킬 수도 있음.
• 룩업 연산
  • 특정 원소가 존재하는지를 알기 위해 저장 가능한 위치 두 군데만 확인해보면 됨.
    • 시간 복잡도는 항상 O(1)
• 삽입 연산
  • 좀 더 오래 걸릴 수 있음.
    • 예) A라는 원소를 삽입할 경우
      • 먼저 첫 번째 해시 테이블에서 A를 삽입할 위치를 찾아 현재 비어 있는지를 검사함.
      • 만약 해당 위치가 비어 있다면 그대로 A를 삽입하면 됨.
      • 그러나 해당 위치에 이미 다른 원소 B가 저장되어 있다면, 해당 위치에 A를 저장하고, B를 두 번째 해시 테이블로 옮김.
        • 만약 B가 이동할 위치에 이미 다른 원소 C 가 저장되어 있다면, 해당 위치에 B를 저장하고 C를 첫 번째 해시 테이블로 옮김.
          • 이러한 작업을 완전히 비어 있는 셀이 나타날 때까지 재귀적으로 반복함.

• 이러한 과정에서 만약 순환(Cycle) 이 발생한다면 무한 루프에 빠질 수 있음.
  • C가 옮겨가야 할 위치에 다른 원소 D가 있고, D를 옮기다 보니 다시 A 위치를 방문하는 경우

• 일단 순환이 발생했다면 새로운 해시 함수 를 이용하여 재해싱 을 수행해야 함.
• 새로운 해시 함수를 사용하여 해시 테이블을 새로 구성한 경우에도 다시금 순환 이 발생할 수 있으므로, 여러 번 재해싱을 수행 해야 할 수도 있음.
  • 그러나 적절한 해시 함수를 사용하면 높은 확률로 O(1)의 성능을 갖는 해시 테이블을 구성할 수도 있음.
• 열린 주소 지정 방법과 마찬가지로 뻐꾸기 해싱도 전체 해시 테이블 크기 이상의 원소를 저장할 수는 없음.
• 높은 성능을 보장하려면 부하율이 0.5보다 작게끔 설정해야 함.
  • 전체 원소 개수 < 해시 테이블 크기 / 2

코드

#include <iostream>
#include <vector>

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

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

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

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

    std::vector<int>::iterator lookup(int key) {
        auto hash_value1 = hash1(key);
        if (data1[hash_value1] == key) {
            std::cout << "1번 테이블에서" << key << "을(를) 찾았습니다." << std::endl;
            return data1.begin() + hash_value1;
        }

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

        return data2.end();
    }

    void erase(int key) {
        auto position = lookup(key);
        if (position != data2.end()) {
            *position = -1;
            std::cout << key << "에 해당하는 원소를 삭제했습니다." << std::endl;
        }
        else {
            std::cout << key <<" 키를 찾지 못했습니다." << std::endl;
        }
    }

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

    void insert_impl(int key, int cnt, int table) {
        if (cnt >= size) {    // 재귀 호출 횟수가 테이블의 크기보다 클 경우
            std::cout << key << " 삽입 시 순환 발생! 재해싱이 필요합니다." << std::endl;
            return;
        }

        if (table == 1) {
            int hash = hash1(key);
            if (data1[hash] == -1) {
                std::cout << table << "번 테이블에 " << key << " 삽입" << std::endl;
                data1[hash] = key;
            }
            else {
                int old = data1[hash];
                data1[hash] = key;
                std::cout << table << "번 테이블에 " << key << " 삽입: 기존의 " << old << " 이동 -> ";
                insert_impl(old, cnt + 1, 2);
            }
        }
        else {
            int hash = hash2(key);
            if (data2[hash] == -1) {
                std::cout << table << "번 테이블에 " << key << " 삽입" << std::endl;
                data2[hash] = key;
            }
            else {
                int old = data2[hash];
                data2[hash] = key;
                std::cout << table << "번 테이블에 " << key << " 삽입: 기존의 " << old << " 이동 -> ";
                insert_impl(old, cnt + 1, 1);
            }
        }
    }

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

        std::cout << "Data1: ";
        for (auto i : data1) {
            std::cout << i << '\t';
        }
        std::cout << std::endl;

        std::cout << "Data2: ";
        for (auto i : data2) {
            std::cout << i << '\t';
        }
        std::cout << std::endl;
    }
};

int main() {
    hash_map map(7);
    map.print();
    std::cout << std::endl;

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

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

    map.print();
    std::cout << std::endl;

    map.insert(14);   // 순환 발생!

    return 0;
}

결과

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 삽입 시 순환 발생! 재해싱이 필요합니다.