해시 테이블(Hash Table)은 key를 해시 함수에 넣어 배열의 인덱스로 바꾸고, 해당 위치에 값을 저장하는 자료구조다.
문제는 서로 다른 key가 같은 인덱스로 변환될 수 있다는 점이다. 이것을 해시 충돌(Hash Collision) 이라고 한다.
"aa" -> index 5
"ah" -> index 5
"ao" -> index 5Open Addressing은 충돌이 발생했을 때 같은 칸에 리스트를 만들지 않고, 해시 테이블 안의 다른 빈 칸을 찾아 저장하는 방식이다.
Quadratic Probing은 Open Addressing의 한 종류로, 충돌이 발생하면 1², 2², 3²처럼 제곱 간격으로 이동하며 빈 칸을 찾는다.
처음 인덱스 = hash(key)
1번째 확인: hash(key) + 0²
2번째 확인: hash(key) + 1²
3번째 확인: hash(key) + 2²
4번째 확인: hash(key) + 3²예를 들어 처음 인덱스가 5이고 테이블 크기가 7이라면 탐사 순서는 다음과 같다.
(5 + 0²) % 7 = 5
(5 + 1²) % 7 = 6
(5 + 2²) % 7 = 2
(5 + 3²) % 7 = 0즉, 5 -> 6 -> 2 -> 0 순서로 빈 칸을 확인한다.
1. Quadratic Probing 구현 수도 코드
Quadratic Probing 방식의 해시 테이블은 다음 기능을 가진다.
put(key, value): 데이터를 저장하거나 기존 key의 값을 수정한다.get(key): key에 해당하는 값을 조회한다.delete(key): key에 해당하는 데이터를 삭제한다.hash_function(key): key를 배열 인덱스로 변환한다.probe_index(start_index, i): i번째 탐사 위치를 계산한다.show(): 해시 테이블의 전체 상태를 출력한다.
수도 코드로 표현하면 다음과 같다.
HashTable(size):
table을 size만큼 None으로 초기화한다.
삭제된 칸을 표시할 DELETED 객체를 준비한다.
hash_function(key):
total = 0
key의 각 문자에 대해:
문자의 숫자 값을 total에 더한다.
return total % size
probe_index(start_index, i):
return (start_index + i * i) % size
put(key, value):
시작 인덱스 = hash_function(key)
처음 발견한 삭제 위치 = 없음
i를 0부터 테이블 크기 전까지 반복한다.
index = probe_index(시작 인덱스, i)
현재 칸이 DELETED라면:
처음 발견한 삭제 위치를 기억한다.
현재 칸이 None이라면:
기억해둔 삭제 위치가 있으면 그곳에 저장한다.
없다면 현재 칸에 저장한다.
True를 반환한다.
현재 칸의 key가 입력 key와 같다면:
기존 value를 새 value로 수정한다.
True를 반환한다.
삭제 위치가 있었다면 그곳에 저장한다.
빈 위치가 없다면 False를 반환한다.
get(key):
시작 인덱스 = hash_function(key)
i를 0부터 테이블 크기 전까지 반복한다.
index = probe_index(시작 인덱스, i)
현재 칸이 None이라면:
None을 반환한다.
현재 칸이 DELETED라면:
다음 탐사 위치를 확인한다.
현재 칸의 key가 입력 key와 같다면:
value를 반환한다.
None을 반환한다.
delete(key):
시작 인덱스 = hash_function(key)
i를 0부터 테이블 크기 전까지 반복한다.
index = probe_index(시작 인덱스, i)
현재 칸이 None이라면:
False를 반환한다.
현재 칸의 key가 입력 key와 같다면:
현재 칸을 DELETED로 바꾼다.
True를 반환한다.
False를 반환한다.핵심은 충돌이 발생했을 때 다음 인덱스를 계산하는 부분이다.
index = (start_index + i * i) % self.sizeLinear Probing은 한 칸씩 이동하지만, Quadratic Probing은 제곱 간격으로 이동한다.
2. 파이썬 구현
아래 코드는 Open Addressing의 Quadratic Probing 방식으로 해시 충돌을 처리하는 간단한 해시 테이블 구현이다.
class HashTable:
DELETED = object()
def __init__(self, size):
self.size = size
self.table = [None for _ in range(size)]
def hash_function(self, key):
total = 0
for char in key:
total += ord(char)
return total % self.size
def probe_index(self, start_index, i):
return (start_index + i * i) % self.size
def put(self, key, value):
start_index = self.hash_function(key)
first_deleted_index = None
for i in range(self.size):
index = self.probe_index(start_index, 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.hash_function(key)
for i in range(self.size):
index = self.probe_index(start_index, 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.hash_function(key)
for i in range(self.size):
index = self.probe_index(start_index, 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 ('ao', 'third')
3 None
4 None
5 ('aa', 'updated')
6 DELETED"aa", "ah", "ao"는 모두 처음 인덱스가 5이다.
"aa"
97 + 97 = 194
194 % 7 = 5
"ah"
97 + 104 = 201
201 % 7 = 5
"ao"
97 + 111 = 208
208 % 7 = 5세 key 모두 같은 위치에서 시작하지만, Quadratic Probing은 제곱 간격으로 다음 위치를 확인한다.
"aa" -> index 5 저장
"ah" -> index 5 충돌
-> (5 + 1²) % 7 = 6 저장
"ao" -> index 5 충돌
-> index 6 충돌
-> (5 + 2²) % 7 = 2 저장4. 각 함수 설명
__init__(self, size)
def __init__(self, size):
self.size = size
self.table = [None for _ in range(size)]해시 테이블을 초기화하는 생성자다.
Open Addressing은 한 칸에 하나의 데이터만 저장하므로 각 칸을 None으로 초기화한다.
hash_function(self, key)
def hash_function(self, key):
total = 0
for char in key:
total += ord(char)
return total % self.sizekey를 배열 인덱스로 변환하는 함수다.
문자열의 각 문자를 숫자 값으로 바꾼 뒤 모두 더하고, 테이블 크기로 나눈 나머지를 인덱스로 사용한다.
probe_index(self, start_index, i)
def probe_index(self, start_index, i):
return (start_index + i * i) % self.sizei번째 탐사 위치를 계산하는 함수다.
i = 0 -> start_index + 0²
i = 1 -> start_index + 1²
i = 2 -> start_index + 2²
i = 3 -> start_index + 3²이 함수 때문에 충돌이 발생했을 때 한 칸씩 이동하지 않고 제곱 간격으로 이동한다.
put(self, key, value)
put()은 key-value 데이터를 저장하는 함수다.
처음에는 해시 함수로 시작 인덱스를 구한다.
start_index = self.hash_function(key)현재 칸이 비어 있으면 데이터를 저장한다.
이미 다른 데이터가 있으면 probe_index()를 사용해 다음 탐사 위치를 계산한다.
같은 key를 만나면 새 데이터를 추가하지 않고 value만 수정한다.
hash_table.put("aa", "first")
hash_table.put("aa", "updated")위 코드에서는 "aa"가 두 개 생기지 않고 기존 값이 "updated"로 변경된다.
get(self, key)
get()은 key에 해당하는 value를 조회하는 함수다.
Quadratic Probing으로 저장된 데이터는 원래 해시 인덱스가 아닌 다른 위치에 있을 수 있다.
따라서 조회할 때도 저장할 때와 같은 제곱 탐사 순서를 따라야 한다.
시작 인덱스 확인
↓
key가 다르면 제곱 간격으로 다음 위치 확인
↓
같은 key를 찾으면 value 반환delete(self, key)
delete()는 key에 해당하는 데이터를 삭제하는 함수다.
Open Addressing에서는 삭제된 칸을 단순히 None으로 바꾸면 탐색 경로가 끊길 수 있다.
그래서 삭제된 칸은 DELETED로 표시한다.
index 5 -> ("aa", "first")
index 6 -> ("ah", "second")
"aa"를 None으로 삭제하면
"ah"를 찾는 탐색 경로가 끊길 수 있다.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 ('ao', 'third')
3 None
4 None
5 ('aa', 'first')
6 ('ah', 'second')탐사 순서는 다음과 같다.
시작 인덱스: 5
i = 0 -> (5 + 0²) % 7 = 5
i = 1 -> (5 + 1²) % 7 = 6
i = 2 -> (5 + 2²) % 7 = 26. Quadratic Probing의 장점과 주의할 점
Quadratic Probing은 Linear Probing보다 데이터가 연속적으로 뭉치는 문제를 줄일 수 있다.
Linear Probing은 충돌이 나면 바로 다음 칸으로 이동한다.
5 -> 6 -> 0 -> 1 -> 2Quadratic Probing은 제곱 간격으로 이동한다.
5 -> 6 -> 2 -> 0따라서 연속된 구간에 데이터가 몰리는 Primary Clustering 문제를 줄이는 데 도움이 된다.
하지만 같은 시작 인덱스를 가진 key들은 같은 탐사 순서를 따라간다.
이 문제를 Secondary Clustering이라고 한다.
또한 테이블 크기와 탐사 공식에 따라 모든 칸을 확인하지 못할 수도 있다.
그래서 실제 구현에서는 테이블 크기를 소수로 잡거나, 적재율이 너무 높아지기 전에 리사이징하는 전략이 필요하다.
7. Chaining과 Quadratic Probing 비교
| 구분 | Chaining | Quadratic Probing |
|---|---|---|
| 저장 방식 | 같은 bucket 리스트에 저장 | 테이블 내부의 다른 빈 칸에 저장 |
| 한 칸의 데이터 수 | 여러 개 가능 | 하나만 가능 |
| 충돌 처리 | bucket에 추가 | 제곱 간격으로 탐사 |
| 삭제 | 리스트에서 제거 | DELETED 표시 필요 |
| 장점 | 구현이 직관적 | 연속 군집을 줄일 수 있음 |
| 주의점 | bucket이 길어질 수 있음 | 모든 칸을 탐사하지 못할 수 있음 |
정리
Quadratic Probing은 Open Addressing 방식 중 하나로, 충돌이 발생했을 때 제곱 간격으로 다음 위치를 확인한다.
key 입력
↓
해시 함수로 시작 인덱스 계산
↓
현재 칸 확인
↓
충돌 발생 시 1², 2², 3² 간격으로 이동Linear Probing보다 연속된 데이터 뭉침을 줄일 수 있지만, 같은 시작 인덱스를 가진 key들은 같은 탐사 경로를 따라간다.
따라서 Quadratic Probing은 충돌 해결에 유용하지만, 테이블 크기와 적재율 관리가 함께 고려되어야 한다.
