Perfect Hash and the gperf Tool

MIT的算法导论课上,老师用了整整一节课来讲Perfect Hash这个问题。所以这是一个很重要的问题,但是内容太多,我这里只是做一个简要的介绍。感兴趣的请去MIT的网站上下载视频以了解的更详细。
Perfect Hash主要是为了降低或消灭Hash冲突。 当你用Hash表来存储一个集合或映射时,不同的key可能被映射到同一个槽(slot)当中,此时就得用链表或者Open Address或其它方法来解决Hash冲突。毫无疑问,冲突越多,查找性能越低。对于一个含有N个元素的Hash表,在最坏情况下,查找效率是O(N)的。但是如果这是一个静态的Hash表,所有的key预先已知,我们就可以挑选适当的Hash函数来把最坏情况降低到O(1)。 本文会先介绍通用散列函数族(Universal Hashing Functions),然后介绍Perfect Hash,然后介绍如何使用gperf这个工具生成这样的Hash函数。

通用散列函数族(Universal Hashing Functions)

先介绍一下背景。对于任何的Hash函数,我们都可以刻意构造一些特殊的输入,使得Hash冲突非常高,从而让Hash表的性能大大降低。为了抵御这种攻击,我们可以实现一大堆的Hash函数,然后在构造Hash表的时候从中随便挑一个。由于你不知道我挑的是哪一个,你也就没办法捣乱了。这有点像用随机化方法来优化quick sort在bad case下的表现。我们也打算用随机化方法来优化hash表面对bad case时的性能。
通用函数族的定义:设集合\(U\)是一个全域, \( \left| U \right| \geq n \),令集合\( V=\{0,1,2,3,...,n-1\} \),\(H\)是一个从\(U\)到\(V\)的Hash函数族。如果\(H\)满足:对于任意的元素\( x_1,x_2,x_3,...,x_k \) 以及从\(H\)中均匀随机选取的一个散列函数h,有\(h(x_1) = h(x_2) = h(x_3) =... = h(x_k)\)的概率小于\(\frac{1}{n^{k-1}}\),那么\(H\)就被称为k维通用Hash函数族
所以,如果hash函数h是从一个2维通用hash函数族中选取的,那么对于任何两个元素x,y,它们的hash值h(x)=h(y)的概率最多为1/n。
下面给出一个二维通用函数族的例子:
$$ h_{a,b}(x) = ((ax+b)\mod p ) \mod n .$$
其中p是质数,\( \left| U \right| \leq p , 1 \leq a \leq p-1, 0 \leq b \leq p \)。至于它为什么是二维通用函数族,证明略过。MIT算法导论课上讲的以随机向量和点积的方式构造二维通用函数族的例子,是上面这个函数的延伸。因为我还没有看见谁在实际代码中这么用,所以细节不再探讨。
下面再给出一个重要的推论:
如果hash函数h是从一个二维通用散列函数族中均匀随机选取的,我们用它把n个元素映射到m个桶中,如果\(m \geq n^2\),那么出现冲突(某个桶中有2个或2个以上元素)的概率小于0.5。
证明: 设输入的key为\(k_1,k_2,...,k_n\). 定义示性随机变量\(X_{i,j}\)
$$ \begin{equation} X_{i,j}=\begin{cases} 1 & \text{if}\ h(k_i) = h(k_j) \\ 0 & \text{otherwise} \end{cases} \end{equation} $$
下面计算X的数学期望
$$ E[X] = E[\sum{X_{ij}}] = \sum{E[X_{ij}]} \leq \frac{1}{m}\binom{n}{2} < \frac{n^2}{2m} $$
接着用Markov不等式有: \(P(X \geq \frac{m^2}{n}) \leq P(X\geq 2E[X]) \leq \frac{1}{2} \) 。 证明完毕。

完美散列(Perfect Hash)

如果对于给定集合S,存在Hash函数h,使得对于S中的任意元素,都能在O(1)时间内完成Hash查找,那么h就是S的完美散列。为了找到这样一个hash函数,我们可以采用随机挑选、反复重试的方法。即,先构造一个二维通用散列函数族,然后从中挑一个,把所有元素都hash一遍,如果发现有冲突,那么重新再挑一个。放心,不会很麻烦。你可以视为我们在扔一枚均匀的硬币,为了得到有正面向上,平均需要扔多少次?由于每次的成功概率是0.5,所以根据几何分布的结论,平均2次就够了。
空间复杂度为O(N)的方案:传统的开链法中,每个slot中是一个链表。现在我们把链表换成Hash table。于是对于每个元素x,我们会做两次散列。假设我们有N各元素,并且第一级散列有N个slot。设第一次散列后,第i个slot中有\(c_i\)个元素,那么我们只需要\(c_i^2\)的空间就可以让第二级hash表不冲突。可以证明\(\sum_{i=1}^{N}{c_i^2 \leq N } \)
完美散列还有一个重要的应用领域是稀疏数据的压缩。参见:http://research.microsoft.com/en-us/um/people/hoppe/proj/perfecthash/

