Hash Collision Resolution (해시 충돌 해결)

Hash Collision Resolution (해시 충돌 해결)

서로 다른 키가 동일 해시 값을 갖는 충돌을 해결하는 기법

특징: Chaining vs Open Addressing, 부하율(Load Factor)=항목수/버킷수

Chaining: 버킷에 연결 리스트/트리, 삭제 용이, α>1 가능, 포인터 오버헤드, 캐시 비효율

Open Addressing: 빈 슬롯 탐색하여 저장, 캐시 효율, Tombstone 삭제, α<1 필수

• •Linear Probing: (h+i)%m, 캐시 최고, 1차 클러스터링 심각
• •Quadratic Probing: (h+c₁i+c₂i²)%m, 클러스터링 완화
• •Double Hashing: (h₁+i·h₂)%m, 클러스터링 거의 없음, 가장 안정적

기타: Cuckoo Hashing(O(1) 최악 조회), Robin Hood Hashing(프로브 거리 균형)

부하율: 0.75 권장(Java HashMap), 초과 시 재해싱(2배 확장+재삽입, O(n))

비교: Chaining(리스트/삭제용이/α>1/캐시낮음) vs Open Addressing(테이블내/캐시높음/삭제복잡/α<1)

적용사례: HashMap, HashSet, DB 인덱스, 캐시, 심볼 테이블

연관: 해시 테이블, 해시 함수, Load Factor, 재해싱