问题标签 [perfect-hash]

我有一系列像这样的十六进制数字

我需要一个哈希函数，该函数将接受一个 4 字节的值并为成员资格生成 Y/N 答案。

我尝试使用 gperf 但不幸的是它不会将 * 解释为通配符。有没有人遇到过这个问题？我的代码在 C 中。

我想用无序映射实现完美的散列。我有一组编译时已知的字符串，它映射到某些东西。我想为他们生成完美的哈希函数。我发现如果我选择 unordered_map 的大小比已知字符串集的大小大 3 倍，我就能找到一个完美的散列函数（即种子数）。我想尽量减少这个数字。和相关的问题是，如果我使用更大的无序地图，我会得到更快的地图，这是真的吗？

我玩过 Google 的 CityHash 函数： http ://code.google.com/p/cityhash/

我有两个未排序的 32 位无符号整数数组，大小分别为 N1 和 N2。每个数组可能包含重复项。我想将每个值（2^32 个可能的键）映射到大小为（N1 + N2）的字节数组中的一个点，以记录每个键的频率。重复的键值应映射到此数组中的相同位置。此外，每个整数的频率不会超过 100（这就是为什么我选择一个字节数组来记录每个键的频率以节省空间）；如果最大可能频率超过此值，我只需将字节数组更改为短裤数组或其他东西。

最后，我需要一个大小为 N1 + N2 的数组——不一定会使用所有条目，因为可能会遇到重复项——每个唯一键值的频率。最坏的情况下，将只使用一个字节条目（例如，两个数组中的所有值都相同）而使 ((N1 + N2) - 1) 个条目未使用。最佳情况下，使用所有字节条目。

据我了解，我需要找到一个最小完美的散列函数来将已知数量的未知键（N1 + N2；所有范围从 0 - 2^32）映射到已知数量的点（N1 + N2）。我能够找到其他一些帖子，但两个答案基本上都说使用 gperf：

在这种情况下是否可以制作一个最小的完美哈希函数？

最小完美散列函数

第二个（最小完美散列函数）正是我想要做的。

与其期望答案中的源代码（顺便说一句，我正在使用 C），我更愿意解释如何为 N 个桶的任何可能正整数的 N 个创建一个最小完美的散列函数。我可以很容易地使用 4 GB 的直接映射数组来处理具有大量未使用空间的每个可能的整数，但我宁愿尝试减少这种巨大的空间效率低下。我也希望不使用任何外部库，主要用于教育目的，以了解更多关于散列本身的信息。

所以这就是问题所在：我在我的项目中使用 MongoDB，所以有 24 个字符的 ObjectId，只使用十六进制字母。我在我的项目中向提供者发出 http 请求，在此请求中，我需要放置一个唯一的 ID 用于回调目的，但提供者只允许此 ID 包含20 个字符，我不知道为什么。

所以，我的问题是，使用 16 个字符的字母（六进制），有：16^24 个可能的 mongo Id，对吗？假设我在 HTTP 请求中使用基于 64 个不同字符（[0-9][az][AZ]-_）的 Id，如果我错了，请纠正我，但我认为有 64^20 个可能的 Id。所以从技术上讲，可以用相应的 Id 对每个可能的 MongoDB ObjectId 进行编码，不是吗？

这似乎是一个经典的 Base64 编码，但神秘的是这并没有像我预期的那样工作，我想我不明白 Base64 编码是如何工作的，因为生成的字符串比原始字符串大......

你认为这一切都是可能的，还是我完全错过了什么？

提前致谢！

编辑：我的一位同事尝试了一些似乎有效的方法。这是Java代码：

由于我忽略的原因，这样做是不一样的：

它打印：NTM4ODQ1OTRlNGIwNjk1ZjM2NmY4MTI4

我当前的解决方案使用多维数组，是否存在更简单的解决方案？我想在 O(1) 时间内访问散列对象，并希望充分利用内存空间，因此需要完美的散列。

我在 Go 中实现了一个简约的非循环有限状态自动机（MA-FSA；一种特定类型的 DAG），并希望将一些额外的数据与指示 EOW（词尾）的节点相关联。使用 MA-FSA，传统方法是不可能的，因为有多个单词可能以该节点结尾。所以我正在寻找最小的完美散列函数作为替代方案。

在他博客文章顶部的“更正”框中，Steve Hanov说他使用了Lucchesi 和 Kowaltowski 在这篇论文中描述的方法。在查看图 12（第 19 页）时，它描述了散列函数。

在第 8 行，它指的是FirstLetterand Predecessor()，但它没有描述它们是什么。或者我没看到。这些是什么？

我所能弄清楚的是它只是遍历树，Number从每个节点开始累加，但这不可能是正确的。它产生的数字太大而且不是一对一的，就像论文说的那样。我误读了什么吗？

我发现 gperf 适合我的项目，现在正在寻找一种优化生成表大小的方法。由于开关 -i 和 -j 确定性地影响表的长度，我编写了一个小脚本迭代这些值，找到最小的表长度。该脚本存储 -i 和 -j 值以在脚本终止时检索当前最小表以及当前尝试的值，以便稍后继续搜索。

现在我看到存在一个开关 -m，它表明它与我对我的小脚本所做的完全一样。我想使用这个开关比只调用 gperf 进行一次迭代要快得多。但是我需要知道两件事来替换 gperf 调用，我在 gperf 帮助中找不到：

1. 如果我使用 -m 开关，如果 -i 和 -j 会尝试哪些值？
2. 我怎么知道实际使用了 -i 和 -j 的哪些值，即哪些值导致当前 gperf 调用的最小找到表长度？

我有 4000 个字符串，我想用这些字符串创建一个完美的哈希表。字符串是事先知道的，所以我的第一个想法是使用一系列if语句：

然而，这将是非常低效的。有没有更好的办法？

我有一组 C++ 函数。我想将这个函数映射到一个哈希表中，比如：unordered_map<function<ReturnType (Args...)> , SomethingElse>，其中SomethingElse与这个问题无关。

这组函数是以前已知的，小（比如说少于 50 个）和静态（不会改变）。

由于查找性能至关重要（应该在 中执行O(1)），我想定义一个完美的散列函数。

这种场景是否存在完美的哈希函数生成器？

我知道存在完美的散列函数生成器（如GPERF或CMPH），但由于我从未使用过它们，我不知道它们是否适合我的情况。

原因：

我正在尝试设计一个框架，给定一个用 C++ 编写的程序，用户可以选择F该程序中定义的函数的子集。

对于每个f属于F，框架实现了一个记忆策略：当我们f用输入调用时i，我们存储(i,o)在一些数据结构中。因此，如果我们要调用 AGAIN f，i我们将返回o而不再次执行（时间昂贵的）计算。

“已经计算的结果”将在不同的用户之间共享（可能在云端），所以如果用户u1已经计算了o，用户u2将节省计算时间调用（使用f与i之前相同的注释）。

显然，我们需要存储对的集合(f,inputs_sets)（inputs_sets我之前谈到的已经计算好的结果集在哪里），这是最初的问题：我该怎么做？

因此，在这种情况下使用评论中提出的“枚举技巧”可能是一个解决方案，假设所有用户都使用完全相同的枚举，这可能是一个问题：假设我们的程序有f1, f2，f3如果u1想要记忆怎么办只有f1和f2（所以F={f1,f2}），而u2只想记住f3（所以F={f3}）？一个矫枉过正的解决方案可能是枚举程序中定义的所有函数，但这可能会产生巨大的内存浪费。