Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8033038
  • 博文数量: 594
  • 博客积分: 13065
  • 博客等级: 上将
  • 技术积分: 10324
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-26 16:44
个人简介

推荐: blog.csdn.net/aquester https://github.com/eyjian https://www.cnblogs.com/aquester http://blog.chinaunix.net/uid/20682147.html

文章分类

全部博文(594)

分类: C/C++

2014-05-20 17:04:31

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明显不同,但同样通过多个数组来降低冲突概率,所以说它们很亲。

 

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

阅读(5967) | 评论(1) | 转发(0) |
0

上一篇:HDFS Federation

下一篇:C++11中的to_string

给主人留下些什么吧!~~

Heartwork2014-05-21 18:35:46

像Cuckoo Hash这种"发生冲突了就换另一个Hash试试"的东西都能当成一个算法, 算是被打败了.

对于简单粗暴的hash来说, 针对具体应用数据编写相应的hasher才是王道, 这个过程需要不断的调优和profile.