IT·行·思·录

一个月前左右的某晚与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<xj，有h(xi)<h(xj)，即满足“保序性”（order preserving），则称为保序最小完美哈希函数(Order Preserving Minimal Perfect Hash Function, OPMPHF)。 当然，以上性质都是针对某一个键值集合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] [...]