[可扩展哈希](https://en.wikipedia.org/wiki/Extendible_hashing) 是一种动态散列方案，其中的目录和桶被用来散列数据。
对于静态哈希来说，可扩展哈希的优势在于，在扩容的时候，**不需要重新散列所有的数据，只需要重新散列一部分数据即可**。

> 静态哈希不等于不能扩容，只是扩容的时候需要重新散列所有的数据，并且需要重新寻找一个散列函数。

可扩展 hash 的大致架构如下图所示：

![可扩展hash架构](https://user-images.githubusercontent.com/55543743/205441868-9f312eae-0959-4905-8685-97cd0ffcff9c.png)

其中几个概念：

- 目录(direcotory)：用来存储桶指针的数组，其中目录的大小为 2^全局深度，全局深度初始为 1，每次扩容时，全局深度加 1，即目录大小翻倍。这里需要注意，目录中会有多个指针指向同一个桶。
- 桶(bucket)： 用来存储数据的数组，每个桶的大小**固定**，由参数进行指定，局部深度初始为 1，每次分裂时，该桶局部深度加 1。
- 全局深度(global depth)： 用来确定目录的大小，此外，全局深度还用来确定数据的散列地址。例如，全局深度为 1 时，数据的散列地址为 0 或 1，全局深度为 2 时，数据的散列地址为 00、01、10、11。
- 局部深度(local depth)：局部深度用来确定在桶溢出时候进行的操作：当局部深度小于全局深度时，进行桶的分裂，且桶的局部深度加 1；当局部深度等于全局深度时，进行目录的扩容和桶的分裂，且全局深度和局部深度都加 1。指向当前桶的指针的个数等于 2^(全局深度 - 局部深度)。
- 桶分裂：当桶溢出时，将桶中的数据重新散列到旧的桶和新的桶中。例如桶 A 已满，且 A 的局部深度为 1，溢出时，创建桶 A\*，局部深度为 2，且将桶 A 的深度也改为 2。~~然后将桶 A 中的数据重新散列到桶 A 和桶 A\*中~~。 这里更好的说法是，将桶 A 的数据进行重新散列。且散列的数据只会落在桶 A 和桶 A\*中，而不会落在其他桶中。
- 目录扩容：当全局深度增加时候，需要对目录进行扩容，即将目录的大小翻倍。且将新增加的目录的桶指针指向合适的桶。例如，当全局深度从 1 增加到 2 时，需要将目录的大小从 2 增加到 4，且将目录的第 2 个和第 3 个指针指向对应的桶 0 和桶 1。对应关系为: **遍历前一半目录索引，将其最高位从 0 变为 1 即可。公式为 dir[reverse_the_highest_bit(index)] = dir[index]**

## 流程

流程如下所示：

![流程](https://user-images.githubusercontent.com/55543743/205441887-ca3ff3e3-4348-4503-8c8f-0b72a1ca45b1.png)

找到对应的桶之后，可以进行查找/删除/增加等操作。

举个例子：

此时的状态为：全局深度 1，局部深度 1，key 为"qianxi", hash(key) = 114514。

按照流程，先对 key = qianxi 应用 hash 函数，得到 114514。然后，寻找对应的目录索引 dir_index = (114514 & ((1 << 全局深度) - 1)) = 0，得到索引 0，在按照目录中所存放的桶指针找到的目录项 0 所指向的桶，随后进行对应的操作。

## 举个栗子

查找和删除操作这里都不讲，着重讲讲插入操作。

预设：桶的大小为 2，hash(key) = key，待插入的 key 为 1-8。

首先的初始情况为：

![初始情况](https://user-images.githubusercontent.com/55543743/205441902-83c6e4ed-bda9-49f8-8d21-e9f805f0be79.png)

1. 插入 1，hash(1) = 1，dir_index = 1 & 1 = 1，所以插入到桶 1 中。
2. 插入 2，hash(2) = 10，dir_index = 10 & 1 = 0，所以插入到桶 0 中。
3. 插入 3，hash(3) = 11，dir_index = 11 & 1 = 1，所以插入到桶 1 中。
4. 插入 4，hash(4) = 100，dir_index = 100 & 1 = 0，所以插入到桶 0 中。

此时，桶 0 和桶 1 都已满，状态如下：

![阶段1](https://user-images.githubusercontent.com/55543743/205441908-11412e98-315c-47ba-8566-7ada36f13b06.png)

5. 插入 5，hash(5) = 101，dir_index = 101 & 1 = 1，所以插入到桶 1 中。

问题来了，桶 1 已经满了（桶的大小固定且在这里设定为 2），而且此时桶 1 的局部深度为 1，全局深度也为 1，这就代表着，没有多余的指针指向桶 1，所以你需要首先对目录进行扩容，扩容后的目录如下：

![第一次扩容](https://user-images.githubusercontent.com/55543743/205441912-fa3b0bab-2833-4c82-87c3-b4ebb88ed263.png)

注意到，此时的全局深度增加 1 之后为 2，而且，扩容增加之后的目录指向了桶 0 和桶 1。且此时，全局深度为 2，局部深度为 1，key 为 5，hash(key) = 5， 插入到桶 1 中。

扩容之后，桶 1 的局部深度 1 小于全局深度 2，这就意味着，有不止一个指针指向桶 1，所以，你仅仅需要对桶 1 进行分裂。首先，需要找到另一个指向桶 1 的目录项，这里就是目录项 3，将其指向一个新的空桶，然后，对目录项 1 所指向的桶进行分裂（别忘了加上新增的元素 5），即对 1、3、5 这些元素重新进行哈希：

- 插入 1，hash(1) = 1, dir_index = 1 & 11 = 1,所以插入到桶 01 中。
- 插入 3，hash(3) = 11, dir_index = 11 & 11 = 11 ，所以插入到桶 11 中。
- 插入 5，hash(5) = 101, dir_index = 101 & 11 = 01 ，所以插入到桶 01 中。

这样，就完成了桶的分裂，且没有桶溢出。

> 但是还个问题是？如何找到桶 1 的对分裂项桶 3 呢？假设桶 1 对应的分裂桶为桶 1\*。
> 思路是，此时桶 1 的本地深度为 1，设桶 1 的索引号为 index，则桶 1\*的目录索引号 index\* = (1 << local_depth) | index，代入数据可以得到 index\* = (1 << 1) | 1 = 3 = 11，所以桶 1\* 对应的目录项为 3(11)。

分裂之后的状态如下：

![分裂之后的状态](https://user-images.githubusercontent.com/55543743/205441932-3653da0b-bb6e-4a95-afcc-5152178da704.png)

别忘了对新的桶和分裂的桶进行局部深度的更新。

6. 插入 6，hash(6) = 110，dir_index = 110 & 11 = 10，所以插入到桶 10 中。

注意，此时，桶 10 的局部深度为 1，全局深度为 2，所以，此时只需要进行桶分裂，不需要对目录进行扩容。

所以步骤如上，对 2、4、6 进行重新哈希：

- 插入 2，hash(2) = 10，dir_index = 10 & 11 = 10，所以插入到桶 10 中。
- 插入 4，hash(4) = 100，dir_index = 100 & 11 = 00，所以插入到桶 00 中。
- 插入 6，hash(6) = 110，dir_index = 110 & 11 = 10，所以插入到桶 10 中。

插入完成，且更新对应的局部深度之后的状态如下：

![第二次分裂](https://user-images.githubusercontent.com/55543743/205441945-e06f4304-243a-4fff-a2be-a5cb35cbdd73.png)

7. 插入 7，hash(7) = 111，dir_index = 111 & 11 = 11，所以插入到桶 11 中。
8. 插入 8，hash(8) = 1000，dir_index = 1000 & 11 = 00，所以插入到桶 00 中。

全部插入完成之后的状态如下：

![全部插入完成之后的状态](https://user-images.githubusercontent.com/55543743/205441950-78907d24-8301-4489-9031-3d153479a007.png)

## 总结

所以，动态哈希的插入过程可以总结为：

1. 计算哈希值，得到目录项的索引号，从而找到对应的桶。
2. 如果目标桶可以直接插入，则直接插入。
3. 如果不能直接插入，如果此时桶的局部深度等于全局深度则进行4，否则 5。
4. 对目录进行扩容，然后将新增的目录项的桶指针指向对应的桶。
5. 对目标桶进行分裂，将该桶中的所有数据和代插入的新数据进行重新哈希，然后插入到对应的桶中。
6. 如果全部重新哈希之后插入成功，则完成插入，否则重复 2-5。