[CS 기초 #10] 해시 테이블: O(1) 검색의 비밀과 충돌 해결 전략
[CS 기초 #10] 해시 테이블: O(1) 검색의 비밀과 충돌 해결 전략
O(1) 검색의 마법! 해시 테이블은 어떻게 순식간에 데이터를 찾아낼까요?
🎯 이 글을 읽고 나면
- 해시 함수와 해시 테이블의 원리를 이해합니다
- 충돌(Collision) 해결 방법을 설명할 수 있습니다
- O(1) 평균 시간 복잡도의 의미를 안다
- Python의 dict, set이 어떻게 구현되는지 이해합니다
- 캐시, 중복 제거 등 실무 활용법을 알게 됩니다
📚 사전 지식
- 배열 기초: 이전 글: 배열과 연결 리스트
- 시간 복잡도: 복잡도 분석 기본 개념
- 모듈로 연산: 나머지 연산 (%) 이해
💡 핵심 개념 미리보기
해시 테이블은 키를 해시 함수로 변환하여 배열 인덱스로 사용, 평균 O(1)에 데이터를 찾습니다. Python의 dict, JavaScript의 Object, Java의 HashMap이 모두 해시 테이블입니다. 충돌을 체이닝이나 개방 주소법으로 해결하며, 캐시, 중복 제거, 빠른 조회에 필수적입니다!
🔑 들어가며: 해시 테이블은 어디서 사용될까?
데이터베이스 인덱스, 캐시 시스템, 컴파일러 심볼 테이블, 라우팅 테이블… 빠른 검색이 필요한 모든 곳에 해시 테이블이 있습니다!
오늘은 평균 O(1) 시간 복잡도로 검색, 삽입, 삭제를 가능하게 하는 해시 테이블(Hash Table)의 원리와 구현을 깊이 있게 알아보겠습니다. 자료구조편의 마지막 여정입니다!
📊 해시 테이블의 기본 개념
해시 테이블은 키(Key)를 해시 함수(Hash Function)를 통해 인덱스로 변환하여 데이터를 저장하는 자료구조입니다.
graph LR
K[Key: "apple"] --> HF[해시 함수]
HF --> I[Index: 3]
I --> V[Value: "사과"]
subgraph "해시 테이블"
T0[0: empty]
T1[1: "banana" → "바나나"]
T2[2: empty]
T3[3: "apple" → "사과"]
T4[4: "grape" → "포도"]
end
I -.-> T3
해시 테이블의 구성 요소
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
class HashTableComponents:
"""해시 테이블 구성 요소 설명"""
def __init__(self):
self.components = {
"버킷(Bucket)": "데이터가 저장되는 배열의 각 위치",
"해시 함수": "키를 배열 인덱스로 변환하는 함수",
"키(Key)": "데이터를 식별하는 고유 값",
"값(Value)": "키와 연결된 실제 데이터",
"적재율(Load Factor)": "저장된 항목 수 / 버킷 수",
"충돌(Collision)": "서로 다른 키가 같은 인덱스를 가지는 경우",
"재해싱(Rehashing)": "테이블 크기를 조정하고 모든 항목을 재배치"
}
def explain_time_complexity(self):
"""시간 복잡도 설명"""
return {
"평균": {
"검색": "O(1)",
"삽입": "O(1)",
"삭제": "O(1)"
},
"최악": {
"검색": "O(n)",
"삽입": "O(n)",
"삭제": "O(n)"
}
}
components = HashTableComponents()
for term, description in components.components.items():
print(f"• {term}: {description}")
🎯 해시 함수 (Hash Function)
좋은 해시 함수는 키를 균등하게 분산시켜 충돌을 최소화합니다.
다양한 해시 함수 구현
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class HashFunctions:
"""다양한 해시 함수 구현"""
@staticmethod
def division_method(key, table_size):
"""나눗셈 방법: key % table_size"""
if isinstance(key, str):
key = sum(ord(c) for c in key)
return key % table_size
@staticmethod
def multiplication_method(key, table_size):
"""곱셈 방법: floor(table_size * (key * A % 1))"""
if isinstance(key, str):
key = sum(ord(c) for c in key)
A = 0.6180339887 # 황금비 - 1
return int(table_size * ((key * A) % 1))
@staticmethod
def universal_hashing(key, table_size, a, b, p):
"""범용 해싱: ((a * key + b) % p) % table_size"""
if isinstance(key, str):
key = sum(ord(c) for c in key)
return ((a * key + b) % p) % table_size
@staticmethod
def string_hash(s, table_size):
"""문자열 해시 함수 (다항식 롤링 해시)"""
hash_value = 0
prime = 31 # 소수
for i, char in enumerate(s):
hash_value = (hash_value + ord(char) * (prime ** i)) % table_size
return hash_value
@staticmethod
def djb2_hash(s, table_size):
"""DJB2 해시 함수 (문자열에 효과적)"""
hash_value = 5381
for char in s:
hash_value = ((hash_value << 5) + hash_value) + ord(char)
return hash_value % table_size
@staticmethod
def murmur_hash(key, seed=0):
"""MurmurHash (간단한 버전)"""
if isinstance(key, str):
key = key.encode()
h = seed
for byte in key:
h ^= byte
h = (h * 0x5bd1e995) & 0xFFFFFFFF
h ^= h >> 15
return h
# 해시 함수 테스트
hf = HashFunctions()
keys = ["apple", "banana", "grape", "orange", "melon"]
table_size = 10
print("해시 함수 비교:")
print("-" * 60)
print(f"{'Key':<10} {'Division':<10} {'Multiplication':<15} {'DJB2':<10}")
print("-" * 60)
for key in keys:
div = hf.division_method(key, table_size)
mul = hf.multiplication_method(key, table_size)
djb2 = hf.djb2_hash(key, table_size)
print(f"{key:<10} {div:<10} {mul:<15} {djb2:<10}")
💥 충돌 해결 방법
1. 체이닝 (Chaining)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
class HashTableChaining:
"""체이닝으로 충돌을 해결하는 해시 테이블"""
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
self.count = 0
def _hash(self, key):
"""해시 함수"""
if isinstance(key, int):
return key % self.size
elif isinstance(key, str):
return sum(ord(c) for c in key) % self.size
else:
return hash(key) % self.size
def insert(self, key, value):
"""삽입 - 평균 O(1)"""
index = self._hash(key)
bucket = self.table[index]
# 키가 이미 존재하는지 확인
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # 업데이트
return
# 새로운 키-값 쌍 추가
bucket.append((key, value))
self.count += 1
# 적재율 확인 및 재해싱
if self.count > self.size * 0.75:
self._rehash()
def search(self, key):
"""검색 - 평균 O(1)"""
index = self._hash(key)
bucket = self.table[index]
for k, v in bucket:
if k == key:
return v
return None
def delete(self, key):
"""삭제 - 평균 O(1)"""
index = self._hash(key)
bucket = self.table[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
self.count -= 1
return True
return False
def _rehash(self):
"""재해싱 - O(n)"""
old_table = self.table
self.size *= 2
self.table = [[] for _ in range(self.size)]
self.count = 0
for bucket in old_table:
for key, value in bucket:
self.insert(key, value)
print(f"재해싱 완료: 크기 {self.size//2} → {self.size}")
def display(self):
"""테이블 출력"""
print("해시 테이블 (체이닝):")
for i, bucket in enumerate(self.table):
if bucket:
items = " → ".join([f"({k}, {v})" for k, v in bucket])
print(f" [{i}]: {items}")
else:
print(f" [{i}]: empty")
def statistics(self):
"""통계 정보"""
chain_lengths = [len(bucket) for bucket in self.table]
max_chain = max(chain_lengths)
avg_chain = sum(chain_lengths) / len([b for b in chain_lengths if b > 0]) if self.count > 0 else 0
print(f"\n통계:")
print(f" 항목 수: {self.count}")
print(f" 테이블 크기: {self.size}")
print(f" 적재율: {self.count/self.size:.2f}")
print(f" 최대 체인 길이: {max_chain}")
print(f" 평균 체인 길이: {avg_chain:.2f}")
# 체이닝 테스트
ht_chain = HashTableChaining(5)
items = [
("apple", 100), ("banana", 200), ("grape", 300),
("orange", 400), ("melon", 500), ("peach", 600),
("berry", 700), ("lemon", 800)
]
for key, value in items:
ht_chain.insert(key, value)
ht_chain.display()
ht_chain.statistics()
2. 개방 주소법 (Open Addressing)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class HashTableOpenAddressing:
"""개방 주소법으로 충돌을 해결하는 해시 테이블"""
def __init__(self, size=10):
self.size = size
self.keys = [None] * size
self.values = [None] * size
self.deleted = [False] * size # 삭제 표시
self.count = 0
def _hash(self, key):
"""기본 해시 함수"""
if isinstance(key, int):
return key % self.size
elif isinstance(key, str):
return sum(ord(c) for c in key) % self.size
else:
return hash(key) % self.size
def _probe_linear(self, key, i):
"""선형 탐사: h(k, i) = (h(k) + i) % m"""
return (self._hash(key) + i) % self.size
def _probe_quadratic(self, key, i):
"""이차 탐사: h(k, i) = (h(k) + i²) % m"""
return (self._hash(key) + i * i) % self.size
def _probe_double(self, key, i):
"""이중 해싱: h(k, i) = (h1(k) + i * h2(k)) % m"""
h1 = self._hash(key)
h2 = 1 + (key % (self.size - 1)) if isinstance(key, int) else \
1 + (sum(ord(c) for c in key) % (self.size - 1))
return (h1 + i * h2) % self.size
def insert(self, key, value, probe_method="linear"):
"""삽입"""
if self.count >= self.size * 0.7:
self._rehash()
for i in range(self.size):
if probe_method == "linear":
index = self._probe_linear(key, i)
elif probe_method == "quadratic":
index = self._probe_quadratic(key, i)
else: # double
index = self._probe_double(key, i)
if self.keys[index] is None or self.deleted[index] or self.keys[index] == key:
if self.keys[index] != key:
self.count += 1
self.keys[index] = key
self.values[index] = value
self.deleted[index] = False
return True
return False # 테이블이 가득 참
def search(self, key, probe_method="linear"):
"""검색"""
for i in range(self.size):
if probe_method == "linear":
index = self._probe_linear(key, i)
elif probe_method == "quadratic":
index = self._probe_quadratic(key, i)
else:
index = self._probe_double(key, i)
if self.keys[index] is None and not self.deleted[index]:
return None # 키가 없음
if self.keys[index] == key and not self.deleted[index]:
return self.values[index]
return None
def delete(self, key, probe_method="linear"):
"""삭제 (lazy deletion)"""
for i in range(self.size):
if probe_method == "linear":
index = self._probe_linear(key, i)
elif probe_method == "quadratic":
index = self._probe_quadratic(key, i)
else:
index = self._probe_double(key, i)
if self.keys[index] is None and not self.deleted[index]:
return False # 키가 없음
if self.keys[index] == key:
self.deleted[index] = True
self.count -= 1
return True
return False
def _rehash(self):
"""재해싱"""
old_keys = self.keys
old_values = self.values
old_deleted = self.deleted
self.size *= 2
self.keys = [None] * self.size
self.values = [None] * self.size
self.deleted = [False] * self.size
self.count = 0
for i in range(len(old_keys)):
if old_keys[i] is not None and not old_deleted[i]:
self.insert(old_keys[i], old_values[i])
print(f"재해싱 완료: 크기 {self.size//2} → {self.size}")
def display(self):
"""테이블 출력"""
print("해시 테이블 (개방 주소법):")
for i in range(self.size):
if self.keys[i] is not None and not self.deleted[i]:
print(f" [{i}]: {self.keys[i]} → {self.values[i]}")
elif self.deleted[i]:
print(f" [{i}]: DELETED")
else:
print(f" [{i}]: empty")
# 개방 주소법 테스트
ht_open = HashTableOpenAddressing(10)
print("선형 탐사:")
for key, value in items[:5]:
ht_open.insert(key, value, "linear")
ht_open.display()
print("\n이차 탐사:")
ht_open2 = HashTableOpenAddressing(10)
for key, value in items[:5]:
ht_open2.insert(key, value, "quadratic")
ht_open2.display()
🎨 고급 해시 테이블 기법
1. 일관된 해싱 (Consistent 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import hashlib
import bisect
class ConsistentHashing:
"""일관된 해싱 (분산 시스템에서 사용)"""
def __init__(self, nodes=None, virtual_nodes=150):
self.nodes = nodes or []
self.virtual_nodes = virtual_nodes
self.ring = {}
self.sorted_keys = []
for node in self.nodes:
self.add_node(node)
def _hash(self, key):
"""MD5 해시 함수"""
md5 = hashlib.md5()
md5.update(key.encode('utf-8'))
return int(md5.hexdigest(), 16)
def add_node(self, node):
"""노드 추가"""
for i in range(self.virtual_nodes):
virtual_node = f"{node}:{i}"
hash_value = self._hash(virtual_node)
self.ring[hash_value] = node
bisect.insort(self.sorted_keys, hash_value)
def remove_node(self, node):
"""노드 제거"""
for i in range(self.virtual_nodes):
virtual_node = f"{node}:{i}"
hash_value = self._hash(virtual_node)
if hash_value in self.ring:
del self.ring[hash_value]
self.sorted_keys.remove(hash_value)
def get_node(self, key):
"""키에 대한 노드 찾기"""
if not self.ring:
return None
hash_value = self._hash(key)
# 시계 방향으로 가장 가까운 노드 찾기
index = bisect.bisect_right(self.sorted_keys, hash_value)
if index == len(self.sorted_keys):
index = 0
return self.ring[self.sorted_keys[index]]
def distribute_keys(self, keys):
"""키 분산 통계"""
distribution = {}
for key in keys:
node = self.get_node(key)
distribution[node] = distribution.get(node, 0) + 1
return distribution
# 일관된 해싱 테스트
ch = ConsistentHashing(nodes=["Server1", "Server2", "Server3"])
# 데이터 분산
data_keys = [f"data_{i}" for i in range(100)]
distribution = ch.distribute_keys(data_keys)
print("초기 분산:")
for node, count in distribution.items():
print(f" {node}: {count} keys ({count/len(data_keys)*100:.1f}%)")
# 노드 추가
ch.add_node("Server4")
new_distribution = ch.distribute_keys(data_keys)
print("\nServer4 추가 후:")
for node, count in new_distribution.items():
print(f" {node}: {count} keys ({count/len(data_keys)*100:.1f}%)")
# 재분배된 키 계산
moved_keys = 0
for key in data_keys:
old_node = ConsistentHashing(nodes=["Server1", "Server2", "Server3"]).get_node(key)
new_node = ch.get_node(key)
if old_node != new_node:
moved_keys += 1
print(f"\n재분배된 키: {moved_keys}/{len(data_keys)} ({moved_keys/len(data_keys)*100:.1f}%)")
2. 블룸 필터 (Bloom Filter)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import math
import mmh3 # pip install mmh3
class BloomFilter:
"""블룸 필터 (확률적 자료구조)"""
def __init__(self, expected_items, false_positive_rate=0.01):
# 최적 비트 배열 크기
self.size = self._optimal_size(expected_items, false_positive_rate)
# 최적 해시 함수 개수
self.hash_count = self._optimal_hash_count(self.size, expected_items)
# 비트 배열
self.bit_array = [0] * self.size
self.items_count = 0
def _optimal_size(self, n, p):
"""최적 비트 배열 크기 계산"""
m = -(n * math.log(p)) / (math.log(2) ** 2)
return int(m)
def _optimal_hash_count(self, m, n):
"""최적 해시 함수 개수 계산"""
k = (m / n) * math.log(2)
return int(k)
def _hash(self, item, seed):
"""해시 함수"""
return abs(hash(f"{item}{seed}")) % self.size
def add(self, item):
"""항목 추가"""
for i in range(self.hash_count):
index = self._hash(item, i)
self.bit_array[index] = 1
self.items_count += 1
def contains(self, item):
"""항목 포함 여부 확인 (False Positive 가능)"""
for i in range(self.hash_count):
index = self._hash(item, i)
if self.bit_array[index] == 0:
return False # 확실히 없음
return True # 있을 수도 있음
def false_positive_probability(self):
"""현재 False Positive 확률"""
return (1 - math.exp(-self.hash_count * self.items_count / self.size)) ** self.hash_count
def info(self):
"""블룸 필터 정보"""
print(f"블룸 필터 정보:")
print(f" 비트 배열 크기: {self.size}")
print(f" 해시 함수 개수: {self.hash_count}")
print(f" 저장된 항목 수: {self.items_count}")
print(f" False Positive 확률: {self.false_positive_probability():.4f}")
print(f" 메모리 사용량: {self.size / 8 / 1024:.2f} KB")
# 블룸 필터 테스트
bloom = BloomFilter(expected_items=1000, false_positive_rate=0.01)
# 항목 추가
items = ["apple", "banana", "grape", "orange", "melon"]
for item in items:
bloom.add(item)
# 포함 여부 확인
test_items = ["apple", "banana", "kiwi", "mango"]
print("블룸 필터 테스트:")
for item in test_items:
result = bloom.contains(item)
actual = item in items
print(f" {item}: {result} (실제: {actual})")
bloom.info()
💼 실제 응용 사례
1. LRU 캐시
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from collections import OrderedDict
class LRUCache:
"""LRU 캐시 (OrderedDict 활용)"""
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
self.hits = 0
self.misses = 0
def get(self, key):
"""값 조회 - O(1)"""
if key in self.cache:
# 최근 사용으로 이동
self.cache.move_to_end(key)
self.hits += 1
return self.cache[key]
self.misses += 1
return -1
def put(self, key, value):
"""값 저장 - O(1)"""
if key in self.cache:
# 기존 키 업데이트
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
# 가장 오래된 항목 제거
self.cache.popitem(last=False)
def statistics(self):
"""캐시 통계"""
total = self.hits + self.misses
hit_rate = self.hits / total if total > 0 else 0
print(f"캐시 통계:")
print(f" 용량: {self.capacity}")
print(f" 현재 크기: {len(self.cache)}")
print(f" 히트: {self.hits}")
print(f" 미스: {self.misses}")
print(f" 히트율: {hit_rate:.2%}")
# LRU 캐시 테스트
lru = LRUCache(3)
operations = [
("put", 1, "A"),
("put", 2, "B"),
("put", 3, "C"),
("get", 1, None),
("put", 4, "D"),
("get", 2, None),
("get", 3, None),
("get", 4, None),
]
for op in operations:
if op[0] == "put":
lru.put(op[1], op[2])
print(f"PUT({op[1]}, {op[2]})")
else:
result = lru.get(op[1])
print(f"GET({op[1]}) = {result}")
lru.statistics()
2. 단어 빈도 카운터
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
52
53
54
55
56
57
58
59
60
class WordFrequencyCounter:
"""단어 빈도 카운터"""
def __init__(self):
self.word_count = {}
self.total_words = 0
def add_text(self, text):
"""텍스트 추가"""
words = text.lower().split()
for word in words:
# 구두점 제거
word = ''.join(c for c in word if c.isalnum())
if word:
self.word_count[word] = self.word_count.get(word, 0) + 1
self.total_words += 1
def get_frequency(self, word):
"""단어 빈도 조회"""
word = word.lower()
return self.word_count.get(word, 0)
def get_top_words(self, n=10):
"""상위 n개 단어"""
sorted_words = sorted(self.word_count.items(),
key=lambda x: x[1], reverse=True)
return sorted_words[:n]
def get_statistics(self):
"""통계 정보"""
unique_words = len(self.word_count)
avg_frequency = self.total_words / unique_words if unique_words > 0 else 0
return {
"total_words": self.total_words,
"unique_words": unique_words,
"average_frequency": avg_frequency
}
# 단어 빈도 카운터 테스트
counter = WordFrequencyCounter()
text = """
Python is a powerful programming language.
Python is used for web development, data science, and AI.
Many developers love Python because Python is easy to learn.
"""
counter.add_text(text)
print("상위 5개 단어:")
for word, count in counter.get_top_words(5):
print(f" {word}: {count}회")
stats = counter.get_statistics()
print(f"\n통계:")
print(f" 전체 단어 수: {stats['total_words']}")
print(f" 고유 단어 수: {stats['unique_words']}")
print(f" 평균 빈도: {stats['average_frequency']:.2f}")
3. 분산 해시 테이블 (DHT)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class DistributedHashTable:
"""간단한 분산 해시 테이블"""
def __init__(self, nodes):
self.nodes = {}
self.node_count = len(nodes)
# 각 노드에 해시 테이블 생성
for node in nodes:
self.nodes[node] = {}
def _get_node(self, key):
"""키에 대한 노드 결정"""
hash_value = hash(key)
node_index = hash_value % self.node_count
node_names = list(self.nodes.keys())
return node_names[node_index]
def put(self, key, value):
"""분산 저장"""
node = self._get_node(key)
self.nodes[node][key] = value
print(f"PUT {key} → {node}")
def get(self, key):
"""분산 조회"""
node = self._get_node(key)
value = self.nodes[node].get(key)
print(f"GET {key} ← {node}")
return value
def delete(self, key):
"""분산 삭제"""
node = self._get_node(key)
if key in self.nodes[node]:
del self.nodes[node][key]
print(f"DELETE {key} from {node}")
return True
return False
def statistics(self):
"""노드별 통계"""
print("\n노드별 데이터 분포:")
for node, data in self.nodes.items():
print(f" {node}: {len(data)} items")
if data:
print(f" Keys: {list(data.keys())[:5]}...")
# DHT 테스트
dht = DistributedHashTable(["Node1", "Node2", "Node3"])
# 데이터 저장
data = {
"user1": "Alice",
"user2": "Bob",
"user3": "Charlie",
"user4": "David",
"user5": "Eve",
"user6": "Frank"
}
for key, value in data.items():
dht.put(key, value)
dht.statistics()
# 데이터 조회
print("\n데이터 조회:")
for key in ["user1", "user3", "user5"]:
value = dht.get(key)
print(f" {key} = {value}")
💡 성능 분석과 최적화
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import time
import random
import string
class HashTablePerformance:
"""해시 테이블 성능 분석"""
@staticmethod
def generate_random_string(length=10):
"""랜덤 문자열 생성"""
return ''.join(random.choices(string.ascii_letters, k=length))
@staticmethod
def benchmark_operations(hash_table, n=10000):
"""연산 벤치마크"""
keys = [HashTablePerformance.generate_random_string() for _ in range(n)]
values = [random.randint(1, 1000) for _ in range(n)]
# 삽입 벤치마크
start = time.time()
for key, value in zip(keys, values):
hash_table[key] = value
insert_time = time.time() - start
# 검색 벤치마크
search_keys = random.sample(keys, min(1000, n))
start = time.time()
for key in search_keys:
_ = hash_table.get(key)
search_time = time.time() - start
# 삭제 벤치마크
delete_keys = random.sample(keys, min(100, n))
start = time.time()
for key in delete_keys:
if key in hash_table:
del hash_table[key]
delete_time = time.time() - start
return {
"insert": insert_time,
"search": search_time,
"delete": delete_time
}
@staticmethod
def compare_implementations():
"""구현 비교"""
n = 10000
# Python dict
dict_perf = HashTablePerformance.benchmark_operations({}, n)
# 커스텀 체이닝
chain_ht = {}
chain_perf = HashTablePerformance.benchmark_operations(chain_ht, n)
print(f"성능 비교 ({n}개 항목):")
print(f"{'구현':<15} {'삽입(초)':<12} {'검색(초)':<12} {'삭제(초)':<12}")
print("-" * 50)
print(f"{'Python dict':<15} {dict_perf['insert']:<12.6f} "
f"{dict_perf['search']:<12.6f} {dict_perf['delete']:<12.6f}")
print(f"{'Custom Chain':<15} {chain_perf['insert']:<12.6f} "
f"{chain_perf['search']:<12.6f} {chain_perf['delete']:<12.6f}")
# 성능 비교
HashTablePerformance.compare_implementations()
🎯 핵심 정리
꼭 기억해야 할 5가지
- 해시 테이블은 평균 O(1) 검색/삽입/삭제
- 해시 함수의 품질이 성능을 좌우
- 충돌 해결: 체이닝 vs 개방 주소법
- 적재율이 높으면 재해싱 필요
- 일관된 해싱은 분산 시스템에 필수
실무 활용 팁
- 캐시 시스템 → LRU with 해시 테이블
- 중복 검사 → 해시 셋
- 빠른 검색 → 해시 맵
- 분산 저장 → 일관된 해싱
- 확률적 검사 → 블룸 필터
📚 추가 학습 자료
추천 문제
- LeetCode: Two Sum, Group Anagrams, LRU Cache
- 프로그래머스: 완주하지 못한 선수, 전화번호 목록
- 백준: 1620(나는야 포켓몬 마스터), 7785(회사에 있는 사람)
심화 주제
- Cuckoo Hashing
- Robin Hood Hashing
- HyperLogLog
- Count-Min Sketch
🚀 다음 시간 예고
자료구조편이 끝났습니다! 다음 포스트부터는 알고리즘편이 시작됩니다. 복잡도 분석부터 시작하여 정렬, 탐색, 동적 계획법까지 다룰 예정입니다!
📌 시리즈 네비게이션
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.