해시 테이블(hash table)의 기본

* 해시(Hash): 임의의 데이터를 고정 길이의 데이터로 매핑하는 것 (Key는 고정 길이일 수도, 아닐 수도)
* 해시 테이블(Hash table): Key에 Value를 저장하는 자료 구조
  - Key 값을 통해 직접 Value 값에 접근이 가능하다
  - 보통 배열로 해시 테이블 공간만큼 생성하여 사용한다
  - 대표적인 예: Python의 Dictionary 타입
                   (python에서는 이 타입을 이용하면 되기 때문에 해시 테이블을 굳이 구현할 필요가 없다)
* 해시 값(Hash value): Key값을 받은 해싱 함수가 특정 연산을 시행하여 반환해주는 값 (고정된 길이)
             이를 통해, 해시 테이블에서 Key에 맞는 Value 값을 일관되게 찾을 수 있다
             (Key값을 구하는 함수를 따로 만들 수 있다)

hash_table = list([0 for i in range(6)])

# ord(): 문자의 ASCII(아스키) 코드 리턴
def get_key(data):
    return ord(data[0]) 

## 6으로 나눈 나머지가 return되기 때문에 
## key 값이 얼마이든 고정된 길이의 값이 반환됨
def hash_func(key):
    return key % 6 
    
def save(data, value):
    address = hash_func(get_key(data))
    hash_table[address] = value 

def value_of_(data):
    address = hash_func(get_key(data))
    return hash_table[address]

save('South Korea', 'Kimchi')
save('Turkey', 'Kebab')
save('United Kingdom', 'Roast Beef')

print(value_of_('South Korea')) # Kimchi
print(value_of_('Turkey')) # Kebab
print(value_of_('United Kingdom')) # Roast Beef
print(hash_table) # ['Kebab', 'Chips', 0, 0, 0, 'Kimchi']

* 장점
  - 데이터 저장/읽기 속도가 빠름 (검색하기가 쉬우므로 속도가 배열보다 빠르다)
  - 중복 확인이 쉽다 (Key의 데이터가 있는지 중복 확인이 쉬움)

* 단점
  - 알반적으로 저장 공간이 데이터의 공간보다 크다
  - Key에 해당하는 주소(슬롯)가 동일할 경우 충돌을 해결해주어야 한다
    (저장공간을 크게 하거나, 추가적인 자료구조 이용)

* 시간 복잡도
  - 일반적으로 O(1)
  - 최악의 경우 O(n)

출처 : FASTCAMPUS