개방 주소법
충돌 발생 시 다른 배열을 추가하지 않고, 같은 배열 내에서 빈 슬롯을 탐색하여 저장하는 방식입니다.
핵심 아이디어
충돌 발생 → 다른 빈 슬롯을 찾아 저장
모든 데이터를 하나의 배열 안에서 해결
탐사 방식 3가지
1. 선형 탐사 (Linear Probing)
충돌 시 index+1, index+2, index+3 ... 순서로 탐색
index 3에 충돌 → 4 → 5 → 6 ... 빈 슬롯 발견 시 저장
| 장점 | 단점 |
|---|
| 구현 간단 | 클러스터링 심함 (데이터 몰림 현상) |
2. 이차 탐사 (Quadratic Probing)
충돌 시 index+1², index+2², index+3² ... 순서로 탐색
index 3에 충돌 → 4 → 7 → 12 ... 빈 슬롯 발견 시 저장
| 장점 | 단점 |
|---|
| 선형 탐사보다 클러스터링 감소 | 같은 해시값이면 탐사 경로 동일 |
3. 이중 해싱 (Double Hashing)
두 번째 해시 함수로 탐사 간격을 결정
index + 1 * hash2(key)
index + 2 * hash2(key)
index + 3 * hash2(key)
| 장점 | 단점 |
|---|
| 클러스터링 거의 없음 | 해시 함수 2개 필요, 구현 복잡 |
삭제의 어려움
[A] [B] [C] [ ] ...
↑ B 삭제
[A] [ ] [C] [ ] ...
C를 탐색할 때 빈 슬롯에서 탐색 중단
→ C를 못 찾는 문제 발생
해결: 삭제된 슬롯에 "삭제 표시(Dummy)" 를 남김
[A] [DEL] [C] [ ] ...
→ DEL은 탐색 시 건너뛰고 계속 탐색
체이닝 vs 개방 주소법
| 체이닝 | 개방 주소법 |
|---|
| 충돌 처리 | 연결 리스트 | 빈 슬롯 탐색 |
| 메모리 | 추가 사용 | 배열만 사용 |
| 캐시 효율 | 낮음 | 높음 |
| 로드 팩터 | 1 초과 가능 | 1 초과 불가 |
| 삭제 | 간단 | 복잡 (Dummy 필요) |
개방 주소법은 로드 팩터가 낮을 때 성능이 좋으며, 배열이 가득 찰수록 충돌이 급격히 증가합니다. 배열이 꽉 차면 더 큰 배열로 재해싱(Rehashing) 이 필요합니다.