Cuckoo hash算法分析——其根本思想和bloom filter一致 增加hash函数来解决碰撞 节省了空间但代价是查找次数增加
基本思想:
cuckoo hash是一种解决hash冲突的方法,其目的是使用简单的hash 函数来提高hash table的利用率,同时保证O(1)的查询时间
基本思想是使用2个hash函数来处理碰撞,从而每个key都对应到2个位置。
插入操作如下:
1. 对key值hash,生成两个hash key值,hashk1和 hashk2, 如果对应的两个位置上有一个为空,那么直接把key插入即可。
2. 否则,任选一个位置,把key值插入,把已经在那个位置的key值踢出来。
3. 被踢出来的key值,需要重新插入,直到没有key被踢出为止。
我们先来看看cuckoo hashing有什么特点,它的哈希函数是成对的(具体的实现可以根据需求设计),每一个元素都是两个,分别映射到两个位置,一个是记录的位置,另一个是 备用位置。这个备用位置是处理碰撞时用的,这就要说到cuckoo这个名词的典故了,中文名叫布谷鸟,这种鸟有一种即狡猾又贪婪的习性,它不肯自己筑巢, 而是把蛋下到别的鸟巢里,而且它的幼鸟又会比别的鸟早出生,布谷幼鸟天生有一种残忍的动作,幼鸟会拼命把未出生的其它鸟蛋挤出窝巢,今后以便独享“养父 母”的食物。借助生物学上这一典故,cuckoo hashing处理碰撞的方法,就是把原来占用位置的这个元素踢走,不过被踢出去的元素还要比鸟蛋幸运,因为它还有一个备用位置可以安置,如果备用位置上 还有人,再把它踢走,如此往复。直到被踢的次数达到一个上限,才确认哈希表已满,并执行rehash操作。如下图所示(图片来源):
我们不禁要问发生哈希碰撞之前的空间利用率是多少呢?不幸地告诉你,一维数组的哈希表上跟其它哈希函数没什么区别,也就50%而已。但如果是二维的呢?
一个改进的哈希表如下图所示,每个桶(bucket)有4路槽位(slot)。当哈希函数映射到同一个bucket中,在其它三路slot未被填满 之前,是不会有元素被踢的,这大大缓冲了碰撞的几率。笔者自己的简单实现上测过,采用二维哈希表(4路slot)大约80%的占用率(CMU论文数据据说 达到90%以上,应该是扩大了slot关联数目所致)。
摘自:http://coolshell.cn/articles/17225.html
最新文章
- PHP就业班心得:IP与域名以及DNS和端口号的概念
- angular2-aot-webpack 生产环境下编译angular2
- DOM事件类型详解
- 渗透测试报告收集、生成工具MagicTree
- iOS与日期相关的操作
- winpcap 发送接收速率
- oracle 物化视图导入导出报错
- 玩转Web之JavaScript(二)-----javaScript语法总结(二) 涉及Date与数组的语法
- 十天学会php第五天
- ajax 实现三级联动
- react入门到进阶(一)
- 内网IP无法访问
- Windows下安装tesserocr
- arcgis api 3.x for js 入门开发系列二十二地图模态层(附源码下载)
- canvas绘图工具
- hibernate @OneToMany等注解设置查询过滤条件
- 转 ObjExporter Unity3d导出场景地图寻路
- [SequenceFile_1] Hadoop 序列文件
- TopCoder FlowerGarden【拓扑排序】
- [LeetCode&;Python] Problem 455. Assign Cookies
热门文章
- Ubuntu 18.04 初始化(server版本 )
- COM对象模型
- 对Mybatis的理解
- centos7.0 tomcat9.0 ip访问 manager
- jquery 使用笔记
- Django之stark组件的使用和总结
- 我的Android进阶之旅------>Android无第三方Jar包的源代报错:The current class path entry belongs to container ...的解决方法
- centos7 Authentication failure
- lua的弱弱引用表
- abap Excel 导入