数据结构 可扩展哈希代码解析

可扩展哈希（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]; // 通过目录找到桶

目录的作用：

1. 间接寻址：目录指向桶，多个目录项可以指向同一个桶

2. 平滑扩容：分裂桶时，只需要更新部分目录指针

3. 减少数据迁移：只迁移被分裂桶的数据

四、深度（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); // 只分裂这个桶 }

优势：

1. 局部性：只有热点桶才分裂

2. 精准扩容：不浪费内存

3. 无全局停顿：扩容不影响其他桶的访问

七、可视化示例

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 适合的场景

1. 数据库索引：B+树的替代，支持范围查询

2. 文件系统：ext2/ext3的目录索引

3. 内存受限环境：避免一次性大扩容

4. 实时系统：需要保证响应时间

9.2 不适合的场景

1. 小数据量：目录开销太大

2. 频繁删除：不容易合并桶

3. 内存敏感：目录占用额外空间

十、与传统哈希的对比

十一、代码关键点解释

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; }

十二、总结

可扩展哈希通过目录+桶的二级结构实现了渐进式扩容：

1. 目录：提供间接寻址，允许平滑扩容

2. 桶：固定大小的容器，满时分裂

3. 深度：控制哈希值的使用位数

4. 无全局负载因子：每个桶独立管理

核心优势：扩容时只移动一个桶的数据，避免了传统哈希的全表rehash，特别适合大规模、高并发的场景。

代价：需要额外的目录空间，实现比传统哈希复杂。