2009年2月25日星期三

Second-hand Hash

二手散列这个名字是我起的,官方叫法是Cuckoo hashing,他是一个散列算法框架而不是一个散列函数。事实上,二手散列需要两个散列函数h1和h2,对应两个散列表T1和T2,散列函数从值域(domain of values)映射到键域(domain of keys),散列表把键应成值。判断值x是否存在于字典D中:lookup(x,D)=(T1[h1(x)]==x || T2[h2(x)]==x)。
插入的方式很有趣,如果有散列冲突,就把原有值的踢出去,提到另一个表里去,知道没有冲突为止。用伪代码来说:
insert x into D:
如果lookup(x,D)返回真,返回
重复maxloop次:
    若T1[h1(x)]为空,则T1[h1(x)]=x后返回
    交换T1[h1(x)]和x
    若T2[h2(x)]为空,则T2[h2(x)]=x后返回
    交换T2[h2(x)]和x
如果代码走到了这一行,调整T1,T2的大小和h1,h2的值域,重新insert x into D

这是一个完美散列,因为我们确定地知道,lookup至多探查两次,绝对O(1)。难点在insert的复杂度的分析。注意到在insert中使用了递归调用,因此必需首先证明,insert的做法能够以较大的概率在有限步内终止。然后还能证明,insert的均摊复杂度的期望也是常数。证明过程这里就不转载了。
------
另外有一种d手链式散列的框架,针对一种特殊的问题,也有很漂亮的结果,出自《概率与计算》一书。n个球放入n个箱子,每个球放的时候先从n个箱子中等概率地选d(>=2)个箱子,然后放入这d个箱子中球最少的那个箱子。可以证明,以1-o(1)的概率,球最多的箱子中球的个数(称为最大负荷)是
基于此,我们可以开发出确定性O(d)时间插入、依很大的概率在至多lnlnn/lnd时间查找的链式散列算法。
d=1时,没有选择的余地,书中引理5.12告诉我们:n个球独立等概率放入n个箱子,最大负荷以1-1/n的概率至少为lnn/lnlnn。这告诉我们,在散列表比较满的时候,“一手”链式散列的性能和二分查找相当。对比发现,d手链式散列对传统链式散列的改进还是挺大的。
------
应用中,二手散列或d手链式散列还有一个好处:在多核处理器上可以并行计算散列函数,进一步提高效率。
------
P.S.复杂度的概率分析中大量用到了切尔诺夫界技巧

没有评论: