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

之前的网络算法课上老师讲到了一个最坏查找时间为\(\)的Hash算法,听上去挺神奇的,于是回来看了下原始的论文,顺便就总结到这里吧.

Hash 算法是个很常用的存储和查找的方法了,而其中的关键就是Hash的函数,这个函数的选取关系到最后算法的复杂度.这个算法使用了一个奇妙的函数,使得所用空间复杂度在保持\(\)的情况下最坏时间复杂度为\(\). 那么,在讲相关的数学推导之前先来定义一下所要用到的各类字母吧~

将要Hash的全部可能数值的集合统称为\(\),\(\)中的元素个数定义为\(\). 实际要Hash的数的集合为\(\),其中的元素个数为\(\).显然我们有\(\),并且\(\). 除此之外,我们再定义一个\(\),并且\(\),为了简化起见,我们认为\(\)为素数,实际上这个也并不难做到,大不了往\(\)里加些永远也用不到的数就好了.另外还有\(\),这个是将\(\)分块后的集合,所谓的分块当然可以分一块(蛋疼不疼?),也可以分多块,准确来说如果分多块的话要加上下标来表示一下,不过这里先略去,就当做统称为\(\)好了.那么第一步首先是一个引理.

Lemma:

给定一个\(\)\(\) 另外还有 \(\)\(\).令\(\) 其中 \(\) ,于是就有 \(\) 使得下面这个式子成立:

\[\]

那么首先来解释一下吧,
\(\) 的含义就是取出所有在\(\)中的\(\),将这些\(\)带入到函数\(\) 中计算,最后所得到的值为\(\)的,满足这样条件的所有\(\)的集合.那么为什么会是这样一个式子呢.....这个我也不知道..只能说数学大牛威武,灵机一动就是如此等级.... 那么后面那个式子,\(\), 刚才不是算出了用前面那个函数计算过后值为\(\)的集合么,现在我们把他们两两配对(真的可以随便配对么...你怎么知道其中的男女比例的....百合还好,要是Yoooooooooooooooooooooooooo什么的)最后得到的总对数的个数.
好吧,有了这个引理我们就可以从这个中得到两个推论:

COROLLARY1.
\(\)使得\(\)

COROLLARY 2.
\(\)使得映射\(\)\(\)中是一一映射.

这两个式子可以由引理1直接得到,就是换换\(\)式中的字母就可以了,并不复杂.那么前戏就到这里为止了~下面就可以上本垒进入正题了,到底要如何实现呢?
首先我们将内存称作\(\).并且我们将其分块,第\(\)块称其为\(\).在\(\)块的第一小块\(\)中(你知道的,程序员们数数都是从0开始的....)存放上面反复提到的\(\),并且根据\(\)的值和函数\(\)的值将\(\)分割成\(\)个块,每个块我们称之为\(\),每一个\(\)都被映射到对应的\(\)上,并且我们把\(\)的值保存在\(\)大块中的第\(\)小块中.(不要被\(\)\(\)搞混了哦). 至于\(\)值的选择,只需要满足推论1给出的条件就行了,因为推论1说满足条件的\(\)是存在的,所以总而言之你是能找到的.而\(\)映射到\(\)的方法则可以由推论2来提供(这个稍后说),而且每个\(\)所占用的空间是\(\).不过事情这样并没有完,推论2中不是还有一个\(\)么?之前的\(\)我们记录到了\(\)大块中的\(\)小块中,这个\(\)虽然是二房(厄...习惯性的用删除符删了不过现在找不到合适的名词了....所以大家意会吧...)但是也要保留下来用啊.另外,虽然说我们把\(\)分割成了一堆\(\),但是并没有说是均匀分割,所以\(\)的元素个数并没有准确的值,但是这个值却是很有必要的.于是我们对于每个\(\),在它的存储空间的前两部分里,一部分保存\(\),另一部分就保留\(\).最后,其他的数\(\)则按照推论2的映射保存在\(\)大块的第\(\)个小块中.

那么现在就要到高潮部分了,最后我要查询\(\)中的一个\(\)要怎么做呢?

1. 设置\(\)\(\)的值为\(\)并且设置\(\).

2. 设置\(\)\(\)的值为对应\(\)的首地址,由此可以得到\(\)中前两格保存的\(\)\(\)的信息.

3. 访问\(\)的第\(\)个小块,则\(\)\(\)中当且仅当\(\)在这个小格中.

好啦~那么我们查找的任务也就完成了~~怎么样,是不是很神奇呢?不过慢点,虽然我们查找时间上没什么问题了,但是空间上,还有构造这个结构所用的 时间上还 很糟糕.不过也并不是没有解决办法,感兴趣的人可以参考最后列出来的原始文献,这只是一个开头,后面还有好多哦,另外所有的证明也可以在文献里找到,如果你觉得我这说的不清楚,或者有错(真心希望没有错..否则的话太糟糕了....),还请参考原始的资料哦.

参考文献:

Storing a Sparse Table with O(1) Worst Case Access Time by MICHAEL L. FREDMAN AND JÁNOS KOMLÓS

PS:其实我只是来测试WP LaTeX插件的....现在预览功能莫名不能用实在是太糟糕了啊.

发表评论

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