해시 테이블(Hash Table) 딥 다이브
맵(Map)의 강력한 구현체, 해시 테이블
해시 테이블(Hash Table)은 맵(Map) 자료구조를 효율적으로 구현하는 데 널리 사용되는 자료구조이다. 키(key)를 해시 함수(Hash Function)를 통해 해시 값(Hash Value)으로 변환하고, 이 해시 값을 배열의 인덱스로 사용하여 값(value)을 저장한다. 이러한 방식을 통해 빠른 검색, 삽입, 삭제 연산을 지원한다.
해시 함수(Hash Function)
해시 함수는 임의의 길이의 데이터를 고정된 길이의 해시 값으로 변환하는 함수이다. 좋은 해시 함수는 다음과 같은 특징을 가져야 한다.
- 결정론적(Deterministic): 동일한 입력에 대해 항상 동일한 해시 값을 생성
- 균등 분포(Uniform Distribution): 가능한 모든 해시 값에 대해 균등하게 분포
- 빠른 계산(Fast Computation): 해시 값을 빠르게 계산
해시 함수의 구성 요소
- 해시 코드(Hash Code): 키를 정수로 변환하는 함수이다.
- 압축 함수(Compression Function): 해시 코드의 결과를 해시 테이블의 크기에 맞게 조정하는 함수이다.
h2(y) = [(ay + b) mod p] mod N (p는 N보다 큰 소수, a와 b는 0 이상의 정수)충돌(Collision) 해결 방법
해시 함수는 서로 다른 키에 대해 동일한 해시 값을 생성할 수 있다. 이를 충돌(Collision)이라고 한다. 해시 테이블에는 충돌을 효율적으로 해결하기 위한 다양한 방법이 있다.
1. Separate Chaining (분리 연결법)
각 해시 테이블의 슬롯(slot)에 linked list를 사용하여 충돌하는 항목들을 저장한다.
def put(k, v):
i = h(k) # 해시 값 계산
A[i].put(k, v) # linked list에 삽입
2. Linear Probing (선형 탐색법)
충돌이 발생하면 다음 빈 슬롯을 찾을 때까지 순차적으로 탐색한다.
def put(k, v):
i = h(k) # 해시 값 계산
while A[i] is not None: # 빈 슬롯을 찾을 때까지
i = (i + 1) % N # 다음 슬롯으로 이동 (원형 탐색)
A[i] = (k, v)
3. Double Hashing (이중 해싱법)
충돌이 발생하면 두 번째 해시 함수를 사용하여 다음 탐색 위치를 결정한다.
def put(k, v):
i = h(k) # 첫 번째 해시 함수를 통해 초기 위치 계산
d = d(k) # 두 번째 해시 함수를 통해 탐색 간격 계산
while A[i] is not None: # 빈 슬롯을 찾을 때까지
i = (i + d) % N # 다음 슬롯으로 이동 (두 번째 해시 함수 사용)
A[i] = (k, v)
해시 테이블 성능 분석
해시 테이블의 성능은 해시 함수의 품질과 충돌 해결 방법에 따라 달라진다. 이상적인 경우, 해시 테이블의 탐색, 삽입, 삭제 연산은 평균적으로 O(1) 시간 복잡도를 갖는다. 그러나 최악의 경우, 모든 키가 충돌하면 O(n)까지 증가할 수 있다.
로드 팩터(Load Factor): 해시 테이블의 성능을 측정하는 중요한 지표로, 전체 슬롯 수에 대한 저장된 항목 수의 비율을 나타낸다. 로드 팩터가 높을수록 충돌 확률이 높아지므로, 일반적으로 70% 이하로 유지하는 것이 좋다.
(https://hyeonb.blogspot.com/2024/03/blog-post.html)
[자료구조] Map에 대하여
(https://hyeonb.blogspot.com/2024/05/map.html)
