N个未知键的最小完美哈希

Question

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

最终，我需要一个大小为N1 + N2的数组--不一定所有条目都会被使用，因为可能遇到重复项--其中包含每个唯一键值的频率。在最坏的情况下，只使用一个字节条目（例如，两个数组中的所有值都相同），留下（（N1 + N2）-1）个未使用的条目。在最好的情况下，所有字节条目都被使用。

根据我的理解，我需要找到一个最小完美哈希函数，将已知数量的未知键（N1 + N2；范围均为 0 - 2^32）映射到已知数量的位置（N1 + N2）。我能够找到一些其他帖子，但是两个答案基本上都说要使用 gperf： 在这种情况下是否可能制作最小完美哈希函数？ 最小完美哈希函数 第二个帖子（最小完美哈希函数）正是我正在尝试做的事情。

与其期望从答案中得到源代码（我使用的是C语言），我更希望能够得到一个关于如何创建一个对于N个任意正整数到N个桶的最小完美哈希函数的解释。我可以很容易地使用一个4GB的数组来进行每个可能整数的直接映射，但这会浪费大量未使用的空间，因此我希望能够减少这种巨大的空间浪费。同时，出于教育目的，我也希望不使用任何外部库来学习更多有关哈希的知识。请保留HTML标签。

- datboi

---

为什么它必须是“最小的”？为什么它必须是“完美的”？假设要求：tablesize = (n1+n2)，普通哈希函数只需要平均 ~(O= 1.5) * (n1+n2) 次探测。 - wildplasser

我从未说过它需要完美；我的目标是一个最小完美哈希表。而我只是想寻求有关如何设计哈希函数的建议，以便仅使用（N1 + N2）个条目生成任何正整数的唯一索引，并且不发生冲突。不确定是否正确，但允许冲突的最坏情况会导致O(N)操作，不是吗？ - datboi

一个完美的哈希函数将会有恰好2^32个条目（在这种情况下）用于N个输入值，因此永远不会发生碰撞。一个最小完美哈希函数只需要N个唯一条目用于N个唯一输入值。这是两者之间差异的很好的解释： http://cmph.sourceforge.net/concepts.html - datboi

Answer 1

这显然是不可能的。如果你有N个数字，除非你事先知道这些数字是什么，否则没有办法想出一个函数将它们全部哈希到范围[0，N)中的不同值。否则，对于任何这样的函数（当然，N < 2^32），至少会有一对整数，使得这两个整数都被哈希到相同的值，因此如果这些整数都出现在输入中，那么该函数将不完美。

如果你放宽条件允许函数在运行时创建，这就变得可能了，但只以一种非常微不足道且无用的方式存在。也就是说，哈希函数可以通过记录每个输入的数字并为每个数字生成新的独特输出（比如从0开始计数）来构建自己。但这样的函数需要一个哈希表（或等效物）作为其实现的一部分，因此在实现哈希表时肯定没什么用处！

- user149341

---

它们不应全部散列为唯一值——尽管它们可以。如果所有的N1 + N2个数字都是实际相同的数字，它们将全部散列到N1 + N2数组的同一位置。不确定这是否会改变是否可能，但听起来你可能误解了问题。 - datboi

@user2962642 数学不是靠希望推动的；它是在恐惧中茁壮成长的。有用重复的可能性无法为任何不需要它们的解决方案提供支持。你只需要考虑最坏情况。 - Potatoswatter

@user2962642：你的评论说条目不需要哈希到不同的位置，因为有些条目可能相等。这与此答案所解决的问题不同，该问题是没有可能的函数可以保证将不同的条目哈希到不同的位置，因为它可以被给定的条目数量（在多个可能的调用中）大于位置的数量。 - Eric Postpischil

考虑一个哈希函数 f(x)，我们声称它将任何包含 N1+N2 个条目的列表映射到 N1+N2 个位置，除非这些条目是重复的，否则不会出现重复。考虑值 f(0), f(1), f(2),… f(N1+N2)。这些值中有 N1+N2+1 个。因此，它们中至少有两个不同的值必须映射到 N1+N2 个位置中的相同位置。我所要做的就是找到这两个条目 A 和 B，然后提供一个包含 A 和 B 的列表。那么，函数 f 就无法将具有不同值的条目在此列表中哈希到不同的位置。 - Eric Postpischil

@Eric：根据此处其他答案中的鸽巢原理，我们将"鸽子"的数量视为N1 + N2，因为我们知道这是我们可能拥有的唯一键的最大数量，还是应该视为2^32？ - datboi

Answer 2

根据鸽巢原理，你将会有“哈希槽”被多个数字占用。换句话说：不同的数字将“哈希”到相同的值。

现在，我想知道你是否可以从Bloom过滤器中受益。来自维基百科：

可能存在误报匹配，但不存在误拒匹配；即查询返回“可能在集合中”或“肯定不在集合中”。

如果某些东西“肯定”不在键集中，你可以继续（其频率为一），如果它可能在集合中，则进一步处理以累积其实际统计数据。

- Escualo

---

我对此有些不清楚，但在我提出的情况下，“鸽子”的数量是N1 + N2还是2^32？我知道“鸽巢”的数量将是N1 + N2，因为这就是我试图将这些值映射到的内容。 - datboi

从我理解的问题来看（我可能误解了），因为这些是您可能的数据成员（否则哈希将不完美），所以有2^32个鸽子。如果您要在每个问题实例上创建哈希函数，则可以放宽此假设，但您将失去所有的普适性（即，您必须为每对数据容器创建一个新的哈希函数）。 - Escualo

是的，我认为你是正确的。我感到困惑，以为输入的_domain_是2^32，而不是“鸽子”的数量。虽然我相当确定它们是一样的。 - datboi