해시 충돌
서로 다른 키(Key)가 해시 함수를 통해 동일한 해시값(인덱스)으로 매핑되는 현상입니다.
발생 원인
해시 함수: key → index (0 ~ N-1)
키의 종류는 무한하지만 인덱스는 유한
→ 비둘기집 원리에 의해 충돌은 필연적으로 발생
해결 방법
1. 체이닝(분리연결법) (Chaining)
같은 인덱스에 연결 리스트로 연결
index 3 → [A] → [D] → [G]
index 4 → [B]
index 5 → [C] → [F]
// Java의 HashMap이 사용하는 방식
// 충돌 발생 시 LinkedList로 연결
// 8개 이상이면 Red-Black Tree로 전환 (Java 8+)
| 장점 | 단점 |
|---|
| 구현 간단 | 메모리 추가 사용 |
| 데이터 많아도 유연 | 캐시 효율 낮음 |
2. 개방 주소법 (Open Addressing)
충돌 시 다른 빈 슬롯을 탐색
선형 탐사: index+1, index+2, index+3 ...
이차 탐사: index+1², index+2², index+3² ...
이중 해싱: 다른 해시 함수로 탐사 간격 결정
| 장점 | 단점 |
|---|
| 메모리 효율 좋음 | 클러스터링 발생 가능 |
| 캐시 효율 높음 | 삭제 처리 복잡 |
Java HashMap의 동작
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
// 내부적으로
// 1. key.hashCode()로 해시값 계산
// 2. 해시값 % 배열크기로 인덱스 결정
// 3. 충돌 시 체이닝(LinkedList → Tree)으로 처리
성능 영향
| 상황 | 시간복잡도 |
|---|
| 충돌 없음 | O(1) |
| 체이닝 (충돌) | O(n) 최악 |
| 체이닝 (Java 8+ Tree) | O(log n) 최악 |
충돌을 줄이려면 좋은 해시 함수와 적절한 로드 팩터(load factor) 관리가 중요합니다. Java HashMap의 기본 로드 팩터는 0.75로, 75% 이상 차면 배열 크기를 2배로 늘립니다.