从定义说起，这个名字很长，一步步解释。

哈希函数 任意函数h(x)都可以说哈希函数，一般来说，一个良好的哈希函数可以尽量避免重复。x的集合是参数域，h(x)的集合是值域。
完美哈希函数 完美哈希函数，就是完全不会冲突的哈希函数，这要求函数的值域至少比参数域要大
最小完美哈希函数 最小完美哈希函数，就是指函数的值域和参数域的大小完全相等，一个也不多
保序最小完美哈希函数 保序的意思就是指这个哈希之后顺序是不变的，同时还能满足其他两个条件。

这个函数的优点就是形式上很完美，就像给一个排好序的文档编上的序号一般紧凑可靠。但是这个函数有两个缺点，一是必须事前必须知道原数据集，二是需要花一定的CPU来生成这个函数。我认为，对于数据仓库类的线下搜索应用，这个算法是有用武之地的。但对于强调实时的数据业务，这个算法是不适合的。

最小完美哈希函数

step1，假定存在两个一般的哈希函数h1和h2,它们都是将字符串映射到范围0——n-1的一个整数，允许重复。比如我利用GetHashCode方法（maxValue=n，n是字符串个数）：

\[ h1[k] = GetHashCode(stringList[k],maxValue, seed1) \]

\[ h2[k] = GetHashCode(stringList[k],maxValue, seed2) \]

step2，设计一个特别的映射g，使得它满足最小完美哈希函数。

\[ （g[h1[k]] + g[h2[k]]） \% n == k \] 总的来说，就是凑出一组w1和w2，再凑一个 g ，就好了。听起来是不是特别简单？首先看一下生成h1和h2的代码。

using System;

namespace Study_Csharp
{
    public class MinimalPerfectHash
    {
        static Random rnd = new Random(2557176);

        public MinimalPerfectHash()
        {
            var target = new string[] { "Alias", "Bob", "John", "Still", "Young"};
            int[] h1 = null;
            int[] h2 = null;

            int seed1 = 0;
            int seed2 = 0;
            for (int i = 0; i < 1000; ++i)
            {
                if (calculator(target, out h1, out h2, out seed1, out seed2))
                {
                    break;
                }
                else
                {
                    System.Console.WriteLine($"retry {i}");
                }
            }
        }

        private bool calculator(string[] input, out int[] h1, out int[] h2, out int seed1, out int seed2)
        {
            h1 = new int[input.Length];
            h2 = new int[input.Length];

            int n = input.Length;

            seed1 = rnd.Next();
            seed2 = rnd.Next();

            for (int i = 0; i < n; ++i)
            {
                h1[i] = GetHashCodeWithSeed(input[i], n, seed1);
                h2[i] = GetHashCodeWithSeed(input[i], n, seed2);
            }

            string s1 = string.Join(",", h1);
            System.Console.WriteLine($"h1 = {s1}");

            string s2 = string.Join(",", h2);
            System.Console.WriteLine($"h2 = {s2}");

            System.IO.File.WriteAllLines("../../h.txt", new string[] { s1, s2 });

            var graph = new Graph(h1, h2);
            return !graph.HasCycle();
        }

        private int GetHashCodeWithSeed(string values, int n, int seed)
        {
            int hashCode = 17;
            int prime = 65599;

            if (values != null)
            {
                foreach (var value in values)
                {
                    hashCode = hashCode * prime + value + seed;
                }
            }

            while (hashCode < 0)
            {
                hashCode += n;
                hashCode %= n;
            }

            return hashCode % n;
        }
    }
}

此时h1和h2分别是

h1 = 4, 1, 4, 3, 0
h2 = 2, 0, 4, 2, 3

需要注意的是，此时seed1=1968008906, seed2=1523385053

我还想要凑出一个g，使得
k == (g[h[k]] + g[h[k]]) % n // 神奇关系

n = 7

我们用附件1的python画一下。顶点是n个点，点i代表映射完的第i个h。边是凑出来的“神奇关系”的g的下标k。

根据这个关系图，我们可以得知，我们要凑一个数组g，使得g[h1[k]] + g[h2[k]] == k

h1	h2	(g[h1[k]] + g[h2[k]]) % n	k
4	2	(g[4] + g[2])%5	0
1	0	(g[1] + g[0])%5	1
4	4	(g[4] + g[4])%5	2
3	2	(g[3] + g[2])%5	3
0	3	(g[0] + g[3])%5	4

显而易见，n个未知数，n个条件。

当然，它很有可能是无解的，也就是说，当上图存在环时，就变成了无解。因此我们可以不断重试（有理论支撑不会重试很多次），来暴搜一个无环的状态。

如果是无环的，那它就有解啦。需要注意的是，它不是线性方程，因为有取模运算。所以它是有无数种解的。

接下来就是如何解了。我们可以非常暴力地给g[0]随机赋值，然后根据推理，例如a+b=c，已知b 和c，求a。很简单哇。我通过暴力搜索得到了一组解g = [0,1,4,4,1]。暴搜代码实在是太难看了，这就不贴了。

接下来我们实现这个哈希函数。

private int GetIndex(string s, int?[] g, int seed1, int seed2)
{
    var h1 = GetHashCodeWithSeed(s, g.Length, seed1);
    var h2 = GetHashCodeWithSeed(s, g.Length, seed2);

    return (g[h1].Value + g[h2].Value) % g.Length;
}

通过这个哈希函数，我们得到了

Alias   =0
Bob     =1
John    =2
Still   =3
Young   =4

这样就得到了这组数据的最小完美哈希啦！而且是保序的！太完美了吧。

附件

附件1 h画图

import numpy as np
import matplotlib.pyplot as plt

h = []

with open("h.txt") as file:
	for line in file:
		line = line.strip().split(",")
		line = [int(e) for e in line]
		h.append(line)
		print(line)
h1 = h[0]
h2 = h[1]
n = len(h[0])

print(n)

# plot points
theta = np.linspace(0, 2 * np.pi, n + 1)
x = np.cos(theta)
y = np.sin(theta)
fig, ax = plt.subplots(figsize=(4, 4))
ax.scatter(x, y, color="r", s = 20)
ax.xaxis.set_major_locator(plt.NullLocator()) # 删除x轴刻度
ax.yaxis.set_major_locator(plt.NullLocator()) # 删除y轴刻度
ax.axis("equal")

nrange = np.arange(n)

for i,txt in enumerate(nrange):
    ax.text(x = x[i],y = y[i], s = str(i), color = 'r')

# plot lines

for i in nrange:
	x_i = [x[h1[i]],x[h2[i]]]
	y_i = [y[h1[i]],y[h2[i]]]
	ax.plot(x_i, y_i)
	ax.text(x = sum(x_i)/2,y = sum(y_i)/2, s = str(i))

plt.show()

甲乙小朋友的房子

算法-最小完美哈希函数

最小完美哈希函数

附件

附件1 h画图

参考文献