之前的网络算法课上老师讲到了一个最坏查找时间为$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插件的….现在预览功能莫名不能用实在是太糟糕了啊.