Cuckoo Hash和多级Hash的粗浅认识
2024-09-20 16:08:54
通过对Cuckoo Hash、多级Hash和BloomFilter的粗浅了解，感觉它们三者存在类似之处，算是近亲（暂且把普通的Hash称作远亲）。
Cuckoo Hash的思想非常简单，冲突时，重Hash，也就是为Key重新找个新的位置。显然，极端情况下，需要反反复复找位置，效率低。为了减少这个过程，Cuckoo Hash的实现一般引入了两个数组，这样只有在其中一个数组中不存在，就不会重新找位置。
对于Cuckoo Hash的实现有一个小疑问：Google/Baidu出的介绍或实现，都是将已存在的踢出来，但感觉为新插入的找个位置，貌似也没有问题，除非考虑到新插入的可能是热点，暂没能想出更好的理由。
多级Hash弱化了这个问题，它引入了更多的数组，比如20个，第一个位置被占了，就试第二个位置，依次类推，级数够多，最终能找到存放位置的概率就很高。但是也带来了另一个问题：太多级数，也会导致效率下降，因为每次都需要遍历级数次。常规的实现中，一般不同级的桶数会设定不同，一般从1级往后递减。
BloomFilter的用途和Cuckoo Hash、多级Hash明显不同，但同样通过多个数组来降低冲突概率，所以说它们很亲。
总的来说，这些思想都非常简单，而且很实用。而Google的SparseHash则是另一种思想，省内存效率又不错，可以看作是虚拟化的思想，但它不适合用于共享内存这样一次性分配内存的场景。
最新文章
- 代写assignment
- 多线线程async与await关键字
- 使用Object的wait,notify,notifyAll做线程调度
- CentOS 6.5 Python 2.6.6+Flask 用wsgi方式部署在Apache 2.2.15下
- Android Design Support Library 的 代码实验——几行代码，让你的 APP 变得花俏
- nodejs的cs模式聊天客户端和服务器实现
- SRM 585
- ASP.NET MVC局部视图
- laravel安装插件laravel-ide-helper
- java 反射机制 观点
- redis与CPU、内存
- mac用pecl安装swoole可能出现的报错及解决办法
- 开放数据接口 API 简介与使用场景、调用方法
- java 线程理解
- jQuery链式选择器方法-导航
- 多目标遗传算法 ------ NSGA-II （部分源码解析）辅助变量 双链表操作 list.c
- RGB颜色参考
- python 获取excel文件的所有sheet名字
- Chrome 字体模糊解决
- HDU 5862 Counting Intersections 扫描线+树状数组