Hopscotch Hashing
浏览:2412次 出处信息
这是一种开放地址HASH,主要目的是为了提高查询速度。提高查询速度常用的思路是在插入的时候对数据作调整,让数据更紧凑。常用的方法在HASH表比较满的情况下,复杂度都很难保证。这个方法的特点是,它可以保证最坏情况下,查询的复杂度也是个常数。
元素X算HASH后,应该存在I节点,则允许它存在【I,I+H)之间第一个空闲的节点,H一般去32,一是H比较小,用一个INT作BITMAP就可以表示它后面哪些元素是HASH到这里的。二是,H太大,跨越的CACHE行太多,性能得不到保证。
如果【I,I+H)之间都没空闲的了,可以把【I,I+H)之间本应该HASH到I后面节点的数据往后挪。如果不管怎么挪都不行,就REHASH,把HASH表增大。
根据这样构造出来的HASH表,查询的时候至多访问H个元素。
插入的复杂度跟普通线性探测的HASH差不多,都是找到第一个空闲的就行了。
难点是REHASH。如果在负载还很低的时候,就需要REHASH,那就不如用普通线性探测的HASH。论文里认为REHASH的概率,跟有H个元素HASH到同一个节点的概率是相同的,为(1/H!)。我觉得这个分析是有问题的,因为相邻的节点是互相影响的,不需要H个节点就可能无法调整了。比如I节点有H/2+1个,I+1有H/2+1个,就无法调整了。所以对这个方法的实用性表示怀疑。
建议继续学习:
- HashMap解决hash冲突的方法 (阅读:11258)
- 关于memcache分布式一致性hash (阅读:10698)
- MinHash原理与应用 (阅读:5874)
- LVS hash size解决4096个并发的问题 (阅读:5430)
- 无锁HashMap的原理与实现 (阅读:5369)
- 如果用户在5分钟内重复上线,就给他发警告,问如何设计? (阅读:4875)
- Ubuntu 下Hash校验和不符问题的解决 (阅读:4506)
- 分布式系统hash策略 (阅读:3762)
- redis源代码分析 - hash table (阅读:3550)
- 一致性hash算法 (阅读:3404)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:趣题:不用相似怎么办?
后一篇:字符串匹配那些事(一) >>
文章信息
- 作者:杨镇锋 来源: 我思故我在
- 标签: hash
- 发布时间:2011-07-09 22:32:03
建议继续学习
近3天十大热文
- [46] 界面设计速成
- [42] Oracle MTS模式下 进程地址与会话信
- [42] 视觉调整-设计师 vs. 逻辑
- [40] 图书馆的世界纪录
- [40] IOS安全–浅谈关于IOS加固的几种方法
- [39] 【社会化设计】自我(self)部分――欢迎区
- [39] 如何拿下简短的域名
- [39] android 开发入门
- [37] 程序员技术练级攻略
- [35] 读书笔记-壹百度:百度十年千倍的29条法则