Hopscotch Hashing
浏览:2444次 出处信息
这是一种开放地址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冲突的方法 (阅读：11444)
- 关于memcache分布式一致性hash (阅读：10791)
- MinHash原理与应用 (阅读：6046)
- 无锁HashMap的原理与实现 (阅读：5594)
- LVS hash size解决4096个并发的问题 (阅读：5501)
- 如果用户在5分钟内重复上线，就给他发警告，问如何设计？ (阅读：4926)
- Ubuntu 下Hash校验和不符问题的解决 (阅读：4682)
- 分布式系统hash策略 (阅读：3843)
- redis源代码分析 - hash table (阅读：3657)
- 一致性hash算法 (阅读：3463)
QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习
扫一扫订阅我的微信号：IT技术博客大学习
<< 前一篇：趣题：不用相似怎么办？
后一篇：字符串匹配那些事（一） >>
文章信息
- 作者：杨镇锋 来源： 我思故我在
- 标签： hash
- 发布时间：2011-07-09 22:32:03
建议继续学习
近3天十大热文
-
[84] memory prefetch浅析 -
[53] 基本排序算法的PHP实现
-
[52] 深入浅出cassandra 4 数据一致性问
-
[50] 转载：cassandra读写性能原理分析
-
[45] 字符引用和空白字符
-
[42] MySQL半同步存在的问题
-
[41] 获取Dom元素的X/Y坐标
-
[40] javascript插入样式
-
[40] Inline Form Labels
-
[38] JS中如何判断字符串类型的数字
