问题标签 [perfect-hash]

我花了几天时间试图让图书馆在我的系统上工作。该库有几种生成 MPHF 的算法。我对最小散列函数的理解是，当我使用 MPHF 散列两个不同的键时，它们将返回两个不同的 id。我生成的 200 万个键似乎不是这种情况（整数，由算法读取为字符串）。我已经尝试了该库实现的几种算法，但所有这些算法都会导致很多键出现重复的“ID”。

这是我写的：

如果算法声称生成最小完美散列函数，那么每个不同键的 ID 不应该是唯一的吗？有 2048383 个键。对于我的项目，我需要将 id 从 0 映射到 2048382，因为我计划使用最小的完美哈希函数。我不确定我的理解哪里出了问题。请帮忙。

我需要构造一个完美的散列函数，将一组整数 [1..2^64 - 1] 映射到自身（这个函数实际上是一些复杂的排列）。

为了解释这个问题，假设我们在数据库中有整数主键序列。我们需要显示构造一个数字（我们向用户显示），以使关闭的数字对应于彼此尽可能远的主键。

所以，基本上我需要一个大型整数集的双射函数。例如

• 1 -> X1
• 2 -> X3
• 3 -> X3
• ...
• 2^64 - 1 -> X2^64 - 1

任何建议或参考将不胜感激。

我试图弄清楚如何将我完美的哈希类中的 4 个基本伪代码方法转换为最终将在我的PerfectHash类的主要方法中使用的可行方法。我知道我还没有创建类的实例，但我会的。

您知道，当您使用堆栈调用 4 个方法时，例如，您在方法中输入参数，但我的应用程序将能够获取用户输入的键并在其中插入、获取、删除或更新的结构。

我是否需要对这些方法进行更多思考，或者伪代码现在是否足以工作？这是我到目前为止所做的。我知道第一堂课编译得很好，但是我在上面已经指出的第二堂课遇到了麻烦。

我经常处理单射的映射。在编程术语中，这可以表示为一个字典，其中所有值都是唯一的，当然，所有键也是唯一的。

单射映射是否具有内存高效的数据结构，具有您期望从字典中获得的所有时间复杂性属性？

例如：

Two way/reverse map中的所有解决方案似乎都需要使用或组合两组映射，重点是使在双向映射上执行操作更容易。这对于完全适合内存的小型词典来说很好，但对于大型词典来说却不是很好。

要求是存储单向双向映射与仅存储单向映射的常规字典相比，不应有额外的内存开销。

我了解字典使用哈希表，它使用关联数组数据类型。根据定义，关联数组使用唯一键实现键 -> 值映射。理论上或实际上是否有可能产生一个允许反向查找的智能单射映射？

如果不可能，我会很感激解释为什么这样的结构很难或不可能以与字典相同的效率实现。

更新

在与@rpy 讨论之后（请参阅下面的评论），有关如何使用完美的可逆哈希函数设置类似 python 字典的对象的任何信息都会很有用。但是，当然，一个可行的实现将是理想的（我已经尝试过完美）。

我需要一个 64 位到 16 位的完美散列函数来处理稀疏的键列表。

我在 python 中有一个字典，它有 48326 个长度为 64 位的键。我想为这个键列表创建一个最小的完美哈希。（我不想等待几天来计算 MPH，所以我也可以将它映射到 16 位哈希）

目标是最终将此字典作为包含字典值的数组移植到 C 中，并且索引由以键为输入的最小完美散列函数计算。我无法在我正在构建的应用程序的 C 端口中使用外部哈希库

问题：是否有任何 python 库将我的密钥作为输入并为我提供散列参数和（基于用于散列的已定义算法）作为输出。

我找到了一个完美的库 2.0.0，但由于我的密钥是 64 位形式的，所以这只是挂起。（即使我在 2000 个键的子集上对其进行了测试）

编辑 正如评论中所建议的，我查看了史蒂夫·哈诺夫的算法并修改了哈希函数以采用 64 位整数（根据此wiki 页面更改 FNV Prime 和偏移量的值）

虽然我得到了结果，但不幸的是，地图返回 -ve 索引值，而我可以让它工作，这意味着我必须通过检查 -ve 索引向哈希计算添加另外 4 个周期

想避免这种情况

我有一组由 uint16_t 唯一标识的结构。这些结构永远不会超过 256 个（由于我不会进入的原因，必须使用 uint16_t 来识别结构）。

我想通过指针数组存储这些结构。由于不会有超过 256 个结构，我想静态分配一个大小为 256 的结构指针数组。不过，为此，我需要一个函数来将 uint16_t 唯一地映射到 uint8_t。

鉴于我将在运行时知道所有键（尽管在运行前我不会知道），是否存在一种算法，它通常会给我一个唯一的映射（即完美的哈希）？

需要注意的是，我使用的系统有 16 位地址。因此，出于效率原因，我不想使用任何大于 uint16_t 的类型。

我正在编写一个解析器（在 C++ 中），我有一个小字符串列表（少于 100 个），其中每个字符串都代表一个有效的解析器标记。我需要将每个这样的已知标签映射到一个枚举值以进行进一步处理。由于所有字符串在编译时都是已知的，因此我一直在研究为此目的使用完美的哈希函数。

我知道用于完美哈希函数生成 sa gperf、mph、cmph的现有工具和算法。然而，所有这些工具/实现都在一些限制性许可（如 GPL、LGPL、MPL）下，而由于我的限制，我正在寻找一些代码，这些代码是在宽松的重用许可（如 MIT 许可）下，最好在C/C++ 或 C#。你知道任何这样的工具或代码吗？

我正在尝试使用编译时生成的数组来实现一个快速函数调度程序，以便能够在运行时在 O(1) 中使用它。

一些代码行只是为了澄清：

让我们将 N 称为调度程序的输入数（在本例中为 4），将 M 称为调度程序输入的最大值（在本例中为 300）。

我已经能够创建一个大小等于 M 的数组。这利用了这样一个事实，即在运行时您可以执行以下操作：

这当然可行，但对于大尺寸的数组是不可行的。

最好的办法是只生成一个包含 N 个元素的数组，并做一些数学技巧将输入索引转换为第二个数组的索引。

在示例中，将 1,5,100,300 分别转换为 0,1,2,3。我已经能够做一种预处理方法来转换它们，但我正在寻找一种方法来避免这一步。

换句话说，我认为我正在寻找某种最小的完美散列，可以在编译时以非常有效的方式用于我的特定情况（理想情况下没有任何开销，例如：goto: MyInstruction）。

我不是在寻找使用虚函数、std::map 或复杂操作的替代方案。

请问有什么不清楚的。

PS我正在使用C++ 11，但欢迎任何想法

[编辑] 我知道标签是 GCC 的值语言扩展。有了这些，我也许可以实现我的目标，但需要一个可移植的解决方案。

可能发生冲突的常规哈希函数在恒定时间内运行：O(1)。但是完美哈希函数的时间复杂度是多少？是1吗？

我有无符号 32 位整数的小（？）集（计数范围从 0 到 100）。对于给定的集合，我想用最少的参数来描述给定集合的最小（标准）完美散列。我用来试验这个想法的高级代码最终类似于：

这只是 2 轴蛮力搜索的基本伪代码。我通过跟踪不同的值来添加行，我可以找到提供完美哈希的种子和模值，然后选择具有最小模数的值。

在我看来，应该有一种更优雅/确定性的方式来提出这些值？但这就是我的数学技能溢出的地方。

我现在正在用 Python 进行试验，但最终想在一个小型嵌入式平台上用 C 语言实现一些东西。