c - 完美/理想的哈希来隔离字谜

Question

为了加速测试字谜字符串的快速输出行为，我 came up with基于质数的哈希方案——尽管它看起来像 I wasn't the first .

基本思想是将字母映射到素数，并计算这些素数的乘积。字母的任何重新排列都会产生相同的结果，如果结果可以任意大，那么其他字母的组合都不会产生相同的结果。

我最初将其设想为只是一个哈希值。最终该产品会溢出并开始为其他字母组合起别名。然而，通过将最常见的字母映射到最小的素数，乘积增长缓慢，并且通常可以完全避免溢出。在这种情况下，我们得到了一个完美的哈希值，无需额外测试即可给出明确的正面和负面结果。

值得注意的是，它在溢出之前并没有非常有效地填充编码空间。结果中不会有任何大于 103 的素数因子，并且小素数的分布是固定的，不一定与字母频率非常匹配。

现在我想知道是否有比这更好的东西。用完美的哈希值覆盖更多结果并且在其余情况下具有很强的分布性的东西。

我能想到的最密集的编码方案是对字母进行排序，然后用熵编码器将它们打包成一个单词。在这个方案中，由于每个位置都受到范围限制，字母频率显然会有很大偏差(例如，以 z 开头的排序数组的可能性大大低于以 z 结尾的排序数组的可能性)。

不过，这听起来像是一项繁重的工作——而且我看不出它能保证在溢出情况下提供良好的分配。

也许有一组更好的因素可以将字母映射到，以及更好的方法来检测锯齿风险何时开始。或者不依赖乘法的哈希方案？有什么容易计算的吗？

所以这就是:

• 针对尽可能多的现实世界输入(对于一些合理的位数)的完美哈希。
• 剩余情况的强哈希，以及区分这两种情况的方法。
• 易于计算。

英语语言限制(26 个字母，具有典型的英语单词结构)就可以了。多字节编码方案是另一个问题。

首选 C 代码，因为我理解它。

Answer 1

如果您使用大小为 m 的字母表的 n 位哈希，则可以使用我描述的方法 here 获得长达 (n-m) 个字符的字谜的唯一哈希。 。这使得冲突检测变得不必要，但它确实限制了您的单词大小，具体取决于字母表的大小和可用空间。

为了允许任意长度的单词，我将使用 n-1 位对长度最多 (n-m-1) 个字符的单词进行哈希处理，并保存最后一位以表明该单词是 m 个字符或更长。在这些情况下，您将使用剩余的 n-1 位作为素数或其他哈希算法，但当然，只要您在这些存储桶中有多个单词，您就必须进行冲突检测。由于在现实世界的应用程序中，大多数单词将占据较短的单词长度，因此您将大大减少较长单词所需的冲突检测。