동적해싱기법

📘 동적 해싱 (Dynamic Hashing) 이란?

동적 해싱(Dynamic Hashing)은 해시 테이블의 크기를 동적으로 확장할 수 있도록 고안된 기법으로, 데이터가 점점 많아질 때 버킷 분할을 통해 공간을 동적으로 조절할 수 있습니다.

일반적인 고정 해싱(Static Hashing)은 레코드 수 증가에 유연하지 않아 성능 저하 문제가 있었고, 이를 보완하기 위해 등장한 방식입니다.

---

🧱 핵심 구성 요소

구성 요소	설명
디렉토리(Directory)	메인 메모리에 위치하며, 해시 값에 따라 버킷을 참조하는 인덱스 역할을 수행
버킷(Bucket)	디스크에 저장되며, 실제 데이터를 담는 공간. 하나의 버킷에는 여러 개의 레코드가 저장됨
해시 함수(Hash Function)	키 값으로부터 해시 값을 생성하여, 디렉토리에서 어떤 버킷을 참조할지를 결정
전역 깊이(Global Depth)	디렉토리에서 사용되는 해시 비트 수
지역 깊이(Local Depth)	각 버킷이 참조할 수 있는 해시 비트 수. 버킷 분할 시 사용됨

---

🔄 동작 원리

1. 레코드 저장 시
   • 키 값을 해시 함수에 적용하여 해시 값을 구함
   • 해시 값의 앞 global depth 비트를 사용해 디렉토리 인덱스를 결정
   • 디렉토리 엔트리가 가리키는 버킷에 저장
2. 버킷 오버플로우 발생 시
   • 해당 버킷의 local depth 값을 1 증가시킴
   • 버킷을 2개로 분할하고, 해시 비트를 한 자리 더 보고 분배
   • 디렉토리를 재구성할 필요가 있으면 global depth도 증가
   • 디렉토리 크기를 2배로 확장하여 포인터 재배치
3. 검색 시
   • 동일하게 해시 값을 구하고 디렉토리에서 해당 버킷 참조 후 검색

---

📌 주요 특징

항목	설명
확장성	데이터 증가에 따라 디렉토리와 버킷이 동적으로 확장
공간 효율성	필요한 경우에만 버킷과 디렉토리를 확장하므로 공간 낭비 최소화
디스크 접근 최적화	해시를 통해 O(1)에 가까운 검색 성능 제공
가상 메모리 연계	디렉토리 및 버킷이 커질 경우, page fault 발생 가능성 존재

---

🧠 예시 시나리오

1. hash(key) = 101010
2. global depth = 3 → 디렉토리는 8개 슬롯 (2^3)
3. 상위 3비트를 사용하여 디렉토리 인덱스 선택
4. 특정 버킷이 꽉 찼다면:
   • 해당 버킷만 분할 (local depth ↑)
   • 필요한 경우 디렉토리 전체 크기 확장 (global depth ↑)

---

✅ 장단점 정리

장점	단점
데이터 증가에 강함 (확장성)	구조가 복잡해 메모리 사용량 증가
빠른 검색 성능 유지	디렉토리 크기 증가로 인한 page fault 가능성
버킷 단위 분할로 공간 낭비 최소화	구현이 정적 해싱보다 복잡함

---

📚 관련 개념 비교

항목	고정 해싱 (Static Hashing)	동적 해싱 (Dynamic Hashing)
크기	고정된 버킷 수	버킷 및 디렉토리 크기 동적 확장
오버플로우 처리	체이닝, 오버플로우 버킷	버킷 분할 및 디렉토리 확장
검색 성능	데이터 증가 시 성능 저하	안정적인 O(1) 유지
유연성	낮음	높음