如何设计一个完美哈希函数？

Question

我需要翻译的内容是： 需要匹配字符串，假设我有这样一个结构。

The domain of interest is string matching. Assume I have a structure like this.

typedef struct
{
    char *name,
    int (*function)();

} StringArray

StringArray s[] = 
{
    {"George", func1},
    {"Paul",   func2},
    {"Ringo",  func3},
    {"John",   func4},
    {"",       NULL}   /* End of list */ 
}

数组中的字符串数量是固定的，就像示例中一样硬编码。如果表格发生变化，则需要重新评估哈希函数的质量。

我想对一个字符串应用哈希函数，如果该字符串与数组中的某个字符串匹配，则调用此函数。这需要一个完美的哈希函数，不允许出现冲突。要求哈希的目的是获得O(1)的查找性能。

您有什么关于设计此功能的想法？

- EvilTeach

---

请查看gperf主页。 - anon

以下网页提供了多个通用哈希函数的实现，它们高效且碰撞（collision）较少：http://partow.net/programming/hashfunctions/index.html。 - Matthieu N.

Answer 1

摘要中列出了C和C++，你需要哪一个？C和C++是两种不同的语言，在它们的字符串处理和数据结构方面有很大的区别（即使C的函数可以在C++中使用也不改变这一点）。

具体而言，为什么您需要完美的哈希函数？您是否想将一个字符串与一个函数关联起来，并认为这是一个好方法？这是某种作业吗？您是否有不使用C ++中的map<>（或unordered_map<>如果可用）的原因？

如果您确实需要完美的哈希，那么字符串的限制是什么？您是否要将一定的固定集合分配给字符串？与不匹配集合之一的字符串如何处理？您是否愿意接受来自随机字符串的命中，还是传入字符串的数量有限？

如果您可以编辑您的问题并包含此类信息，我们可以提供更多帮助。

编辑（针对前两条评论）：

好的，我们应该看一下C语言的解决方案，因为您可能希望在C和C++的工作中都使用它。您可能希望获得更好的性能，但是您进行了测试吗？如果我们处理从I/O系统输入的字符串，那里的时间很可能会超过分派时间。

您期望任意字符串。期望一个完美的哈希函数避免所有随机数据的冲突有点过分，因此您需要考虑这一点。

您考虑过trie吗？它可能比完美的哈希函数更有效（也可能不是），在C中实现应该相当容易，并且它将避免重新做您的调度字符串列表或可能的冲突问题。

- David Thornley

---

我使用C和C++编程，天哪，帮帮我吧Pro*C。 O(1)哈希用于提高性能。 哈哈，没有作业。我想要构建一个工具来加速一些关键性能代码。这个示例是为了讨论而简单制作的。实际应用不会这么简单。 - EvilTeach

字符串的长度会有所不同，但它们都不会是零长度。作为实际限制，数组中没有任何一个字符串的长度会超过32个字符。调用者传入的字符串可以是任意长度，但如果它比表格中的字符串更长，则表示没有匹配项。 - EvilTeach

Answer 2

你可以使用 map 函数

std::string foo() { return "Foo"; }
std::string bar() { return "Bar"; }

int main()
{
   std::map<std::string, std::string (*)()> m;
   m["foo"] = &foo;
   m["bar"] = &bar; 
}

- Vinay

---

std::map不使用哈希，而是基于树的。 - anon

为什么要重新发明轮子，你可以使用像map这样的现有库。 - Vinay

也许提问者想要了解哈希的性能特征，而不是树搜索的特征？ - anon

@Mitch：有什么问题吗？我们应该经常问自己的不是如何做这个或那个，而是为什么我想要使用这个或那个。 - Mykola Golubyev

没错。为什么EvilTeach想要一个哈希函数？可能确实有很好的理由，但我还没有看到。对于将字符串作为输入并执行函数的一般情况，这个方法是有效的。 - David Thornley

Answer 3

这个练习的最终结果是：

