Cuckoo hashing主要适合在哪些场景使用?
正好我在博士时候做过几个基于cuckoo hashing的工作。回答一下。
先上答案cuckoo hashing适合空间需求量大，对读性能要求高，对写性能相对低，操作比例读为主写为辅的场景。理由基于Cuckoo hashing的优点和缺点。
优点包括
- 哈希表本身的空间利用率高。Pagh证明set associative为1也就是表宽为1 时，最大load factor（多少空间被利用）大概率能到50%；我们的实验显示表宽大于4以后，大概率load factor能到95%。
- 查询可以使用两次读完成。表宽不大的情况下，两次（可并行）的cacheline read就能完成一个查询。相比之下查询链式哈希表可能有多次pointer dereference，查询时间方差会大过cuckoo hashing
缺点包括
- 插入操作的复杂度大。当表接近其最大load factor时，会有很多次cuckoo操作才能完成一次插入
- 读写的高并发算法复杂。不像链式哈希表，每个bucket放一把读写锁就可以实现细粒度的读写并发，cuckoo hashing的写会涉及到多个且事先不预知的bucket，抢锁会复杂。有兴趣的可以看一下MemC3 论文里的分析
具体的应用列一些当年做过的基于基于Cuckoo Hashing的其他衍生数据结构和系统:
CuckooFilter: 一个基于Cuckoo Hashing的approximate set-membership数据结构。简单说来就是类似BloomFilter那样，可以用很小--O(N)--的空间代价近似存储和判定任意给定元素x是否属于一个N个元素的集合S。具体说来，当它判定任意元素x不属于S时，不会错；当它判定x属于S时，小概率会错。换言之，对于任何事先已知属于这个集合的元素，它绝不会误判；对于事先已知集合外的元素，它会以很小的概率误判。CuckooFilter在支持BloomFilter的功能的同时，还比BloomFilter多了删除元素的操作。这里主要利用到了Cuckoo Hashing的高空间利用率。https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdfMemC3: 一个基于memcached，但是使用Cuckoo Hashing来替代传统chained hashing来对memcached的空间利用率加以改进的工作。这里的难点在于实现cuckoo hash的同时能加上多线程读写高并发的支持。https://www.cs.cmu.edu/~binfan/papers/nsdi13_memc3.pdfCuckooSwitch: 使用Intel的DPDK系统搭建一个基于Cuckoo Hashing的地址查找表https://www.cs.cmu.edu/~binfan/papers/conext13_cuckooswitch.pdflibCuckoo: C++源码的高并发、低空间占用率的哈希表实现。这个现在很多公司包括微软都在用。efficient/libcuckoo
【Cuckoo hashing主要适合在哪些场景使用?】
■网友
conext 某年best paper：cuckoo switch
■网友
GitHub - zheng-ji/goCuckoo: 一个 CuckooFilter 的 Go 库
■网友
HPCA有一篇用cuckoo hashing实现较小缓存数据存储的文章 cuckoo directory
推荐阅读
- 中外合作研究：四万多年前东北亚真猛犸象主要以禾草苔草类为食
- 偷窃|车主要注意！有洗车工在打车内财物的主意
- 营销型外贸网站用哪种建站程序和语言比较好呢主要是适合优化，可扩展兼容性，安全性，后期网站扩展升级
- |福建海南省委主要负责同志职务调整
- 理科女选择啥专业
- 汽车知识|才开了一个月的特斯拉半路趴窝，车主要求换车，4s店:要折旧费
- 从未接触过软件测试和java，可以学习主要是自学这两种其一吗
- 过敏|阴虱的传播途径主要有2个，稍不注意，年轻男女就易中招
- 网络存储，数通，安全，这三个方面的工程师主要都是干啥，在现今那个技术找工作容易些呢
- 汽车知识|形式大于内容，长安CS75百万版上市，中期改款主要是换壳