1. key-value 데이터
- 순서와 상관 없이 key 값을 통해 value에 저장한 정보를 검색할 수 있는 데이터 유형
- 하나의 key에는 하나의 value만 있어야 된다.
2. Direct Access Table
- 배열 인덱스를 키로 이용해서 데이터를 저장하고 가지고 오는 방식
- O(1)으로 key-value 쌍을 저장하고 가져올 수 있다.
- 낭비하는 공간이 많을 수 있다.
3. 해시 테이블 개념
해시 함수(Hash function)
- 특정 값을 원하는 범위의 자연수로 바꿔주는 함수
해시 테이블(Hash table)
- 해시 함수와 배열을 같이 사용하는 자료 구조
- 키를 바로 인덱스로 사용하지 않고 해시 함수에 넣어서 리턴된 값을 인덱스로 사용한다.
4. 해시 함수
해시 함수의 조건
- 한 해시 테이블에서 해시 함수는 결정론적이어야 된다.
- 원하는 범위의 자연수 하나하나가 리턴될 확률이 최대한 비슷해야 된다.
- 빨리 계산을 할 수 있어야 된다.
나누기 방법
- 자연수 key를 해시 테이블의 크기로 나눈 나머지를 리턴하는 함수
- 일대일 함수가 아니기 때문에 충돌이 발생할 수 있다.
곱셈 방법
0 < a < 1인 임의의 a 값을 정한다.- a에 key값을 곱하고 정수 부분은 버린다.
- 마지막으로 남은 소수 부분에 배열의 크기를 곱하고 소수 부분을 버린다.
- 일대일 함수가 아니기 때문에 충돌이 발생할 수 있다.
5. 파이썬 hash 함수
- 파라미터로 받은 객체를 정수 해시 값으로 리턴하는 함수
- 같은 값을 넣으면 항상 같은 정수를 리턴한다.
- 서로 다른 두 값을 파라미터로 넣었을 때 같은 정수가 리턴되지 않는다.
- 만약 서로 다른 두 파라미터가 같은 해시 값을 갖는다면 다른 하나의 해시 값이 변환되어 리턴된다.
- 파라미터로 불변 타입 자료형만 쓸 수 있다.
- 불변 타입 자료형
- 불린형
- 정수형
- 소수형
- 튜플
- 문자열
6. 해시 테이블 충돌과 Chaining 개념
해시 테이블 충돌(Collision)
- 서로 다른 키 값이 같은 해시 값을 갖을 때 충돌하는 문제
Chaining
- 충돌이 일어날 값들을 쇠사슬처럼 엮어서 충돌을 방지하는 기술
- 각 인덱스에 링크드 리스트를 저장하는 방식으로 구현할 수 있다.
- 이 때 링크드 리스트는 key, value 값을 저장하는 노드를 사용한다.
7. Chaining을 쓰는 해시 테이블 탐색 연산
- Key 값을 파라미터로 해시 함수를 실행한다. (O(1))
- 해시 함수 리턴값으로 배열 인덱스에 접근한다. (O(1))
- 해당 인덱스에서 key 값을 갖고 있는 노드를 링크드 리스트에서 탐색한다. (링크드 리스트 길이 m일 때: O(m))
- 배열 탐색은 value 값을 갖는 index를 찾는 것이지만, 해시 테이블 탐색은 key 값을 인풋으로 줘서 value 값을 찾는 것이기 때문에 일반적으로 더 빠르다.
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Hash 함수가 제대로 설계됐을 경우에 average time complexity가 O(1)이다.
8. Chaining을 쓰는 해시 테이블 삽입 연산
- Key 값을 파라미터로 해시 함수를 실행한다. (O(1))
- 해시 함수 리턴값으로 배열 인덱스에 접근한다. (O(1))
- 해당 인덱스에서 key 값을 갖고 있는 노드를 링크드 리스트에서 탐색한다. (링크드 리스트 길이 m일 때: O(m))
- key 값을 갖고 있는 노드가 있을 경우 그 노드를 수정하고, 없을 경우 링크드 리스트에 새로운 노드로 저장한다. (O(1))
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Hash 함수가 제대로 설계됐을 경우에 average time complexity가 O(1)이다.
9. Chaining을 쓰는 해시 테이블 삭제 연산
- Key 값을 파라미터로 해시 함수를 실행한다. (O(1))
- 해시 함수 리턴값으로 배열 인덱스에 접근한다. (O(1))
- 해당 인덱스에서 key 값을 갖고 있는 노드를 링크드 리스트에서 탐색한다. (링크드 리스트 길이 m일 때: O(m))
- key 값을 갖고 있는 노드가 있을 경우 그 노드를 삭제한다. (O(1))
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Hash 함수가 제대로 설계됐을 경우에 average time complexity가 O(1)이다.
10. Chaining을 쓰는 해시 테이블 구현
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)
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:
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)
if existing_node is not None:
existing_node.value = value
else:
linked_list = self._get_linked_list_for_key(key)
linked_list.append(key, value)
def delete_by_key(self, key):
"""주어진 key에 해당하는 key - value 쌍을 삭제하는 메소드"""
node_to_delete = self._look_up_node(key)
if node_to_delete is not None:
linked_list = self._get_linked_list_for_key(key)
linked_list.delete(node_to_delete)
def __str__(self):
"""해시 테이블 문자열 메소드"""
res_str = ""
for linked_list in self._table:
res_str += str(linked_list)
return res_str[:-1]
test_scores = HashTable(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, "\n")
# 학생들 시험 점수 삭제
test_scores.delete_by_key("태호")
test_scores.delete_by_key("지웅")
test_scores.delete_by_key("신의")
test_scores.delete_by_key("현승")
test_scores.delete_by_key("규식")
print(test_scores)"규식: 97"
"태호: 90"
"지웅: 99"
"신의: 88"
"현승: 85"
"동욱: 87"
"영훈: 90"
85
90
90
"규식: 97"
"태호: 20"
"지웅: 99"
"신의: 88"
"현승: 10"
"동욱: 87"
"영훈: 30"
"영훈: 30"
"동욱: 87"11. Open Addressing을 이용한 충돌 해결
Open Addressing
- 충돌이 일어날 값을 아직 사용되지 않는 인덱스에 대체 할당하여 충돌을 방지하는 기술
- 아직 사용되지 않은 인덱스는 선형 탐사(Linear probing), 제곱 탐사(Quadratic probing)같은 방법을 통해 검색한다.
- Closed hasing이라고도 한다.
선형 탐사
- 충돌이 일어났을 때, 빈 인덱스를 하나씩 순서대로, 선형적으로 찾는 방법
제곱 탐사
- 충돌이 일어났을 때, 빈 인덱스를 제곱한 값(1, 4, 9, 16, ...)을 더한 순서대로 찾는 방법
Open addressing 삽입 시간 복잡도
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Hash 함수가 제대로 설계됐을 경우에 average time complexity가 O(1)이다.
12. Open Addressing 탐색/삭제 연산
탐색
- Key 값을 파라미터로 해시 함수를 실행한다. (O(1))
- 해시 함수 리턴값으로 배열 인덱스에 접근한다. (O(1))
- 해당 인덱스에 key 값이 있다면 value를 리턴한다. (O(1))
- 해당 인덱스에 key 값이 없다면 open adressing에서 정한 탐사 방법대로 빈 인덱스를 발견하기 전까지 탐색을 시작한다. (시작 인덱스로부터 인접한 인덱스의 길이가 m일 때: O(m))
- 탐색 중에 빈 인덱스에 도착했다는 것은 해시 테이블에 해당 key가 존재하지 않는다는 뜻이다.
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Hash 함수가 제대로 설계됐을 경우에 average time complexity가 O(1)이다.
삭제
- Key 값을 파라미터로 해시 함수를 실행한다. (O(1))
- 해시 함수 리턴값으로 배열 인덱스에 접근한다. (O(1))
- 해당 인덱스에 key 값이 있다면 해당 data를 삭제한다. (O(1))
- 해당 인덱스에 key 값이 없다면 open adressing에서 정한 탐사 방법대로 빈 인덱스를 발견하기 전까지 탐색을 시작한다. (시작 인덱스로부터 인접한 인덱스의 길이가 m일 때: O(m))
- key 값을 발견하면 해당 데이터를 삭제한다. (O(1))
- Data를 삭제할 때 해당 index를 빈 값으로 둔다면, 나중에 탐사를 실행할 때 큰 문제가 될 수 있다.
- 그러므로 삭제한 인덱스를 빈 값으로 두지 않고 "DELETED" 같은 약속된 표시를 해줘야 한다.
- 메모리 최적화를 위해, 주기적으로 삭제 표시를 지우고 탐사가 정상적으로 실행될 수 있도록 나머지 인덱스를 옮기는 방법을 사용할 수 있다.
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Hash 함수가 제대로 설계됐을 경우에 average time complexity가 O(1)이다.
13. Open Addressing을 쓰는 해시 테이블 평균 시간 복잡도
load factor α
- 전체 크기에 대해 실제 사용중인 크기의 비율
α = n/m, m은 배열의 크기, n은 해시 테이블 안의 데이터 쌍 수
Open Addressing을 쓰는 해시 테이블 평균 시간 복잡도
- 삽입, 탐색, 삭제 연산의 Average time complexity는
1 / (1 - α)보다 작다. (O(1))
Feedback
- Complexity를 분석할 때, 수학적으로 분석해보자.
- 해시 테이블의 open addressing을 파이썬으로 구현해보자.
- "DELETED" 같은 약속된 표시를 어떻게 하는지 찾아보자.
- 해시 테이블의 삭제된 데이터를 메모리 최적화하는 방법을 찾아보자.
참고 자료
job's done