[자료구조] 해쉬 테이블 (Hash table)

1. 구조와 용도 

방대한 데이터를 고정된 길이로 변환하는 기능을 말합니다. 
키key에 데이터data를 저장하는 데이터 구조이며, 키를 통해 데이터를 바로 받아올 수 있어 획기적으로 속도가 빠른 자료구조입니다.  
파이썬에서는 dictionary type과 방식이 같으므로 별도의 구현 없이 딕셔너리를 사용하면 됩니다. 

검색이 많이 필요한 경우, 저장과 삭제 및 읽기가 빈번한 경우, 웹 프로그래밍 시 캐쉬의 구현(중복 확인)이 필요한 경우에 사용합니다. 

2. 용어

Hash 해쉬: 임의의 값을 고정 길이로 변환하는 것
Hash table 해쉬 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터구조 
Hashing Function 해싱 함수: 키에 대해 산술연산을 이용해 데이터 위치를 찾을 수 있는 함수 혹은 임의의 데이터(키)를 특정 값(해시값)으로 매핑시키는 함수, 시간 복잡도: $ O(1) $
Hash value / Hash address 해쉬값 / 해쉬 주소: 키를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해쉬 테이블에서 키에 대한 데이터 위치를 찾을 수 있음
Slot 슬롯: 한 개의 데이터를 저장할 수 있는 공간 

3. 구현

#빈 리스트 생성
hash_table = list([0 for i in range(10)])
hash_table

#hash function 생성
def hash_func(key):
    return key % 10 #0~9까지의 key 부여 가능
    
#키와 데이터를 저장하는 함수
def storage_data(data, value):
    key = ord(data[0]) #ord(): 문자의 ASCII(아스키)코드를 return해주는 함수
    hash_address = hash_func(key)
    hash_table[hash_address] = value
    
#이름과 전화번호 저장
storage_data('A', '0105533')
storage_data('D', '0104433')
storage_data('F', '0102233')

#특정 주소의 데이터를 가져오는 함수 만들기
def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]
    
get_data('A') #print : '0105533'

#해쉬 key를 부여하는 함수
hash(data)

하지만 hash()의 경우 커널을 재시작할 때 주소가 매번 다시 부여되므로 고정된 값이 필요할 때에는 적합하지 않습니다. 

4. 장/단점

▶장점
 배열에 비해 탐색 속도가 빠릅니다.  
 해쉬는 키에 대한 데이터가 있는지, 즉 중복을 확인하기가 쉽습니다. 배열의 경우 기존 데이터를 하나하나 탐색해야 하지만 해쉬는 키 값을 통해 중복을 찾을 수 있기 때문입다. 
▶단점
  데이터가 존재하지 않는 경우에도 키 값을 배정해두어야 하기 때문에 일반적으로 저장공간이 더 많이 필요합니다. 
  여러 키에 해당하는 주소가 같을 경우 충돌이 발생하므로 이를 해결하기 위한 별도의 자료구조가 필요합니다. 

5. 충돌 해결 알고리즘

Dolphin과 주소가 같은 Dugong이 삽입될 경우

▶ Chaining 기법
 Open hashing 기법 중 하나. 충돌이 일어나면 링크드리스트를 이용해 데이터를 뒤에 추가로 연결시키는 방법
 한 개의 주소에 한 개 이상의 데이터가 있을 경우 해당 주소에서 키 값을 참조하여 데이터를 찾을 수 있도록 하는 구현이 필요하다.

▶ Linear Probing 기법 
 Close hashing 기법 중 하나. 충돌이 일어나면 다음 주소부터 시작하여 나오는 비어있는 공간에 저장하는 방법
 주소에 이미 데이터가 있고 넣어주려는 데이터의키가 동일하다면 value만 업데이트, 다르다면 다음의 비어있는 공간에 해당 키와 데이터를 저장해줍니다. 
 일단 해당하는 주소를 찾고, 찾고자 하는 키 값과 매칭이 될 때까지 hash table을 순회해야 합니다.  

6. 시간복잡도

충돌이 없는 경우 : $ O(1) $
최악의 경우 (충돌이 모두 발생하는 경우) : $O(n)$