해시 테이블 - 딕셔너리는 어떻게 빠른가
이 장에서 배우는 것
앞 장에서 만든 스택과 큐는 데이터를 넣은 순서에 따라 꺼낼 위치가 정해졌다. 이번에는 순서 대신 이름으로 데이터를 찾는다. 과제 번호로 제출 점수를 찾거나 설정 이름으로 값을 꺼낼 때처럼, 키를 주면 그 키에 연결된 값을 돌려주는 구조를 만든다. 《논리로 푸는 알고리즘》이 자료구조를 이용해 문제를 푸는 쪽이라면, 이 책은 그 자료구조 안에서 어떤 일이 일어나는지 직접 만드는 쪽에 초점을 둔다.
파이썬 딕셔너리의 빠른 조회를 이해하려면 이름을 배열 위치로 바꾸는 과정부터 살펴봐야 한다. 서로 다른 이름이 같은 위치를 가리킬 때도 데이터가 사라지지 않아야 하며, 데이터가 늘면 저장 공간도 다시 배치해야 한다. 이번 장의 완성 코드는 이 세 가지 일을 수행하고, 각 연산이 조사한 키의 개수까지 출력한다.
- 키를 정수로 바꾸는 해시 함수와 배열 위치를 정하는 나머지 연산을 구분한다.
- 충돌을 연결 구조로 처리하는 체이닝과 배열 안에서 처리하는 개방 주소를 설명한다.
- 적재율을 계산하고, 배열을 늘릴 때 기존 항목을 다시 배치한다.
- 조회·삽입·수정·삭제의 실제 연산 횟수와 시간 복잡도를 연결한다.
- 직접 만든 구현과 내장 딕셔너리의 결과를 비교하고, 비교할 수 없는 내부 비용도 구별한다.
문제 상황
자료구조 구현 과제를 제출하는 작은 연습 도구를 만든다고 가정한다. 도구는 제출 코드에 붙인 문자열 식별자로 점수를 저장한다. 식별자와 점수를 배열에 차례로 넣고 조회할 때마다 처음부터 찾을 수도 있다. 그러나 제출 기록이 늘면 마지막 기록을 찾기 위해 앞의 기록을 모두 확인해야 한다. 없는 식별자를 조회할 때는 배열 끝까지 가야 한다.
원하는 동작은 단순하다. 같은 식별자로 점수를 다시 저장하면 기존 점수가 바뀐다. 처음 보는 식별자라면 항목이 하나 늘어난다. 삭제한 식별자는 더 이상 조회되지 않는다. 저장 순서는 이번 구현의 요구사항에 포함하지 않는다. 키는 문자열로 제한하며, 값에는 별도의 자료형 제한을 두지 않는다.
이처럼 키와 값의 연결을 저장하는 자료구조를 전공 수업에서는 맵 또는 사전이라 부른다. 해시 테이블(hash table)은 이 동작을 구현하는 한 방법이다. 모든 키를 차례로 확인하는 대신, 키로부터 조사할 위치를 계산한다. 다만 계산한 위치가 항상 하나의 항목만 가리킨다고 가정해서는 안 된다. 그 가정을 깨는 작은 입력부터 만들어 볼 것이다.
키를 배열 위치로 바꾸기
해시 함수(hash function)는 키를 정수로 바꾸는 함수다. 여기서는 문자열을 왼쪽부터 읽으며 누적값에 31을 곱하고 현재 문자의 번호를 더한다. 문자 번호는 파이썬의 ord로 얻는다. 이렇게 얻은 정수 전체를 배열 인덱스로 쓰지는 않는다. 배열 길이로 나눈 나머지를 최종 위치로 쓴다.
수식으로 쓰면 다음과 같다. 시작값 h = 0이며, 문자를 하나 읽을 때마다 h = (h × 31 + 문자 번호) % 2의 32제곱으로 바꾼다. 마지막에 인덱스 = h % 배열 길이를 계산한다. 매 단계에서 나머지를 취하는 이유는 누적 정수가 문자열 길이에 따라 계속 커지는 일을 막기 위해서다. 이 예제의 계산 규칙은 학습을 위해 정한 것이며 보안 용도로 설계한 함수가 아니다.
문자 순서를 반영하는지도 확인해야 한다. 문자 번호를 더하기만 하면 "ab"와 "ba"의 결과가 같다. 이번 함수에서는 "ab"가 3105, "ba"가 3135가 된다. 완성 코드의 첫 출력에서 이 값을 확인한다. 입력이 같으면 결과도 같다. 서로 다른 입력의 결과가 항상 다를 필요는 없다.
| 키 | 해시값 | 길이 4의 위치 | 길이 8의 위치 |
|---|---|---|---|
| "a" | 97 | 1 | 1 |
| "e" | 101 | 1 | 5 |
| "i" | 105 | 1 | 1 |
표에서 세 키는 길이가 4인 배열의 같은 위치로 간다. 서로 다른 키가 같은 저장 위치를 가리키는 일을 전공 수업에서는 충돌(collision)이라 부른다. 해시값 자체가 달라도 나머지가 같으면 충돌한다. 저장할 키의 수에 비해 배열의 칸 수가 제한되어 있으므로, 충돌은 구현에서 처리해야 할 정상적인 상황이다.
이번 프로그램은 실행할 때마다 같은 출력을 얻기 위해 직접 정의한 해시 함수를 쓴다. 내장 hash의 문자열 결과에 출력값을 의존하지 않는다. 난수도 사용하지 않으므로 고정할 난수 시드가 없다. 통계에서 해시 문자 수는 함수가 읽은 문자 수다. 따라서 길이가 L인 문자열의 해시 계산에는 L번의 문자 처리가 필요하다.
충돌을 처리하는 두 가지 방법
체이닝: 같은 위치에 연결하기
배열의 각 칸에 항목을 하나만 저장하는 대신, 같은 위치로 가는 항목들의 첫 노드를 저장할 수 있다. 노드는 키, 값, 다음 노드 참조를 묶은 작은 객체다. 전공 수업에서는 이 방법을 체이닝(chaining)이라 부른다. 배열에서 연결 구조의 시작을 보관하는 칸은 버킷(bucket)이라 부른다.
파이썬에서 다음 노드 참조를 보관한다는 말은 다른 노드 객체를 가리키는 값을 속성에 넣는다는 뜻이다. 메모리 주소를 직접 계산할 필요는 없다. 빈 버킷과 연결의 끝은 None으로 표시한다. 새 키는 해당 버킷의 맨 앞에 연결한다. 기존 키라면 새 노드를 만들지 않고 값을 바꾼다.
그림은 "a", "e", "i" 순서로 넣은 뒤의 상태다. 맨 앞에 추가하므로 연결 순서는 "i", "e", "a"다. "a"를 조회하면 세 키를 비교한다. "i"는 한 번만 비교하면 된다. 같은 버킷에 들어간다는 사실은 키가 같다는 뜻이 아니므로, 연결을 따라가며 실제 문자열이 같은지 확인해야 한다.
완성 코드의 키 비교 수는 이 문자열 동등성 검사를 수행한 횟수다. 문자열 비교 한 번이 항상 같은 시간인 것은 아니다. 긴 문자열 두 개가 끝부분에서 다르면 여러 문자를 확인할 수 있다. 따라서 이 통계는 문자열 내부의 문자 비교 수나 실행 시간을 나타내지 않는다. 구조가 몇 개의 후보 키를 조사했는지를 나타낸다.
개방 주소: 배열 안에서 다른 칸 찾기
노드를 연결하지 않고 배열 안에서 다음 후보 칸을 찾는 방법도 있다. 전공 수업에서는 개방 주소(open addressing)라 부른다. 충돌한 위치의 바로 다음 칸부터 차례로 조사하는 방식은 선형 조사(linear probing)다. 배열 끝을 만나면 나머지 연산으로 처음 칸으로 돌아온다.
길이가 4인 배열에 "a", "e", "i"를 넣으면 세 키의 시작 위치는 모두 1이다. "a"는 1번, "e"는 2번, "i"는 3번 칸에 들어간다. 이때 "e"를 삭제하면서 2번 칸을 처음부터 비어 있던 칸처럼 만들면 문제가 생긴다. "i"를 찾는 조회가 2번 칸에서 멈춰 버릴 수 있기 때문이다.
그래서 삭제된 칸에는 검색을 계속하라는 별도의 표시를 남긴다. 전공 수업에서는 이를 삭제 표식 또는 툼스톤(tombstone)이라 부른다. 완성 코드의 작은 실험에서는 서로 다른 객체 하나를 이 표식으로 사용한다. 표식은 삽입할 때 재사용할 수 있지만, 조회할 때는 연결된 조사 경로가 끝났다는 뜻으로 해석하면 안 된다.
실험은 삭제 후 "i"를 찾을 때 1번의 "a", 2번의 삭제 표식, 3번의 "i"까지 세 칸을 조사했음을 출력한다. 이 칸 조사 수는 체이닝의 키 비교 수와 다른 측정값이다. 표식을 본 것도 한 칸을 조사한 것으로 센다. 실험의 조사 반복은 배열 길이까지만 수행하므로 빈칸이 없어도 끝난다. 개방 주소 전체 구현에는 갱신, 삭제 표식 재사용, 확장 정책이 더 필요하다. 이 장의 완성 자료구조는 체이닝이며, 개방 주소 코드는 삭제 후 탐색 원리를 확인하는 실험이다.
적재율과 다시 배치하는 비용
항목이 늘어도 버킷 수가 그대로라면 연결이 길어진다. 저장한 항목 수를 버킷 수로 나눈 값을 전공 수업에서는 적재율(load factor)이라 부른다. 항목 수를 n, 버킷 수를 m이라고 쓰면 적재율은 n / m이다. 체이닝에서는 한 버킷에 여러 항목을 연결하므로 적재율이 1보다 클 수도 있다.
이번 구현은 새 항목을 넣었을 때 적재율이 0.75를 넘으면 버킷 수를 두 배로 늘린다. 정확히 0.75이면 늘리지 않는다. 소수 계산 대신 (n + 1) × 4 > m × 3을 검사한다. 길이 4에서 항목 세 개까지는 유지하고 네 번째 새 키를 넣기 직전에 길이 8로 바꾼다. 이미 있는 키의 값만 수정하면 항목 수가 늘지 않으므로 이 검사를 하지 않는다.
버킷 배열만 길게 만든다고 작업이 끝나지는 않는다. 표의 "e"는 길이 4에서는 1번, 길이 8에서는 5번으로 가야 한다. 기존 항목을 새 크기에 맞게 다시 배치하는 작업을 전공 수업에서는 재해시(rehash)라 부른다. 이 구현은 노드에 원래 해시값을 저장해 두므로 재배치할 때 문자열을 다시 읽지는 않는다. 저장된 해시값을 새 길이로 나눈다.
재해시 중에는 다음 노드 참조를 먼저 따로 보관한다. 새 버킷에 연결하면서 현재 노드의 next를 바꾸기 때문이다. 원래 연결의 다음 위치를 잃으면 아직 옮기지 않은 노드까지 도달할 수 없다. 재해시 횟수는 배열을 교체한 횟수이고, 이동 수는 그 과정에서 새 버킷에 연결한 노드 수다. 사용자 삽입의 충돌 수와는 별도로 센다.
확장을 일으킨 삽입은 기존 n개 항목을 모두 옮기므로 그 한 번에 O(n + m) 작업이 들 수 있다. 다만 용량을 두 배씩 늘리면 여러 삽입에 걸쳐 발생한 재배치 비용을 나누어 볼 수 있다. 이런 분석을 전공 수업에서는 분할 상환 분석(amortized analysis)이라 부른다. 해시값이 고르게 퍼지고 키 길이를 일정하게 보면 삽입의 평균적인 분할 상환 비용은 O(1)로 설명한다. 모든 키가 한 버킷에 모이는 경우까지 O(1)이라는 뜻은 아니다.
완성 코드
다음 내용을 main.py로 저장한다. 내부 버킷과 실험 저장소는 고정 크기 리스트를 배열처럼 사용한다. append나 리스트를 이용한 버킷별 수집은 사용하지 않는다. 딕셔너리는 직접 구현의 실행을 마친 뒤 결과를 대조하는 부분에서만 사용한다. 연산 기록을 묶은 튜플은 실험 입력이며 해시 테이블의 저장 구조가 아니다.
MODULUS = 2 ** 32
def hash_text(key):
if not isinstance(key, str):
raise TypeError("키는 문자열이어야 한다")
value = 0
for char in key:
value = (value * 31 + ord(char)) % MODULUS
return value
class Node:
def __init__(self, key, value, code, next_node=None):
self.key = key
self.value = value
self.code = code
self.next = next_node
class HashTable:
def __init__(self, capacity=4):
if type(capacity) is not int or capacity < 1:
raise ValueError("용량은 양의 정수여야 한다")
self.buckets = [None] * capacity
self.size = 0
self.hash_chars = 0
self.comparisons = 0
self.collisions = 0
self.rehashes = 0
self.moves = 0
def _hash(self, key):
code = hash_text(key)
self.hash_chars += len(key)
return code
def _find(self, index, key):
node = self.buckets[index]
while node is not None:
self.comparisons += 1
if node.key == key:
return node
node = node.next
return None
def _rehash(self):
old = self.buckets
new = [None] * (len(old) * 2)
for head in old:
node = head
while node is not None:
following = node.next
index = node.code % len(new)
node.next = new[index]
new[index] = node
self.moves += 1
node = following
self.buckets = new
self.rehashes += 1
def put(self, key, value):
code = self._hash(key)
index = code % len(self.buckets)
node = self._find(index, key)
if node is not None:
node.value = value
return False
if (self.size + 1) * 4 > len(self.buckets) * 3:
self._rehash()
index = code % len(self.buckets)
if self.buckets[index] is not None:
self.collisions += 1
self.buckets[index] = Node(
key, value, code, self.buckets[index]
)
self.size += 1
return True
def get(self, key, default=None):
code = self._hash(key)
index = code % len(self.buckets)
node = self._find(index, key)
if node is None:
return default
return node.value
def delete(self, key):
code = self._hash(key)
index = code % len(self.buckets)
previous = None
node = self.buckets[index]
while node is not None:
self.comparisons += 1
if node.key == key:
if previous is None:
self.buckets[index] = node.next
else:
previous.next = node.next
self.size -= 1
return True
previous = node
node = node.next
return False
def probing_demo():
empty = None
deleted = object()
slots = [empty] * 4
for key in ("a", "e", "i"):
start = hash_text(key) % len(slots)
for offset in range(len(slots)):
index = (start + offset) % len(slots)
if slots[index] is empty:
slots[index] = key
break
else:
raise RuntimeError("빈칸이 없다")
# 위 삽입 결과에서 "e"가 있는 칸을 삭제한다.
slots[2] = deleted
inspected = 0
found = False
start = hash_text("i") % len(slots)
for offset in range(len(slots)):
index = (start + offset) % len(slots)
inspected += 1
item = slots[index]
if item is empty:
break
if item is deleted:
continue
if item == "i":
found = True
break
print(f"개방 주소: i 발견={found}, 조사 칸={inspected}")
def apply_custom(table, action, key, value):
if action == "put":
return table.put(key, value)
if action == "get":
return table.get(key, "-")
return table.delete(key)
def apply_builtin(table, action, key, value):
if action == "put":
is_new = key not in table
table[key] = value
return is_new
if action == "get":
return table.get(key, "-")
if key in table:
del table[key]
return True
return False
def main():
print(f"해시: ab={hash_text('ab')}, ba={hash_text('ba')}")
probing_demo()
operations = (
("put", "a", 10),
("put", "e", 20),
("put", "i", 30),
("put", "b", 40),
("get", "a", None),
("get", "i", None),
("get", "z", None),
("put", "e", 50),
("delete", "i", None),
("delete", "x", None),
)
table = HashTable()
results = [None] * len(operations)
for index, (action, key, value) in enumerate(operations):
before_hash = table.hash_chars
before_compare = table.comparisons
result = apply_custom(table, action, key, value)
results[index] = result
hash_count = table.hash_chars - before_hash
compare_count = table.comparisons - before_compare
print(
f"{action} {key}: {result}, "
f"해시 문자={hash_count}, 키 비교={compare_count}"
)
print(f"항목={table.size}, 버킷={len(table.buckets)}")
print(
f"누적: 해시 문자={table.hash_chars}, "
f"키 비교={table.comparisons}, 충돌 삽입={table.collisions}, "
f"재해시={table.rehashes}, 이동={table.moves}"
)
# 직접 구현의 실행을 마친 뒤 내장 구현과 대조한다.
reference = {}
same = True
for index, (action, key, value) in enumerate(operations):
result = apply_builtin(reference, action, key, value)
if result != results[index]:
same = False
if len(reference) != table.size:
same = False
for key in ("a", "e", "i", "b", "z", "x"):
if table.get(key, "-") != reference.get(key, "-"):
same = False
print(f"내장 dict와 결과 일치={same}")
print(f"논리 연산: 직접={len(operations)}, 내장={len(operations)}")
print("내장 dict의 내부 키 비교 수: 이 프로그램에서 측정하지 않음")
if __name__ == "__main__":
main()
줄별 해설
MODULUS와 hash_text는 문자열을 정수로 바꾸는 부분이다. 문자열이 아니면 예외를 발생시켜 사용 조건을 명확히 한다. 예외는 정상적인 반환값 대신 잘못된 사용을 알리는 신호다. 빈 문자열은 반복문을 한 번도 실행하지 않아 해시값 0을 얻는다. 이 값도 유효한 해시값이다.
Node.__init__는 키와 값 외에 해시값인 code와 다음 노드 참조인 next를 저장한다. 키는 새 값을 대입해 바꾸지 않는다. 키가 바뀌면 저장된 해시값 및 버킷 위치와 실제 키가 어긋난다. 값은 위치 계산에 참여하지 않으므로 수정할 수 있다.
HashTable.__init__의 [None] * capacity는 정해진 개수의 빈 버킷을 만든다. 각 칸의 None은 변경 가능한 공유 컨테이너가 아니므로 같은 연결 구조가 여러 칸에 생기지 않는다. size는 실제 항목 수이며 배열 길이와 구분한다. 뒤따르는 다섯 속성은 문자 처리, 키 비교, 충돌 삽입, 재해시, 이동을 각각 기록한다.
_hash와 _find의 이름 앞 밑줄은 클래스 내부에서 사용할 의도라는 관례다. 접근 자체를 금지하지는 않는다. _hash는 유효한 문자열의 해시 계산이 끝나면 그 길이를 누적한다. _find는 버킷의 첫 노드부터 시작해 키를 비교할 때마다 카운터를 하나 늘린다. 빈 버킷에서는 키 비교가 발생하지 않는다.
_rehash는 기존 배열을 old에 보관하고 두 배 크기의 배열을 만든다. 각 노드에서 following = node.next를 먼저 실행한 다음 연결을 바꾼다. 이동한 노드 수만 늘리고 항목 수는 유지한다. 이 과정은 기존 키의 존재를 다시 검사하지 않으므로 사용자 조회의 키 비교 수에 포함하지 않는다. 함수가 끝난 뒤에는 노드의 상대적인 연결 순서가 바뀔 수 있다.
put은 먼저 기존 키를 찾는다. 발견하면 값만 바꾸고 False를 반환한다. 이 반환값은 실패가 아니라 새 항목을 만들지 않았다는 뜻이다. 새 키인 경우에만 확장 조건을 검사한다. 재해시 후에는 배열 길이가 바뀌었으므로 삽입할 인덱스를 다시 계산한다. 마지막으로 현재 버킷의 첫 노드를 새 노드의 다음 노드로 연결한다.
collisions는 새 항목을 실제로 연결하는 시점에 그 버킷이 비어 있지 않으면 한 번 증가한다. 기존 키 수정, 재해시 중 노드 연결, 조회 실패는 이 수에 포함하지 않는다. 충돌의 통계 정의는 구현마다 다를 수 있으므로 숫자를 비교하기 전에 무엇을 세는지 정해야 한다. 여기서는 충돌한 키 쌍의 수를 세지 않는다.
get은 찾은 값이나 기본값을 반환한다. 값으로 None을 저장하는 것도 허용하므로, 기본값 None만 보고 키의 존재 여부를 일반적으로 판정할 수는 없다. delete는 현재 노드와 앞 노드를 함께 따라간다. 첫 노드를 지울 때는 버킷의 시작을 바꾸고, 그 밖의 노드를 지울 때는 앞 노드가 다음 노드를 건너뛰게 한다. 실제로 삭제했을 때만 항목 수가 줄어든다.
probing_demo의 object()는 다른 값과 구분할 삭제 표식을 만든다. is는 값이 같은지가 아니라 같은 객체인지를 검사한다. 2번 칸 삭제는 앞서 정해진 세 키의 배치를 확인하는 실험용 동작이다. 일반적인 삭제 함수처럼 임의의 키를 검색하는 코드는 아니다.
main은 각 연산 전후의 카운터 차이를 출력한다. 네 번째 삽입에서는 키 비교가 0이어도 노드 세 개를 옮긴다. 따라서 비교 횟수 하나만으로 전체 작업량을 판단하면 안 된다. 마지막 검증은 각 연산의 반환값과 최종 조회 결과를 모두 비교한다. 검증 조회도 직접 구현의 카운터를 늘리지만, 누적 통계는 그 전에 출력하여 실험의 열 번 연산과 분리한다.
실행 결과
macOS 또는 Linux의 터미널에서 다음과 같이 실행한다. 외부 패키지나 입력 파일은 필요하지 않다.
python3 main.py
예상 출력은 다음과 같다.
해시: ab=3105, ba=3135
개방 주소: i 발견=True, 조사 칸=3
put a: True, 해시 문자=1, 키 비교=0
put e: True, 해시 문자=1, 키 비교=1
put i: True, 해시 문자=1, 키 비교=2
put b: True, 해시 문자=1, 키 비교=0
get a: 10, 해시 문자=1, 키 비교=1
get i: 30, 해시 문자=1, 키 비교=2
get z: -, 해시 문자=1, 키 비교=1
put e: False, 해시 문자=1, 키 비교=1
delete i: True, 해시 문자=1, 키 비교=2
delete x: False, 해시 문자=1, 키 비교=0
항목=3, 버킷=8
누적: 해시 문자=10, 키 비교=10, 충돌 삽입=2, 재해시=1, 이동=3
내장 dict와 결과 일치=True
논리 연산: 직접=10, 내장=10
내장 dict의 내부 키 비교 수: 이 프로그램에서 측정하지 않음
세 번째 삽입까지 키 비교 수는 0, 1, 2로 증가한다. 같은 버킷의 기존 키를 모두 확인한 뒤 새 키를 추가하기 때문이다. 네 번째 삽입 직전에는 재해시가 일어나며 기존 세 노드가 이동한다. 새 배열의 1번 연결은 "a", "i" 순서가 되므로 이후 조회 비교 수는 각각 1과 2다. "z"는 2번 버킷으로 가서 "b"와 한 번 비교한 뒤 실패한다.
내장 딕셔너리와 비교한 열 번은 동일한 의미의 저장·조회·삭제 요청 수다. 내장 쪽의 새 키 여부 판정에는 포함 검사도 사용하므로 내부 함수 호출 수가 열 번이라는 뜻은 아니다. 표준 인터페이스만으로 내장 딕셔너리의 내부 키 비교 수를 얻었다고 주장할 수 없다. 여기서 확인한 것은 동작 결과의 일치이며, 직접 구현에서 관찰한 횟수를 내장 구현의 횟수로 대신 쓰지 않는다.
단일 실행의 숫자는 복잡도 증명을 대신하지 않는다. 다만 증가 원인을 확인할 수 있다. 충돌한 키 k개를 비어 있는 한 버킷에 차례로 추가하면, 확장이 없다는 조건에서 비교 수의 합은 0 + 1 + … + (k - 1)이 된다. 빈 배열에서도 해시를 위해 키 문자를 읽으며, 조회 실패도 연결 끝까지 조사할 수 있다는 점을 출력과 함께 읽어야 한다.
실무에서 자주 틀리는 것
같은 위치라는 이유로 기존 값을 덮어쓴다
다음 코드는 충돌한 다른 키를 지운다. 배열 위치는 검색의 시작점이며 키의 신원이 아니다.
# 틀린 코드: 기존 연결을 잃는다.
self.buckets[index] = Node(key, value, code)
기존 키가 없는지 먼저 확인한 뒤, 새 키라면 기존 연결을 다음 노드로 보존한다. 아래 수정은 완성 코드의 기존 키 검사 이후에 해당한다.
# 고친 코드: 기존 연결 앞에 새 노드를 붙인다.
self.buckets[index] = Node(
key, value, code, self.buckets[index]
)
배열을 늘린 뒤 이전 인덱스를 사용한다
해시값을 저장해 두었어도 인덱스까지 그대로 쓸 수는 없다. 나머지를 구할 기준이 바뀌었기 때문이다.
# 틀린 코드
index = code % len(self.buckets)
self._rehash()
self.buckets[index] = Node(
key, value, code, self.buckets[index]
)
기존 항목을 재배치한 뒤 새 키의 위치도 다시 계산한다. 재해시 안에서도 각 기존 노드에 같은 원칙을 적용한다.
# 고친 코드
self._rehash()
index = code % len(self.buckets)
self.buckets[index] = Node(
key, value, code, self.buckets[index]
)
재해시 도중 다음 노드를 잃는다
아래 반복은 next를 새 연결로 바꾼 뒤 그 값을 따라간다. 원래 연결의 나머지 항목을 제대로 순회하지 못한다.
# 틀린 코드
node.next = new[index]
new[index] = node
node = node.next
연결을 바꾸기 전에 다음 위치를 별도 변수에 저장한다. 완성 코드의 이동 통계가 기존 항목 수와 같은지도 함께 확인한다.
# 고친 코드
following = node.next
node.next = new[index]
new[index] = node
node = following
개방 주소에서 삭제 표식을 빈칸처럼 취급한다
삭제 표식에서 조회를 멈추면 그 뒤에 있는 키를 놓친다. 완성 코드의 실험에서 다음 조건으로 바꾸면 "i"를 찾지 못한다.
# 틀린 코드
if item is empty or item is deleted:
break
처음부터 비어 있던 칸에서는 멈추고, 삭제 표식에서는 다음 칸을 조사한다.
# 고친 코드
if item is empty:
break
if item is deleted:
continue
한눈에 보기
| 연산 | 고르게 분포할 때 | 최악의 경우 | 확인할 통계 |
|---|---|---|---|
| 조회 | O(1) | O(n) | 해시 문자, 키 비교 |
| 기존 키 수정 | O(1) | O(n) | 키 비교, 항목 수 유지 |
| 새 키 삽입 | 분할 상환 O(1) | O(n + m) | 키 비교, 충돌 삽입, 이동 |
| 삭제 | O(1) | O(n) | 키 비교, 항목 수 감소 |
| 재해시 | O(n + m) | O(n + m) | 재해시 횟수, 이동 수 |
표의 n은 항목 수, m은 확장 전 버킷 수다. 키의 해시 및 동등성 검사 비용을 일정하게 보고, 평균 비용에는 적재율이 제한된다는 조건을 둔다. 문자열 길이를 함께 따지면 해시 문자 처리 비용도 더해야 한다. 재해시는 기존 배열을 순회하고 새 배열을 만드는 비용까지 포함한다. 저장 공간은 노드와 버킷을 합쳐 O(n + m)이며, 확장 도중에는 이전 배열과 새 배열이 함께 존재한다.
| 구분 | 충돌한 항목의 위치 | 조회 종료 조건 | 삭제할 때 할 일 |
|---|---|---|---|
| 체이닝 | 같은 버킷의 연결 | 키 발견 또는 연결 끝 | 앞뒤 연결을 잇는다 |
| 선형 조사 | 배열의 다음 후보 칸 | 키 발견, 빈칸, 조사 한도 | 조사 경로를 표식으로 보존한다 |
키가 어느 버킷으로 가는지 계산하는 일과, 그 버킷에서 같은 키를 확인하는 일은 구분해야 한다. 적재율 관리는 연결의 평균 길이를 다루지만 특정 입력의 충돌을 없애지는 않는다. 다음 장에서는 키로 위치를 찾는 대신 항목 사이의 크기 관계에 따라 데이터를 정렬하는 구현을 살펴본다.
연습 문제
- 빈 테이블에 "a", "e", "i"를 넣고 재해시 전에 "a"를 조회하라. 조회만으로 늘어난 키 비교 수를 출력하고, 완성 코드의 조회 결과와 다른 이유를 설명하라.
- 문자열 "a", "i", "q"를 기본 용량의 테이블에 넣은 뒤 없는 키 "y"를 조회하라. 조회의 키 비교 수와 이 입력이 보여 주는 최악의 경우를 설명하라.
- 완성 코드의 열 번 연산을 그대로 실행하되 초기 용량을 8로 바꾸라. 재해시 횟수, 이동 수, 키 비교 수의 누적값을 예측한 뒤 확인하라.
- 값으로 None을 저장한 항목과 없는 항목을 서로 구분하는 실험을 작성하라. get의 기본값에 별도 객체를 전달하고 is로 판정하라.
정답과 해설
-
조회 비교 수는 3이다. 새 테이블을 만들고 다음 코드를 main 안에서 실행한다. 재해시 전에는 "i", "e", "a" 순서이므로 마지막 노드까지 간다. 완성 코드에서는 재해시가 연결 순서를 바꾼 뒤 조회하여 한 번만 비교한다.
sample = HashTable() sample.put("a", 10) sample.put("e", 20) sample.put("i", 30) before = sample.comparisons print(sample.get("a")) print(sample.comparisons - before) # 출력: 10 다음 줄에 3 -
비교 수는 3이다. 네 키의 문자 번호는 모두 4로 나눈 나머지가 1이다. 저장한 항목은 세 개이므로 아직 확장이 없다. 없는 키를 찾으려면 연결 전체를 확인해야 한다. 같은 버킷에 n개가 모이면 조회가 O(n)이 될 수 있음을 보여 준다.
sample = HashTable() for key in ("a", "i", "q"): sample.put(key, 1) before = sample.comparisons print(sample.get("y", "-")) print(sample.comparisons - before) # 출력: - 다음 줄에 3 -
table = HashTable(8)로 바꾸면 재해시 0회, 이동 0개, 누적 키 비교 8회다. 삽입 시에는 "i"가 "a"와 한 번 비교한다. 이후 조회는 "a"가 두 번, "i"가 한 번, "z"가 한 번이며, "e" 수정과 "i" 삭제는 각각 한 번이다. "x" 삭제는 빈 버킷에서 끝난다. "a" 삽입, "e" 삽입, "b" 삽입의 비교 수는 0이다. 합은 8이다. 용량을 바꾸면 충돌 관계와 연결 순서가 달라져 개별 연산 비용도 달라진다. -
저장된 값이 None이어도 반환값이 별도 객체와 같은 객체는 아니다. 없는 키만 전달한 기본값을 그대로 돌려준다. 표식을 실제 값으로 저장하지 않는다는 사용 규칙도 필요하다.
sample = HashTable() sample.put("memo", None) missing = object() print(sample.get("memo", missing) is missing) print(sample.get("absent", missing) is missing) # 출력: False 다음 줄에 True