问题标签 [perfect-hash]

有谁知道一个好的库（windows），它可以让我为数百万个项目（可能大约 10m）创建一个静态（而不是运行时）完美的散列？

我基本上有数百万组字符串，我想以最小的 O(1) 知道字符串是否在我的集合中 - 就是这样。我不需要它来实际查找字符串 - 它背后没有任何价值（除了存在之外）。

我想知道如何将字符串值（例如：“myObjectName”）散列为 0-19 之间的 int 值，我保证不超过 20 个唯一字符串值。

谢谢

我正在寻找一个哈希函数，我可以使用它为使用 GSM 调制解调器或以太网连接连接到我们网络的设备提供统一的唯一 ID。

因此，对于任何给定的设备，我都有一个IMEI 号码或一个硬编码的MAC 地址，可用于生成哈希。

在过去的几个小时里，我一直在研究散列函数，阅读我可能想要使用的不同的非加密和加密散列。我的重点是性能上的低冲突，因为不会经常计算哈希。

我的领跑者是 MD5、FNV-1a、MurmurHash2、Hsieh 和 DJB。

无论我使用什么哈希，都必须用 C 语言实现，并且将在带有微型处理器的微控制器上使用。

我知道为您的需要选择一个好的散列函数的诀窍是知道您将提供什么样的输入。

我问这个问题的原因是我脑海中突然出现了一个想法，即 IMEI 和 MAC 都有有限的长度和范围，所以也许存在一个相当简单的哈希函数可以覆盖两者的全部集合并且不会发生冲突。（因此，一个完美的哈希函数）

一个 IMEI 号码是 15 个十进制数字（十六进制是 12-13 个字节？），一个 MAC 地址是 6 个字节。仔细考虑我认为您不会在两组输入数字之间发生冲突，但如果这是错误的，请随时纠正我。如果你这样做了，你能做些什么来阻止它吗？在其中一组中添加一些种子？

我在正确的轨道上吗？是否可以为这些组合集找到完美的哈希函数？

谢谢！

更新

感谢您的回答和评论。我最终使用了恒等函数；）作为我的哈希函数，然后还使用了掩码，因为数字集之间可能存在重叠。

IMEI、IMEISV 和 MAC 都适合 6.5 个字节或更少，所以我将我的值存储在 7 个字节中，然后对第一个字节进行按位或运算，并使用基于数字来自哪个集合的掩码，以确保它们是在所有集合中都是独一无二的。

我有一个 C 语言应用程序，我需要在其中进行表查找。

条目是字符串，所有在运行时开始时都是已知的。该表被初始化一次，然后多次查找。表格可以更改，但基本上就像应用程序重新开始一样。我认为这意味着我可以使用完美哈希？可以花一些时间来初始化哈希表，因为它只发生一次。

将有 3 到 100,000 个条目，每个条目都是唯一的，我估计 80% 的案例的条目少于 100 个。在这些情况下，简单的简单查找“足够快”。（==没有人抱怨）

但是，在有 10k+ 个条目的情况下，幼稚方法的查找速度是不可接受的。为 C 中的字符串提供良好的基于​​哈希表的查找性能的好方法是什么？假设我没有像 Boost/etc 这样的第 3 方商业库。我应该使用什么哈希算法？我该如何决定？

我想创建一个哈希映射（或其他结构，如果您有任何建议）来存储键值对。键将在创建映射的同时同时插入，但直到运行时，当我需要创建映射时，我才知道键是什么（任意长度的字符串）。

我正在解析这样的查询字符串"x=100&name=bob&color=red&y=150"（但字符串可以有无限数量的变量，并且变量可以有任何长度的名称）。

我想解析一次并创建一个哈希映射，最好是最小的并且具有完美的哈希函数来满足线性存储要求。一旦创建了映射，值就不会被修改或删除，也不会再向映射添加键值对，因此整个映射实际上是一个常量。我假设一个变量在字符串中没有出现两次（IE。"x=1&x=2"无效）。

我正在编码C，目前有一个我可以使用的函数，get("x")它将返回字符串"100"，但它每次都会解析查询字符串，这需要O(n)时间。我想在第一次加载它时解析一次，因为它是一个非常大的查询字符串，每个值都会被读取多次。即使我正在使用C，我也不需要代码C作为答案。伪代码或任何建议都很棒！

我将使用 key:value 存储并希望在 Perl 中创建不可碰撞的哈希。是否有 Perl 模块或函数可用于生成不可碰撞的哈希函数或表（可能类似于gperf）？我已经知道我的输入值范围。

我想知道如何将短 ASCII 字符串转换为数字（int、float 或数字字符串）。我在这里看到一些帖子提到了完美的哈希，这似乎是我需要的。但是，我不太了解这方面的数学。

如何将 ASCII 字符串转换为数字序列，然后再转换回字符串？

作为旁注，将字符串分解为它的 ASCII 字符数字很容易。

更新

经过更多阅读，我想出了这个。但是，我想知道是否有办法缩短数字序列，所以它不会那么长。

我在 ubuntu 上使用 gcc 4.4.3。我使用命令安装了 cmph 库工具 0.9-1

sudo apt-get install libcmph-tools

现在，当我尝试编译示例程序 vector_adapter_ex1.c 时，gcc 能够在其包含文件中检测到 cmph.h 库，但显示多个错误，例如

vector_adapter_ex1.c:(.text+0x93): 未定义对cmph_io_vector_adapter' vector_adapter_ex1.c:(.text+0xa3): undefined reference tocmph_config_new' 的引用 vector_adapter_ex1.c:(.text+0xbb): 未定义对cmph_config_set_algo' vector_adapter_ex1.c:(.text+0xcf): undefined reference tocmph_config_set_mphf_fd' 的引用

尽管如此，这些都是在 cmph 库的源代码中定义的。

谁能告诉可能发生的错误或建议另一种方法来构建最小的完美哈希函数。

我需要为字符串标识符列表创建一个完美的哈希，所以在开始这个实现之前（我以前从未做过）我想知道是否有任何好的框架或好的教程可能有用？

谢谢！

我有一个大约 200 万个值的集合（静态，在编译时已知），每个值 20 个字节。我需要的是一种快速的 O(1) 方法来检查给定值是否在这个集合中。似乎带有位数组的完美散列函数是理想的，但我找不到一种简单的方法来创建它。有一些实用程序，例如 gperf，但它们太复杂了。此外，在我的情况下，不需要接近 100% 的负载系数，即使 10% 也足够了，但要保证没有碰撞。此功能的另一个要求是简单，无需太多条件：它将在 GPU 上运行。你对这个案子有什么建议？