这是一种开放地址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冲突的方法    (阅读：12057)
2. 关于memcache分布式一致性hash    (阅读：11328)
3. MinHash原理与应用    (阅读：6624)
4. 无锁HashMap的原理与实现    (阅读：6215)
5. LVS hash size解决4096个并发的问题    (阅读：5981)
6. 如果用户在5分钟内重复上线，就给他发警告，问如何设计？    (阅读：5553)
7. Ubuntu 下Hash校验和不符问题的解决    (阅读：5161)
8. 分布式系统hash策略    (阅读：4576)
9. redis源代码分析 - hash table    (阅读：4130)
10. Cuckoo Filter：设计与实现    (阅读：3884)