最坏查找时间为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插件的....现在预览功能莫名不能用实在是太糟糕了啊.

发表评论

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