해시 테이블(Hash Table)
해시 테이블은 key-value형태로 데이터를 저장하는 자료구조로, 일반적인 경우 O(1)의 시간복잡도로 값을 탐색할 수 있다.
1. Direct Access Table
우리가 저장할 key-value 쌍들이 있을 때 key값 중 가장 큰 숫자만큼의 배열을 생성한 뒤 해당 인덱스에 value를 저장하면, value에 접근하고 싶을 때 key를 통해 바로 접근할 수 있으므로 O(n)의 시간복잡도를 가진다. 이를 Direct Access Table이라고 한다.
data = [(57, "고영희"), (208, "강아지"), (900, "고릴라")]
max_index = 0
for key, value in data:
if key > max_index:
max_index = key
direct_access_table = [None] * (max_index + 1)
for key, value in data:
direct_access_table[key] = value
print(direct_access_table[57])
print(direct_access_table[900])
print(direct_access_table[600])고영희
고릴라
None
현재 key의 max값인 고릴라의 key가 900이기 때문에 큰 문제가 없지만, 만약 10^100을 키로 가진 데이터가 나타나면 10^100 + 1 크기 만큼의 배열을 생성해야 하므로 문제가 발생한다. 즉 낭비되는 공간이 너무 클 가능성이 있다.
2. 해시 함수(Hash Function)
해시함수는 특정 값을 원하는 범위의 자연수로 바꿔주는 함수, 즉 임의의 길이를 가진 데이터를 입력받아 고정된 길이의 해시값으로 변환하는 함수다.
해시 함수의 조건은 여러가지가 있다. (1) 한 해시 테이블의 해시 함수는 결정론적이어야 한다. 즉 같은 key을 입력값으로 넣었을 때는 항상 같은 결과가 나와야 한다. (2) 결과 해시값이 치우치지 않고 고르게 나와야 한다. 따라서 원하는 범위가 0 ~ 100 사이의 자연수라면 아무 숫자를 넣었을 때 결과가 0 ~ 100 사이에서 최대한 고르게 나와야 한다. (3) 빨리 계산할 수 있어야 한다. 해시 테이블에서 모든 연산에 해시 함수가 사용되므로 최대한 효율적인 해시 함수를 사용해야 한다.
이를 모두 만족하는 해시 함수를 만드는 방법은 생각보다 다양한데, 가장 간단한 방법으로는 버킷 크기만큼의 숫자로 나눈 나머지를 사용하는 모듈러(Modulo)연산이 있다. 그 밖에도 MD5, SHA-1, 블록체인에 사용되는 SHA-2의 SHA256 등등이 있다.
가장 간단한 모듈러 연산을 통한 해시 함수를 보면 다음과 같다.
def hash_function(key, array_size):
return key % array_size
data = [(57, "고영희"), (208, "강아지"), (900, "고릴라")]
for key, value in data:
print(hash_function(key, 4))1
0
0
3. 해시 테이블 충돌(Collision)
위의 해시 함수를 이용해 버킷의 크기를 4로 하고 208과 900을 계산했을 때 둘다 0이 나왔다. 해시값을 이용해 버킷에 넣어야 하는데 둘다 0이므로 한 인덱스에 두 개의 데이터 쌍을 저장해야하는 경우가 생겼다. 이렇게 이미 사용하고 있는 인덱스에 새로운 key-value쌍을 저장해야 할 경우를 충돌이 일어났다고 한다.
이를 해결하는 방법은 크게 두 가지로 나눌 수 있는데 첫번째로는 체이닝(Chaining), 두번째로는 오픈 어드레싱(Open Addressing)이다. 체이닝 방식은 각 버킷 인덱스에 단순하게 값을 저장하는 것이 아니라 링크드 리스트를 연결해 중복되는 해시값을 가진 값들을 연속해서 연결하는 것이다. 오픈 어드레싱 방식은 해당 버킷의 인덱스를 다른 데이터 쌍이 차지하고 있다면 인접한 다른 인덱스를 사용하도록 하는 것이다.
4. 체이닝
다음은 해시함수는 모듈러 연산, 충돌 방지는 더블리 링크드 리스트를 이용한 해시테이블을 파이썬으로 구현해본 것이다. 실제로 자바의 HashMap이 체이닝 방식으로 구현되어 있다.
class Node:
"""링크드 리스트 노드"""
def __init__(self, key, value) -> None:
self.key = key
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self) -> None:
self.head = None
self.tail = None
def find_node_at(self, index):
iterator = self.head
for _ in range(index):
iterator = iterator.next
return iterator
def find_node_with_key(self, key):
iterator = self.head
while iterator is not None:
if iterator.key == key:
return iterator
iterator = iterator.next
return None
def __str__(self) -> str:
s_str = ""
iterator = self.head
while iterator is not None:
s_str += "{}: {}\n".format(iterator.key, iterator.value)
iterator = iterator.next
return s_str
def append(self, key, value):
"""링크드 리스트 추가 연산 리스트"""
new_node = Node(key, value)
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 self.head == self.tail:
self.head = None
self.tail = None
elif self.head == node_to_delete:
self.head = self.head.next
self.head.prev = None
elif self.tail == node_to_delete:
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
class HashTable:
"""해시 테이블 클래스"""
def __init__(self, capacity) -> None:
self._capacity = capacity
self._table = [DoublyLinkedList() for _ in range(self._capacity)]
def _hash_function(self, key):
"""나머지 연산을 통한 해시 함수"""
return hash(key) % self._capacity
def look_up_value(self, key):
"""키로 값을 찾는 메소드"""
return self._table[hash(key) % self._capacity].find_node_with_key(key).value
def insert(self, key, value):
"""삽입 메소드"""
linked_list = self._table[hash(key) % self._capacity]
if linked_list.find_node_with_key(key) is not None:
linked_list.find_node_with_key(key).value = value
else:
linked_list.append(key, value)
def delete_by_key(self, key):
"""삭제 메소드"""
linked_list = self._table[hash(key) % self._capacity]
if linked_list.find_node_with_key(key) is not None:
linked_list.delete(linked_list.find_node_with_key(key))
def __setitem__(self, key, value):
self.insert(key, value)
def __getitem__(self, key):
return self.look_up_value(key)
def __str__(self) -> str:
res_str = ""
for linked_list in self._table:
res_str += str(linked_list)
return res_str[:-1]
hash_table = HashTable(3)
hash_table.insert(1, "김밥")
hash_table.insert(2, "치킨")
hash_table.insert(3, "피자")
hash_table.insert(4, "나물")
hash_table.insert(5, "볶음밥")
hash_table.insert(6, "콜라")
hash_table.insert(7, "순대")
hash_table.insert(8, "마늘")
hash_table.insert(9, "파스타")
print(hash_table)3: 피자
6: 콜라
9: 파스타
1: 김밥
4: 나물
7: 순대
2: 치킨
5: 볶음밥
8: 마늘
5. 오픈 어드레싱
다음은 해시 함수는 모듈러 연산, 그리고 충돌 방지는 오픈 어드레싱의 Linear Probing(선형 탐사)를 이용한 해시 테이블 구현 코드다. 오픈 어드레싱 방식은 파이썬의 딕셔너리에서 채택하고 있는 방식이다. 오픈 어드레싱은 연속적인 공간 안에 데이터들을 저장하므로 밀도가 낮을 때(=load factor가 낮을 때)는 캐시 효율이 높다. 하지만 배열의 크기가 커질수록 캐시 적중률이 급격히 떨어지고 속도도 느려진다. 따라서 파이썬에서는 load factor를 0.66정도로 낮게 잡아 해결하고 있다.
class HashTableOpenAddressing:
DELETED = "<DELETED>"
def __init__(self, capacity) -> None:
self._capacity = capacity
self._table = [None] * capacity
self._size = 0
def _hash_function(self, key):
"""모듈러 방식 해시 함수"""
return key % self._capacity
def _find_bucket(self, key):
"""키를 이용해 맞는 버킷 찾는 메소드"""
bucket = self._hash_function(key)
first_bucket = bucket
while self._table[bucket] is not None and self._table[bucket] != self.DELETED and self._table[bucket][0] != key:
bucket = (bucket + 1) % self._capacity
if bucket == first_bucket:
return None
return bucket
def look_up_value(self, key):
"""key를 이용해 value를 반환하는 메소드"""
bucket = self._find_bucket(key)
if self._table[bucket] is not None:
return self._table[bucket][1]
return None
def _resize(self):
"""load factor가 특정값 이상일 때 테이블 크기를 두배로 증가하는 메소드"""
old_table = self._table
self._capacity *= 2
self._table = [None] * self._capacity
self._size = 0
for entry in old_table:
if entry is not None and entry != self.DELETED:
self.insert(entry[0], entry[1])
def insert(self, key, value):
"""삽입 메소드"""
if self._size / self._capacity > 0.7: # Load factor > 0.66
self._resize()
bucket = self._find_bucket(key)
if self._table[bucket] is None or self._table[bucket] == self.DELETED:
self._size += 1
self._table[bucket] = (key, value)
def delete_by_key(self, key):
"""값 삭제 메소드"""
bucket = self._find_bucket(key)
if self._table[bucket] is not None and self._table[bucket][0] == key:
self._table[bucket] = HashTableOpenAddressing.DELETED
self._size -= 1
def __setitem__(self, key, value):
self.insert(key, value)
def __getitem__(self, key):
return self.look_up_value(key)
def __str__(self):
return ', '.join(str(item) for item in self._table if item is not None)
hash_table = HashTableOpenAddressing(5)
hash_table[1] = "김밥"
hash_table[9] = "파스타"
hash_table[6] = "콜라"
print(hash_table._table)
hash_table.delete_by_key(6)
print(hash_table._table)
hash_table[6] = "감자피자"
print(hash_table._table)
hash_table[2] = "치킨"
hash_table[3] = "피자"
hash_table[4] = "나물"
hash_table[5] = "볶음밥"
hash_table[7] = "순대"
hash_table[8] = "마늘"
print(hash_table)
print(hash_table._table)[None, (1, '김밥'), (6, '콜라'), None, (9, '파스타')]
[None, (1, '김밥'), '<DELETED>', None, (9, '파스타')]
[None, (1, '김밥'), (6, '감자피자'), None, (9, '파스타')]
(1, '김밥'), (2, '치킨'), (3, '피자'), (4, '나물'), (5, '볶음밥'), (6, '감자피자'), (7, '순대'), (8, '마늘'), (9, '파스타')
[None, (1, '김밥'), (2, '치킨'), (3, '피자'), (4, '나물'), (5, '볶음밥'), (6, '감자피자'), (7, '순대'), (8, '마늘'), (9, '파스타'), None, None, None, None, None, None, None, None, None, None]
오픈 어드레싱 방식에서 주목해야 할 것은_find_bucket함수에서 비어있는 버킷을 찾을 때까지 while연산을 계속해서 수행한다는 점, insert메소드에서 (현재 데이터의 개수) / (전체 배열의 크기) = Load Factor가 어느 크기 이상일 때 배열의 크기를 두배로 늘리는 _resize 메소드를 호출한다는 점, delete_to_key 메소드에서 값을 삭제할 때 해당 버킷 자체를 삭제하는 것이 아니라 그 공간을 DELETED 상수를 이용해 별도의 값으로 수정한다는 점이 있다.
예를 들어 버킷의 총 크기가 5인 공간에 데이터를 삽입할 때 키가 1, 6, 11인 데이터가 연속적으로 들어갔다고 생각해보자. 이 세 데이터는 모두 인덱스가 1인 공간에 삽입이 되려 하지만 키가 1인 데이터가 먼저 차지했으므로 차례대로 다음 버킷에 저장될 것이다. 그 상태에서 키가 6인 데이터가 None으로 삭제되었다면, 추후에 키가 11인 데이터를 찾고자할 때 이미 앞서서 None이 되어버린 데이터 때문에 탐색할 수 없다. 그래서 별도의 값인 DELETED를 만들어 해결하는 것이다.
'프로그래밍 > Computer Science' 카테고리의 다른 글
| [Data Structure] 분리 집합 (Disjoint Set) (0) | 2023.09.21 |
|---|---|
| [Data Structure] NonLinear - (1) Binary Tree (0) | 2023.09.19 |
| [Data Structure] Linear - (6) Queue (0) | 2023.09.13 |
| [Data Structure] Linear - (5) Stack (0) | 2023.09.13 |
| [Data Structure] Linear - (4) Deque (0) | 2023.09.12 |