확장성 해싱 (Extendible Hashing)
확장성 해싱 (Extendible Hashing)
데이터 증가에 따라 해시 테이블의 크기를 동적으로 확장할 수 있는 해싱 기법으로, 디렉토리와 버킷의 2단계 구조를 통해 오버플로우 없이 효율적인 데이터 접근을 제공하는 동적 해싱 방식
목적: 정적 해싱의 오버플로우 문제 해결, 데이터 증감에 따른 유연한 크기 조절, 균등한 데이터 분포 유지
특징: 디렉토리+버킷 2단계 구조, 해시 값의 접두사(prefix) 기반 버킷 매핑, 필요한 버킷만 분할(점진적 확장), 오버플로우 체인 불필요
구성요소
- •디렉토리(Directory): 버킷을 가리키는 포인터 배열, 크기 = 2^(글로벌 깊이), 해시 값의 상위 비트로 인덱싱
- •버킷(Bucket): 실제 데이터(키-값 쌍) 저장 공간, 고정 용량, 각 버킷마다 로컬 깊이 보유
- •글로벌 깊이(Global Depth): 디렉토리 크기를 결정하는 비트 수, 디렉토리 엔트리 수 = 2^d
- •로컬 깊이(Local Depth): 해당 버킷을 참조하는 데 사용되는 비트 수, 항상 글로벌 깊이 이하
버킷 분할 과정
디렉토리 확장: 글로벌 깊이 d → d+1, 디렉토리 크기 2배(2^d → 2^(d+1)), 새 엔트리는 기존 버킷을 동일하게 가리킴, 분할 버킷만 새 버킷 가리킴
검색/삽입/삭제: 검색 O(1)(해시 계산 → 디렉토리 → 버킷), 삽입 O(1)(분할 시 추가 비용), 삭제 후 버킷 병합 가능
장점: 오버플로우 없는 동적 확장, 검색 성능 O(1) 유지, 필요한 부분만 분할(공간 효율), 데이터 편중 시에도 유연 대응
단점: 디렉토리 크기가 2의 거듭제곱으로 증가(메모리), 데이터 편중 시 디렉토리 과다 확장, 디렉토리가 메모리에 상주해야 성능 보장, 축소(병합) 구현 복잡
정적 해싱과 비교: 정적 해싱(고정 버킷 수/오버플로우 체인/성능 저하) vs 확장성 해싱(동적 버킷 분할/오버플로우 없음/O(1) 유지)
선형 해싱과 비교: 확장성 해싱(디렉토리 사용/2배 확장/빠른 검색/메모리 오버헤드) vs 선형 해싱(디렉토리 없음/순차 분할/오버플로우 허용/메모리 절약)
적용사례: DBMS 내부 해시 인덱스, 메모리 기반 해시 테이블, 파일 시스템 디렉토리 관리
연관: 해시 인덱스, 정적 해싱, 선형 해싱, B-Tree, 동적 자료구조