你会如何设计一个完美哈希的函数？
感兴趣的领域是字符串匹配。 假设我有这样的结构。
typedef struct { char *name, int (*function)(); } StringArray StringArray s[] = { {"George", func1}, {"Paul", func2}, {"Ringo", func3}, {"John", func4}, {"", NULL} /* End of list */ } 数组中有固定数量的字符串。 它们是硬编码的，如示例中所示。 如果表发生变化，则需要重新评估散列函数的质量。
我想将哈希函数应用于字符串，如果字符串与数组中的字符串匹配，则调用该函数。 这需要一个完美的哈希函数。 不允许冲突。要求散列的目的是在查找上获得O（1）性能。
您在设计function时有什么想法？
请参阅gperf主页。
摘要列出了C和C ++。 你在寻找哪一个？ C和C ++是两种不同的语言，它们的字符串处理和数据结构差异很大（而且C语言在C ++中工作的事实不会改变它）。
具体来说，为什么要使用完美的哈希函数？ 是否要将字符串与函数关联起来，并认为这是一个很好的方法吗？ 这是某种家庭作业吗？ 你有理由不在C ++中使用map <>吗？ （或unordered_map <>如果可用？）
如果你确实需要一个完美的哈希，那么字符串的约束是什么？ 您想要发送某个固定集吗？ 怎么样的字符串与其中一个字符串不匹配？ 你是否愿意接受来自随机字符串的命中，或者是否限制传入字符串的数量？
如果你可以编辑你的问题以包含这样的信息，我们可能会更有帮助。
编辑（回应前两条评论）：
好的，我们应该看看C解决方案，因为你可能想要这个C和C ++工作。 你可能想要性能，但你测试过吗？ 如果我们正在处理I / O系统中的字符串，则可能会使调度时间相形见绌。
你期待任意的字符串。 期望完美的散列函数可以避免来自随机数据的所有冲突，所以你需要考虑这一点。
你考虑过特里 ？ 它可能比完美的散列函数（或可能不是）更有效，它应该相当容易在C中实现，并且它将避免重做调度字符串列表或可能的冲突的问题。
看到：
什么是好的哈希函数？
在哈希冲突和性能方面的最佳哈希算法
什么是高性能字符串散列函数，导致32位整数具有低冲突率 ？
选择（字符串）散列函数的乘数
非常低成本的哈希函数
使用hash_map时，在stl字符串上使用的最佳散列算法是什么？
你可以使用地图
std::string foo() { return "Foo"; } std::string bar() { return "Bar"; } int main() { std::map m; m["foo"] = &foo; m["bar"] = &bar; }
如果绝对不允许冲突，您唯一的选择是跟踪数据库中的每个字符串，这可能不是最好的方法。
我要做的是应用现有的常见强哈希算法之一，例如：MD5或SHA。 这里有样品镜像，例如： http ： //www.codeproject.com/KB/security/cryptest.aspx
使用平衡二叉树。 然后你知道行为总是O（登录）。
我强烈不喜欢哈希。 人们没有意识到他们的算法带来了多大的风险。 他们运行一些测试数据，然后在现场部署。 我从未见过部署的哈希算法在字段中检查行为。
O（log n）几乎总是可以接受代替O（1）。
这次演习的最终结果是
- 从网上窃取一些面向字符串的哈希函数。
- 构建一种工厂类，使用一系列mod运算符值对数据集测试每个函数，寻找与该函数一起使用的最小完美散列。
- 该工厂类的默认构造函数返回一个字符串，该字符串表示一组参数，当使用时选择正确的哈希函数，而mod大小则提供需要最少内存量的完美哈希。
- 在正常使用情况下，您只需使用返回的参数实例化该类，并且该类将自身置于具有所需函数的工作状态。
- 该构造函数validation没有冲突和中止（如果有）。
- 在没有找到完美散列的情况下，它会降级为输入表的排序版本的二进制搜索。
对于我在我的域中的数组，这似乎非常好。 未来可能的优化是在输入的子串上进行相同类型的测试。 在示例中，每个音乐家名称的第一个字母足以区分它们。 然后，需要平衡实际散列函数的成本与使用的内存。
感谢所有贡献想法的人。
邪恶
好吧，没有完美的哈希函数。
你有几个可以最大限度地减少碰撞，但没有一个消除它们。
但不能告诉一个人：P
编辑：解决方案无法找到完美的哈希函数。 解决方案是了解碰撞。 通常，哈希函数具有冲突。 这显然取决于数据集和生成的哈希代码的大小。