问题标签 [perfect-hash]

我正在开发一种编程语言，并且在我的编程语言中，我将对象存储为哈希表。我使用的散列函数是Pearson Hashing，它依赖于 256 位查找表。这是功能：

我的问题是，给定一个少于 256 个成员名称的固定组，如何确定一个lookup表以pearson()返回从'\0'. 换句话说，我需要一种算法来为完美的哈希创建查找表。这将允许我拥有不超过其成员数量的对象。这将在编译时完成，因此速度不是一个大问题，但更快会更好。蛮力这样做很容易，但我认为（希望）有更好的方法。

这是一个例子：给定一个类中的成员变量“foo”、“bar”和“baz”，我想确定一个lookup这样的：

请注意，顺序无关紧要，因此以下结果也是可以接受的：

在理想的世界中，所有不在表中的名称都会返回一个大于 2 的值，因为这可以让我避免检查，甚至可能避免存储成员名称，但我认为这是不可能的，所以我将不得不添加一个额外的检查以查看它是否在表中。鉴于此，不初始化查找表中未使用的值可能会节省时间（碰撞无关紧要，因为如果它发生碰撞并且检查失败，它根本不在对象中，所以碰撞不需要解决；只需要处理错误）。

我有一些C类：

我想用它来索引一个有效的地图。最有效的地图是一个数组。所以我在伴生对象中添加了一个“全局”“静态”计数器，为每个对象提供唯一 ID：

在 C 的主要构造函数中，每次创建 CI 时都希望记住全局计数器值并增加它。
问题一：怎么办？

现在我可以使用 C 对象中的 id 作为索引数组的完美哈希。但是数组不会像 map 那样保留类型信息，即给定数组由 C 的 id 索引。

问题2：是否有可能具有类型安全性？

更新：
问题 2 中的类型安全涉及地图索引的类型，以避免混合两个不相关的整数。值当然是（类型）安全的..

问题 1 询问如何在默认构造函数中增加变量？
即：放在哪里？

我需要（非常）快速处理有限范围的字符串，计算它们的值。输入文件的格式为：

等等。因为线宽是相同的，所以我可以以fread相当快的速度简单地阅读一行，并且我开发了一个完美的散列函数，它可以工作，但我想看看是否有人可以就如何让它更快地提供任何建议。我将分析每个建议，看看它是如何进行的。

散列函数基于月份名称，以允许将值快速分配到存储桶。在这里忍受我。我首先计算出完美哈希的最少字符数：

请记住，月份都是九个字符，因为我有整个输入行。

不幸的是，没有单一的列来标记月份的唯一性。第 1 列重复J，第 2 列重复a，第 3 列重复r，第 4 列重复u和第 5 列向前重复<space>（还有其他重复，但一个足以防止单列哈希键）。

但是，通过使用第一列和第四列，我得到了唯一的值Ju, Fr, Mc, Ai, M<space>, Je, Jy, Au, St, Oo,Ne和。De此文件中不会有无效值，因此我不必担心输入数据的存储桶不正确。

通过查看字符的十六进制代码，我发现我可以通过与战略值进行 AND 运算来获得较低的唯一值：

这让我可以设置一个静态数组来创建一个（希望）令人眼花缭乱的快速哈希函数：

用代码测试：

表明它在功能上是正确的：

但我想知道它是否可以更快。

有什么建议吗？如果我的散列函数本身存在问题，我愿意接受任何简单的优化，甚至完全重写。

我认为这并不重要，但最终版本将使用 EBCDIC。该理论仍然有效，但由于字符具有不同的代码点，AND 操作可能会略有变化。我会很高兴仅在 ASCII 方面提供任何帮助，因为我相信所提供的任何建议都可以转化为 EBCDIC。

我想使用CMPH的最小完美哈希。知道如何在 VC++ 项目中使用它吗？

我在这里使用 VC++ 2008 Express Edition 创建了一个新项目，并添加了头文件和源文件，但它输出编译错误。

我正在尝试散列值

我需要一个函数将它们映射到一个大小为 13 的数组而不会引起任何冲突。

我已经花了几个小时思考这个问题并在谷歌上搜索，但无法弄清楚。我还没有接近可行的解决方案。

我将如何寻找这种散列函数？我玩过 gperf，但我不太了解它，也无法得到我想要的结果。

在阅读 Wikipedia 上的鸽巢原理时，我遇到了 - “在哈希表中冲突是不可避免的，因为可能的键数超过了数组中的索引数。没有哈希算法，无论多么聪明，都可以避免这些冲突”。但是gperf不正是这样做的吗？

请赐教。

我被要求寻找一个完美的散列/单向函数来散列 10^11 个数字。但是，由于我们将使用嵌入式设备，它没有存储相关存储桶的内存，所以我想知道如果没有它们，是否有可能拥有一个像样的（最小）完美哈希？

计划是使用设备对数字进行散列，我们使用彩虹表或使用散列作为偏移量的文件。

干杯

编辑：

我会尝试提供更多信息:)

