1. 해시 충돌(Collision) 해결의 두 가지 축
해시 함수를 통해 얻은 해시값이 중복될 때, 이를 처리하는 메커니즘은 크게 두 종류로 분류.
- Open Addressing (개방 주소법): 충돌 발생 시 정해진 규칙에 따라 테이블 내 다른 비어 있는 슬롯을 찾아 데이터를 저장하는 방식.
- Separate Chaining (분리 연결법): 충돌 발생 시 해당 슬롯에 연결 리스트(Linked List)나 트리(Tree)를 연결하여 데이터를 저장하는 방식.
2. Open Addressing 세부 기법
추가적인 메모리 할당 없이 테이블 내 공간을 활용하며, 조사(Probing) 방식에 따라 구분.
| 기법 명칭 | 작동 원리 | 특징 및 단점 |
|---|---|---|
| Linear Probing | 일정한 간격(+1, +2…)으로 건너뛰며 빈 슬롯 탐색. | 특정 영역에 데이터가 몰리는 클러스터링(Clustering) 현상 발생 가능. |
| Quadratic Probing | 제곱수(+1², +2²…) 간격으로 건너뛰며 빈 슬롯 탐색. | 선형 조사법보다 완화되었으나 여전히 클러스터링 취약점이 존재. |
| Double Hashing | 2개의 해시 함수를 사용하여 탐사 이동폭을 결정함. | 클러스터링 문제를 효과적으로 해결하며 탐사 효율이 높음. |
3. Separate Chaining 방식의 특징
추가적인 메모리 구조를 사용하여 충돌을 해결하는 유연한 방식.
- 삽입 연산: 해시값이 중복되면 리스트의 노드를 추가하여 데이터를 저장하며, 시간 복잡도는 O(1).
- 검색/삭제 연산: 기본적으로 O(1)이나, 충돌이 빈번할 경우 리스트를 순회해야 함.
- 최악의 경우 (Worst Case): 모든 데이터가 동일한 해시값을 가져 하나의 리스트로 연결될 경우 O(n)의 성능 저하가 발생.
- 성능 개선: 리스트의 길이가 길어질 경우 Binary Search Tree(BST)를 사용하여 최악의 경우 성능을 O(log n)으로 낮추기도 함.
추가 정리
Q. 이중 해싱(Double Hashing)에서 두 번째 해시 함수의 역할은?
- 첫 번째 함수는 최초 해시값을 얻기 위해, 두 번째 함수는 충돌 발생 시 탐사 이동폭을 일정하지 않게 생성하기 위해 사용.
- 이를 통해 선형/이차 조사법의 고정된 이동폭으로 인한 클러스터링 문제를 방지.
Q. Separate Chaining에서 Tree를 사용하는 기준은?
- 통상적으로 하나의 슬롯에 연결된 노드의 개수가 많아질 때 리스트를 트리로 전환하여 탐색 효율을 높임.
- Java의 HashMap 등 실무 구현체에서도 이 방식을 채택하여 성능을 최적화.
핵심 정리
- 충돌 해결: 추가 메모리를 쓰는 Chaining과 테이블 내 빈 공간을 찾는 Open Addressing으로 나뉨.
- 성능 리스크: Chaining의 최악의 경우 성능은 O(n)이며, Open Addressing은 클러스터링으로 인해 탐색 시간이 증가할 수 있음.
- 면접 포인트: 각 기법의 시간 복잡도 차이와 클러스터링 현상의 원인 및 해결책(이중 해싱 등)을 연관 지어 설명하는 것이 중요.