不需要更新的整数集合的完美哈希函数

Question

在我所工作的一个应用程序中，需要有这样一个函数：

bool IsInList(int iTest)
{
   //Return if iTest appears in a set of numbers.
}

数字列表在应用程序加载时已知（但在同一应用程序的两个实例之间并不总是相同），并且在整个程序执行过程中不会改变（或添加）。这些整数本身可能很大，并且具有很大的范围，因此使用vector<bool>不是高效的方法。性能是一个问题，因为该函数位于热点中。我听说过完美散列，但找不到任何好的建议。任何指针都将有所帮助。谢谢。

附：理想情况下，如果解决方案不是第三方库，那就太好了，因为我不能在这里使用它们。如果有可能的话，一些简单易懂且可以手动实现的东西将是很棒的。

- nakiya

---

我也在尝试阅读关于将字符串哈希到数字的完美哈希的相关信息。但是发现只有很少的信息 :( - Johannes Schaub - litb

你确定 O(log n) 的查找（例如在已排序数组上的二分查找）不够快吗？请记住，哈希是O(k)，其中k与n无关（因此哈希在n方面是O(1)），但对于非巨大的n值（即小于一百万），k仍然可能大于O(log n)。 - Fred Nurk

这里是一个Java实现的最小完美哈希查找器。 - Pointy

@Pointy：有趣的是，它将C++的面向对象特性称为奇怪的，然后使用Java的四个原因中有两个是面向对象的。 - Fred Nurk

@Fred Nunk 是的，我没有太关注那些小怒气; 我只看了代码，它至少基本上是有能力的 - 而且他引用了一些看起来很有趣的论文。 - Pointy

Answer 1

我建议在使用简单的 std::map 时同时使用 布隆过滤器（Bloom Filters）。

不幸的是，布隆过滤器并不是标准库的一部分，因此您需要自己实现它。然而，事实证明这是一个相当简单的结构！

布隆过滤器是一种数据结构，专门处理以下问题：一个元素是否是集合的一部分，但内存需求非常小且速度快。

略微捕捉到的是答案是特殊的：这个元素是集合的一部分吗？

• 否
• 可能（具体概率取决于布隆过滤器的属性）

这看起来很奇怪，直到你看到实现方式，并且它可能需要一些调整（有多个属性）以降低概率，但...

对于所有情况下回答为No的情况，您可以保证它不是集合的一部分。

因此，布隆过滤器非常适合作为二叉树或哈希映射的门卫。经过精心调整，它只会让非常少的误判通过。例如，gcc使用布隆过滤器。

- Matthieu M.

---

通常情况下，当集合只需构建一次且之后仅被引用时，排序的 std::vector 比 std::map 具有更好的性能。std::vector 具有极佳的缓存局部性，并且 std::lower_bound 的速度与 std::map::find 相同。 - deft_code

@deft_code：我完全同意（实际上我自己通常使用排序的数组/向量来表示常量）。这不仅仅是缓存局部性，还有缓存预取在起作用，因为内存是连续的，而树中的访问则不太可预测（对于CPU而言）。 - Matthieu M.

Answer 2

我想到的是gperf。然而，它是基于字符串而不是数字。但是，可以调整计算的一部分，使用数字作为哈希生成器的输入。

- Diego Sevilla

---

如何调整gperf以使用数字？ - undefined

Answer 3

整数、字符串，都没关系。

http://videolectures.net/mit6046jf05_leiserson_lec08/

在介绍之后的49:38处，您将学习如何实现这一点。演示了Dot Product哈希函数，因为它有一个优美的证明。大多数哈希函数就像巫术黑魔法一样。不要浪费时间在这里，找到适合您数据类型且提供一些可调节种子进行哈希的快速方法。这里的好组合比增加哈希表的替代方案更好。

@54:30教授画了一个标准的完美哈希方式的图片。完美的最小哈希超出了本讲座的范围。(祝你好运！)

这真的取决于你用什么来取模。

请记住，通过了解您正在运行的硬件，可以进一步优化所展示的分析。

在99.9％的情况下，std::map可以获得非常好的性能。如果您的热点多次具有相同的iTest，则将地图结果与临时哈希缓存组合。

Int是其中一种数据类型，可以只执行：

bool hash[UINT_MAX]; // stackoverflow ;)

填充它。如果您不关心负数，则这将变得容易两倍。

- ticktock

Answer 4

一个完美的哈希函数将一组输入映射到整数上，而不会发生碰撞。考虑到您的输入是一组整数，这些值本身就是完美的哈希函数。这与手头的问题无关。

测试存在性最明显且易于实现的解决方案是排序列表或平衡二叉树。然后，您可以在log（N）时间内确定存在性。我怀疑它不会比那更好。

- Donnie

---

你写的是正确的，然而事实仍然如此，一个最小化的完美哈希函数将是有用的，如果找到该函数的成本不太大，那么将会得到一个O(1)的解决方案。 - Pointy

如果您将源整数用作哈希值，那么您必须使用一个非常大的数组，可能有很多未使用的项，因为他说范围很大。 - Johannes Schaub - litb

@Johannes Schaub，这就是为什么人们会寻找最小化的完美哈希函数，它可以产生一个范围内的值，该范围等于不同集合成员的数量，而与原始范围无关。 - Pointy

@Pointy 是的，但那不使用源整数作为哈希值。我的评论是给 @Donnie 的。 - Johannes Schaub - litb

@Donnie那并不确切 - 最小完美哈希函数将源整数集合映射到最小值范围内。如果原始集合中有n个不同的值（分布在任意范围内），则最小完美哈希函数会产生[0...n)范围内的整数。 - Pointy

Answer 5

针对这个问题，我会使用二分搜索算法，假设可以保持数字列表排序。

维基百科有示例实现，应该很容易转换成C++。

- zildjohn01

Answer 6

将N个不同的随机分散整数映射到N个连续的桶中并不是必要或实际的 - 即完美的最小哈希 - 重要的是要确定一个可接受的比率。为了在运行时完成这个任务，您可以首先配置一个最差可接受比率（例如1:20）和一个无需更好比率（例如1:4），然后随机变化（例如更改使用的质数）一个快速计算的哈希算法，以查看您能够满足越来越困难的比率。对于最差可接受比率，您不会超时，或者您会退回到一些更慢但可靠的方法（容器或位移列表来解决冲突）。然后，允许每个X％更好的第二个或十个（可配置），直到您无法成功达到该比率或达到无需更好比率....

为了让大家清楚，这仅适用于在运行时已知的输入，没有预先知道有用模式的情况下，这就是为什么不同的哈希函数必须在运行时进行尝试或主动派生的原因。简单地说“整数输入形成哈希”是不可接受的，因为当它们被%到任何合理的数组大小时都会发生碰撞。但是，您也不需要针对完美填充的数组进行目标设置。还要记住，您可以拥有指向紧凑数组的稀疏指针数组，因此对于大型对象浪费的内存很少。

- Tony Delroy

Answer 7

原始问题

在使用它一段时间后，我想出了许多哈希函数，似乎在字符串上表现得相当不错，导致了一种独特的-完美哈希。

假设值在数组中的范围从 L 到 H。这产生了一个范围 R = H - L + 1。通常比较大。

然后我从 H 往下到 L + 1 应用模运算符，寻找一个能够保持它们唯一但具有更小范围的映射。

在你的情况下，你正在使用整数。从技术上讲，它们已经被哈希了，但范围很大。

也许你可以通过应用模运算符来获得你想要的结果。也可能需要先放置一个哈希函数。

还可能是你无法为它找到完美的哈希，此时，你的容器类应该有一个备用方案......二分查找、映射或类似的东西，这样就可以保证容器在所有情况下都能正常工作。

- EvilTeach

Answer 8

使用Trie树或van Emde Boas树可能是创建空间高效的整数集合并且在数据结构中对象数量增加时具有恒定查找时间的更好选择，假设即使使用std::bitset也太大。

- Steve Massey

Answer 9

（初始时）确保整数列表已排序（且连续）。

（根据需要）使用二分查找测试成员资格。

如果列表中的整数范围确实很大且任意，我认为你不会有比这更好的选择，正如你所说的。

- Glenn Slayden