[Python] 해시 테이블 (Hash Table)

key-value 쌍(매핑)을 통해 빠르게 삽입, 탐색, 삭제 하는데 사용되는 자료구조

https://www.geeksforgeeks.org/hash-table-data-structure/?ref=header_outind

개요

키 값을 해시 함수를 통해 값을 변환시키고, 해시값을 이용해 데이터가 저장된 배열 내 인덱스를 구함. 그 인덱스를 통해 테이블 내에 데이터를 저장하거나, 탐색을 함

예시 (banana라는 key 를 사용해 2000이란 값에 접근)

hash_table = {'apple': 1000, 'banana': 2000, 'melon': 3000}
print(hash_table['banana'])  # 2000

해싱 (Hashing)이란?

해시 함수를 사용해 다양한 크기의 입력을 고정된 길이의 출력값으로 생성해주는 절차. 자료구조에서 저장소를 위한 인덱스 또는 위치값을 결정하는 방식으로 사용된다.

해싱의 구성요소

1. key : 자료구조의 인덱스값을 해시함수를 통해 결정하기 위한 문자 또는 숫자열이 될 수 있음
2. 해시 함수 (Hash Function) : 입력 키를 받고, 해시 테이블(배열) 안에있는 요소의 인덱스로 반환해줌. 인덱스는 hash index로 불림
3. 해시 테이블

해시 함수 (Hash function)

임이 길이의 입력값을 고정 길이 출력값으로 변환하는 함수. key를 index로 매핑하는데 사용

좋은 함수의 조건은 계산이 빨라야 하고, 키들이 배열 전체에 균등하게 분포 되어야하며, 충돌을 최소화해야함.

함수의 구현은 Integer Universe Assumption 이라는 가정을 사용하여 5가지 해싱방식을 사용함.

• Integer Universe Assumption
  • 해싱에 사용되는 모든 key를 정수형이라고 가정. 즉, 키들이 미리 정해진 범위 내 정수(ex. 0~1,000,000)로 제한된다고 보는 것
  • 이러한 가정을 바탕으로 수학연산으로 간단히 해시 함수를 설계

함수 구현의 종류

1. 단순 해싱
   구현이 쉽고 계산이 단순한 기본적인 해싱
   • 나눗셈 법(Division method) : 키(key)를 해시테이블의 크기(m)로 나눈 나머지를 해시 값으로 사용
   • 곱셈법(Multiplication method) : 키(key)에 특정 상수 (A)를 곱한 후, 결과의 소수 부분만 사용. 그 후 소수 부분을 배열 크기(m)으로 곱해 인덱스를 획득
     h(k) = ⌊m * (kA mod 1)⌋ 상수 A는 보통 0~ 1 사이의 실수, 대표적으로는 황금비의 역수(0.618033) 을 사용
2. 복합적 해싱 (Complex / Advanced Hashing)
   • 범용 해싱(Universal hashing) : 하나의 해시 함수를 사용 하는 대신 여러개의 함수 중 랜덤하게 골라 사용
   • 완벽 해싱(Perfect hashing) : 충돌이 전혀 없는 해싱 방법. 키의 개수가 미리 정해져있거나 변하지 않을 때 사용
   • 이중 해싱(Double hashing) : 충돌 시 두 번째 해시 함수를 사용해 새로운 위치를 찾음

해시충돌 (Hash Collision)

보통 해시 함수는 입력의 범위(정의역)보다 출력의 범위(치역)이 작아, 해시 함수를 통과한 서로 다른 두 키가 같은 인덱스로 매핑되는 상황이 발생할 수 있음. 이러한 상황을 해시 충돌이라고 함

키: apple → 5글자 % 4 → 1
키: melon → 5글자 % 4 → 1 (apple과 충돌!)
# 예시
print(hash_division(5, 4))  # 출력: 1 ('apple')
print(hash_division(9, 4))  # 출력: 1 ('melon'), 충돌 발생

이는 다양한 방법으로 해결이 가능하다

1. 체이닝 (Chaining)
   • 충돌 발생 시 각 인덱스를 연결 리스트 로 만들어 다수의 데이터를 저장함
2. 개방 주소법 (Open Addressing)
   • 충돌 발생 시 다른 빈 공간을 찾아 저장
     • 선형 조사법(Linear Probint) : 충돌 시 바로 다음 빈 인덱스 탐색
     • 이차 조사법(Quadratic Probing) : 충돌 시 일정한 규칙으로 떨어진 곳 탐색
     • 이중 해싱(Double Hashing) : 충돌 시 다른 해시 함수를 써서 재계산
3. (번외) RobinHood Hashing : 충돌 발생 시 탐색 거리를 비교하여 가장 긴 거리를 가진 키를 우선적으로 더 좋은 위치로 이동. 즉 전체적으로 탐색거리를 균등하게 분배

장점

• 키를 알고 있다면, 데이터를 빠르게 검색하거나 삽입 할 수 있음. 평균적으로 O(1), 최악의 경우(모든 키 충돌 시) O(n)
• 키-값 쌍으로 인해 데이터를 다룰때 직관적으로 운용가능

단점

• 공간 효율성 문제
  • 배열의 크기를 크게 잡으면 공간이 낭비되고, 작게 잡으면 충돌 확률이 높아짐
• 충돌 문제
  • 충돌처리를 잘못 할 경우 성능 저하가 극심
• 테이블은 데이터가 정렬되지 않으며 순서보장이 어려움