一个月前左右的某晚与Doctor Bai、Felix021讨论一个问题，其中要解决用尽量少的空间在尽量少的时间内查找一个集合中的一个元素（可以进行预处理）。
当时我们分析了trie、binary tree、block tree、hashing等各种查询方法的时空复杂度方面的优势劣势。讨论到最后对时空复杂度的限制都到了苛刻的地步。为了达到空间复杂度严格为n、每次查询时间复杂度为O(1)，我提出针对已知数据集构造一个“特别”的哈希函数，该函数对于当前数据集满足任意两个不同的key通过哈希后不会产生冲突。
当时felix用实际经验佐证这几乎是不可能的，Doctor Bai也对此持怀疑态度，不过还是承认：对于特定的数据集合，这种函数是可能存在的。
最近在读《深入搜索引擎》（Managing Gigabytes即MG的中文版）时居然遇上了这种避免所有冲突的哈希函数——最小完美哈希函数。
以下转述MG中对于最小完美哈希函数的介绍。
哈希的一些概念
哈希是一种常用的具有查找表功能并且提供平均情况下快速访问的标准方法。
哈希函数h：将n个键值xj的集合映射到一个整数集合的函数h(xi)，其值域是0<=h(xj)<=m-1，允许重复。
其中m>n/a，a（<=1）是装载因子。a越小，两个不同键值在相同哈希值相互冲突的可能性越小，然而冲突总是不可避免。
完美哈希函数
若一个哈希函数满足对于任意的xi和xj，当且仅当i=j时才有h(xi)=h(xj)，就是完美哈希函数(Perfect Hash Function, PHF)。即对一个键值集合L进行哈希时，不可能产生任何冲突。
如果哈希函数不仅是完美的，并映射到值域范围m=n，n个键值中的任意一个都一一映射到唯一整数，这是装载因子a=1，该函数称为“最小完美哈希函数”(Minimal Perfect Hash Function, MPHF)。
若一个最小完美哈希函数同时满足对于xi
当然，以上性质都是针对某一个键值集合L的，即所得哈希函数对于另外的键值集合可能不在满足以上性质。
完美哈希函数的设计
最小完美哈希函数是针对特定函数集合的，所以生成这些哈希函数需要对所求单一静态集合进行预计算生成函数。
最小完美哈希函数公式：
h(t) = ( g(h1(t)) + g(h2(t)) ) % n
h1(t1) = sum(t[i]*w1[i] , i:1–>|t|) % m
h2(t1) = sum(t[i]*w2[i] , i:1–>|t|) % m
构造一个OPMPHF的第一步就是要随机地选择函数h1和h2的映射方法。（最简单的方法：随机生成数组w1和w2）
将该问题转化为m点图（m-vertex graph），点的标号0~m-1。其中有n条边，每条边对应于h1(t)和h2(t)两个哈希值定义连接的两个顶点，每条边用h(t)值标记。此时构造完美哈希函数即通过g映射后使得每个顶点映射到0~n-1的整数( g(h1(t)) + g(h2(t)) ) % n。
（图例）
如果图是无环的，函数g很容易推导出来：任意选择一个未处理的顶点作为根，令g(v)=0，顺着该点出发的边，这些边指向的顶点用该边的h值标记下一代的顶点（该值等于边值减去顶点值之差）。如果不存在未标记的边，就选择下一个根重复进行如上操作。
算法综述（生成一个完美哈希函数）：
1、选定m的值（后面算法实用性理论证明中有说明）；
2、随机选择w1[i]和w2[i]（1<=i<=max{|t|}，其中max{|t|}为L中所有字符串的最大长度）；
3、生成一个图G=(V,E)，其中V={1,..,m}，E={(h1(t),h2(t)))}（其中t属于L）；
4、计算映射g（算法细节见后面描述）；
5、如果步骤4执行失败，跳到步骤2继续执行；
6、返回w1，w2和g。（根据上面的公式描述完美哈希函数）
步骤4细节（检查无环图，生成映射函数）：
1、对于V中的所有顶点v，令g(v)为未设定；
2、遍历V中的所有顶点v，如果g(v)未知，执行LabelFrom(v, 0)。
LabelFrom(v, c)操作:
1、如果g(v)的值已设定:
若g(v)!=c，报告（有环）失败；
否则，返回该节点已经被访问。
2、令g(v):=c；
3、遍历v的邻接点u,执行LabelFrom(u, h((v,u))-g(v))。
算法实用性的理论证明
（纯摘录，没深刻理解）
根据随机图理论分析，对于m<=2n，随着n的增长生成一个无环图的概率趋近于0。
当m>2n时，一个m个顶点n条边的随机图是一个无环图的概率近似于:sqrt((m-2*n)/m)，即发现第一个无环图之前生成图的数量的期望是sqrt(m/(m-2*n))。
总的看来，规定m>2n，生成哈希函数的代价与L的项数成正比。
另外，虽然通过完美哈希函数节省了哈希表的开销，但是g耗费的空间开销也是不小的；若将m/n比例降低到2以下，则生成无环图开销太大（只适合集合较小的情况）。
可以将2-graph（二维图）变为3-graph（三维图）降低m/n的比值。（原理不变：一幅图可用）
点评：
(by liulixiang)
“最小完美哈希函数”从概念上很完美，生成的思想也很不错，不过实际运用中并不是那么常见：应用中已知数据集再做哈希的情况不是特别多，对时空的复杂度要求也没有过于苛刻，普通的方法即可承受。另外一般数据集很大，生成该函数的开销也太大。一个月前左右的某晚与Doctor Bai、Felix021讨论一个问题，其中要解决用尽量少的空间在尽量少的时间内查找一个集合中的一个元素（可以进行预处理）。
当时我们分析了trie、binary tree、block tree、hashing等各种查询方法的时空复杂度方面的优势劣势。讨论到最后对时空复杂度的限制都到了苛刻的地步。为了达到空间复杂度严格为n、每次查询时间复杂度为O(1)，我提出针对已知数据集构造一个“特别”的哈希函数，该函数对于当前数据集满足任意两个不同的key通过哈希后不会产生冲突。
当时felix用实际经验佐证这几乎是不可能的，Doctor Bai也对此持怀疑态度，不过还是承认：对于特定的数据集合，这种函数是可能存在的。
最近在读《深入搜索引擎》（Managing Gigabytes即MG的中文版）时居然遇上了这种避免所有冲突的哈希函数——最小完美哈希函数。
以下转述MG中对于最小完美哈希函数的介绍。
哈希的一些概念
哈希是一种常用的具有查找表功能并且提供平均情况下快速访问的标准方法。
哈希函数h：将n个键值xj的集合映射到一个整数集合的函数h(xi)，其值域是0<=h(xj)<=m-1，允许重复。
其中m>n/a，a（<=1）是装载因子。a越小，两个不同键值在相同哈希值相互冲突的可能性越小，然而冲突总是不可避免。
完美哈希函数
若一个哈希函数满足对于任意的xi和xj，当且仅当i=j时才有h(xi)=h(xj)，就是完美哈希函数(Perfect Hash Function, PHF)。即对一个键值集合L进行哈希时，不可能产生任何冲突。
如果哈希函数不仅是完美的，并映射到值域范围m=n，n个键值中的任意一个都一一映射到唯一整数，这是装载因子a=1，该函数称为“最小完美哈希函数”(Minimal Perfect Hash Function, MPHF)。
若一个最小完美哈希函数同时满足对于xi
当然，以上性质都是针对某一个键值集合L的，即所得哈希函数对于另外的键值集合可能不在满足以上性质。
完美哈希函数的设计
最小完美哈希函数是针对特定函数集合的，所以生成这些哈希函数需要对所求单一静态集合进行预计算生成函数。
最小完美哈希函数公式：
h(t) = ( g(h1(t)) + g(h2(t)) ) % n
h1(t1) = sum(t[i]*w1[i] , i:1–>|t|) % m
h2(t1) = sum(t[i]*w2[i] , i:1–>|t|) % m
构造一个OPMPHF的第一步就是要随机地选择函数h1和h2的映射方法。（最简单的方法：随机生成数组w1和w2）
将该问题转化为m点图（m-vertex graph），点的标号0~m-1。其中有n条边，每条边对应于h1(t)和h2(t)两个哈希值定义连接的两个顶点，每条边用h(t)值标记。此时构造完美哈希函数即通过g映射后使得每个顶点映射到0~n-1的整数( g(h1(t)) + g(h2(t)) ) % n。
（图例）
如果图是无环的，函数g很容易推导出来：任意选择一个未处理的顶点作为根，令g(v)=0，顺着该点出发的边，这些边指向的顶点用该边的h值标记下一代的顶点（该值等于边值减去顶点值之差）。如果不存在未标记的边，就选择下一个根重复进行如上操作。
算法综述（生成一个完美哈希函数）：
1、选定m的值（后面算法实用性理论证明中有说明）；
2、随机选择w1[i]和w2[i]（1<=i<=max{|t|}，其中max{|t|}为L中所有字符串的最大长度）；
3、生成一个图G=(V,E)，其中V={1,..,m}，E={(h1(t),h2(t)))}（其中t属于L）；
4、计算映射g（算法细节见后面描述）；
5、如果步骤4执行失败，跳到步骤2继续执行；
6、返回w1，w2和g。（根据上面的公式描述完美哈希函数）
步骤4细节（检查无环图，生成映射函数）：
1、对于V中的所有顶点v，令g(v)为未设定；
2、遍历V中的所有顶点v，如果g(v)未知，执行LabelFrom(v, 0)。
LabelFrom(v, c)操作:
1、如果g(v)的值已设定:
若g(v)!=c，报告（有环）失败；
否则，返回该节点已经被访问。
2、令g(v):=c；
3、遍历v的邻接点u,执行LabelFrom(u, h((v,u))-g(v))。
算法实用性的理论证明
（纯摘录，没深刻理解）
根据随机图理论分析，对于m<=2n，随着n的增长生成一个无环图的概率趋近于0。
当m>2n时，一个m个顶点n条边的随机图是一个无环图的概率近似于:sqrt((m-2*n)/m)，即发现第一个无环图之前生成图的数量的期望是sqrt(m/(m-2*n))。
总的看来，规定m>2n，生成哈希函数的代价与L的项数成正比。
另外，虽然通过完美哈希函数节省了哈希表的开销，但是g耗费的空间开销也是不小的；若将m/n比例降低到2以下，则生成无环图开销太大（只适合集合较小的情况）。
可以将2-graph（二维图）变为3-graph（三维图）降低m/n的比值。（原理不变：一幅图可用）
点评：
(by liulixiang)
“最小完美哈希函数”从概念上很完美，生成的思想也很不错，不过实际运用中并不是那么常见：应用中已知数据集再做哈希的情况不是特别多，对时空的复杂度要求也没有过于苛刻，普通的方法即可承受。另外一般数据集很大，生成该函数的开销也太大。
参考资料：
最小完美哈希函数方法来自于Czech, Havas, Majewski等的论文：
An optimal algorithm for generating minimal perfect hash functions(Czech等1991)
Graphs, hypergraphs and hashing(Havas等1993)
A family of perfect hashing methods(Majeki等1996)
本文大部分转述或摘抄自《深入搜索引擎——海量信息的压缩、索引和查询》（该书豆瓣链接）一书（Page 173~181），该书由梁斌翻译（原版即大名鼎鼎的MG——“Managing Gigabytes: Compressing and Indexing Documents and Image, Second Edition” 由Ian H. Witten, Alistair Moffat, Timothy C.Bell合著）（MG网站）
阅读(1294) | 评论(0) | 转发(0) |
