해시 코드
노트의 개념을 Python 3로 옮긴 코드다. 표준 라이브러리만 쓰고, 파일 끝의 assert 예제가 그대로 실행된다. 복사해 python3 파일이름.py로 돌려 보자.
해시 함수
"""해시 함수: 다항식 해시(31을 곱해 더하기)와 나쁜 해시(첫 글자, 글자 합)의 분포를 비교한다.
시간: 키 길이 L에 대해 O(L)
공간: O(1)
"""
MASK_32 = 0xFFFFFFFF
def polynomial_hash(key: str) -> int:
"""h = h × 31 + 글자 코드를 32비트로 자르며 계산한다."""
value = 0
for char in key:
value = (value * 31 + ord(char)) & MASK_32
return value
def polynomial_steps(key: str) -> list[int]:
"""글자를 하나 읽을 때마다의 h(자르기 전)."""
steps = []
value = 0
for char in key:
value = value * 31 + ord(char)
steps.append(value)
return steps
def first_letter_hash(key: str) -> int:
"""첫 글자만 보는 나쁜 해시."""
return ord(key[0]) if key else 0
def sum_hash(key: str) -> int:
"""글자 코드를 더하기만 하는 나쁜 해시. 글자 순서를 보지 못한다."""
return sum(ord(char) for char in key)
def bucket_counts(keys: list, size: int, hash_function) -> list[int]:
"""키를 hash_function(key) mod size 칸에 나눠 칸마다 개수를 센다."""
counts = [0] * size
for key in keys:
counts[hash_function(key) % size] += 1
return counts
if __name__ == "__main__":
items = [f"item{number}" for number in range(1, 9)]
assert bucket_counts(items, 4, first_letter_hash) == [0, 8, 0, 0]
assert bucket_counts(items, 4, polynomial_hash) == [2, 2, 2, 2]
assert polynomial_steps("abc") == [97, 3105, 96354]
assert polynomial_hash("abc") % 8 == 2
assert polynomial_hash("cab") % 8 == 4
assert sum_hash("abc") == sum_hash("cab") == 294
multiples = list(range(0, 64, 8))
identity = lambda key: key
assert bucket_counts(multiples, 8, identity) == [8, 0, 0, 0, 0, 0, 0, 0]
assert bucket_counts(multiples, 7, identity) == [2, 1, 1, 1, 1, 1, 1]
assert polynomial_hash("") == 0
assert polynomial_hash("x" * 1000) <= MASK_32
print("ok")체이닝
"""체이닝: 칸마다 목록을 매다는 해시 표. 같은 칸에 떨어진 키는 그 목록에 함께 둔다.
시간: 찾기·넣기·지우기 평균 O(1 + α), 최악(모두 한 칸) O(n)
공간: O(n + m) — 키 n개와 칸 m개
"""
class ChainingHashTable:
"""정수 키를 key mod size 칸의 목록에 두는 해시 표. 비교 횟수를 센다."""
def __init__(self, size: int) -> None:
if size <= 0:
raise ValueError("칸 수는 1 이상이다")
self.buckets: list[list[int]] = [[] for _ in range(size)]
self.comparisons = 0
def _bucket(self, key: int) -> list[int]:
return self.buckets[key % len(self.buckets)]
def _scan(self, key: int) -> bool:
"""그 칸의 목록을 훑어 key가 있는지 본다."""
for stored in self._bucket(key):
self.comparisons += 1
if stored == key:
return True
return False
def insert(self, key: int) -> bool:
"""key를 넣는다. 이미 있으면 넣지 않고 False. 충돌했으면 목록 끝에 붙는다."""
if self._scan(key):
return False
self._bucket(key).append(key)
return True
def contains(self, key: int) -> bool:
"""key가 있는지."""
return self._scan(key)
def remove(self, key: int) -> bool:
"""key를 목록에서 뺀다. 없었으면 False."""
bucket = self._bucket(key)
if key not in bucket:
return False
bucket.remove(key)
return True
def load_factor(self) -> float:
"""부하율 α = 키 수 / 칸 수."""
return sum(len(bucket) for bucket in self.buckets) / len(self.buckets)
def comparisons_for(table: ChainingHashTable, key: int) -> int:
"""key를 찾을 때 한 비교 횟수."""
before = table.comparisons
table.contains(key)
return table.comparisons - before
if __name__ == "__main__":
table = ChainingHashTable(5)
for key in [10, 3, 15, 8, 20, 13]:
table.insert(key)
assert table.buckets == [[10, 15, 20], [], [], [3, 8, 13], []]
assert comparisons_for(table, 20) == 3
assert comparisons_for(table, 25) == 3
assert comparisons_for(table, 4) == 0
assert table.load_factor() == 1.2
traced = ChainingHashTable(5)
collisions = 0
for key in [8, 13, 21, 5, 16, 11]:
if traced._bucket(key):
collisions += 1
traced.insert(key)
assert traced.buckets == [[5], [21, 16, 11], [], [8, 13], []]
assert collisions == 3
assert not traced.insert(16)
assert traced.remove(16)
assert not traced.remove(16)
assert traced.buckets[1] == [21, 11]
# 모든 키가 한 칸에 몰리면 넣기의 중복 확인이 n(n - 1) / 2번 비교한다
flooded = ChainingHashTable(5)
for key in range(0, 5 * 1000, 5):
flooded.insert(key)
assert flooded.comparisons == 499_500
print("ok")오픈 어드레싱
"""오픈 어드레싱: 선형 탐사 해시 표. 홈 칸이 차 있으면 옆 칸으로 가고, 지운 칸에는 묘비를 남긴다.
시간: 부하율이 낮으면 평균 O(1), 표가 거의 차면 O(n)
공간: O(m) — 칸 m개 안에 키를 직접 둔다
"""
TOMBSTONE = object()
class LinearProbingTable:
"""정수 키를 key mod size 홈 칸부터 한 칸씩 탐사하는 해시 표."""
def __init__(self, size: int) -> None:
if size <= 0:
raise ValueError("칸 수는 1 이상이다")
self.slots: list = [None] * size
self.last_probes = 0
def _probe(self, key: int) -> tuple[int | None, int | None]:
"""(key가 있는 칸, 넣을 칸)을 찾는다. 빈 칸을 만나면 멈추고, 묘비는 지나간다."""
size = len(self.slots)
first_tombstone = None
self.last_probes = 0
for step in range(size):
index = (key + step) % size
self.last_probes += 1
slot = self.slots[index]
if slot is None:
target = first_tombstone if first_tombstone is not None else index
return None, target
if slot is TOMBSTONE:
if first_tombstone is None:
first_tombstone = index
continue
if slot == key:
return index, None
return None, first_tombstone
def insert(self, key: int) -> int:
"""key를 넣고 앉은 칸을 돌려준다. 이미 있으면 그 칸."""
found, target = self._probe(key)
if found is not None:
return found
if target is None:
raise OverflowError("표가 가득 찼다")
self.slots[target] = key
return target
def find(self, key: int) -> int | None:
"""key가 있는 칸. 없으면 None."""
return self._probe(key)[0]
def delete(self, key: int) -> bool:
"""key의 칸에 묘비를 세운다. 비우면 뒤에 밀려 앉은 키를 못 찾는다."""
found = self.find(key)
if found is None:
return False
self.slots[found] = TOMBSTONE
return True
def view(self) -> list:
"""묘비를 'X'로 바꾼 칸 목록."""
return ["X" if slot is TOMBSTONE else slot for slot in self.slots]
if __name__ == "__main__":
table = LinearProbingTable(7)
for key in [3, 10, 17]:
table.insert(key)
assert table.view() == [None, None, None, 3, 10, 17, None]
table.delete(10)
assert table.find(17) == 5
# 묘비 대신 칸을 그냥 비우면 17을 못 찾는다
table.slots[4] = None
assert table.find(17) is None
traced = LinearProbingTable(7)
for key in [5, 12, 19, 6]:
traced.insert(key)
assert traced.view() == [19, 6, None, None, None, 5, 12]
assert traced.delete(12)
assert traced.find(19) == 0
assert traced.last_probes == 3
assert traced.insert(26) == 6
assert traced.last_probes == 5
assert traced.view() == [19, 6, None, None, None, 5, 26]
assert not traced.delete(40)
# 덩어리(2~6번 칸) 뒤의 7번 칸에는 홈 칸 10개 중 6개가 모인다
clustered = LinearProbingTable(10)
for key in [12, 22, 14, 23, 6]:
clustered.insert(key)
# 표에 없는 키 100 + home으로 홈 칸마다 어디에 앉을지 본다
landing = [clustered._probe(100 + home)[1] for home in range(10)]
assert landing.count(7) == 6
full = LinearProbingTable(2)
full.insert(1)
full.insert(2)
try:
full.insert(3)
raise AssertionError("가득 찬 표는 넣기를 거부해야 한다")
except OverflowError:
pass
print("ok")부하율과 재해시
"""부하율과 재해시: 선형 탐사의 기대 탐사 수, 큰 표로 다시 넣기, 두 배씩 키울 때 옮기는 키의 총수.
시간: 재해시 한 번 O(n), 두 배씩 키우면 넣기 한 번의 분할 상환 O(1)
공간: O(n) — 재해시하는 동안은 옛 표와 새 표가 함께 있다
"""
def expected_probes(load_factor: float) -> tuple[float, float]:
"""선형 탐사에서 (있는 키, 없는 키)를 찾을 때의 기대 탐사 수(Knuth의 근사식)."""
if not 0 <= load_factor < 1:
raise ValueError("부하율은 0 이상 1 미만이다")
hit = 0.5 * (1 + 1 / (1 - load_factor))
miss = 0.5 * (1 + 1 / (1 - load_factor) ** 2)
return hit, miss
def probe_insert(slots: list, key: int) -> int:
"""선형 탐사로 key를 넣고 앉은 칸을 돌려준다."""
size = len(slots)
for step in range(size):
index = (key + step) % size
if slots[index] is None:
slots[index] = key
return index
raise OverflowError("표가 가득 찼다")
def build(keys: list[int], size: int) -> list:
"""keys를 차례로 넣은 크기 size의 표."""
slots: list = [None] * size
for key in keys:
probe_insert(slots, key)
return slots
def rehash(slots: list, new_size: int) -> list:
"""옛 표를 0번 칸부터 읽어 크기 new_size의 새 표에 다시 넣는다."""
return build([key for key in slots if key is not None], new_size)
def displaced(slots: list) -> list[int]:
"""홈 칸이 아닌 칸에 앉은 키."""
return [key for index, key in enumerate(slots) if key is not None and key % len(slots) != index]
def growth_moves(inserts: int, initial_size: int = 8, max_load: float = 0.75) -> tuple[int, int]:
"""넣은 뒤 부하율이 max_load를 넘을 넣기 직전에 두 배로 키울 때 (재해시 수, 옮긴 키 수)."""
size = initial_size
count = 0
rehashes = 0
moves = 0
for _ in range(inserts):
if count + 1 > max_load * size:
rehashes += 1
moves += count
size *= 2
count += 1
return rehashes, moves
if __name__ == "__main__":
assert expected_probes(0.5) == (1.5, 2.5)
assert expected_probes(0.75) == (2.5, 8.5)
hit, miss = expected_probes(0.375)
assert round(hit, 2) == 1.3
assert round(miss, 2) == 1.78
try:
expected_probes(1.0)
raise AssertionError("부하율 1은 계산할 수 없다")
except ValueError:
pass
small = build([5, 12, 19, 26], 7)
assert small == [19, 26, None, None, None, 5, 12]
assert displaced(small) == [19, 26, 12]
large = rehash(small, 14)
assert [index for index, key in enumerate(large) if key is not None] == [5, 6, 12, 13]
assert large[5] == 19 and large[12] == 26
assert displaced(large) == [5, 12]
assert growth_moves(100) == (5, 186)
assert growth_moves(6) == (0, 0)
for inserts in (10, 1000, 100_000):
assert growth_moves(inserts)[1] < 2 * inserts
print("ok")블룸 필터
"""블룸 필터: 비트 m개와 해시 k개로 "확실히 없음"과 "아마 있음"을 답한다. 거짓 음성은 없다.
시간: 넣기·묻기 O(k)
공간: O(m) 비트 — 키 길이와 상관없다. 1% 거짓 양성에 키당 약 9.6비트
"""
import hashlib
import math
class BloomFilter:
"""비트 bits개, 해시 hash_count개짜리 블룸 필터. 이중 해싱 h1 + i·h2로 자리를 고른다."""
def __init__(self, bits: int, hash_count: int) -> None:
if bits <= 0 or hash_count <= 0:
raise ValueError("비트 수와 해시 수는 1 이상이다")
self.bits = [False] * bits
self.hash_count = hash_count
def positions(self, key: str) -> list[int]:
"""key가 켜는 비트 자리 k개."""
digest = hashlib.sha256(key.encode("utf-8")).digest()
first = int.from_bytes(digest[:8], "big")
# 두 번째 해시를 홀수로 만들어 자리가 한곳에 고이지 않게 한다
second = int.from_bytes(digest[8:16], "big") | 1
return [(first + index * second) % len(self.bits) for index in range(self.hash_count)]
def add(self, key: str) -> None:
"""key의 비트를 모두 켠다."""
for position in self.positions(key):
self.bits[position] = True
def might_contain(self, key: str) -> bool:
"""False면 확실히 없다. True면 아마 있다."""
return all(self.bits[position] for position in self.positions(key))
def query_bits(bits: list[bool], positions: list[int]) -> bool:
"""주어진 자리가 모두 켜졌는지(아마 있음)."""
return all(bits[position] for position in positions)
def false_positive_rate(bits: int, hash_count: int, items: int) -> float:
"""거짓 양성 확률 근사 (1 - e^(-kn/m))^k."""
return (1 - math.exp(-hash_count * items / bits)) ** hash_count
def optimal_size(items: int, rate: float) -> tuple[int, int]:
"""목표 거짓 양성률에 필요한 (비트 수, 해시 수)."""
bits = math.ceil(-items * math.log(rate) / math.log(2) ** 2)
hash_count = round(bits / items * math.log(2))
return bits, hash_count
if __name__ == "__main__":
# 문제 1의 손 계산: x는 1, 4, 7, y는 2, 4, 9
manual = [False] * 10
for position in [1, 4, 7, 2, 4, 9]:
manual[position] = True
assert query_bits(manual, [1, 2, 7])
assert not query_bits(manual, [3, 4, 9])
for position in [1, 4, 7]:
manual[position] = False
assert not query_bits(manual, [2, 4, 9]), "x를 지우면 y가 거짓 음성이 된다"
animals = BloomFilter(1024, 7)
added = [f"animal-{number}" for number in range(100)]
for key in added:
animals.add(key)
assert all(animals.might_contain(key) for key in added)
misses = sum(animals.might_contain(f"other-{number}") for number in range(10_000))
assert misses < 10_000 * 0.05
assert [round(100 * false_positive_rate(10, k, 1), 2) for k in range(1, 9)] == [
9.52, 3.29, 1.74, 1.18, 0.94, 0.84, 0.82, 0.85,
]
assert optimal_size(1_000_000, 0.01) == (9_585_059, 7)
try:
BloomFilter(0, 3)
raise AssertionError("비트 0개 필터는 만들 수 없다")
except ValueError:
pass
print("ok")