c - N 个未知键的最小完美散列

Question

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

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

据我所知，我需要找到一个至少完美的散列函数来映射已知数量的未知键(N1 + N2 ; 所有范围从 0 - 2^32) 到已知点数 (N1 + N2)。我能够找到其他一些帖子，但两个答案基本上都说使用 gperf:

Is it possible to make a minimal perfect hash function in this situation?

Minimal perfect hash function

第二个 ( Minimal perfect hash function ) 正是我想要做的。

与其期望从答案中获得源代码(顺便说一句，我正在使用 C)，我更愿意解释如何着手为 N- 创建一个最小完美的哈希函数N 个桶中任何可能的正整数的数量。我可以使用一个 4 GB 的直接映射数组轻松地为每个可能的整数和大量未使用的空间做到这一点，但我宁愿尝试减少这种巨大的空间效率低下。我也希望不使用任何外部库，主要用于教育目的，以了解更多关于哈希本身的信息。

Answer 1

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

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