[Algorithm] 해시 테이블

* Python을 기준으로 합니다

---

해시 테이블 (Hash Table)

- 개념

• 해시 테이블 : 키와 값을 매핑해 데이터 양에 상관없이 빠른 탐색을 가능하는 자료구조
  • Python에서는 일반적으로 dictionary 자료형으로 해시 테이블을 활용함
  • 해시 테이블의 탐색은  $O(1)$의 time complexity를 가진다는 장점이 있음
    - 키 자체가 해시 함수에 의해 값이 있는 index가 되기 때문 
  • 따라서 특정 값을 기준으로 조회를 여러번 해야 하거나, 특정 값과 매핑되는 값의 관계를 활용하는 경우 사용 
    - BUT, 완전 탐색이나 정렬, 최대/최소 등이 필요한 경우는 배열이 더 유용함
  • Time Complexity
    1. $O(1)$ : 조회, 값 할당, 키 가져오기 `new_dict.keys()`, 딕셔너리 초기화 `new_dict.clear()`
    2. $O(n)$ : 딕셔너리 할당 `dict(data)`

해시 테이블의 구조

• 해시 함수의 고려사항
  • 해시 함수 : 임의의 데이터를 고정된 데이터로 변환하는 함수
  • 충돌 (Collision) : 서로 다른 두 키에 대해서 해시를 적용할 때, 결과가 동일하게 발생하는 경우
    - 이로 인해 해시의 탐색은 모든 상황에서 항상 $O(1)$을 보장하지 않을 수 있음  
  • 비둘기집 원리 : $n$개 아이템을 $m$개의 컨테이너에 넣을 때, $n>m$이면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 존재한다는 원리
  • 해시 함수의 종류
    
    1. 나눗셈법 : 키를 소수(prime number)로 나누는 modular 연산을 활용
    2. 곱셈법 : 나눗셈법과 비슷하지만 소수를 활용하지 않음
    3. 문자열 해싱 : 키의 자료형이 문자열인 경우 사용, 문자를 숫자로 변환하고 해당 숫자를 값으로 변환
• 해시의 충돌을 방지하는 방법
  • 체이닝 (Chaining) : 충돌 발생 시 충돌되는 데이터를 연결 리스트로 연결하는 방식
    - 충돌이 많아지면 연결 리스트의 길이가 길어지므로 해시 테이블의 공간 활용성이 떨어짐
    - 연결 리스트 구조로 인해 탐색 성능이 떨어짐 (최악의 경우 $O(n)$의 time complexity)
  • 오픈 어드레싱 (Open Addressing) : 충돌 발생 시 다른 빈 공간을 탐색하는 방법
    - 해시 테이블 공간 내에서 탐사 (Probing)을 활용하여 빈 공간을 찾는 방법
    - 모든 값들이 반드시 자신의 해시와 일치하는 주소에 저장된다는 보장이 없음
    - 해시 테이블 내에 연속된 데이터 그룹이 생기는 클러스터링 문제가 발생

Chaining과 Linear Probing의 성능 비교

- 구현

1. dictionary 자료형을 통한 구현

• dictionary 선언

new_dict = { }

• 값 삽입, 조회, 수정, 삭제

#삽입
new_dict['A'] = 1
new_dict['B'] = 2

print(new_dict) #{'A':1, 'B':2}

#조회
key = 'A'
print(new_dict[key]) #1

#수정
new_dict['A'] = 3
print(new_dict) #{'A':3, 'B':2}

#삭제
del new_dict['A']
print(new_dict) #{'B': 2}

2. collections의 defaultdict를 통한 구현

• `collections`를 import하여 `defaultdict()`를 사용할 수 있음
  - 사용 방식은 일반 dictionary와 유사함

import collections

new_dict = collections.defaultdict()

#삽입
new_dict['A'] = 1
new_dict['B'] = 2

print(new_dict) #{'A': 1, 'B': 2}

#조회
key = 'A'
print(new_dict[key]) #1