Collision resolutions

Collision Resolutions

해시 테이블(Hash Table)은 키(Key)를 해시 함수(Hash Function)에 적용하여 특정 인덱스(Index)에 데이터를 저장하는 자료구조이다.
그러나 서로 다른 키가 같은 해시 인덱스로 매핑되는 경우가 발생할 수 있으며, 이를 충돌(Collision) 이라고 한다.

해시 함수는 임의 크기의 데이터를 고정된 크기의 값으로 매핑한다. 해시 테이블의 크기가 제한되어 있기 때문에, 서로 다른 키들이 같은 해시 값(버킷 인덱스)을 가지는 ‘충돌’이 불가피하게 발생한다. 이는 ‘비둘기집 원리(Pigeonhole Principle)‘에 의해 증명된다 - 가능한 키의 수가 해시 테이블의 크기보다 크면 충돌은 반드시 발생한다.

해시 함수를 hash(key) % 5로 정의하고, 아래 데이터를 저장한다고 가정하자.

1
2
Key1 → hash(Key1) % 5 → Index 2
Key2 → hash(Key2) % 5 → Index 2  (충돌 발생!)

Key1과 Key2가 동일한 인덱스(2)에 저장되려 하면 충돌이 발생한다.

해시 테이블의 충돌 해결 방법은 다양한 상황과 요구사항에 따라 선택할 수 있다. 각 방법은 고유한 장단점을 가지고 있으며, 구현의 복잡성, 메모리 사용량, 성능 특성이 다르다. 응용 프로그램의 특성과 데이터 패턴, 그리고 성능 요구사항을 고려하여 적절한 충돌 해결 방법을 선택하는 것이 중요하다.

최근 연구에서는 여러 기법을 결합한 하이브리드 접근 방식도 등장하고 있으며, 머신 러닝을 활용하여 데이터 패턴에 맞게 해시 함수를 최적화하는 방법도 연구되고 있다.

Collision Resolution (충돌 해결 방법) 개요

충돌이 발생할 경우, 데이터를 올바르게 저장하고 검색할 수 있도록 해결하는 방법이 필요하다.
해시 테이블에서 충돌을 해결하는 방법에는 “체이닝(Chaining)” 과 “오픈 어드레싱(Open Addressing)” 기법이 대표적이다.

충돌 해결 방법

해시 충돌을 해결하기 위한 다양한 기법들을 크게 두 가지 범주로 나눌 수 있다:

체이닝(Chaining)
개방 주소법(Open Addressing)

체이닝(Chaining)

체이닝은 각 해시 버킷에 연결 리스트(linked list)나 다른 자료구조를 사용하여 충돌이 발생한 항목들을 저장하는 방법이다.

작동 방식:

키의 해시 값을 계산한다.
계산된 해시 값(인덱스)에 해당하는 버킷에 키-값 쌍을 저장한다.
충돌이 발생하면, 같은 버킷에 있는 연결 리스트에 새 항목을 추가한다.

구현 예제 (Python):

 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
class HashNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
    
    def _hash(self, key):
        # 간단한 해시 함수
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        
        if self.table[index] is None:
            self.table[index] = HashNode(key, value)
        else:
            # 충돌 발생: 연결 리스트의 시작 부분에 새 노드 추가
            current = self.table[index]
            
            # 이미 존재하는 키라면 값 업데이트
            if current.key == key:
                current.value = value
                return
                
            while current.next:
                if current.next.key == key:
                    current.next.value = value
                    return
                current = current.next
            
            # 새 노드 추가
            current.next = HashNode(key, value)

체이닝의 변형:

단순 연결 리스트(Singly Linked List): 가장 기본적인 구현 방식.
이중 연결 리스트(Doubly Linked List): 양방향 탐색이 가능.
동적 배열(Dynamic Array): 메모리 지역성이 좋아 캐시 효율이 높다.
균형 이진 트리(Balanced Binary Tree): 최악의 경우 검색 시간을 O(log n)으로 보장.
자체 균형 이진 탐색 트리(Self-balancing BST): AVL 트리나 레드-블랙 트리를 사용.

장점:

구현이 간단.
해시 테이블이 절대 가득 차지 않는다(연결 리스트가 계속 확장될 수 있으므로).
삭제 연산이 비교적 간단하다.

단점:

각 노드마다 포인터를 저장해야 하므로 추가 메모리가 필요하다.
연결 리스트가 길어지면 검색 시간이 O(n)까지 증가할 수 있다.
캐시 지역성(cache locality)이 좋지 않을 수 있다.

개방 주소법(Open Addressing)

개방 주소법은 모든 키-값 쌍을 해시 테이블 배열 자체에 직접 저장하는 방법. 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장하다.

주요 탐사(Probing) 방법:

선형 탐사(Linear Probing)

