해시 테이블
해시 테이블은 자료를 검색, 삽입, 삭제하는데 평균 O(1)(상수시간)이 가능하게 하여 극단적 효율에 다다른 자료구조이다.
적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율
해시 테이블의 크기가 m이고 저장된 키의 총 수가 n이면, 적재율은 n/m이고 보통 알파로 표기한다.
적제율이 높을수록 충돌 확률이 높아져 해시 테이블의 성능이 나빠진다.
1. 해시 함수
(1) 나누기 방법
h(x) = x % m
m은 2의 멱수에 가깝지 않은 소수를 택하는 것이 좋다
나누기 방법은 해시 테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어 오도록 수축시킨다.
(2) 곱하기 방법
h(x) = lower(m*(x*A % 1))
곱하기 방법에서는 먼저 입력 값을 0과 1 사이의 소수로 대응시킨 다음
해시 테이블 크기 m을 곱하여 0 부터 m-1 사이로 팽창시킨다.
x에서 A를 곱한 다음 소수부만 취한다.
방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
곱하기 방법은 나누기 방법과 달리 해시 테이블의 크기 m을 아무렇게나 잡아도 상관없다,
따라서 컴퓨터의 이진수 환경에 맞게 m = 2**p으로 잡는 것이 자연스럽다.
2. 충돌 해결
(1) 체이닝
충돌을 일으킨 키들을 연결리스트로 관리하는 방법.
체이닝에서 임의의 키를 삽입할 때는 연결리스트의 맨 앞에 삽입하는 것이 좋다.
체이닝은 적재율이 1을 넘어도 사용할 수 있다는 장점이 있다.
(2) 개방 주소 방법
충돌이 일어나면 키가 원래 들어갈 자리가 아니더라도 테이블의 다른 자리를 찾아
들어가는 방법으로 추가 공간을 사용하지 않는다.
개방 주소 방법은 테이블에 주어진 공간만 사용할 수 있으므로 적재율이 1을 넘을 수 없고,
적재율이 어느 정도 이상 높아지면 효율이 급격하게 떨어지게 된다.
해시 테이블에서 자료가 삭제될 경우 처리법
h(x) = x % 13
| 0 | 13 |
| 1 | 1 --> ∅(삭제됨) |
| 2 | 15 |
| 3 | 16 |
| 4 | 28 |
| 5 | 31 |
| 6 | 38 |
| 7 | 7 |
| 8 | 20 |
| 9 | |
| 10 | |
| 11 | |
| 12 | 25 |
| 0 | 13 |
| 1 | |
| 2 | 15 |
| 3 | 16 |
| 4 | 28 |
| 5 | 31 |
| 6 | 38 |
| 7 | 7 |
| 8 | 20 |
| 9 | |
| 10 | |
| 11 | |
| 12 | 25 |
38 검색 : h(38) = 38 % 13 = 12
1에 이르면 빈자리를 발견하게 되어 키 38은 없다고 판단한다.
그런데 38은 6에 존재한다.
이런 상황이 발생하지 않도록 키를 삭제할 때 원래는 키가 있던 자리였음을 표시해 주어야 한다.(DELETED)
개방 주소 방법에서 충돌이 일어났을 때 다음 주소를 정하는 방법
(1) 선형 탐색 : 충돌이 일어난 자리에서 i에 관한 일차 함수의 보폭으로 점프
hi(x) = (h(x) + a*i + b) % m (i = 0, 1, 2 ...)
(2) 이차원 탐색 : 충돌이 일어난 자리에서 보폭을 이차 함수에 의해 넓혀가면서 점프
hi(x) = (h(x) + a*i^2 + b*i + c) % m (i = 0, 1, 2 ...)
(3) 더블 해싱 : 2개의 해시 함수를 사용
hi(x) = (h(x) + i*f(x)) % m (i = 0, 1, 2 ...) (여기서 h(x)와 f(x)는 서로 다른 해시 함수)
권장되는 방법은 h(x) = x % m으로 잡고, m보다 조금 작은 소수 m'에 대해 f(x) = 1 + (x % m')로 잡는 것이다.
체이닝 해시 테이블의 구현
# 체이닝 해시 테이블의 구현
from CircularLinkedList import *
class ChainedHashTable:
def __init__(self, n):
self.__table = [CircularLinkedList() for _ in range(n)]
self.__size = 0
def __hash(self, x):
return x % len(self.__table)
def insert(self, x):
slot = self.__hash(x)
self.__table[slot].insert(0,x)
self.__size += 1
def delete(self, x):
slot = self.__hash(x)
success = self.__table[slot].remove(x)
if success != None:
self.__size -= 1
def search(self, x):
slot = self.__hash(x)
if self.__table[slot].isEmpty():
return None
head = prev = self.__table[slot].getNode(-1) # 더미 헤드, index : -1
curr = prev.next
while curr != head:
if curr.item == x:
return curr
prev = curr; curr = curr.next
return None
def isEmpty(self):
return len(self.__table) == 0
def clear(self):
for i in range(len(self.__table)):
self.__table[i] = CircularLinkedList()
self.__size = 0
개방 주소 해시 테이블의 구현
# 개방 주소 해시 테이블의 구현
# None, DELETED, x, x가 아닌 값
class OpenAdressedHashTable:
def __init__(self, n):
self.__table = [None for _ in range(n)]
self.__size = 0
self.__DELETED = -12345
self.__NotFound = -54321
def __hash(self, i, x):
return (x + i) % len(self.__table)
def insert(self, x):
if self.__size == len(self.__table):
raise Error # 적재율이 1이 된 경우
for i in range(len(self.__table)):
slot = self.__hash(i, x)
if self.__table[slot] = None or self.__table[slot] = self.__DELETED:
self.__table[slot] = x
self.__size += 1
break # 소요되는 시간을 단축하기 위해 if문이 성립하면 break나 return으로 for문을 종료시켜야 함!!
def delete(self, x):
for i in range(len(self.__table)):
slot = self.__hash(i, x)
if self.__table[slot] == None:
return self.__NotFound
if self.__table[slot] == x:
self.__table[slot] = self.__DELETED
self.__size -= 1
return x
def search(self, x):
for i in range(len(self.__table)):
slot = self.__hash(i, x)
if self.__table[slot] == None:
return self.__NotFound
if self.__table[slot] == x:
return slot
return self.__NotFound # for루프를 다 돌때까지 나오지 않았으므로 x는 존재하지 않음
def isEmpty(self):
return self.__size == 0
def clear(self):
self.__table = []
self.__size = 0