一个高性能无锁哈希表的设计和实现

无锁哈希表(Lock-Free Hash Table)是多线程编程中的理想数据结构，但是实现以及使用都需要一定的技巧。作者对此做了一个巧妙的设计实现，在现代X86平台上能取得千万次每秒的并发查找/增加/删除操作。 

通过考察各种基于CAS原子操作的无锁数据结构实现，目前公认可实现无锁安全的数据结构是数组和单向队列。其他实现都一定程度上受到ABA问题的威胁。数组的实现相对于单向队列要简单，所以无锁hash table理想的选择是数组，对于冲突不拉链。但是如何解决hash冲突呢？基本思想依然是开放寻址探测法。为了同时支持增加/查找/删除三种操作，业界各种开放寻址探测的算法，都为一次探测做了优化且照顾了其他探测次数以及最坏情况，但是这个照顾动作对于无锁设计实在是不太完美。为了达到O(1)的操作性能，开放寻址应该限制探测的次数为固定有限次，超过这个数目的探测应该通过算法降低为0，但同时用一个很小的数组（遍历模式）收容最坏情况（这里称之为保险数组）。由此可以实现，所有的操作都是对数组做无锁设计。

为了保证固定有限的探测次数极为有效（也就是够用），应该通过算法保证冲突率够低。降低冲突，一般不外乎两种措施:

一，增加hash表长度。此措施受限于内存，所以对每个bucket要尽量节省内存。一般用指针作为bucket单元就是很节省内存了。但64bit系统指针是8个字节，我认为4个字节作为bucket单元，就可以支持40亿buckets了，同样的内存带来双倍hash表长度，对降低hash冲突率有很大的改进。不用指针，怎么去找hash node呢？你自然会想到“内存池”。对，4个字节作为hash node在内存池的索引。

二，增加hash函数的分散性能，尽量接近理论极限。业界对于hash函数的讨论和实现已经有很多了，高计算性能分散性极佳的已有很多，比如murmur hash，city hash。 

但是，好像上面两种办法并没有什么特别的，跟大家常用的降低冲突率没啥改进啊。这里增加了第三种措施:固定有限的探测位置，如果尽量彼此独立（也就是不会导致二次卷积），将会从理论上降低hash冲突概率。那么如何做到彼此独立呢？作者的设计就是利用hash函数的输出 -- 选用输出128位结果的hash函数，分割成四个32位整数（128位是随机的因而四个整数是独立的），每个32bit整数对hash table长度求模，可以得到4个独立的位置，这样将大大减少冲突率。

但是，这样一般还不够好。原因是我们想尽量提hash table的装载率（load factor）且仍然能够处理冲突增加的倾向。为此，增加第二个数组，用上面四个32bit整数同样地映射出第二个数组内的4个位置，这样对一个key我们就有8个独立的位置了。8个位置都探测过了仍然冲突的怎么办？扔到保险数组里面去。

至此我们有三个优化目标：1，进入保险数组的概率应该极低；2，总的bucket利用率（性能墙）尽量高；3，两个数组占用的内存之和应该最小。通过计算（此略），可以限定1，得到2和3的最佳配置。在作者的实现中创建了三个数组：一个高load factor的大数组作为主hash表，一个低load factor的小数组作为辅hash表，和一个极其微小（64或128足够）的数组作为保险。

这个优化目标需要一个前提，就是基于概率计算的前提是可靠的，也就是对于任何key，选用hash函数输出要足够随机。这个前提，对于key足够长，city hash和murmurhash函数已经做得足够好。但是对于key小于12字节，就变差了。这个也是理论上没办法的事情。使用者应该明白并避让这一点。