해시 충돌이 발생하면 순차적으로 다음 슬롯을 확인하여 빈 공간을 찾는다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def insert(self, key, value):
    index = self._hash(key)
    
    # 선형 탐사를 사용하여 빈 슬롯 찾기
    original_index = index
    while self.table[index] is not None:
        # 이미 존재하는 키라면 값 업데이트
        if self.table[index].key == key:
            self.table[index].value = value
            return
        
        # 다음 슬롯으로 이동
        index = (index + 1) % self.size
        
        # 테이블이 가득 찼거나 모든 슬롯을 확인한 경우
        if index == original_index:
            raise Exception("해시 테이블이 가득 찼습니다")
    
    # 빈 슬롯에 새 노드 삽입
    self.table[index] = HashNode(key, value)

장점:

캐시 지역성이 좋아 메모리 효율이 높다.
체이닝보다 메모리 오버헤드가 적다.

단점:

‘클러스터링(clustering)’ 현상: 연속된 슬롯이 채워져 충돌 가능성 증가
해시 테이블 로드 팩터(load factor)가 증가하면 성능이 급격히 저하된다.

제곱 탐사(Quadratic Probing)

선형 탐사의 클러스터링 문제를 완화하기 위해, 충돌 발생 시 1², 2², 3², … 간격으로 다음 위치를 탐색한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def insert(self, key, value):
    index = self._hash(key)
    
    original_index = index
    i = 1
    while self.table[index] is not None:
        if self.table[index].key == key:
            self.table[index].value = value
            return
        
        # 제곱 탐사
        index = (original_index + i*i) % self.size
        i += 1
        
        if i >= self.size:
            raise Exception("해시 테이블이 가득 찼거나 순환이 발생했습니다")
    
    self.table[index] = HashNode(key, value)

장점:

선형 탐사보다 클러스터링이 적게 발생.

단점:

여전히 2차 클러스터링(secondary clustering) 문제가 있다.
테이블이 충분히 크지 않으면 모든 슬롯을 탐색하지 못할 수 있다.

이중 해싱(Double Hashing)

충돌 발생 시 두 번째 해시 함수를 사용하여 다음 위치를 결정하는 방법.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def insert(self, key, value):
    index = self._hash1(key)
    
    if self.table[index] is not None and self.table[index].key != key:
        # 충돌 발생: 두 번째 해시 함수 사용
        step = self._hash2(key)
        original_index = index
        
        while True:
            index = (index + step) % self.size
            
            if self.table[index] is None or self.table[index].key == key:
                break
                
            if index == original_index:
                raise Exception("해시 테이블이 가득 찼습니다")
    
    if self.table[index] is not None and self.table[index].key == key:
        self.table[index].value = value
    else:
        self.table[index] = HashNode(key, value)

장점:

클러스터링 문제를 크게 줄일 수 있다.
충돌이 많이 발생하는 경우 더 효율적.

단점:

두 번째 해시 함수 계산으로 인한 추가 비용이 발생.
두 번째 해시 함수는 0을 반환하지 않아야 하며, 테이블 크기와 서로소여야 한다.

로빈 후드 해싱(Robin Hood Hashing)

개방 주소법의 변형으로, ‘부자에게서 빼앗아 가난한 자에게 주는’ 원칙에 기반한다. 각 키의 ‘탐색 거리(probe distance)‘를 기록하고, 새 항목이 기존 항목보다 탐색 거리가 더 길면 자리를 바꾼다.

 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
def insert(self, key, value):
    index = self._hash(key)
    distance = 0
    
    while True:
        if self.table[index] is None:
            # 빈 슬롯에 삽입
            self.table[index] = HashEntry(key, value, distance)
            return
        
        if self.table[index].key == key:
            # 기존 키 업데이트
            self.table[index].value = value
            return
        
        if self.table[index].distance < distance:
            # 로빈 후드: 현재 항목보다 더 멀리 이동한 경우 위치 교환
            entry = HashEntry(key, value, distance)
            entry, self.table[index] = self.table[index], entry
            key, value = entry.key, entry.value
            distance = entry.distance
        
        # 다음 슬롯으로 이동
        index = (index + 1) % self.size
        distance += 1
        
        if distance >= self.size:
            raise Exception("해시 테이블이 가득 찼습니다")

장점:

최악의 경우 검색 시간이 개선.
클러스터링을 효과적으로 관리.

단점:

구현이 더 복잡.
삭제 연산이 까다로울 수 있다.

쿠쿠 해싱(Cuckoo Hashing)

두 개 이상의 해시 함수를 사용하며, 충돌 시 기존 항목을 다른 위치로 강제 이동시키는 방식.

 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
49
50
51
class CuckooHashTable:
    def __init__(self, size):
        self.size = size
        self.table1 = [None] * size
        self.table2 = [None] * size
        self.max_recursion = 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, recursion_depth=0):
        if recursion_depth >= self.max_recursion:
            # 재해싱 필요
            self._rehash()
            self.insert(key, value)
            return
        
        h1 = self._hash1(key)
        
        # 테이블1 확인
        if self.table1[h1] is None:
            self.table1[h1] = (key, value)
            return
        
        if self.table1[h1][0] == key:
            self.table1[h1] = (key, value)  # 업데이트
            return
        
        # 테이블1의 항목을 임시 저장
        old_key, old_value = self.table1[h1]
        self.table1[h1] = (key, value)
        
        # 이전 항목을 테이블2로 이동
        h2 = self._hash2(old_key)
        
        if self.table2[h2] is None:
            self.table2[h2] = (old_key, old_value)
            return
        
        if self.table2[h2][0] == old_key:
            self.table2[h2] = (old_key, old_value)  # 업데이트
            return
        
        # 테이블2의 항목을 다시 테이블1로 이동 (재귀적)
        next_key, next_value = self.table2[h2]
        self.table2[h2] = (old_key, old_value)
        self.insert(next_key, next_value, recursion_depth + 1)