• 从网络上窃取了一些面向字符串的哈希函数。
• 构建了一种工厂类，该类使用一系列模运算值对数据集测试每个函数，寻找能够与该函数配合使用的最小完美哈希。
• 该工厂类默认构造函数返回一个字符串，该字符串表示一组参数，当使用时选择正确的哈希函数和模大小，以给出需要最少内存的完美哈希。
• 在正常使用情况下，您只需使用返回的参数实例化该类，该类将使用所需的函数将自身置于工作状态。
• 该构造函数验证是否存在冲突，如果存在则中止。
• 在没有找到完美哈希的情况下，它会退化为对输入表的排序二分搜索。

对于我领域中的数组集，这似乎非常有效。可能的未来优化是对输入的子字符串进行相同类型的测试。在示例案例中，每位音乐家姓名的第一个字母就足以区分他们。然后需要权衡实际哈希函数的成本和内存使用。

感谢所有贡献想法的人。

邪恶

- EvilTeach

Answer 4

如果绝对不允许碰撞，那么你唯一的选择是跟踪数据库中的每个字符串，这可能不是最好的方法。

我会使用现有的常见强哈希算法之一，例如：MD5或SHA。这里有无数的示例，例如：http://www.codeproject.com/KB/security/cryptest.aspx

- galets

Answer 5

使用平衡二叉树。然后你知道行为始终是O(logn)。

我强烈不喜欢哈希。人们没有意识到他们的算法有多大的风险。他们运行一些测试数据，然后在现场部署。我从未见过在现场检查行为的部署哈希算法。

除O(1)外，O(log n)几乎总是可以接受的。

- user82238

---

“在大多数情况下，O(log n)可以代替O(1)，但在许多应用程序中，这种说法是完全错误的。只需将数据点数量增加到几百万以上即可看出。” - Konrad Rudolph

完成后，请进行测试。哈希不会给出保证结果，除非您事先知道所有可能的输入。倾向于聚集输入的哈希函数可能不会给您O（1）。 - David Thornley

在这种情况下，所有的输入都是已知的。它们坐落在数组中。而输入字符串要么完全匹配，要么不匹配。 - EvilTeach

不，所有可调度的输入都是已知的。一旦你把输入字符串进行哈希处理并获得一个匹配，你确实需要进行比较。 - David Thornley

Konrad - 是的。但是具有如此多数据的应用程序数量很少且稀少。它们形成了一个特定而罕见的类别。这就是为什么我说“几乎总是可以接受”的原因。 - user82238

Answer 6

嗯，没有完美的哈希函数。

有一些可以最小化冲突，但没有一个能够完全消除它们。

不过我不能给出建议 :P

编辑： 解决方案不是找到一个完美的哈希函数。解决方案是意识到冲突的存在。通常哈希函数都会有冲突。这显然取决于数据集和生成哈希代码的大小。

- Megacan

---

@Adam：这里有一个相当大的警告，因为它仅适用于存在明显数据集的情况。由于OP没有提及限制使用的字符串，我同意Megacan在这种情况下没有完美的哈希。+1。 - sipsorcery

提问者确实隐含地提到了这一点 - 只有四个披头士（如果你包括他们解雇的鼓手和斯图·沃茨纳姆，那就是六个） - 这是一个固定的数据集。 - anon

我只是在说，解决方案不能是找到一个完美的哈希函数。解决方案是要意识到碰撞的存在。通常情况下，哈希函数会发生碰撞。这显然取决于数据集和生成哈希代码的大小。 - Megacan

是的，它将是一个固定的数据集，他一生中只能输入那么多字符串 :）。然而，这里的重点是，“没有完美的哈希函数”是一个真理，除非有明确指定的约束条件。在我看来，Megacan是符合逻辑的。 - sipsorcery

@Neil - 我已经阅读了链接。它说完美哈希函数将一个键映射到单个哈希码，并且没有两个键具有相同的哈希码？我是对的吗？我不会对此提出异议。只有在键的组合数小于或等于哈希码数时，这才可能实现。 - Megacan