gperf

终于到实用的部分了。C++有一个很著名的网络库叫ACE,它的主要作者是Douglas C. Schmidt,而gperf这个工具也是他写的。下面给一个例子,如何利用它把12个月份,从英文名对应到具体的数字,以及它有多少天。
首先我们需要一个gperf的输入文件。内容如下:
%language=C++
%includes
struct month { char *name; int number; int days; int leap_days; };
%%
january,   1, 31, 31
february,  2, 28, 29
march,     3, 31, 31
april,     4, 30, 30
may,       5, 31, 31
june,      6, 30, 30
july,      7, 31, 31
august,    8, 31, 31
september, 9, 30, 30
october,  10, 31, 31
november, 11, 30, 30
december, 12, 31, 31
 %%
解释一下。这个文件一共有三部分,用%%隔开。其中第一部分是一些声明。
%language=C++: 最终生成的源代码是C++的。
%includes : 这个告诉gperf,把必须包含的系统头文件(如stdlib.h)都包含进来。
struct Month { const char *name; int number; int days;}; 这里我们定义了一个结构体,来描述第二部分的数据。
第二部分一共12行,对应12个月份。每一个有三项,分别用逗号隔开。
如 january, 1, 31
分别对应Month结构体中的name, number, days 这三个变量
第二个%%后面是第三部分,通常用来放一些函数。在这个例子中是空的。
把这些东西保存成months.txt,接着,用gperf命令把它变成C++的头文件
$ gperf -t months.txt > months_gperf.hpp
然后就可以用C++写我们的hello world了!
#include <iostream>
#include "months_gperf.hpp"

int main(int argc,char* argv[]){  
  char* month_name=argv[1];
  Month* m=Perfect_Hash::in_word_set(month_name,strlen(month_name));
  if(m==NULL){
    std::cout<<"not found"<<std::endl;
    return 0;
  }
  std::cout<<month_name<<" is the "<<m->number<<"th month,it has "
  <<m->days<<" days"<<std::endl; 
  return 0;
}
它把命令行的第一个参数作为month_name读入,然后打印出它是今年的第几个月,以及有多少天。
例如:
$ ./t may may is the 5th month,it has 31 days
下面聊一聊它内部的实现。
gperf这个工具并没有上一节所说的二次散列表(Secondary hash table)。gperf生成的是一个一维的散列表,这个表的大小也许和输入集一样大,也许比它更大些。首先,gperf会从输入的keys中挑选一些字母做成keysig。在我们这个例子中是这样:
keysig, keyword
my, may ot, october jn, january jn, june jl, july cd, december mr, march ag, august ar, april nv, november bf, february ps, september
然后它会尝试给每一个字母赋予一个associated value,最终的hash函数就是把这些associated values加起来,然后加上字符串的总长度(你也可以要求gperf不加长度)。在这个例子中,hash值是这么计算的:hash(str) = strlen(str) + asso_values[(unsigned char)str[2]] + asso_values[(unsigned char)str[0]];
其中:
asso_values[a] = 5, occurrences[a] = 2
asso_values[b] = 5, occurrences[b] = 1
asso_values[c] = 5, occurrences[c] = 1
asso_values[d] = 0, occurrences[d] = 1
asso_values[f] = 5, occurrences[f] = 1
asso_values[g] = 0, occurrences[g] = 1
asso_values[j] = 0, occurrences[j] = 3
asso_values[l] = 10, occurrences[l] = 1
asso_values[m] = 0, occurrences[m] = 2
asso_values[n] = 0, occurrences[n] = 3
asso_values[o] = 5, occurrences[o] = 1
asso_values[p] = 0, occurrences[p] = 1
asso_values[r] = 0, occurrences[r] = 2
asso_values[s] = 0, occurrences[s] = 1
asso_values[t] = 0, occurrences[t] = 1
asso_values[v] = 0, occurrences[v] = 1
asso_values[y] = 0, occurrences[y] = 1
最终hash值就是index,最大的hash值是18(february),所以静态分配一个长度为19的数组即可。
关于gperf的设计可参考这篇pdf: http://www.cse.wustl.edu/~schmidt/PDF/gperf.pdf

Real world example: https://github.com/adobe/webkit/blob/master/Source/WebCore/platform/ColorData.gperf


ref: http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-and-faster-than-memcmp.html

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