哈希函数的确定

问题描述：

我们如何找到这组字符串的最有效的哈希函数（碰撞的可能性最小）。哈希函数的确定

假设我们给了一些字符串..而字符串的长度也没有定义。阿贾伊维杰拉祈彩 ....

我们知道的不计数。可用的字符串，所以我们可以设计一个大小的哈希表（可用的计数）。什么可能是我们可以为这样的问题设计的完美散列函数？

以增量方式将每个字符的ascii值乘以31（主要编号）将导致散列值大于MAX_INT的值，然后模数将无法正常工作......所以请给出一些有效的散列函数构建up解决方案....

我有几个字符串集，可以说count = 10 ....我需要实现一个哈希函数，使所有这10个字符串适合哈希表中的唯一...任何完美的散列函数O（1）都可用，对于这种问题??哈希表的大小将是10，这种情况下...

只有C语言编程...

请解释逻辑在网站.... http://burtleburtle.net/bob/c/perfect.c 这看起来很复杂，但完美的我..！！这里使用的算法是什么......马上阅读代码，非常困难！

谢谢....

哦，这些解决方案是没有帮助亲爱的....是否存在任何解决方案可以给出一组给定的字符串完美的哈希值..没有字符串可能会非常大....完美的哈希解决方案！它是否存在..？ – AGeek 2011-03-16 19:05:34

@Necrolis推荐的gperf程序是一个实际工作的开源程序。您可以下载并查看源代码，看看它是如何完成的。很难想象一个比这更好的例子。 – 2011-03-16 19:10:20

那么这个网站上的代码呢... – AGeek 2011-03-16 19:20:07

答

你可能要考虑perfect hashing.

菲利普，你可以用一个例子来支持这个...如果我们有字符串...我们如何从这些字符串列表中得到一个整数（唯一）？ – AGeek 2011-03-16 18:42:45

@AGeek：如果你看一下Philipp链接的文章的“外部链接”部分，你会看到几个完美的哈希生成器的免费实现。 – 2011-03-16 18:56:16

我需要一个代码.... examplee ...在C程序中...并且需要一个完美的散列函数..它可以给出O（1）时间的结果.. – AGeek 2011-03-16 19:06:38

答

哈希表是为了能够处理动态输入。如果你只能保证一组特定的输入，并且你希望保证每个输入的特定插槽，为什么散列呢？

只需为每个已知的可用输入建立一个数组索引。

对于几乎只读访问的大型数据集，使用类似完美哈希的东西可能是明智的。 – 2011-03-16 17:57:27

当你有一组已知的输入并保证每个输入有一个插槽时，为什么会有意义散列？您可以跳过散列函数的代价，并对每个“已知输入”使用#defined索引进行数组查找。 – 2011-03-16 18:10:01

“已知输入”是相对的。如果您知道您将随机访问在运行时提供的5GiB数据，则首先完全哈希以获得O（1）访问权限可能是个好主意。 – 2011-03-16 18:17:15

答

检查一些这些了，他们apparantly具有良好的分布

答

你可能想看看gperf，你可以有点做到这一点如果你不太经常这样做，并且你的数据设置的很小，那么你就可以在飞行中使用。如果字符串提前知道，那么这是方法