可扩展哈希（Extendible Hashing）详解
一、传统哈希的问题
1.1 传统哈希扩容的痛苦
c
// 传统链地址法哈希表扩容 void rehash(hashtable* table) { // 1. 分配新桶数组（通常翻倍） // 2. 重新计算所有元素的哈希值 // 3. 迁移所有数据到新数组 // 问题：扩容时所有数据都要移动！O(n)时间复杂度 }扩容代价：
数据量大时，扩容卡顿
扩容期间服务可能不可用
内存瞬间翻倍
二、可扩展哈希的核心思想
2.1 核心目标：渐进式扩容
每次只扩容一点点，而不是全部重来
2.2 目录（Directory）的作用
text
想象一下：你有一本电话号码本（目录） 1. 目录不是直接存储数据，而是存储指向桶的指针 2. 每个桶是一个固定大小的容器 3. 当某个桶满了，只分裂这个桶，不影响其他桶
三、数据结构设计解析
3.1 为什么需要Bucket结构体？
c
// 传统链地址法：每个桶是一个链表 hashnode** buckets; // 桶数组，每个元素是链表头 // 可扩展哈希：每个桶是一个固定大小的数组 typedef struct bucket { int local_depth; // 这个桶的局部深度（关键！） int count; // 当前元素数量 hash_node* entries[BUCKET_CAPACITY]; // 固定大小的数组 } bucket;对比：
| 特性 | 传统链地址法桶 | 可扩展哈希桶 |
|---|---|---|
| 大小 | 动态（链表） | 固定（数组） |
| 冲突解决 | 链表链接 | 分裂桶 |
| 扩容粒度 | 整个表 | 单个桶 |
3.2 为什么需要Directory？
c
// 传统哈希：直接访问桶 index = hash(key) % capacity; bucket = buckets[index]; // 直接访问 // 可扩展哈希：通过目录访问 index = hash(key) & ((1 << global_depth) - 1); // 取低global_depth位 bucket = directory[index]; // 通过目录找到桶
目录的作用：
间接寻址：目录指向桶，多个目录项可以指向同一个桶
平滑扩容：分裂桶时，只需要更新部分目录指针
减少数据迁移：只迁移被分裂桶的数据
四、深度（Depth）的概念
4.1 全局深度（Global Depth）
c
int global_depth; // 目录的大小 = 2^global_depth
整个哈希表的"精度"
决定使用哈希值的多少位
目录大小 = 2^global_depth
4.2 局部深度（Local Depth）
c
typedef struct bucket { int local_depth; // 这个桶的精度 // ... } bucket;每个桶有自己的深度
决定这个桶对应哈希值的多少位
local_depth ≤ global_depth
4.3 深度示例
text
假设哈希值: 10101101 (二进制) 全局深度 = 2 使用低2位: 01 (十进制1) 目录索引 = 1 桶的局部深度 = 2 这个桶负责所有以01结尾的哈希值
五、工作流程详解
5.1 初始状态
text
全局深度 = 1 目录大小 = 2^1 = 2 两个目录项都指向同一个桶 目录[0] --> 桶A (局部深度=1) 目录[1] --> 桶A (局部深度=1)
5.2 插入数据（桶未满）
text
插入 key1 (哈希值...0) -> 目录[0] -> 桶A 插入 key2 (哈希值...1) -> 目录[1] -> 桶A 桶A: [key1, key2]
5.3 桶分裂（当桶满时）
text
桶A已满（假设容量=2），需要插入key3 key3的哈希值以0结尾 -> 目录[0] -> 桶A 分裂过程： 1. 创建两个新桶：桶B(深度=2), 桶C(深度=2) 2. 重新分配桶A的数据： - 以00结尾的 -> 桶B - 以10结尾的 -> 桶C 3. 更新目录： 目录[00] = 桶B 目录[10] = 桶C 目录[01] = 桶A (保持不变) 目录[11] = 桶A 为什么局部深度=1的桶可以同时被多个目录项指向？ 因为哈希值的低1位相同（都是1）的数据都应该去同一个桶
5.4 目录倍增（当局部深度=全局深度时）
text
如果桶的local_depth == global_depth，需要倍增目录 倍增前： 全局深度 = 1 目录: [0]->桶A, [1]->桶A 倍增后： 全局深度 = 2 目录: [00]->桶A, [01]->桶A, [10]->桶A, [11]->桶A
六、为什么没有负载因子？
6.1 传统哈希的负载因子
c
// 传统哈希用负载因子触发扩容 if ((double)size / capacity > LOAD_FACTOR) { rehash(); // 全部扩容 }6.2 可扩展哈希的触发机制
c
// 可扩展哈希不需要全局负载因子 // 每个桶独立判断是否需要分裂 if (bucket->count >= BUCKET_CAPACITY) { split_bucket(bucket); // 只分裂这个桶 }优势：
局部性：只有热点桶才分裂
精准扩容：不浪费内存
无全局停顿：扩容不影响其他桶的访问
七、可视化示例
7.1 初始状态
text
全局深度: 1 目录大小: 2 目录: [0] --> 桶A (局部深度:1, 数据: 空) [1] --> 桶A 插入 "apple"(hash...0), "banana"(hash...1) 后： 桶A: ["apple", "banana"]
7.2 桶分裂
text
插入 "orange"(hash...0)，桶A已满（容量=2） 分裂后： 全局深度: 2 目录大小: 4 目录: [00] --> 桶B (局部深度:2, 数据: ["apple"]) [01] --> 桶A (局部深度:1, 数据: ["banana"]) [10] --> 桶C (局部深度:2, 数据: ["orange"]) [11] --> 桶A 注意：目录[01]和[11]都指向桶A，因为它们哈希值的低1位都是1
八、性能分析
8.1 时间复杂度
text
操作 时间复杂度 说明 查找 O(1) 一次目录访问+桶内查找 插入 O(1) 可能触发分裂，但分摊O(1) 删除 O(1) 分裂 O(B) B是桶容量，只移动一个桶的数据 目录倍增 O(2^d) 指数级，但很少发生
8.2 空间复杂度
text
目录: O(2^global_depth) 指针 数据: O(n) 实际元素 比传统哈希多了一个目录的空间开销
九、适用场景
9.1 适合的场景
数据库索引：B+树的替代，支持范围查询
文件系统：ext2/ext3的目录索引
内存受限环境：避免一次性大扩容
实时系统：需要保证响应时间
9.2 不适合的场景
小数据量：目录开销太大
频繁删除：不容易合并桶
内存敏感：目录占用额外空间
十、与传统哈希的对比
| 特性 | 传统链地址法 | 可扩展哈希 |
|---|---|---|
| 扩容方式 | 全表rehash | 桶分裂 |
| 扩容代价 | O(n) | O(桶容量) |
| 空间开销 | 较小 | 目录+桶 |
| 查找速度 | O(1)平均 | O(1) |
| 删除支持 | 容易 | 较复杂（合并） |
| 内存使用 | 可能浪费 | 更精准 |
十一、代码关键点解释
c
// 1. 计算索引：使用哈希值的低global_depth位 int index = hash(key) & ((1 << global_depth) - 1); // 2. 桶分裂：创建两个新桶，深度+1 bucket* new_bucket1 = create_bucket(old_depth + 1); bucket* new_bucket2 = create_bucket(old_depth + 1); // 3. 重新分配：根据哈希值的第old_depth+1位分配 int new_index = hash & ((1 << (old_depth + 1)) - 1); if (new_index == original_index) { // 去新桶1 } else { // 去新桶2（兄弟桶） } // 4. 目录更新：更新所有指向旧桶的目录项 int step = 1 << (old_depth + 1); for (int i = original_index; i < dir_size; i += step) { directory[i] = new_bucket1; } for (int i = buddy_index; i < dir_size; i += step) { directory[i] = new_bucket2; }十二、总结
可扩展哈希通过目录+桶的二级结构实现了渐进式扩容：
目录：提供间接寻址，允许平滑扩容
桶：固定大小的容器，满时分裂
深度：控制哈希值的使用位数
无全局负载因子：每个桶独立管理
核心优势：扩容时只移动一个桶的数据，避免了传统哈希的全表rehash，特别适合大规模、高并发的场景。
代价：需要额外的目录空间，实现比传统哈希复杂。
