토픽 71 / 76·비교표
## Part 4: 해시 자료구조
Chaining vs Open Addressing
| 항목 | Chaining | Open Addressing |
|---|---|---|
| 충돌 해결 | 버킷별 연결 리스트 | 테이블 내 탐사 (선형/이차/이중) |
| 부하율 (α) | α > 1 허용 | α < 1 필수 |
| 삭제 | 용이 (리스트 삭제) | 복잡 (삭제 표시 필요) |
| 캐시 효율 | 낮음 (포인터 추적) | 높음 (연속 메모리) |
| 클러스터링 | 없음 | 1차/2차 클러스터링 |
| 적용 | Java HashMap | Python dict |
해시 함수: 나눗셈법 vs 곱셈법 vs 유니버설
| 항목 | 나눗셈법 | 곱셈법 | 유니버설 |
|---|---|---|---|
| 수식 | h(k) = k mod m | h(k) = floor(m*(kA mod 1)) | 랜덤 해시 함수 집합 |
| 특징 | 단순, m에 민감 | m 독립적 | 확률적 최적 |
| 단점 | m 선택 중요 (소수 권장) | 부동소수점 연산 | 구현 복잡 |
확장성 해싱 vs 선형 해싱 vs 정적 해싱
| 항목 | 확장성 해싱 | 선형 해싱 | 정적 해싱 |
|---|---|---|---|
| 버킷 분할 | 필요한 버킷만 분할 | 순차적 버킷 분할 | 고정 (분할 없음) |
| 디렉토리 | 사용 (GD/LD) | 불필요 | 불필요 |
| 재해싱 | 불필요 | 불필요 | 필요 |
| 오버플로 | 최소 | 체인 가능 | 체인 필요 |