토픽 32 / 66·해시 자료구조

확장성 해싱 (Extendible Hashing)

동적으로 크기가 변하는 해시 테이블 구조로, 디렉토리(Directory)와 버킷(Bucket)의 2단계 구조를 사용하여 데이터 증가 시 전체 재해싱 없이 해당 버킷만 분할하여 확장하는 동적 해싱 기법 (135회 출제)

목적: 동적 데이터 증가 대응, 전체 재해싱 방지, 디스크 기반 인덱스 효율화, 버킷 오버플로 최소화

특징: 디렉토리+버킷 2단계 구조, 부분 확장(해당 버킷만 분할), 글로벌/로컬 깊이 개념, 디스크 I/O 최적화

구성요소

•디렉토리(Directory): 해시 값의 상위 비트(글로벌 깊이만큼)를 인덱스로 사용하는 포인터 배열, 2^(Global Depth)개 엔트리
•버킷(Bucket): 실제 데이터(키-값 쌍)를 저장하는 고정 크기 페이지, 각 버킷은 로컬 깊이(Local Depth) 보유
•해시 함수: h(key) → 이진 해시 값 생성, 상위 비트를 디렉토리 인덱스로 사용

글로벌 깊이(Global Depth): 디렉토리가 사용하는 해시 비트 수, 디렉토리 크기 = 2^GD

로컬 깊이(Local Depth): 각 버킷이 구분에 사용하는 해시 비트 수, LD ≤ GD, 여러 디렉토리 엔트리가 하나의 버킷을 공유 가능(LD < GD일 때)

버킷 분할 과정(삽입 시 오버플로)

검색 과정: h(key) 계산 → 상위 GD 비트로 디렉토리 인덱스 결정 → 해당 버킷 접근 → 버킷 내 순차 검색 → O(1) 디렉토리 접근 + 버킷 내 검색

삽입 과정: 검색과 동일하게 버킷 위치 결정 → 버킷에 여유 공간 있으면 삽입 → 없으면 버킷 분할 후 재삽입

삭제 과정: 해당 버킷에서 키 삭제 → 버킷이 비어있고 버디 버킷과 합병 가능하면 합병 → LD 감소 → 모든 LD < GD이면 디렉토리 축소 가능

시간 복잡도: 검색 O(1)(디렉토리 접근 + 버킷 접근), 삽입 평균 O(1)(분할 시 해당 버킷만 재분배), 디렉토리 확장 시 O(2^GD) 포인터 복사

장점: 전체 재해싱 불필요(해당 버킷만 분할), 동적 확장/축소, 디스크 I/O 효율(버킷 = 디스크 페이지), 검색 성능 일정(O(1))

단점: 디렉토리 크기가 2배씩 증가(메모리 소비), 편향된 해시 분포 시 비효율, 디렉토리 자체가 메모리에 적재되어야 함, 포인터 오버헤드

정적 해싱과 비교: 정적 해싱(고정 버킷 수/오버플로 체인/재해싱 필요) vs 확장성 해싱(동적 버킷 분할/디렉토리 확장/재해싱 불필요)

선형 해싱과 비교: 선형 해싱(디렉토리 없음/순차적 버킷 분할/분할 포인터) vs 확장성 해싱(디렉토리 사용/필요한 버킷만 분할/GD/LD), 선형 해싱은 디렉토리 오버헤드 없으나 오버플로 체인 가능

적용사례: DBMS 해시 인덱스(디스크 기반), 파일 시스템, 메인 메모리 데이터베이스, 분산 해시 테이블(DHT)

비교: 확장성 해싱(디렉토리/부분분할/O(1)) vs 선형 해싱(순차분할/디렉토리 불필요) vs 정적 해싱(고정/오버플로 체인) vs B+ 트리(정렬/범위쿼리/O(log n))

연관: 해시 테이블, 해시 충돌, DBMS 인덱스, B+ 트리, 동적 해싱, 디스크 I/O