Cuckoo Hash和多级Hash的粗浅认识

Cuckoo Hash和多级Hash的粗浅认识.pdf

通过对Cuckoo Hash、多级Hash和BloomFilter的粗浅了解,感觉它们三者存在类似之处,算是近亲(暂且把普通的Hash称作远亲)。

Cuckoo Hash的思想非常简单,冲突时,重Hash,也就是为Key重新找个新的位置。显然,极端情况下,需要反反复复找位置,效率低。为了减少这个过程,Cuckoo Hash的实现一般引入了两个数组,这样只有在其中一个数组中不存在,就不会重新找位置。

对于Cuckoo Hash的实现有一个小疑问:Google/Baidu出的介绍或实现,都是将已存在的踢出来,但感觉为新插入的找个位置,貌似也没有问题,除非考虑到新插入的可能是热点,暂没能想出更好的理由。

多级Hash弱化了这个问题,它引入了更多的数组,比如20个,第一个位置被占了,就试第二个位置,依次类推,级数够多,最终能找到存放位置的概率就很高。但是也带来了另一个问题:太多级数,也会导致效率下降,因为每次都需要遍历级数次。常规的实现中,一般不同级的桶数会设定不同,一般从1级往后递减。

BloomFilter的用途和Cuckoo Hash、多级Hash明显不同,但同样通过多个数组来降低冲突概率,所以说它们很亲。

总的来说,这些思想都非常简单,而且很实用。而Google的SparseHash则是另一种思想,省内存效率又不错,可以看作是虚拟化的思想,但它不适合用于共享内存这样一次性分配内存的场景。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阮一峰的网络日志

12种不宜使用的Javascript语法

这几天,我在读《Javascript语言精粹》。 这本书很薄,100多页,正好假日里翻翻。 该书的作者是Douglas Crockford,他是目前世界上最精通...

3428
来自专栏JadePeng的技术博客

知识图谱学习笔记(1)

RDF(Resource Description Framework),即资源描述框架,其本质是一个数据模型(Data Model)。它提供了一个统一的标准,用...

1970
来自专栏编程之旅

Python——搞定烦人的字符串编码

在学习Python之前,就听说过Python的版本圣战,最可怕的是有的写Py3的程序员觉得Py2是另一种语言....所以在刚开始学习的时候,我索性把Python...

1033
来自专栏java一日一条

10个实用的但偏执的Java编程技术

这就是为什么我们要采用“防御性编程”,即一些偏执习惯的原因。下面是我个人认为的10个最有用但偏执的Java编程技术。一起来看一看吧:

912
来自专栏青蛙要fly的专栏

Android技能树 — 数组,链表,散列表基础小结

现在安卓面试,对于数据结构的问题也越来越多了,要求也越来越多,所以我对于数据结构只能慢慢补起来了。(灬ꈍ ꈍ灬)

1304
来自专栏JadePeng的技术博客

知识图谱学习笔记(1)

4205
来自专栏JavaQ

写这样的方法让人很反感

写作文要做到段落清晰、每段思路流畅、每段主旨明确,要有一条清晰的线穿插整篇内容,编写程序代码和写作文是一个套路。一个类就像一篇小作文,类的单一职责就是小作文要叙...

3467
来自专栏owent

C++总是很神奇

很多时候看到C/C++的一些奇妙的应用,每次都是惊奇一点时间就随风飘过了 现在我还是决定记录一下这些有意思的东西。

1022
来自专栏工科狗和生物喵

【计算机本科补全计划】指令:计算机的语言(MIPS) Part4

正文之前 这几天陪人玩去了,所以没怎么看书。今早某人回家了。所以我也就可以一个人继续开始在图书馆的浪荡之路了。爽歪歪!!!!而且可以一个人独占温暖的地方,实在...

3556
来自专栏Web行业观察

从JSON进化到BSON

自从MEAN引导的JSON数据格式取代传统JAVA推崇的XML以后, json的发展却停滞不前了, 当然这是好事, 因为稳定的结构是不需要向下兼...

3454

扫码关注云+社区

领取腾讯云代金券