3

我有两个未排序的 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 的直接映射数组来处理具有大量未使用空间的每个可能的整数，但我宁愿尝试减少这种巨大的空间效率低下。我也希望不使用任何外部库，主要用于教育目的，以了解更多关于散列本身的信息。

4

2 回答 2

1

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

如果您放宽条件以允许动态创建函数，这将成为可能，但只是以一种非常微不足道和无用的方式。也就是说，哈希函数可以通过记录输入其中的每个数字并为每个数字生成一个新的唯一输出（例如，从 0 开始计数）来构建自己。但是这样的函数需要一个哈希表（或类似的东西）作为其实现的一部分，所以它在实现一个哈希表时肯定没有用！

于 2013-11-07T00:42:48.417 回答
0

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

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

假阳性匹配是可能的，但假阴性是不可能的；即查询返回“可能在集合中”或“绝对不在集合中”。

如果某些东西“肯定”不在键集中，您可以继续（它的频率是一个），如果它可能在集中，那么您进一步处理它以累积其实际统计信息。

于 2013-11-07T00:52:39.970 回答