之前的网络算法课上老师讲到了一个最坏查找时间为O(1)的Hash算法,听上去挺神奇的,于是回来看了下原始的论文,顺便就总结到这里吧.
Hash 算法是个很常用的存储和查找的方法了,而其中的关键就是Hash的函数,这个函数的选取关系到最后算法的复杂度.这个算法使用了一个奇妙的函数,使得所用空间复杂度在保持O(n)的情况下最坏时间复杂度为O(1). 那么,在讲相关的数学推导之前先来定义一下所要用到的各类字母吧~
将要Hash的全部可能数值的集合统称为U,U中的元素个数定义为m. 实际要Hash的数的集合为S,其中的元素个数为n.显然我们有m \geq n,并且S \subseteq U. 除此之外,我们再定义一个p,并且p = m + 1,为了简化起见,我们认为p为素数,实际上这个也并不难做到,大不了往U里加些永远也用不到的数就好了.另外还有W,这个是将S分块后的集合,所谓的分块当然可以分一块(蛋疼不疼?),也可以分多块,准确来说如果分多块的话要加上下标来表示一下,不过这里先略去,就当做统称为W好了.那么第一步首先是一个引理.
Lemma:
给定一个W\subseteq U 且 |W|=r 另外还有 k \in U 和 s \geq r.令B(s, w, k, j) = | \{ x| x \in W~and~(kx~mod~p)~mod~s = j \} | 其中 1 \leq j \leq s ,于是就有 \exists k \in U 使得下面这个式子成立:
! \sum_{j = 1}^s {{B(s, w, k, j)} \choose {2}}<\frac{r^2}{s}
那么首先来解释一下吧,
B(s, w, k, j) = | \{ x| x \in W~and~(kx~mod~p)~mod~s = j \} | 的含义就是取出所有在W中的x,将这些x带入到函数(kx~mod~p)~mod~s 中计算,最后所得到的值为j的,满足这样条件的所有x的集合.那么为什么会是这样一个式子呢…..这个我也不知道..只能说数学大牛威武,灵机一动就是如此等级…. 那么后面那个式子,{B(s, w, k, j)} \choose {2}, 刚才不是算出了用前面那个函数计算过后值为j的集合么,现在我们把他们两两配对(真的可以随便配对么…你怎么知道其中的男女比例的….百合还好,要是Yoooooooooooooooooooooooooo什么的)最后得到的总对数的个数.
好吧,有了这个引理我们就可以从这个中得到两个推论:
COROLLARY1.
\exists k \in U使得\sum_{j = 1}^r B(r,W,k,j)^2<3r
COROLLARY 2.
\exists k’ \in U使得映射x \rightarrow (k’x~mod~p)~mod~r^2在W中是一一映射.
这两个式子可以由引理1直接得到,就是换换B(s, w, k, j)式中的字母就可以了,并不复杂.那么前戏就到这里为止了~下面就可以上本垒进入正题了,到底要如何实现呢? 首先我们将内存称作T.并且我们将其分块,第i块称其为T_i.在T_0块的第一小块T[0]中(你知道的,程序员们数数都是从0开始的….)存放上面反复提到的k,并且根据k的值和函数f(x)=(kx~mod~p)~mod~n的值将S分割成n个块,每个块我们称之为W_j,1 \leq j \leq n,每一个W_j都被映射到对应的T_j,1 \leq j \leq n上,并且我们把j的值保存在T_0大块中的第T[j]小块中.(不要被T_i和T[i]搞混了哦). 至于k值的选择,只需要满足推论1给出的条件就行了,因为推论1说满足条件的k是存在的,所以总而言之你是能找到的.而W_j映射到T_j的方法则可以由推论2来提供(这个稍后说),而且每个W_j所占用的空间是|W_j|^2 + 2.不过事情这样并没有完,推论2中不是还有一个k’么?之前的k我们记录到了T_0大块中的T[0]小块中,这个k’虽然是二房(厄…习惯性的用删除符删了不过现在找不到合适的名词了….所以大家意会吧…)但是也要保留下来用啊.另外,虽然说我们把S分割成了一堆W_j,但是并没有说是均匀分割,所以W_j的元素个数并没有准确的值,但是这个值却是很有必要的.于是我们对于每个T_i,在它的存储空间的前两部分里,一部分保存k’,另一部分就保留|W_j|.最后,其他的数x \in W_j则按照推论2的映射保存在T_j大块的第\big [(k’x~mod~p)~mod~|W_j|^2 \big ]+2个小块中.
那么现在就要到高潮部分了,最后我要查询S中的一个q要怎么做呢?
1. 设置T_0中T[0]的值为k并且设置j = (kq~mod~p)~mod~n.
2. 设置T_0中T[j]的值为对应T_j的首地址,由此可以得到T_j中前两格保存的k’和|W_j|的信息.
3. 访问T_j的第\big ((k’x~mod~p)~mod~|W_j|^2 \big )+2个小块,则q在S中当且仅当q在这个小格中.
好啦~那么我们查找的任务也就完成了~~怎么样,是不是很神奇呢?不过慢点,虽然我们查找时间上没什么问题了,但是空间上,还有构造这个结构所用的 时间上还 很糟糕.不过也并不是没有解决办法,感兴趣的人可以参考最后列出来的原始文献,这只是一个开头,后面还有好多哦,另外所有的证明也可以在文献里找到,如果你觉得我这说的不清楚,或者有错(真心希望没有错..否则的话太糟糕了….),还请参考原始的资料哦.
Storing a Sparse Table with O(1) Worst Case Access Time by MICHAEL L. FREDMAN AND JÁNOS KOMLÓS
PS:其实我只是来测试WP LaTeX插件的….现在预览功能莫名不能用实在是太糟糕了啊.