1) 10^11 现在实际上是 10^10，这样更容易。这个数字是可能的组合。所以我们可以得到一个介于 0000000001 和 10000000000 (10^10) 之间的数字。

2) 我们的计划是将其作为单向功能的一部分，以确保号码安全，以便我们可以通过不安全的方式发送它。然后，我们将使用彩虹表查找另一端的原始数字。问题是设备的源通常有 512k-4Meg 的内存可供使用。

3）它必须是完美的——我们100%不能发生碰撞。

编辑2：

4）我们不能使用加密，因为我们被告知它在设备上实际上是不可能的，如果可以的话，密钥管理将是一场噩梦。

编辑3：

由于这是不明智的，现在它纯粹是学术问题（我保证）

我正在尝试编写一个生成 Pearson 完美哈希的生成器。请注意，我不需要最小的完美哈希。维基百科说，可以使用随机算法（其中 S 是密钥集）在 O(|S|) 时间内找到 Pearson 完美哈希。但是，我一直无法在网上找到这样的算法。这甚至可能吗？

注意：我不想使用 gperf/cmph/etc.，我宁愿编写自己的实现。

考虑一个具有以下签名的查找函数，它需要为给定的字符串键返回一个整数：

进一步考虑，在编写函数的源代码时，编号为 N 的键值映射是预先知道的，例如：

因此，上述输入的函数的有效（但不完美！）实现将是：

还可以提前知道对于每个给定的键，该函数将在运行时被调用多少次（C>=1）。例如：

但是，此类调用的顺序未知。例如，上面可以描述运行时的以下调用序列：

或任何其他序列，前提是呼叫计数匹配。

还有一个限制 M，以最方便的任何单位指定，定义任何查找表和其他辅助结构可以使用的内存上限GetValue（这些结构是预先初始化的；该初始化不计入复杂性函数）。例如，M=100 个字符，或 M=256 sizeof(object reference)。

问题是，如何编写GetValue尽可能快的主体 - 换句话说，所有GetValue调用的总时间（请注意，我们知道总计数，以上所有内容）是最小的，对于给定的 N，C和M？

该算法可能需要 M 的合理最小值，例如 M >= char.MaxValue。它还可能要求 M 与某个合理的边界对齐——例如，它可能只是 2 的幂。它还可能要求 M 必须是某种 N 的函数（例如，它可能允许有效的 M=N，或 M=2N，...；或有效的 M=N，或 M=N^2， ...; ETC）。

该算法可以用任何合适的语言或其他形式来表达。对于生成代码的运行时性能约束，假设生成的代码GetValue将使用 C#、VB 或 Java（实际上，任何语言都可以，只要字符串被视为不可变的字符数组 - 即 O(1) 长度和 O (1) 索引，并且没有预先为它们计算的其他数据）。此外，为了简化这一点，假设所有键的 C=1 的答案被认为是有效的，尽管那些涵盖更一般情况的答案是首选。

关于可能方法的一些思考

对上述问题的第一个显而易见的答案是使用完美的哈希，但是寻找一个的通用方法似乎并不完美。例如，对于上面的示例数据，可以使用 Pearson 散列轻松生成一个最小完美散列表，但是每次调用 时都必须对输入键进行散列GetValue，并且 Pearson 散列必须扫描整个输入字符串。但实际上所有示例键的第三个字符都不同，因此只能将其用作散列的输入，而不是整个字符串。此外，如果要求 M 至少为char.MaxValue，则第三个字符本身将成为完美哈希。

对于一组不同的键，这可能不再适用，但仍有可能减少在给出精确答案之前考虑的字符数量。此外，在某些情况下，最小完美散列需要检查整个字符串，可以减少对子集的查找，或者通过使散列非最小来使其更快（例如不太复杂的散列函数？） （即 M > N） - 为了速度而有效地牺牲空间。

也可能是传统的散列一开始就不是一个好主意，而且更容易将主体构造GetValue为一系列条件，排列成第一个检查“最可变”的字符（那个在大多数键），并根据需要进行进一步的嵌套检查以确定正确答案。请注意，此处的“方差”可能会受到每个键将被查找的次数的影响 (C)。此外，最好的分支结构应该是什么并不总是很明显 - 例如，可能是“最可变”字符只能让您区分 100 个键中的 10 个，但对于剩余的 90 个键，需要额外检查无需区分它们，不以“最易变”的字符开头。然后，目标是确定完美的检查顺序。

我在 [0; 范围内有很多整数；2^63-1]。然而，只有 10^8 个整数。没有重复。完整列表在编译时是已知的，但它只是唯一的随机数。这些数字永远不会改变。要显式
存储一个整数，需要 8 个字节，并且有关联的 1 个字节值，因此显式存储需要大约 860 MB。 所以我想找到最小的完美散列函数来将 10^8 个整数中的每一个从 [0;2^63-1] 映射到 [0;10^8-1]。我应该只找到这个函数一次，数据永远不会改变，函数可能很复杂。但它应该是最小的、完美的，并且计算应该很快。我怎样才能更好地做到这一点？如果它们发生，也许可以找到并使用一些子序列？

谢谢。