Hash Table
탄생 배경
Direct Access Table 인 배열인덱스 방식으로, key-value쌍을 가져올 때 시간효율은 O(1)이므로 빠르다. 하지만 사용하지 않는 index에 대한 공간낭비가 상존함
1. 해시 함수의 조건
(1) 의의
특정 값을 원하는 범위의 자연수로 바꿔주는 함수
(2) 조건
1) 한 해시테이블의 해시 함수는 결정론적이어야 한다
같은 key 는 같은 결과가 나와야함
2) 결과 해시값이 치우치지 않고 고르게 나온다
각 리턴 값이 나올 확률이 비슷해야한다
3) 빠르게 계산 할 수있어야한다.
해시테이블은 연산할 때 마다 해시함수 사용함. 본 함수가 비효율적이면 해시테이블도 비효율적임
2. 해시함수 만들기
(1) 나누기 방법
자연수 key를 해시테이블의 크기로 나눈 나머지를 리턴하는 해시 함수
def hash_function_remainder(key, array_size):
"""해시 테이블의 key를 나누기 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수"""
return key % array_size
print(hash_function_remainder(40, 200))
print(hash_function_remainder(120, 200))
print(hash_function_remainder(788, 200))
print(hash_function_remainder(2307, 200))
#40
#120
#188
#107
(2) 곱하기 방법
- 순서
key : 300 / 배열크기 : 50
1) 0 < a < 1 사이 a값 정함 (a 는 0.5555)
2) 0.5555 * 300 = 166.65 (a 값 * key) / 이 경우 166.65 에서 소수부분만 남김 => 0.65
3) 0.65 * 50 = 32.5 (소수부분 * 배열 크기) / 이 경우 32.5 에서 정수부분만 남김 => 32
이렇게 연산하는 목적은 해수 함수값이 배열의 크기 보다 값이 적게(50 아래) 나오게끔 함 (1의 배수 아래의 곱은 무조건 곱하는 수보다 아래로)
def hash_function_multiplication(key, array_size, a):
"""해시 테이블의 key를 곱셈 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수"""
temp = a * key # a와 key를 곱한다
temp = temp - int(temp) # a와 key를 곱한 값의 소숫점 오른쪽 부분만 저장한다
return int(array_size * temp) # temp와 배열 크기를 곱한 수의 자연수 부분만 리턴한다
print(hash_function_multiplication(40, 200, 0.61426212))
print(hash_function_multiplication(120, 200, 0.61426212))
print(hash_function_multiplication(788, 200, 0.61426212))
print(hash_function_multiplication(2307, 200, 0.61426212))
#114
#142
#7
#20
3. 해시테이블 충돌과 Chaining
(1)해시테이블 충돌
1) 충돌(Collision) 이란
서로 다른 key 를 해시함수에 넣었을 때 같은 값이 나옴 -> 이미 사용한 해시테이블 인덱스를 또 사용할 때
2) Chaining
해시테이블을 다루기 위해서는 Collision 을 다룰 수 있어야함
- Collision 해결방법 : Chaining
배열 인덱스에 더블리 링크드 리스트로 저장해서 충돌 해결
- Chaining 주요 아이디어
링크드리스트의 data 필드를 key와 value로 저장
class Node:
"""링크드 리스트의 노드 클래스"""
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None # 다음 노드에 대한 레퍼런스
self.prev = None # 전 노드에 대한 레퍼런스
각 동작 별 시간 복잡도
| 동작 (Operation) | 시간 복잡도 |
| 탐색 (search) | O(n) |
| 저장 (save) | O(n) |
| 삭제 (delete) | O(n) |
| 연산 (Operation) | 부분 단계들 | 각 부분 단계 시간 복잡도 |
| 탐색 (search) | 1. 해시 함수 계산 2. 배열 인덱스 접근 3. 링크드 리스트 탐색 |
O(1+1+n) |
| 저장 (save) | 1. 해시 함수 계산 2. 배열 인덱스 접근 3. 링크드 리스트 탐색 4. 탐색한 노드 수정 or 링크드 리스트 앞에 노드 삽입 |
O(1+1+n+1) |
| 삭제 (delete) | 1. 해시 함수 계산 2. 배열 인덱스 접근 3. 링크드 리스트 탐색 4. 탐색한 노드 삭제 |
O(1+1+n+1) |
평균시간복잡도
“해시 테이블 삽입, 삭제, 탐색 연산들은 최악의 경우 O(n)이 걸리지만, 평균적으로는 O(1)이 걸린다”
파이썬으로 구현
class Node:
"""링크드 리스트의 노드 클래스"""
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None # 다음 노드에 대한 레퍼런스
self.prev = None # 전 노드에 대한 레퍼런스
class LinkedList:
"""링크드 리스트 클래스"""
def __init__(self):
self.head = None # 링크드 리스트의 가장 앞 노드
self.tail = None # 링크드 리스트의 가장 뒤 노드
def find_node_with_key(self, key):
"""링크드 리스트에서 주어진 데이터를 갖고있는 노드를 리턴한다. 단, 해당 노드가 없으면 None을 리턴한다"""
iterator = self.head # 링크드 리스트를 돌기 위해 필요한 노드 변수
while iterator is not None:
if iterator.key == key:
return iterator
iterator = iterator.next
return None
def append(self, key, value):
"""링크드 리스트 추가 연산 메소드"""
new_node = Node(key, value)
# 빈 링크드 리스트라면 head와 tail을 새로 만든 노드로 지정
if self.head is None:
self.head = new_node
self.tail = new_node
# 이미 노드가 있으면
else:
self.tail.next = new_node # 마지막 노드의 다음 노드로 추가
new_node.prev = self.tail
self.tail = new_node # 마지막 노드 업데이
def delete(self, node_to_delete):
"""더블리 링크드 리스트 삭제 연산 메소드"""
# 링크드 리스트에서 마지막 남은 데이터를 삭제할 때
if node_to_delete is self.head and node_to_delete is self.tail:
self.tail = None
self.head = None
# 링크드 리스트 가장 앞 데이터 삭제할 때
elif node_to_delete is self.head:
self.head = self.head.next
self.head.prev = None
# 링크드 리스트 가장 뒤 데이터 삭제할 떄
elif node_to_delete is self.tail:
self.tail = self.tail.prev
self.tail.next = None
# 두 노드 사이에 있는 데이터 삭제할 때
else:
node_to_delete.prev.next = node_to_delete.next
node_to_delete.next.prev = node_to_delete.prev
return node_to_delete.value
def __str__(self):
"""링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
res_str = ""
# 링크드 리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
iterator = self.head
# 링크드 리스트 끝까지 돈다
while iterator is not None:
# 각 노드의 데이터를 리턴하는 문자열에 더해준다
res_str += "{}: {}\n".format(iterator.key, iterator.value)
iterator = iterator.next # 다음 노드로 넘어간다
return res_str
class HashTable_best:
def __init__(self, capacity):
self._capacity = capacity # 파이썬 리스트 수용 크기 저장
self._table = [LinkedList() for _ in range(self._capacity)] # 파이썬 리스트 인덱스에 반 링크드 리스트 저장
def _hash_function(self, key):
"""
주어진 key에 나누기 방법을 사용해서 해시된 값을 리턴하는 메소드
주의 사항: key는 파이썬 불변 타입이어야 한다.
"""
return hash(key) % self._capacity
def _get_linked_list_for_key(self, key):
"""주어진 key에 대응하는 인덱스에 저장된 링크드 리스트를 리턴하는 메소드"""
hashed_index = self._hash_function(key)
return self._table[hashed_index]
def _look_up_node(self, key):
"""파라미터로 받은 key를 갖고 있는 노드를 리턴하는 메소드"""
linked_list = self._get_linked_list_for_key(key)
return linked_list.find_node_with_key(key)
def look_up_value(self, key):
"""
주어진 key에 해당하는 데이터를 리턴하는 메소드
"""
return self._look_up_node(key).value
def insert(self, key, value):
"""
새로운 key - 데이터 쌍을 삽입시켜주는 메소드
이미 해당 key에 저장된 데이터가 있으면 해당 key에 대응하는 데이터를 바꿔준다
"""
existing_node = self._look_up_node(key) # 이미 저장된 key인지 확인한다
if existing_node is not None:
existing_node.value = value # 이미 저장된 key면 데이터만 바꿔주고
else:
# 없는 키면 새롭게 삽입시켜준다
linked_list = self._get_linked_list_for_key(key)
linked_list.append(key, value)
def delete_by_key(self, key):
node = self._look_up_node(key) # 예와 처리 신경쓰자!!
"""주어진 key에 해당하는 key - value 쌍을 삭제하는 메소드"""
if node is not None:
self._get_linked_list_for_key(key).delete(node)
def __str__(self):
"""해시 테이블 문자열 메소드"""
res_str = ""
for linked_list in self._table:
res_str += str(linked_list)
return res_str[:-1]
# 삽입 탐색 문제
# print(test_scores)
# test_scores = HashTable_best(50) # 시험 점수를 담을 해시 테이블 인스턴스 생성
# 여러 학생들 이름과 시험 점수 삽입
# test_scores.insert("현승", 85)
# test_scores.insert("영훈", 90)
# test_scores.insert("동욱", 87)
# test_scores.insert("지웅", 99)
# test_scores.insert("신의", 88)
# test_scores.insert("규식", 97)
# test_scores.insert("태호", 90)
#
# print(test_scores)
#
# # key인 이름으로 특정 학생 시험 점수 검색
# print(test_scores.look_up_value("현승"))
# print(test_scores.look_up_value("태호"))
# print(test_scores.look_up_value("영훈"))
#
# # 학생들 시험 점수 수정
# test_scores.insert("현승", 10)
# test_scores.insert("태호", 20)
# test_scores.insert("영훈", 30)
#
# print(test_scores)
# 삭제 문제
test_scores3 = HashTable_best(50) # 시험 점수를 담을 해시 테이블 인스턴스 생성
# 여러 학생들 이름과 시험 점수 삽입
test_scores3.insert("현승", 85)
test_scores3.insert("영훈", 90)
test_scores3.insert("동욱", 87)
test_scores3.insert("지웅", 99)
test_scores3.insert("신의", 88)
test_scores3.insert("규식", 97)
test_scores3.insert("태호", 90)
# 학생들 시험 점수 삭제
test_scores3.delete_by_key("태호")
test_scores3.delete_by_key("지웅")
test_scores3.delete_by_key("신의")
test_scores3.delete_by_key("현승")
test_scores3.delete_by_key("규식")
print(test_scores3)4. 해시테이블 충돌 Open Addressing
(1) Open Addressing 정의
기존의 Chaining 방법과과 달리 충돌이 있는 경우 선형탐사 혹은 제곱탐사를 이용하여 비어있는 인덱스에 삽입함
여기서 선형탐사란 충돌이 있는 경우 빈 인덱스를 선형적으로 순서대로 하나씩 찾는 방법
제곱탐사란 선형탐사처럼 하나씩이 아니라, 제곱으로 [1의 제곱(1) 2의 제곱(4) 3의제곱(9) 4의제곱(16)] 이용해서 인덱스를 찾음
(2) 탐색 / 삭제 연산
1) 공통점
선형(제곱) 탐사 방식으로 삽입했다면 선형탐사로 탐색하거나 삭제하면됨
2) 탐색 연산 시 주의점
선형탐사로 탐색했음에도 비어있는 인덱스를 찾았다는 것은 곳 데이터가 처음 부터 저장되어 있지 않음을 염두
3) 삭제 연산 시 주의점
선형탐사로 탐색하다가 실질적으로 존재하는 인덱스와 달리 중간에 비어있는 경우 존재하지만 없다고 판단하는 경우가 있음
이를 대비하기 위해 삭제한 부분은 "DELETED" 기록이 중요함
(3) 시간복잡도
| 연산 | 시간 복잡도 (최악의 경우) |
| 삽입 | O(n) |
| 탐색 | O(n) |
| 삭제 | O(n) |
(4) 평균시간 복잡도
1) load factor
해시 테이블 연산 분석 시 load factor 는 중요함
a = load factor / n = 배열 크기 / m = 데이터 쌍 수
α = n / m
2)
해시 테이블에서 평균적 탐사 횟수는 1 / 1-a 보다 적음
배열(n) 100개 중 데이터(m)가 50개가 채워졌다고 하더라도 a 는 0.5임
그렇다면 기대값은 2보다 작기 때문에 탐사를 하더라도 평균 2개의 인덱스만 확인해도 빈칸을 찾을 수 있음
만약 탐사를 10개보다 작게 하겠다고 한다면 load factor가 0.9 가 넘지않게끔 약속하면 됨
'배움 __IL > 자료구조&알고리즘' 카테고리의 다른 글
| DFS / BFS 종합정리 (0) | 2024.08.22 |
|---|---|
| 알고리즘 3줄 정리 [DP : Memoization, ] (1) | 2023.12.28 |
| 알고리즘 3줄 정리 [합병정렬, 퀵정렬] (0) | 2023.12.26 |
| 동적계획법 : 동적계획법 이론과 문제 (0) | 2023.04.02 |
| 그리디 : 그리디 알고리즘 이론과 문제 (0) | 2023.04.02 |