서로 다른 키가 같은 버킷 위치로 배정되는 현상. 해시 테이블에서 피할 수 없다.
왜 반드시 일어나는가 — 비둘기집 원리
- 가능한 키: — 무한대 (모든 문자열)
- 버킷 개수: — 유한 (예: 16개)
무한을 유한에 넣으면 반드시 겹친다. 이것이 비둘기집 원리다. 좋은 해시 함수는 충돌을 줄일 뿐 없앨 수 없다.
게다가 생일 문제 때문에 생각보다 훨씬 빨리 겹친다 — 버킷이 365개여도 23개만 넣으면 충돌 확률이 50% 를 넘는다.
해시 테이블의 동작
-
put("apple", 1)
-
① hashCode("apple") = 93029210 ← 키를 정수로
-
② 93029210 % 16 = 10 ← 버킷 번호로 압축
-
③ 10번 버킷에 저장
-
get("apple") → 같은 계산 → 10번 버킷 → O(1)
충돌하면 10번 버킷에 여러 개가 들어간다. 그때 어떻게 할지가 체이닝과 개방 주소법의 갈림길이다.
해시 함수가 나쁘면 어떻게 되나
class Bad {
@Override public int hashCode() { return 1; } // 항상 같은 값
}
모든 키가 한 버킷에 몰려 O(1)이 O(n)으로 붕괴한다. 해시 테이블이 사실상 링크드리스트가 된다.
해시 DoS 공격
공격자가 의도적으로 충돌하는 키를 대량 전송하면 서버의 해시 테이블이 O(n)으로 떨어져 CPU가 마비된다. 실제로 2011년 여러 웹 프레임워크가 이 공격을 받았다.
대응
- 프로세스마다 무작위 시드를 섞어 충돌 키를 미리 계산할 수 없게 함
- 자바 8 HashMap: 한 버킷의 항목이 8개를 넘으면 레드-블랙 트리로 전환 → 최악 O(log n)
부하율(load factor)
부하율 = 항목 수 / 버킷 수
높을수록 충돌이 잦다. 자바 HashMap은 0.75를 넘으면 버킷을 2배로 늘리고 전부 재배치한다(rehashing). 이 리사이징이 분할 상환의 "가끔 비싼 연산"이다.
크기를 알면 미리 지정한다: new HashMap<>(예상크기 / 0.75 + 1).
equals와 hashCode 계약 — 실무에서 가장 자주 깨진다
equals가 true면 hashCode도 반드시 같아야 한다
이걸 어기면 같은 값인데 다른 버킷을 찾아 넣은 값을 못 꺼낸다.
Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
set.contains(new Point(1, 2)); // hashCode 미구현 시 false!
hashCode만 같고 equals가 다른 것은 괜찮다(그냥 충돌). 반대는 치명적이다.