我正在尝试建立一个哈希表(在C++中，使用unordered_map容器)，其中包含1875个整数项，这些项在0到4891的区间内随机分布。现在我的问题是这个区间内的分布是不统一，而是看起来像这样:
其中 1875 个随机整数中的每一个都被绘制为一个点，x 对应于整数值，y = 1(以便可视化分布)。
显然，分布是这样的，即存在很大的间隙，其中没有随机整数。如果我使用恒等函数作为哈希函数(即使用随机整数本身作为哈希值)，我会得到 714 个空桶、814 个包含单个元素的桶、499 个包含 2 个元素的桶和 21 个包含 3 个或更多元素的桶。/p>
我使用的是英特尔 C++ 编译器，它使用 2 的幂来表示哈希表中的存储桶数量。就我而言，现在哈希表有 2^11 = 2048 个存储桶。
对于这种情况，什么是好的哈希函数？我的理解是，在这种情况下，一个好的哈希函数会摆脱这些聚集的整数，并将它们以更均匀的分布进行洗牌，但如何才能实现这一点呢？
最佳答案
我发现 Pearson 的哈希函数是获得随机性的绝佳方法:
https://en.wikipedia.org/wiki/Pearson_hashing
基本上，这个想法是它默认生成一堆非常随机的数字到 256 个 bin 的数组中，但您可以将其修改为 1800 适合您的场景。重要的是数组足够小以适合内存。
关于c++ - 聚集整数的哈希函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33681575/