장점:

최악의 경우 조회 시간이 O(1).
높은 로드 팩터에서도 좋은 성능을 유지.

단점:

재해싱이 필요할 수 있으며, 이는 비용이 큰 연산.
해시 함수의 선택이 중요.
로드 팩터는 일반적으로 50% 이하로 유지해야 한다.

점프 해싱(Hopscotch Hashing)

각 키가 자신의 ‘이웃 영역(neighborhood)’ 내에 위치하도록 보장하는 방법. 충돌이 발생하면 이웃 영역 내에서 자리를 바꿔가며 공간을 확보한다.

장점:

높은 로드 팩터에서도 좋은 성능을 유지.
캐시 지역성이 좋다.

단점:

구현이 복잡.
이웃 영역의 크기 선택이 중요.

확장성 관리

해시 테이블이 너무 가득 차면 성능이 저하된다. 이를 관리하기 위한 방법으로는:

재해싱(Rehashing) 로드 팩터가 특정 임계값을 초과하면 더 큰 테이블을 생성하고 모든 항목을 재삽입한다.

1
2
3
4
5
6
7
8
9
def _rehash(self):
    old_size = self.size
    self.size = old_size * 2
    old_table = self.table
    self.table = [None] * self.size

    for i in range(old_size):
        if old_table[i] is not None:
            self.insert(old_table[i].key, old_table[i].value)

점진적 재해싱(Incremental Rehashing) 전체 테이블을 한 번에 재해싱하는 대신, 작은 단위로 나누어 시간을 분산시킨다. Redis와 같은 시스템에서 사용.

해시 함수의 선택

좋은 해시 함수는 충돌을 최소화하기 위해 중요하다.

좋은 해시 함수의 특성:

균등 분포(Uniform Distribution): 키를 해시 테이블 전체에 고르게 분산시킨다.
계산 효율성: 빠르게 계산할 수 있어야 한다.
결정론적(Deterministic): 같은 키는 항상 같은 해시 값을 가져야 한다.
충돌 최소화: 서로 다른 키가 같은 해시 값을 가질 확률을 최소화해야 한다.

널리 사용되는 해시 함수로는:

문자열을 위한 djb2, fnv1a
일반 데이터를 위한 MurmurHash, xxHash
암호화 관련 용도의 SHA-256, Blake2

충돌 해결 방법 비교

해결 방법	장점	단점	적합한 상황	평균 성능	최악 성능
체이닝	구현 간단, 삭제 쉬움, 로드 팩터 제한 없음	추가 메모리 필요, 캐시 지역성 낮음	데이터 크기가 가변적이고 예측 불가능한 경우	O(1 + α)	O(n)
선형 탐사	캐시 지역성 좋음, 메모리 효율적	클러스터링 발생, 삭제 복잡	작은 크기 해시 테이블, 캐시 성능 중요한 경우	O(1/(1-α))	O(n)
제곱 탐사	클러스터링 감소, 구현 간단	2차 클러스터링 존재, 모든 슬롯 탐색 못할 수 있음	중간 크기 테이블, 선형 탐사보다 일관된 성능 필요한 경우	O(1/(1-α))	O(n)
이중 해싱	클러스터링 최소화, 효율적인 공간 활용	두 번째 해시 계산 비용, 구현 복잡	대규모 해시 테이블, 충돌이 많이 예상되는 경우	O(1/(1-α))	O(n)
로빈 후드 해싱	탐색 시간 분산 효과, 최악 케이스 개선	구현 복잡, 삭제 어려움	검색 성능의 일관성이 중요한 경우	O(log n)	O(log n)
쿠쿠 해싱	최악 조회 O(1), 삭제 간단	로드 팩터 제한, 재해싱 필요, 구현 복잡	조회 성능이 중요하고 일정한 경우	O(1)	O(1)*
점프 해싱	높은 로드 팩터에서 좋은 성능, 캐시 지역성	구현 매우 복잡, 튜닝 필요	높은 로드 팩터와 일관된 성능이 필요한 경우	O(1)	O(1)*

*재해싱이 필요한 경우를 제외하고

여기서 α는 로드 팩터(load factor)로, 해시 테이블에 저장된 항목 수를 테이블 크기로 나눈 값.

실제 구현 사례

Java HashMap: 체이닝 방식을 사용하며, 버킷당 항목이 많으면 연결 리스트에서 균형 트리로 전환합니다.
Python dict: 개방 주소법의 변형을 사용합니다.
Redis: 점진적 재해싱을 사용한 체이닝 방식을 구현합니다.
Google’s SwissTable/FlatMap: 로빈 후드 해싱의 변형을 사용합니다.