algorithm - 给定已知字符串列表生成完美的哈希函数？

Question

假设我有一个 N 个字符串的列表，在编译时已知。

我想生成(在编译时)一个函数，它将每个字符串映射到一个介于 1 和 N 之间的不同整数(含 1 和 N)。该函数应该花费很少的时间或空间来执行。

例如，假设我的字符串是:

 {"apple", "orange", "banana"}

这样的函数可能返回:

f("apple") -> 2
f("orange") -> 1
f("banana") -> 3

生成这个函数的策略是什么？

我想在编译时分析字符串并寻找一些我可以修改或添加的常量？

编译时生成时间/空间可能非常昂贵(但显然不是那么荒谬)。

Answer 1

假设您有 m 个不同的字符串，让 a_{i, j} 是第 j 个字符第 i 个字符串。在下文中，我将假设它们都具有相同的长度。如果 j ≥ |a_i，则可以通过将 a_{i, j} 视为空字符，轻松将其翻译成任何合理的编程语言|.

我建议的想法由两部分组成:

1. 找到(最多)m - 1 个区分字符串的位置，并存储这些位置。

2. 通过将字符串视为长度为 m 的向量并存储完美哈希函数的参数来创建完美哈希函数。

---

显然，一般来说，哈希函数必须至少检查 m - 1 个位置。通过归纳很容易看出这一点。对于 2 个字符串，必须至少检查 1 个字符。假设对于 i 个字符串为真:必须检查 i - 1 个位置。通过将 0 附加到每个 i 字符串的末尾来创建一组新的字符串，并添加一个与其中一个字符串相同的新字符串，只是末尾有一个 1。

相反，很明显，最多可以找到 m - 1 个位置足以区分字符串(对于某些集合，当然数量可能更少，低至 log 到m 的字母大小)。同样，通过归纳很容易看出这一点。两个不同的字符串必须在某些位置不同。将字符串放在具有 m 行的矩阵中，必须有一些列不是所有字符都相同。将矩阵分成两个或更多部分，并将参数递归地应用于每个超过 2 行的部分，显示了这一点。

假设 m - 1 位置是 p₁, ..., p_{m - 1}。在下文中，记忆上面的含义 for a_{i, pj} for p_j ≥ | a_i|:为空字符。

---

让我们定义h(a_i) = ∑_{j = 1}^{m - 1}[q_j a_{i, pj} % n]，用于随机 q_j 和一些n。那么h就是known to be a universal hash function : 碰撞概率 P(x ≠ y ∧ h(x) = h(y)) ≤ 1/n。

---

给定一个通用哈希函数，有known constructions for creating a perfect hash function from it .也许最简单的方法是创建一个大小为 m² 的向量，然后连续尝试上面的 h 和 n = m² 使用随机系数，直到没有冲突。达到此目标所需的尝试次数预计为 2，而需要更多尝试的概率呈指数下降。