最坏查找时间为O(1)的哈希算法小解

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注