해시 테이블(Hash Table)은 key를 해시 함수에 넣어 배열의 인덱스로 바꾸고, 해당 위치에 값을 저장하는 자료구조다.
서로 다른 key가 같은 인덱스로 변환되면 해시 충돌(Hash Collision) 이 발생한다.
Open Addressing은 충돌이 발생했을 때 같은 인덱스에 리스트를 만들지 않고, 해시 테이블 안의 다른 빈 칸을 찾아 데이터를 저장한다.
Double Hashing은 Open Addressing의 한 종류로, 해시 함수를 두 개 사용한다.
첫 번째 해시 함수: 처음 저장을 시도할 위치를 정한다.
두 번째 해시 함수: 충돌이 발생했을 때 이동할 간격을 정한다.즉, Double Hashing은 다음과 같은 방식으로 탐사 위치를 계산한다.
index = (hash1(key) + i * hash2(key)) % table_sizei는 몇 번째 탐사인지 나타내는 값이다.
i = 0 -> hash1(key)
i = 1 -> hash1(key) + hash2(key)
i = 2 -> hash1(key) + 2 * hash2(key)
i = 3 -> hash1(key) + 3 * hash2(key)1. Double Hashing 구현 수도 코드
Double Hashing 방식의 해시 테이블은 다음 기능을 가진다.
put(key, value): 데이터를 저장하거나 기존 key의 값을 수정한다.get(key): key에 해당하는 값을 조회한다.delete(key): key에 해당하는 데이터를 삭제한다.hash1(key): key의 시작 인덱스를 계산한다.hash2(key): 충돌 시 이동 간격을 계산한다.probe_index(start_index, step, i): i번째 탐사 위치를 계산한다.show(): 해시 테이블의 전체 상태를 출력한다.
수도 코드로 표현하면 다음과 같다.
HashTable(size):
table을 size만큼 None으로 초기화한다.
삭제된 칸을 표시할 DELETED 객체를 준비한다.
hash1(key):
key의 문자 숫자 값을 모두 더한다.
return total % size
hash2(key):
key의 문자 숫자 값을 모두 더한다.
return 1 + (total % (size - 1))
probe_index(start_index, step, i):
return (start_index + i * step) % size
put(key, value):
시작 인덱스 = hash1(key)
이동 간격 = hash2(key)
처음 발견한 삭제 위치 = 없음
i를 0부터 테이블 크기 전까지 반복한다.
index = probe_index(시작 인덱스, 이동 간격, i)
현재 칸이 DELETED라면:
처음 발견한 삭제 위치를 기억한다.
현재 칸이 None이라면:
기억해둔 삭제 위치가 있으면 그곳에 저장한다.
없다면 현재 칸에 저장한다.
True를 반환한다.
현재 칸의 key가 입력 key와 같다면:
기존 value를 새 value로 수정한다.
True를 반환한다.
삭제 위치가 있었다면 그곳에 저장한다.
빈 위치가 없다면 False를 반환한다.
get(key):
시작 인덱스 = hash1(key)
이동 간격 = hash2(key)
i를 0부터 테이블 크기 전까지 반복한다.
index = probe_index(시작 인덱스, 이동 간격, i)
현재 칸이 None이라면:
None을 반환한다.
현재 칸이 DELETED라면:
다음 탐사 위치를 확인한다.
현재 칸의 key가 입력 key와 같다면:
value를 반환한다.
None을 반환한다.
delete(key):
시작 인덱스 = hash1(key)
이동 간격 = hash2(key)
i를 0부터 테이블 크기 전까지 반복한다.
index = probe_index(시작 인덱스, 이동 간격, i)
현재 칸이 None이라면:
False를 반환한다.
현재 칸의 key가 입력 key와 같다면:
현재 칸을 DELETED로 바꾼다.
True를 반환한다.
False를 반환한다.핵심은 충돌이 발생했을 때 이동 간격이 고정된 1이 아니라, hash2(key)로 계산된다는 점이다.
index = (start_index + i * step) % self.size2. 파이썬 구현
아래 코드는 Open Addressing의 Double Hashing 방식으로 해시 충돌을 처리하는 간단한 해시 테이블 구현이다.
class HashTable:
DELETED = object()
def __init__(self, size):
self.size = size
self.table = [None for _ in range(size)]
def _total(self, key):
total = 0
for char in key:
total += ord(char)
return total
def hash1(self, key):
return self._total(key) % self.size
def hash2(self, key):
return 1 + (self._total(key) % (self.size - 1))
def probe_index(self, start_index, step, i):
return (start_index + i * step) % self.size
def put(self, key, value):
start_index = self.hash1(key)
step = self.hash2(key)
first_deleted_index = None
for i in range(self.size):
index = self.probe_index(start_index, step, i)
item = self.table[index]
if item is self.DELETED:
if first_deleted_index is None:
first_deleted_index = index
elif item is None:
target_index = (
first_deleted_index
if first_deleted_index is not None
else index
)
self.table[target_index] = (key, value)
return True
else:
saved_key, saved_value = item
if saved_key == key:
self.table[index] = (key, value)
return True
if first_deleted_index is not None:
self.table[first_deleted_index] = (key, value)
return True
print("해시 테이블이 가득 찼다.")
return False
def get(self, key):
start_index = self.hash1(key)
step = self.hash2(key)
for i in range(self.size):
index = self.probe_index(start_index, step, i)
item = self.table[index]
if item is None:
return None
if item is not self.DELETED:
saved_key, saved_value = item
if saved_key == key:
return saved_value
return None
def delete(self, key):
start_index = self.hash1(key)
step = self.hash2(key)
for i in range(self.size):
index = self.probe_index(start_index, step, i)
item = self.table[index]
if item is None:
return False
if item is not self.DELETED:
saved_key, saved_value = item
if saved_key == key:
self.table[index] = self.DELETED
return True
return False
def show(self):
for index, item in enumerate(self.table):
if item is self.DELETED:
print(index, "DELETED")
else:
print(index, item)3. 실행 예시
hash_table = HashTable(7)
hash_table.put("aa", "first")
hash_table.put("ah", "second")
hash_table.put("ao", "third")
print(hash_table.get("aa"))
print(hash_table.get("ah"))
print(hash_table.get("ao"))
hash_table.put("aa", "updated")
print(hash_table.get("aa"))
hash_table.delete("ah")
print(hash_table.get("ah"))
hash_table.show()출력 결과:
first
second
third
updated
None
0 None
1 None
2 DELETED
3 ('ao', 'third')
4 None
5 ('aa', 'updated')
6 None"aa", "ah", "ao"는 모두 첫 번째 해시 함수에서는 같은 시작 인덱스 5를 얻는다.
"aa": 194 % 7 = 5
"ah": 201 % 7 = 5
"ao": 208 % 7 = 5하지만 두 번째 해시 함수에서는 이동 간격이 달라진다.
"aa": 1 + (194 % 6) = 3
"ah": 1 + (201 % 6) = 4
"ao": 1 + (208 % 6) = 5그래서 충돌이 발생해도 key마다 다른 경로로 이동할 수 있다.
"aa" -> index 5 저장
"ah" -> index 5 충돌
-> (5 + 1 * 4) % 7 = 2 저장
"ao" -> index 5 충돌
-> (5 + 1 * 5) % 7 = 3 저장위 출력에서는 "ah" 삭제 후 "ah"가 있던 2번 인덱스에 DELETED가 남는다.
4. 각 함수 설명
__init__(self, size)
def __init__(self, size):
self.size = size
self.table = [None for _ in range(size)]해시 테이블을 초기화하는 생성자다.
Open Addressing은 각 칸에 하나의 데이터만 저장하므로 None으로 초기화한다.
_total(self, key)
def _total(self, key):
total = 0
for char in key:
total += ord(char)
return total문자열 key의 각 문자를 숫자로 바꾼 뒤 모두 더하는 보조 함수다.
hash1()과 hash2()에서 공통으로 사용한다.
hash1(self, key)
def hash1(self, key):
return self._total(key) % self.size첫 번째 해시 함수다.
데이터가 처음 저장을 시도할 인덱스를 계산한다.
hash2(self, key)
def hash2(self, key):
return 1 + (self._total(key) % (self.size - 1))두 번째 해시 함수다.
충돌이 발생했을 때 이동할 간격을 계산한다.
1 +를 붙이는 이유는 이동 간격이 0이 되는 것을 막기 위해서다.
step이 0이면 같은 위치만 계속 확인하게 된다.probe_index(self, start_index, step, i)
def probe_index(self, start_index, step, i):
return (start_index + i * step) % self.sizei번째 탐사 위치를 계산하는 함수다.
i = 0 -> start_index
i = 1 -> start_index + step
i = 2 -> start_index + 2 * step
i = 3 -> start_index + 3 * stepDouble Hashing에서는 key마다 step이 달라질 수 있다.
put(self, key, value)
put()은 key-value 데이터를 저장하는 함수다.
먼저 hash1()으로 시작 인덱스를 구하고, hash2()로 이동 간격을 구한다.
start_index = self.hash1(key)
step = self.hash2(key)충돌이 발생하면 step만큼 떨어진 위치를 확인한다.
index = self.probe_index(start_index, step, i)같은 key를 만나면 새 데이터를 추가하지 않고 기존 value만 수정한다.
get(self, key)
get()은 key에 해당하는 value를 조회하는 함수다.
Double Hashing으로 저장된 데이터는 원래 위치가 아닌 다른 칸에 있을 수 있다.
따라서 조회할 때도 hash1()과 hash2()를 이용해 저장할 때와 같은 경로를 따라가야 한다.
시작 인덱스 계산
↓
이동 간격 계산
↓
같은 탐사 순서로 key 확인delete(self, key)
delete()는 key에 해당하는 데이터를 삭제하는 함수다.
Open Addressing에서는 삭제된 칸을 None으로 바꾸면 탐색 경로가 끊길 수 있다.
따라서 삭제된 칸은 DELETED로 표시한다.
None: 한 번도 사용하지 않은 칸
DELETED: 데이터가 있었지만 삭제된 칸조회할 때 DELETED를 만나면 탐색을 멈추지 않고 다음 위치를 확인한다.
show(self)
show()는 현재 해시 테이블의 전체 상태를 출력하는 함수다.
충돌이 발생한 데이터가 어떤 인덱스로 이동했는지 확인할 수 있다.
5. 해시 충돌 예제
hash_table = HashTable(7)
hash_table.put("aa", "first")
hash_table.put("ah", "second")
hash_table.put("ao", "third")
hash_table.show()출력 결과:
0 None
1 None
2 ('ah', 'second')
3 ('ao', 'third')
4 None
5 ('aa', 'first')
6 None세 key는 모두 시작 인덱스가 5이다.
"aa" -> hash1 = 5, hash2 = 3
"ah" -> hash1 = 5, hash2 = 4
"ao" -> hash1 = 5, hash2 = 5탐사 과정은 다음과 같다.
"aa" -> index 5 저장
"ah" -> index 5 충돌
-> (5 + 1 * 4) % 7 = 2 저장
"ao" -> index 5 충돌
-> (5 + 1 * 5) % 7 = 3 저장같은 시작 인덱스를 가져도 두 번째 해시 함수가 이동 간격을 다르게 만들기 때문에 서로 다른 경로로 이동한다.
6. Double Hashing의 장점과 주의할 점
Double Hashing은 Linear Probing과 Quadratic Probing보다 데이터가 한쪽에 몰리는 문제를 줄일 수 있다.
Linear Probing은 이동 간격이 항상 1이다.
5 -> 6 -> 0 -> 1 -> 2Quadratic Probing은 시작 인덱스가 같으면 같은 제곱 탐사 경로를 따른다.
5 -> 6 -> 2 -> 0Double Hashing은 key마다 이동 간격이 달라질 수 있다.
"aa": 5 -> 1 -> 4 -> 0 ...
"ah": 5 -> 2 -> 6 -> 3 ...
"ao": 5 -> 3 -> 1 -> 6 ...이 때문에 Primary Clustering과 Secondary Clustering을 줄이는 데 도움이 된다.
다만 두 번째 해시 함수가 잘못 설계되면 문제가 생긴다.
hash2(key)가0을 반환하면 안 된다.- 테이블 전체를 잘 탐사할 수 있어야 한다.
- 보통 테이블 크기를 소수로 잡는 것이 유리하다.
- 적재율이 높아지면 리사이징이 필요하다.
7. Chaining과 Double Hashing 비교
| 구분 | Chaining | Double Hashing |
|---|---|---|
| 저장 방식 | 같은 bucket 리스트에 저장 | 테이블 내부의 다른 빈 칸에 저장 |
| 한 칸의 데이터 수 | 여러 개 가능 | 하나만 가능 |
| 충돌 처리 | bucket에 추가 | 두 번째 해시 함수로 이동 간격 결정 |
| 삭제 | 리스트에서 제거 | DELETED 표시 필요 |
| 장점 | 구현이 직관적 | 데이터 분산이 좋음 |
| 주의점 | bucket이 길어질 수 있음 | 두 번째 해시 함수 설계가 중요 |
정리
Double Hashing은 Open Addressing 방식 중 하나로, 충돌이 발생했을 때 두 번째 해시 함수로 이동 간격을 계산한다.
key 입력
↓
hash1(key)로 시작 인덱스 계산
↓
hash2(key)로 이동 간격 계산
↓
충돌 발생 시 step만큼 이동Linear Probing은 한 칸씩 이동하고, Quadratic Probing은 제곱 간격으로 이동한다.
Double Hashing은 key마다 이동 간격이 달라질 수 있으므로 데이터가 한쪽에 몰리는 문제를 줄이는 데 도움이 된다.
좋은 Double Hashing을 만들기 위해서는 hash2()가 0을 반환하지 않도록 하고, 테이블 전체를 잘 탐사할 수 있게 설계해야 한다.
