完美哈希

我们想要一种哈希，可以将n个字符串无冲突地匹配到0到n – 1。这种哈希我们称之为完美哈希。
这似乎是难以想象的，冲突是哈希不可以避免的问题，因为我们无法预知每个哈希的值。但是如果需要求解哈希的字符串的集合是预知的，最简单的得到完美哈希的方法就是不断尝试各种哈希方法，直至找到满足我们需求的哈希方法。
但是这个最简单的方法，每次试验获得完美哈希的概率是很小的，将需求退化一点：求一次可以得到n个字符串无冲突地匹配到0到m – 1的哈希的概率F(m, n)。
于是F(m, n) = F(m – 1, n – 1) * [(m – 1) / m]^(n – 1)
可得F(m, n) = (m – 1) * (m – 2) * …*(m – n + 1)/m^(n – 1)
可以看出要m很大才有比较大的可能获得n个字符串无冲突地匹配到0到m – 1的哈希。当m = n时，概率几乎为0.
我们需要寻求一种更好的算法。其实完美哈希的求解有下面的一个概率算法来解决。

预备知识：
1. 当m>2n时，一个m个顶点n条边的随机图是一个无环图的概率近似于sqrt((m-2*n)/m)
2. 一棵树，每条边有一个值。我们可以对每个节点设置一个值，使得每条边的值两个端点的值的和。

（因为树是无环图，所以我们随便找一个点作为起点，随便设置一个值，然后用这个值去生成其他节点的值）
完美哈希：
有了上面的预备知识，生成完美哈希的算法就不难发现了。
1. 随便搞两个哈希函数h1(x), h2(x)，哈希的值映射到{0,1,…,n-1}上。
2. 构造一张n个节点的图。对n个字符串生成n对哈希值，对串x生成(h1(x), h2(x)),对节点h1(x), h2(x)连一条边。
3. 检查2中的图是否有环，有环跳到1 。
4. 将图中的n条边赋予0到n - 1的值，对每个节点k根据预备知识的第二点设置一个值g(k),保存下来。
5. 根据h1(x),h2(2),g(x),就可以得到完美哈希h(x) = g(h1(x))+g(h2(x))了。