关于哈希函数（hash）的一些论文综述

关于哈希函数（hash）的一些论文综述
http://hi.baidu.com/zkheartboy

2007-11-17 14:56
我这段时间看了一些关于哈希函数的论文， 也有一些自己的想法。本文先只讲述看的别人的论文的Idea， 方便以后有谁想了解哈希函数的话，可以很快入门。
首先哈希函数其实是非常难以找到的，好的哈希函数更是凤毛麟角。Knuth.D.E在其The Art of Computing Programming. volume 3 ：Sorting and Searching 一书中就讲到讲31个最常用英文单词映射到43个哈希地址空间需要的搜索空间为10的43次幂。对于我们常用的词典，一般含有几万个单词，因此需要的搜索空间几乎为无穷大。因此， 构造哈希函数的过程实际上就是一个大浪淘金或者大海寻针的过程。
Cichelli第一次在大海中找到一口小针。Cichelli在“Mimimal Perfect Hash Function made simple” 一文中首次提出一种可行的最小完美哈希函数的构造算法。Cichelli通过对词典每个单词的首尾两字母各关联一个整数，取该两整数以及单词长度之和作为 该单词的哈希值。同时，Cichelli在其论文中提出了对词典的两步排序策略，使对势（词典含有单词的数目）在40左右的词典构造哈希函数的时间只需要 数秒钟。缺点是如果两单词长度系统，首尾字母也相同，则不能区分。例如women和woman，jun和jan。同时排序困难，构造速度比较慢。最致命的 缺点是词典势超过45时基本上找不到哈希函数。
David Alan Wolverton针对Cichelli算法根本不能解决简单的Ada语言保留字的事实，提出单词哈希值的计算方法：H（key）＝X（first)+ X(last)+2.X(second-to-last)+ key-length. 在“A perfect hash function for Ada Reserved words”一文中，作者成功识别了63个Ada语言保留字，将其映射到71个地址空间。
Curtis .R.Cook在“A letter oriented minimal perfect hashing function”一 文中指出了Cichelli算法赋值顺序的缺陷，并提出了更改Cichelli赋值顺序的办法。第一将首尾字母相同的单词其字母关联较大整数，其次每个对 应一个（ch1，ch2，length) 三元组，同时如果某个单词ch2出现频率大于ch1，则交换ch1和ch2。最后对ch2排序。
Cichelli算法， Wolverton算法和Cook算法其实同出一辙，其共同的致命点就是只能针对小词典构造哈希函数。一般不能超过45个单词。针对这个情况，Nick Cercone等人对哈希函数做了大量工作。在“Minimal and almost minimal perfect hash function search with application to natural language lexicon disign”一文中，Cercone提出了三种改善。
第一：将所有单词按照长度分组，对各分组使用Cichelli算法构造哈希函数，然后将各分组哈希函数合并。
第二：构造一个从小到大排序的整数序列（a1，a2， a3.......an），使得任意两个数相加其和互异。对按照字频排序好的词典，依次关联整数a1， a2，a3等。
第三：让用户交互式的输入一个字母位置集，对该集合中所有字母都关联整数。
尽管如此，其方法还是不能适用于大词典。在其“Lexicon Design Using perfect hash function”一文中，Cercone提出针对不同位置的字母关联不同整数的方法。这两篇文章其实可以说一摸一样， 都在ACM上发表，时隔两年，完全是一稿多投。看了老外也很无耻。
可以看成，上面所有方法都是针对小词典有效的方法，同时，不能保证对任意词典构造完美哈希函数。我们的一个台湾同胞该出手时就出手，C C Chang 在“The study of an ordered minimal perfect hashing scheme”一文中，Chang利用中国剩余理论，提出了一种针对质数序列构造保序最小完美哈希函数的方法。对一个质数序列（m1， m2， m3.......mn），构造
Mi＝m1.m2....mn/mi
Mibi=1 % mi.
C=ΣMi.bi.i
由于其质数产生器只能产生40个左右质数， 同时不能针对字符串构造哈希函数，因此其方法作用很有限。基本上只有数学意义。
真正意义上能够处理大规模词典的算法还是Sager在其“A polynomial time generator for minimal perfect hash functions”一文中提出的Mincycle算法。应该说其算法虽然没有实际解决大词典问题，而且有些情况对小词典也不一定管用，但是他开创了一个哈希函数的新纪元。其Idea就是对每个单词关联一个三元组（ho，h1，h2），作者推荐的h0，h1和h2如下：
h0(key)＝{ length(key)+ Σwi}% N i=1, 4, 7,11......
h1(key)={ Σwi} % r i=1,3,5,7......
h2(key)={ Σwi} % r +r i=2, 4,6,8......
而哈希函数的构造就是要构造g：R－>【0..N－1】使得
H(key)={h0(key)+g(h1(key)) +g(h2(key))} % N 是一个完美哈希函数。
很明显，该方法不能区分aabb和bbaa两个单词。（首席注）
历史的车轮滚滚向前，新的哈希函数如雨后春笋搬涌现出来。上世纪九十年代哈希函数基本成熟。对哈希函数有了两个 分支（首席个人认为，如有雷同，纯属巧合）。一个分支就是针对大规模字符串词典，这就是我们常见的词典。另一个分支就是针对大规模稀疏整数集合，就是将一 个大规模整数集合的所有元素映射到一个较小集合。
花开两朵，各表一支。Edward A. Fox等就是第一个分支的核心人物。在“Practical minimal perfect hash function for large databases ”一文中， Fox等采用伪随机数产生器为每个字符每个位置产生三个随机数，计算各单词的h0， h1，h2如下：
h0(key)={ Σtable0i(ki) }% n； 其中i＝1，2，3....y，y为单词长度
h1(key)={ Σtable1i(ki) }% r； 其中i＝1，2，3....y，y为单词长度
h2(key)={ Σtable2i(ki) }% r＋r； 其中i＝1，2，3....y，y为单词长度
对词典构建其相关图。并依此对相关图各节点排序，以次顺序依次对对节点关联整数，使得H(key)={ho(key）+ g[ h1(key) ]+ g[ h2(key) ] } % n 为最小完美哈希函数。
Fox 等还在其“Order－preserving minimal perfect hash functions and information retrieval”一文中提出保序最小完美哈希函数的构造。保序最小完美哈希函数就是使词典中各单词的哈希值与其在词典中的位置一致。其提了三种方法。

• 第一个方法基于无圈图。也就是说只要构造的相关图不包含圈，就可以按照顺序给各单词映射到一个顺序递增的哈希值。
  
• 第二个方法基于两级哈希。即对词典构造哈希函数后， 再用一个哈希函数将各单词的哈希值转换为其在词典的位置。
  
• 第三个方法基于节点标识。就是利用相关图中大约13％的孤立节点，将某些圈中边转移到孤立节点。从而实现保序最小完美哈希函数。

九十年代还有一个可以提一下的哈希函数方法就是Pearson在“Fast hashing of variable length text strings”一文中提出的基于随机数数组的方法。Pearson并没有仔细讲述该随机数数组的产生过程及其修改，而是直接给出了一个256个元素的数 组T[0..255]，对于一个key＝C1C2C3...Cn，其哈希函数计算过程如下：
hah=0;
for(i=1; i hash= T[ hash xor C ];
其中xor 是大家熟悉的异或运算。
至于对稀疏整数集合构造哈希函数的方法也不少，一般都是出现在本世纪初。至于其具体方法由于本人也没有完全看明白，这里不妄加评论，以免贻笑大方。
那么，我们还可以做什么呢？或者说首席还准备做什么呢？
本人私下认为，至少还有以下几个方面可以考虑：
第一： 就是我上次报告提及的全词位置相关完美哈希函数。第一版本的结果并没有想象的那么理想。填充因子并没有想象的那么高，在第二个版本中我打算做如下优化。

• 将单词哈希值随机在给定范围内选择，不是尽量小。
  
• 引入多级相关图的概念。利用该结构对赋值排序。
  
• 对唯一标识字符最后统一赋值。

第二：针对Fox算法需要大量工作空间的问题， 同时针对相关图中某些节点度太大影响赋值过程的问题，提出了一种相关图的平滑技术，使相关图各节点度比较均匀，现在实验结果感觉几种均匀策略都不错， 能够使度非常均匀。
第三：就是上次报告说过的用哈希函数分词的问题，报告上说的方法当然也可以，现在正在考虑一种基于均匀技术的分词策略。因为所有这一切都必须等哈希函数构造的效果。所以对此的评价目前尚为时太早。
哈希函数搞了我太长时间了， 我希望赶快实现已有的想法。毕竟挖掘这边还没有入门。希望跟大家一起共同进步。请大家对我的工作进行点评。希望看到大家的回复。