Open Addressing (개방 주소법) 심화

Open Addressing (개방 주소법) 심화

해시 충돌 발생 시 별도 자료구조 없이 해시 테이블 내부의 다른 빈 슬롯을 탐사(Probing)하여 데이터를 저장하는 충돌 해결 기법

특징: 모든 데이터가 테이블 내부에 저장, 부하율 α < 1 필수, 캐시 효율 우수, 삭제 시 Tombstone 필요

선형 탐사 (Linear Probing)

• •탐사 수식: h(k, i) = (h(k) + i) % m, i = 0, 1, 2, ...
• •연속 메모리 접근 → 캐시 효율 최고
• •1차 클러스터링(Primary Clustering): 충돌 지점 주변에 데이터 군집 형성 → 탐사 거리 증가 → 성능 급락
• •적합: 부하율 낮은 경우(α ≤ 0.5), 캐시 성능 중시

이차 탐사 (Quadratic Probing)

• •탐사 수식: h(k, i) = (h(k) + c₁i + c₂i²) % m
• •1차 클러스터링 해소, 2차 클러스터링 존재(동일 초기 해시값 → 동일 탐사 시퀀스)
• •테이블 크기가 소수(prime)이고 α ≤ 0.5이면 모든 슬롯 탐사 보장

이중 해싱 (Double Hashing)

• •탐사 수식: h(k, i) = (h₁(k) + i × h₂(k)) % m
• •h₂(k)가 키에 따라 다른 탐사 간격 생성 → 클러스터링 거의 제거
• •h₂(k)와 m이 서로소여야 모든 슬롯 탐사 보장 (m을 소수로, h₂(k) ≠ 0)
• •구현 복잡도 높으나 이론적 성능 최우수

클러스터링 문제: 연속된 점유 슬롯 군집이 형성되면 탐사 거리 증가 → 삽입/검색 시간 O(1/(1-α))로 부하율에 민감

삭제와 Tombstone: 삭제 시 빈 슬롯으로 두면 탐사 체인 단절 → Tombstone(삭제 마커) 사용, 검색 시 통과/삽입 시 재활용, 주기적 재해싱으로 정리

비교

적용사례: Python dict(Open Addressing), CPython(Linear Probing 변형), Google dense_hash_map(Quadratic), Redis dictht

연관: 해시 테이블, 해시 충돌, Chaining, 부하율, 재해싱