해시 테이블은 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조이다. 해시 테이블의 시간 복잡도는 O(1)이다.
키와 값을 해시 테이블에 넣을 때 거치는 과정
- 키의 해시 코드를 계산
- 해시 코드를 이용하여 배열의 인덱스를 구함
- 배열의 각 인덱스에 키와 값으로 이루어진 연결 리스트가 존재
해시 함수의 두가지 성질
- 입력 원소가 해시 테이블 전체에 고루 저장되어 있어야 함
- 계산이 간단해야 함
⭐️ 첫번째 성질이 중요: 이 성질을 잘 만족해야 서로 다른 두 원소가 한 주소를 놓고 충돌할 확률이 작아짐
해시 함수를 만드는 두 가지 방법
- 나누기 방법 : 해시 테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 수축시킴
h(x) = x mod m
⭐️ 여기서 m은 테이블의 크기, 소수여야 함 - 곱하기 방법 : 입력값을 0과 1 사이의 소수로 대응시킨 다음 해시 테이블 크기를 곱해서 0부터 m-1 사이로 팽창 시킴
h(x) = ⎣m(xA mod 1)⎦
⭐️ 나누기 방법과 다르게 해시 테이블 크기 m을 아무렇게나 잡아도 상관없지만 컴퓨터의 이진수 환경에 맞게 $2^p$로 잡는 것이 자연스러움
💡상수 A를 어떻게 잡느냐에 따라 해시 값 분포가 많은 영향을 받는데 크누스는 잘 작동하는 A값으로 $\frac{\sqrt{5}-1}{2}$를 제안함
충돌 해결 두 가지 방법
- 오픈 해싱 (chaining)
같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아 관리 - 클로즈 해싱 (Open Addressing)
오픈 해싱처럼 추가 공간을 허용하지 않음, 모든 원소가 반드시 자신의 해시 값과 일치하는 주소에 저장된다는 보장이 없음, 정해진 규칙에 따라 다음 자리를 찾는데 를 찾는데 빈자리를 찾을 때까지 계속 찾음
클로즈 해싱에서 주소를 결정하는 대표적인 세 가지 방법
- 선형 조사
$h_j(x) = (h(x) + i)$ mod $m$
충돌이 일어난 자리에서 i에 관한 일차 함수의 보폭으로 점프를 함
🐱 특정 영역에 원소가 몰릴 때 치명적으로 성능이 떨어짐 - 이차원 조사
$h_1(x) = (h(x)+c_1i^2 + c_2i)$ mod $m$
$i = 0, 1, 2...$
선형 조사와 달리 이차 함수의 보폭으로 점프를 함
🐶 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있음
🐱 여러 개의 원소가 동일한 초기 해시 함숫값을 갖게 되면 모든 같은 순서로 조사할 수밖에 없어서 비효율적임 - 더블 해싱
$h_i(x)=(h(x)+i*f(x))$ mod $m$
다른 해시 함수 두 개를 사용한다.
🐶 두 원소의 첫 번째 해시 값이 같더라도 두 번째 함 수 값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프함
파이썬으로 해시 테이블 구현하기
파이썬으로 해시를 사용하려면 딕셔너리를 사용하면 되지만 직접 구현해보자
class HashTable:
def __init__(self, table_size):
self.table_size = table_size
self.hash_table = [0 for _ in range(self.table_size)]
def getKey(self, data):
return ord(data[0])
def hashFunction(self, key):
return key % self.table_size
def getAddress(self, key):
hash_key = key if type(key) is int else self.getKey(key)
hash_address = self.hashFunction(hash_key)
return hash_address
def put(self, key, value):
hash_address = self.getAddress(key)
self.hash_table[hash_address] = value
def get(self, key):
hash_address = self.getAddress(key)
return self.hash_table[hash_address]
def delete(self, key):
hash_address = self.getAddress(key)
if self.hash_table[hash_address] != 0:
self.hash_table[hash_address] = 0
return True
else: return False파이썬으로 오픈 해싱을 사용하는 해시 테이블 구현하기
class OpenHashTable:
def __init__(self, table_size):
self.table_size = table_size
self.hash_table = [[] for _ in range(self.table_size)]
def getKey(self, data):
return ord(data[0])
def hashFunction(self, key):
return key % self.table_size
def getAddress(self, key):
hash_key = key if type(key) is int else self.getKey(key)
hash_address = self.hashFunction(hash_key)
return hash_address
def put(self, key, value):
hash_address = self.getAddress(key)
if self.hash_table[hash_address]:
for chaining_index in range(len(self.hash_table[hash_address])):
if self.hash_table[hash_address][chaining_index][0] == key:
self.hash_table[hash_address][chaining_index][1] = value
return
self.hash_table[hash_address].append([key, value])
else:
self.hash_table[hash_address] = [[key, value]]
def get(self, key):
hash_address = self.getAddress(key)
if self.hash_table[hash_address]:
for chaining_index in range(len(self.hash_table[hash_address])):
if self.hash_table[hash_address][chaining_index][0] == key:
return self.hash_table[hash_address][chaining_index][0]
return False
else:
return False
def delete(self, key):
hash_address = self.getAddress(key)
if self.hash_table[hash_address]:
for chaining_index in range(len(self.hash_table[hash_address])):
if self.hash_table[hash_address][chaining_index][0] == key:
if len(self.hash_table[hash_address]) == 1:
self.hash_table[hash_address] = []
else:
del self.hash_table[hash_address][chaining_index]
return
return False
else:
return False파이썬으로 클로즈 해싱(더블 해싱)을 사용하는 해시 테이블 구현하기
class CloseHashTable:
def __init__(self, table_size, parameter):
self.table_size = table_size
self.function_parameter = parameter
self.hash_table = [[] for _ in range(self.table_size)]
def getKey(self, data):
return ord(data[0])
def hashFunction(self, key):
return key % self.table_size
def hashFunction2(self, key):
return 1 + key % self.function_parameter
def getAddress(self, key):
hash_key = key if type(key) is int else self.getKey(key)
hash_address = self.hashFunction(hash_key)
return hash_address
def put(self, key, value):
hash_address = self.getAddress(key)
function2_return = self.hashFunction2(key)
while self.hash_table[hash_address] and self.hash_table[hash_address][0] != "delete":
hash_address = self.hashFunction(hash_address+function2_return)
print(key, hash_address)
self.hash_table[hash_address] = [key, value]
def get(self, key):
hash_address = self.getAddress(key)
function2_return = self.hashFunction2(key)
while self.hash_table[hash_address]:
if self.hash_table[hash_address][0] == key: return self.hash_table[hash_address][1]
hash_address = self.hashFunction(hash_address + function2_return)
return False
def delete(self, key):
hash_address = self.getAddress(key)
function2_return = self.hashFunction2(key)
while self.hash_table[hash_address]:
if self.hash_table[hash_address][0] == key:
self.hash_table[hash_address] = ["delete", "delete"]
hash_address = self.hashFunction(hash_address + function2_return)
return False💖 참고 자료 💖
[python] 자료구조 - 해시 테이블(Hash Table)
해시 테이블(Hash Table) 해쉬 테이블은 키와 밸류를 기반으로 데이터를 저장한다. 파이썬에서는 딕셔너리가 있어서 굳이 만들 필요는 없는데, 아무래도 파이썬으로 코드를 짜면 간단해서 파악하
jinyes-tistory.tistory.com
게일 라크만 맥도웰, [코딩 인터뷰 완전 분석], 프로그래밍 인사이트(2017)
문병로, [쉽게 배우는 알고리즘], 한빛 아카데미(2018)