해시 테이블은 (Key, Value)쌍으로 저장하는 자료 구조이다.
해시 테이블의 데이터에 접근하는 방식은 다음과 같다.

• 각각의 key에 hash 함수를 적용하여 index를 찾는다.
• 이 찾은 index로 값을 저장하거나 검색한다. 이 때 실제 값이 저장되는 장소를 bucket 또는 slot이라고 한다.

데이터 저장

---

그림과 같이 ("John Smith", "521-1234") 데이터를 16 크기를 가진 해시 테이블에 저장한다고 하자.

1. 우선 해시 함수를 만들어 보자.

def hash_func(key):
	return (key - 8) % 16 # ord()는 문자의 ASCII 값을 찾아준다.

2. "John Smith"에 해시 함수를 적용하여 index를 찾은 후, 찾은 index에 데이터를 저장한다.

def save_data(data, value):
	key = ord(data[0]) # 74
    hash_address = hash_func(key) # 2
    hash_table[hash_address] = value
    
save_data("John Smith", "521-1234")

데이터 검색

---

검색할 데이터에 대해 해시 함수를 적용하여 index를 찾은 후 해당 index의 데이터를 불러온다.

def get_data(data):
	key = ord(data[0])
    hash_address = hash_func(key)
    
    return hash_table[hash_address]
    
get_data("John Smith")

해시 테이블 장단점

---

장점

• 데이터 저장/읽기가 빠르다. (검색 속도가 빠르다)
  -> key값으로 데이터를 찾을 때 해시 함수 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/조회/삭제할 수 있다.
  -> 해시 테이블의 평균 시간 복잡도는 $O(1)$이다.
• Key에 대한 데이터가 있는지 (중복) 확인이 쉽다.

단점

• 저장공간이 좀 더 필요하다.
• 여러 Key에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
  
  

해시 충돌(Hash Collision)

---

해시 테이블의 가장 큰 문제는 충돌이다. 예를 들어 위 예에서 "James Malin"를 추가하여 해시 함수를 돌려보면 "John Smith"의 index 값 2와 충돌하게 된다.

이러한 충돌을 해결하기 위해 크게 2가지를 적용해볼 수 있다.

• 분리 연결법 (Separate Chaining)
• 개방 주소법 (Open Addressing)

분리 연결법

해시 테이블의 저장공간 외의 공간을 활용하는 기법이다. 충돌이 일어나면 링크드 리스트같은 자료구조를 사용하여 데이터를 추가를 뒤에 연결시키는 기법이다.
다음과 같이 연결할 수 있다.

hash_table = [0 for i in range(8)]
# [0, 0, 0, 0, 0, 0, 0, 0]

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_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        hash_table[hash_address].append([index_key, value]) # chaining
    else:
        hash_table[hash_address] = [[index_key, value]] # insert

save_data('Dd', '1201')
save_data('Data', '3301')
print(hash_table)
# [[[-3861416235556576752, '1201'], [6581991383312608576, '3301']], 0, 0, 0, 0, 0, 0, 0]

개방 주소법

추가 메모리를 사용하는 Chaining 방식과 달리 해시 테이블의 공간을 활용하는 방법

1. Linear Probing : index를 고정폭만큼 이동하며 비어있는 공간을 활용
2. Quadratic Probing : 충돌 시마다 폭을 제곱만큼 이동하는 방식 $1, 2^2, 3^2, ...$
3. Double Hashing Probing : 해시값을 한 번 더 해싱하여 해시 규칙성을 없애는 방식

고정 해시 반환

---

hash() 함수는 실행될 때마다 값이 달라질 수 있다.
SHA(Secure Hash Algorithm)같은 해시 함수는 유일한 고정된 크기의 고정값을 return한다.

SHA-1

import hashlib

hash_object = hashlib.sha1()
hash_object.update('test'.encode())
hex_dig = hash_object.hexdigest()
print(hex_dig)
# a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

SHA-256

import hashlib

hash_object = hashlib.sha256()
hash_object.update('test'.encode())
hex_dig = hash_object.hexdigest()
print(hex_dig)
# 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08