u8,u8国际,u8国际官方网站,u8国际网站,u8国际网址,u8国际链接,u8体育,u8体育官网,u8体育网址,u8注册,u8体育网址,u8官方网站,u8体育APP,u8体育登录,u8体育入口

　　最近看了下布谷鸟哈希（Cuckoo hash），cuckoo hash是2002年提出来的老算法了，它可以应用在数据库的

　　首先要理解布谷鸟的行为，这也是算法的核心，可以观看一下动物世界布谷鸟的视频，布谷鸟不建巢却能让别人帮它孵蛋，出生后又将其他三个兄弟毁掉_哔哩哔哩_bilibili，这个三分钟的视频说了两个关键点：

　　若insert后哈希表空间会不够，则先进行扩容，再rehash，再继续3、4、5

　　用哈希函数h1(x)计算出下标i1，当bucket[i1]为空时，说明鸟巢可用，插入x

　　若bucket[i1]非空，用新值x将bucket[i1]上的老值x踢开（kick out），

　　对应小布谷鸟将老蛋踢出巢穴，老蛋当然也不能坐以待毙，继续kick out别的蛋

　　重复2，直到达到最大循环次数MaxLoop（插入失败）；或者所有被踢开的值都找到新位置（插入完成）

　　lookup逻辑：查找逻辑非常简单，去可能的两个巢穴里寻找，即去下标h1(x)和h2(x)寻找，若没有匹配上，则不存在（从这里可以发现查找是非常快的，且时间复杂度稳定是O(1)）

　　举个例子，插入129、875、312和234到哈希表中，哈希函数h1(x)是x%5，发生哈希冲突时使用哈希函数h2(x)=(x/10)%5

　　在插入234之前，没有哈希冲突，下标都用h1(x)=x%5计算出，如上图（a）

　　新元素234踢出老元素129，老元素129下一个可能的巢穴用h2(x)=(x/10)%5计算得出，是2，上图（c）

　　下标2（桶2）继续发生哈希冲突，新来者129踢出老元素312，312下一个可能的巢穴是1，是空，可以插入，上图（d）

　　图(a)解析：想插入元素x，用哈希函数h1(x)计算出下标i1，发现巢穴中i1已经存在元素y，于是用x踢开y；y用哈希函数h2(x)计算出下一个下标，发现存在元素z，于是用y踢开z；z用哈希函数h1(x)计算出下一个下标，填充进去，算法结束。

　　注意：在T1的元素发生哈希冲突时，用h2(x)去计算下一个下标、在T2的元素发生哈希冲突时，用h1(x)去计算下一个下标。

　　图(b)解析：想插入元素x，x踢出y，y踢出z，z踢出u，u踢出v，v踢出x....形成死循环，达到最大插入限制后，在T1插入失败；转而在T2插入，x踢出t，t踢出s，s踢出x...形成死循环，达到最大插入限制后，在T2插入失败，算法结束。

　　每个鸟蛋有两个可能的巢穴，要么在h1(x)，要么在h2(x)，或者都不在，但引入分支的话会让代码不能向量化执行，工程上可以采用mask的技巧消除分支

　　Cuckoo Hash loopup可以借助这个技巧完全向量化，代码有4个特点

　　性能图源自原论文，测试发生在哈希表大小稳定时（没有太多插入、删除），横坐标是哈希表大小，纵坐标是查询时间（clock cycle），负载因子load factor取1/3进行测试

　　可以看到，只要哈希表能在L2 cache装得下，所有方案查询时间几乎相同；当哈希表在L2 cache装不下，之后的随机查询 cache miss近乎1，这让线性探测成为平均情况的赢家（不管查询是否命中），因为从cache里读下一个可能的值快太多

　　插入：cuckoo插入性能是四种算法中最慢的，需要不断的kick out

　　此外，cuckoo hashing load可以很高，这意味着空间有限的场景下，cuckoo是不错的选择

　　布谷鸟哈希表是一种最坏情况O(1)查询时间复杂度的哈希表，并且具有与以前最好的字典相当的平均大小写性能（2002论文的结论），工程实现上lookup可以利用mask消除分支，达到查找完全向量化，对于大数据量下的查询场景，可以考虑此算法。它的load可以很高，内存空间有限的场景下，也可以考虑。