网站建设费用分几年摊销,网站建设空白栏目整改报告,淘客做的网站属于什么类型,苏州门户网站有哪些可拓展哈希
借CMU 15445的ppt截图来说明问题。
我们传统静态hash的过程是hash函数后直接将值存入对应的bucket#xff0c;但是在可扩展hash中#xff0c;得查询Directory#xff08;左#xff09;#xff0c;存入directory指向的bucket#xff08;右#xff09;。 下面…可拓展哈希
借CMU 15445的ppt截图来说明问题。
我们传统静态hash的过程是hash函数后直接将值存入对应的bucket但是在可扩展hash中得查询Directory左存入directory指向的bucket右。 下面我们存放keyB哈希值为hash(B)查询directory知道要放到第二个bucket中。 然后再放一个keyChash( C)的值被老师的视频挡住了就不放图片了哈希值为hash( C)并且hash( C)高两位也是10查询directory也要放到第二个bucket但此时bucket满了就将该bucket分裂其他bucket不用变动那么directory应该怎么变动呢分为两种情况先说明此时hash( C)对应第2种情况
bucket的local depth global depth分裂bucket改变directory中指向该bucket的指针让他们分别指向分裂出来的两个bucket并且这两个bucket的local depth1bucket的local depth global depth分裂bucket将directory的大小*2并且重新分配directory中的指针这里不知道怎么描述比较好可以结合下面的图来理解并且分裂后的两个bucket的local depth1global depth1
很明显hash©对应上面的情况2因此结果如下
第一种情况在课件中没有提到我也做一下说明懒得画图了。我们先回到这张图基于现在这个状态分析第一种情况 假设现在第一个bucket是满的(我们这里假设bucket中第三个为01…)然后hash©00…要插入第一个bucket那么根据情况1我们将bucket分裂为两个bucketdirectory不用增长但是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?p7vd_source65dfb8ffc4e0d60f317dcde5b6ceb9fd
https://zhuanlan.zhihu.com/p/375039823
