技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> Hopscotch Hashing

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个,就无法调整了。所以对这个方法的实用性表示怀疑。

建议继续学习:

  1. HashMap解决hash冲突的方法    (阅读:11258)
  2. 关于memcache分布式一致性hash    (阅读:10698)
  3. MinHash原理与应用    (阅读:5874)
  4. LVS hash size解决4096个并发的问题    (阅读:5430)
  5. 无锁HashMap的原理与实现    (阅读:5369)
  6. 如果用户在5分钟内重复上线,就给他发警告,问如何设计?    (阅读:4875)
  7. Ubuntu 下Hash校验和不符问题的解决    (阅读:4506)
  8. 分布式系统hash策略    (阅读:3762)
  9. redis源代码分析 - hash table    (阅读:3550)
  10. 一致性hash算法    (阅读:3404)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1