[Algorithm] 해시충돌 해결방법과 각각의 특징

해시 충돌이란?

해시 테이블에서 서로 다른 키 값이 동일한 해시 값을 갖는 현상

 

주요 해결 방법

1. 체이닝 : 같은 해시 값 → 리스트에 이어 붙이기
2. 개방 주소법 : 같은 해시 값 → 테이블 내 다른 빈칸 찾아 저장하기

---

체이닝 (Separate Chaining)

같은 해시 주소에 여러 개의 키가 할당되면, 해당 주소에 연결리스트(Linked List)나 다른 자료구조를 두어 충돌된 키들을 저장하는 방식이다

 

원리

• 해시 테이블의 각 버킷(bucket)이 연결 리스트, 동적 배열, 혹은 트리 구조를 가진다
• 같은 해시값이 나면 그 버킷의 리스트에 추가

특징

• 삭제가 간단: 버킷 내부 자료구조에서만 제거하면 됨
• 부하율(α = n / 버킷 수) > 1도 가능
• 최악의 경우(모두 같은 해시값) 한 버킷에 n개가 몰려 O(n)

장점

• 구현 단순, 삭제 용이
• 확장/축소 시 기존 요소 재배치 없이 버킷만 늘려 재해싱 가능

단점

• 포인터/메모리 오버헤드
• 캐시 적중률 낮음(리스트 노드들이 흩어져 있을 수 있음)

---

개방 주소법 (Open Addressing)

충돌이 발생하면, 해시 테이블 안에서 다른 비어있는 버킷을 찾아 그 자리에 데이터를 저장하는 방식이다.

 

원리

• 충돌이 발생하면, 테이블 내부의 다른 빈 슬롯을 찾아 데이터를 저장
• 탐사(probing) 방식으로 빈 자리를 찾는다

주요 방식

1. 선형 탐사(Linear Probing)
   • h(k), h(k)+1, h(k)+2, ... 순서로 검사 (한 칸씩 이동하며 빈 자리 찾음)
   • 구현 쉽고 캐시 친화적
   • 1차 클러스터링 심함(연속된 빈칸 덩어리가 커짐)
2. 제곱 탐사(Quadratic Probing)
   • h(k)+1², h(k)+2², h(k)+3² ... 식으로 증가
   • 1차 클러스터링 완화
   • 테이블 크기·탐사 함수 제약 존재
3. 이중 해싱(Double Hashing)
   • h1(k) + i * h2(k) 방식
   • 클러스터링 최소화, 분포 균등
   • 해시 함수 2개 필요

특징

• 부하율(α) 0.7~0.8 이상 가면 성능 급격 저하
• 삭제 시 "삭제 마커(tombstone)" 필요 → 많아지면 재해싱 필요

장점

• 포인터 오버헤드 없음, 캐시 친화 (<- 모든 데이터가 테이블 안에 직접 저장되므로 메모리 지역성이 좋음)
• 구현 간단(특히 선형 탐사)

단점

• 삭제 처리 복잡
• 부하율이 높아지면 삽입/탐색 급격히 느려짐

---

비교요약표

방식	메모리 효율	삭제 용이성	평균 조회	최악 조회	구현 난이도	특징
체이닝	낮음(포인터 오버헤드)	매우 쉬움	O(1)	O(n)	쉬움	부하율 제한 적음, 삭제 편함
개방주소법	높음	복잡(마커 필요)	O(1)	O(n)	쉬움~중간	캐시 우호, 부하율 영향 큼