可拓展哈希

可拓展哈希

借CMU 15445的ppt截图来说明问题。

我们传统静态hash的过程是hash函数后直接将值存入对应的bucket，但是在可扩展hash中，得查询Directory（左），存入directory指向的bucket（右）。

下面我们存放key=B，哈希值为hash(B)，查询directory知道要放到第二个bucket中。

然后再放一个key=C（hash( C)的值被老师的视频挡住了，就不放图片了），哈希值为hash( C)，并且hash( C)高两位也是10，查询directory也要放到第二个bucket，但此时bucket满了，就将该bucket分裂，其他bucket不用变动，那么directory应该怎么变动呢？分为两种情况（先说明此时hash( C)对应第2种情况）

1. bucket的local depth < global depth：分裂bucket，改变directory中指向该bucket的指针，让他们分别指向分裂出来的两个bucket，并且这两个bucket的local depth+1
2. bucket的local depth = global depth：分裂bucket，将directory的大小*2，并且重新分配directory中的指针（这里不知道怎么描述比较好，可以结合下面的图来理解），并且分裂后的两个bucket的local depth+1，global depth+1

很明显hash©对应上面的情况2，因此结果如下：

第一种情况在课件中没有提到，我也做一下说明（懒得画图了）。我们先回到这张图，基于现在这个状态分析第一种情况：

假设现在第一个bucket是满的(我们这里假设bucket中第三个为01…)，然后hash©=00…，要插入第一个bucket，那么根据情况1，我们将bucket分裂为两个bucket，directory不用增长，但是00…和01…指针分别要指向第一个分裂的bucket和第二个分裂的bucket，第一个分裂桶存放了两个01…，第二个分裂桶存放了两个00…

如果还是不懂的话，可以多看几遍上述操作过程或者看下面的参考链接

简单的体会总结：可拓展哈希好处在于某个桶分裂的时候，不用移动其他桶的元素，减少开销。存在的问题很明显，如果多次插入的hash值相同，分裂肯定是不可行的，因为无论怎么分裂，这几个相同hash值都在同一个bucket中，因此需要用overflow bucket的方式来“打补丁”了，所以最基本的可拓展哈希算法不能直接拿来用，得做点变种吧，不过思想值得学习。

参考链接：

https://blog.csdn.net/qq_37026934/article/details/125368237

https://www.bilibili.com/video/BV1xa41137S4?p=7&vd_source=65dfb8ffc4e0d60f317dcde5b6ceb9fd

https://zhuanlan.zhihu.com/p/375039823