Cuckoo Hash Table

Cuckoo Hash Table은 해시 충돌 문제를 해결하기 위해 개발된 해시 테이블의 한 종류로, 두 개 이상의 해시 함수를 사용하여 각 키에 대해 여러 개의 가능한 위치를 제공한다.

특징

  1. 다중 해시 함수: 일반적으로 두 개 이상의 해시 함수를 사용한다.
  2. 결정적 성능: 최악의 경우에도 일정한 시간 복잡도를 보장한다.
  3. 동적 재배치: 충돌 발생 시 기존 항목을 다른 위치로 이동시킨다.

장점

  1. 빠른 검색 속도: O(1) 시간 복잡도로 검색 연산을 수행한다.
  2. 공간 효율성: 높은 로드 팩터를 유지할 수 있다.
  3. 삭제 연산 지원: Bloom Filter와 달리 효율적인 삭제가 가능하다.

단점

  1. 삽입 연산의 복잡성: 최악의 경우 무한 루프에 빠질 수 있어 재해싱이 필요할 수 있다.
  2. 구현의 복잡성: 일반 해시 테이블에 비해 구현이 더 복잡하다.

응용

  1. 데이터베이스 인덱싱
  2. 네트워크 라우팅 테이블
  3. 캐시 시스템
  4. 스팸 필터링

동작 원리

  1. 삽입:

    • 첫 번째 해시 함수로 위치를 계산하여 삽입을 시도한다.
    • 충돌 발생 시, 기존 항목을 두 번째 해시 함수로 계산된 위치로 이동시킨다.
    • 이 과정을 반복하며, 필요시 재해싱을 수행한다.

  2. 검색:

    • 두 개의 해시 함수로 계산된 위치만 확인하면 된다.

  3. 삭제:

    • 두 위치를 확인하여 항목을 찾아 삭제한다.

구성 요소

  1. 해시 테이블: 일반적으로 두 개의 테이블을 사용한다.
  2. 해시 함수: 각 테이블에 대한 별도의 해시 함수를 사용한다.
  3. 키-값 쌍: 저장되는 데이터 단위이다.

구현 방식

Cuckoo Hash Table은 주로 배열을 사용하여 구현된다.
각 배열은 하나의 해시 테이블을 나타내며, 일반적으로 두 개 이상의 배열을 사용한다.

주요 연산들의 동작 과정

  1. 삽입 (insert):

    • 첫 번째 해시 함수로 위치를 계산하여 삽입을 시도한다.
    • 해당 위치가 비어있으면 삽입을 완료한다.
    • 충돌 시, 기존 항목을 두 번째 해시 함수로 계산된 위치로 이동시킨다.
    • 이 과정을 반복하며, 일정 횟수 이상 반복되면 재해싱을 수행한다.

  2. 검색 (lookup):

    • 두 개의 해시 함수로 계산된 위치를 확인한다.
    • 둘 중 하나의 위치에서 키를 찾으면 성공, 아니면 실패이다.

  3. 삭제 (delete):

    • 검색과 동일한 방식으로 항목을 찾는다.
    • 항목을 찾으면 해당 위치의 값을 삭제한다.

예시 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class CuckooHashTable:
    def __init__(self, size):
        self.size = size
        self.table1 = [None] * size
        self.table2 = [None] * size

    def hash1(self, key):
        return hash(key) % self.size

    def hash2(self, key):
        return (hash(key) // self.size) % self.size

    def insert(self, key, value):
        for _ in range(self.size):
            key, value = self._insert_helper(key, value, self.table1, self.hash1)
            if key is None:
                return True
            key, value = self._insert_helper(key, value, self.table2, self.hash2)
            if key is None:
                return True
        return False  # 재해싱 필요

    def _insert_helper(self, key, value, table, hash_func):
        index = hash_func(key)
        if table[index] is None:
            table[index] = (key, value)
            return None, None
        return table[index]

    def lookup(self, key):
        index1 = self.hash1(key)
        if self.table1[index1] and self.table1[index1][0] == key:
            return self.table1[index1][1]
        index2 = self.hash2(key)
        if self.table2[index2] and self.table2[index2][0] == key:
            return self.table2[index2][1]
        return None

    def delete(self, key):
        index1 = self.hash1(key)
        if self.table1[index1] and self.table1[index1][0] == key:
            self.table1[index1] = None
            return True
        index2 = self.hash2(key)
        if self.table2[index2] and self.table2[index2][0] == key:
            self.table2[index2] = None
            return True
        return False

참고 및 출처