extendible_hash_table
https://zhuanlan.zhihu.com/p/622221722
这篇文章讲了extendible_hash_table的数据插入、删除、查找的过程，看完之后可以了解global_depth local_depth是干什么的。
简单来说，global_depth 和 local_depth 的作用和掩码是类似的，代表目前只考虑哈希值的几个低位。比如现在算出来的哈希值是11，对应的二进制是1011，如果global_depth是3，那么最终的值就是hash & (1 << global_depth) - 1也就是011（1011右边的三位）。每一个bucket也有自己的local_depth，且local_depth <= global_depth，也就是说，dir中可能有多个指针指向一个bucket，比如，global_depth = 3，位置3（011）和位置7（111）都指向同一个bucket，这个bucket的local_depth是2。
我记录一下我自己在编码过程中遇到的问题
Insert
查找和删除比较简单，主要是插入，因为有扩展哈希表的过程，比较麻烦
graph TB A[根据key计算index 找到对应的bucket] --> B{尝试将key-value加入bucket} B -->|success| C[return] B -->|fail| D[RedistributeBucket] D --> A每次 redistribute bucket 之后，要重新计算key的index，因为redistribute之后，global_depth 可能会增加，index和之前计算的就会不一样
redistribute
graph TB A{global_depth == loacl_depth} -->|true| B[dir容量翻倍,同时global_depth++] B --> C[loacl_depth++,同时创建一个new_bucket,num_buckets++] A -->|false| C C --> D[将bucket中的部分元素移动到new_bucket] D --> E[将dir中对应的那些指针 指向new_bucket]dir扩容
在这个过程中，会用到global_depth和local_depth之间的关系，首先，如果global_depth 和 local_depth 相等，我们需要先将dir扩容，global_depth加一，也就是说：目前的global_depth已经无法分辨这个key了，需要增加。
比如说，当前dir的size是4，也就是
| dir |
|---|
| 0:00 |
| 1:01 |
| 2:10 |
| 3:11 |
如果要扩容了，就会变成
| dir |
|---|
| 0:000 |
| 1:001 |
| 2:010 |
| 3:011 |
| 4:100 |
| 5:101 |
| 6:110 |
| 7:111 |
仔细观察可以发现，新增的下标的二进制的，只有最高位与原来不一样，新增的最高位是1。
所以扩容的时候可以按顺序吧dir中的指针追加到dir中，也就是0和4中的指针指向同一个bucket，1和5中的指针指向同一个bucket，以此类推。。。
之所以可以这样做，是因为这些下标对只有最高位不一样，而此时bucket还没有分裂，所有的bucket的local_depth一定小于global_depth。
bucket分裂
bucket分裂之后，对应的local_depth需要加一，创建一个新bucket，然后把部分元素移动到新bucket。
哪些元素应该被移动到new bucket中呢？
在这样的情况下，我们插入1011，此时bucket已经满了，需要分裂。分裂之后算出来的index和之前的index不一样的元素，移动到新bucket中。
比如在这个例子中，1111，0001之前的index都是1（local_depth是1），分裂之后（local_depth变为2），1111的index是11（和之前的1不相等），0001的index还是1，所以将1111移动到新bucket中
修改dir中的指针
到目前为止，我们已经创建了新的bucket，并将部分元素移动到new bucket中。但是此时dir中，没有任何指针指向new bucket。
指向bucket的指针中，有一半应该指向new bucket，如何快速找到这些指针呢？
如下图所示，这四行的最低位都是1，在loacl_depth=1的时候，他们都指向bucket。local_depth=2的时候，第二位是1的应该指向new bucket，也就是黄色高亮的行
可以发现，假如去掉地位的1，就变成00，01，10，11，也就是0，1，2，3.
而高亮的行对应的是奇数，取值范围是2 ** (global_depth - local_depth + 1)，也就是1 << (global_depth_ - local_depth + 1)。
把这些奇数左移local_depth-1位，加上原来的index，就是我们要修改的下标。
for (int i = 1; i < 1 << (global_depth_ - local_depth + 1); i += 2) {
int cur_key = per_index + (i << (local_depth - 1));
dir_[cur_key] = new_bucket;
}
然后就可以插入新元素了，如果分裂之后还是无法插入，需要继续分裂。因为有一种特殊情况，就是分裂之后所有的元素都在同一个bucket，新元素也要放在这个满的bucket中。
