해쉬 테이블 (Hash Table)
1. 해쉬 구조
•
Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조
◦
Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
◦
파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
◦
보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
◦
파이썬에서는 해쉬를 별도 구현할 이유가 없음 - Dictionary
•
해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
•
해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
•
해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
•
해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고,
이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
•
슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
•
저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음
2. 자료 구조 해쉬 테이블의 장단점과 주요 용도
•
장점
◦
데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
◦
해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
•
단점
◦
일반적으로 저장공간이 좀더 많이 필요하다.
◦
여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
•
주요 용도
◦
검색이 많이 필요한 경우
◦
저장, 삭제, 읽기가 빈번한 경우
◦
캐쉬 구현시 (중복 확인이 쉽기 때문)
3. 충돌(Collision) 해결 알고리즘
3.1. Chaining 기법
•
개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
•
충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
hash_table = list([0 for i in range(8)])
def get_key(data):
return hash(data)
def hash_function(key):
return key % 8
def save_data(data, value):
index_key = get_key(data) # 단순 hash값만 가지고는 여러개의 값중에서 내가 원하는 값을 찾을 수 없으므로 key/hash값을 둘 다 저장
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0:
for index in range(len(hash_table[hash_address])):
if hash_table[hash_address][index][0] == index_key: #기존 값이 있다면 갱신
hash_table[hash_address][index][1] = value
return
hash_table[hash_address].append([index_key, value]) #기존 값 없으면 새로 추가
else:
hash_table[hash_address] = [[index_key, value]]
def read_data(data):
index_key = get_key(data)
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0:
for index in range(len(hash_table[hash_address])):
if hash_table[hash_address][index][0] == index_key:
return hash_table[hash_address][index][1]
return None
else:
return None
Plain Text
복사
3.2. Linear Probing 기법
•
폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
•
충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
◦
저장공간 활용도를 높이기 위한 기법
hash_table = list([0 for i in range(8)])
def get_key(data):
return hash(data)
def hash_function(key):
return key % 8
def save_data(data, value):
index_key = get_key(data) # 단순 hash값만 가지고는 여러개의 값중에서 내가 원하는 값을 찾을 수 없으므로 key/hash값을 둘 다 저장
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0:
for index in range(hash_address, len(hash_table)):
if hash_table[index] == 0: # 비어있다면
hash_table[index] = [index_key, value]
return
elif hash_table[index][0] == index_key: #기존값
hash_table[index][1] = value
return
else: #처음부터 비어있다면
hash_table[hash_address] = [index_key, value]
def read_data(data):
index_key = get_key(data)
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0:
for index in range(hash_address, len(hash_table)):
if hash_table[index] == 0:
return None
elif hash_table[index][0] == index_key:
return hash_table[index][1]
else:
return None
Plain Text
복사
참고: 해쉬 함수와 키 생성 함수
•
파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음
•
유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
◦
어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능
import hashlib
data = 'test'.encode() #바이트 형태로 변환
hash_object = hashlib.sha256() #sha256
hash_object.update(data)
hex_dig = hash_object.hexdigest() #16진수형태로 변환
print (hex_dig)
Plain Text
복사
4. 시간 복잡도
•
일반적인 경우(Collision이 없는 경우)는 O(1)
•
최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음
검색에서 해쉬 테이블의 사용 예
•
n개의 배열에 데이터를 저장하고, 검색할 때 O(n)
•
n개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)
