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中。