数组大小为 600 的哈希代码，冲突最少

Question

所以我正在使用一个包含 400 个数据值的文件，所有整数，值范围从 4 到 20,000。 我将所有这些加载到大小为 400 的数组中。还有另一个大小为 600 的 ListNode 空数组，我将把数据移动到该数组，但使用自己编写的哈希代码(我将在下面发布)。

因为长度为 600 的数组中的每个索引都有一个 ListNode，所以如果有任何冲突，则数据值将添加到 ListNode 的后面。我还有一个返回数组百分比为空的方法。但基本上由于我将 400 个数据值加载到大小为 600 的数组中，因此我可以拥有的最小空值百分比为 33.3%，因为如果没有冲突，则数组中的 400 个插槽被占用，200 个为空，但事实并非如此：

return (num+123456789/(num*9365))%600; //num is the value read from the array of 400

该哈希代码给了我 48.3% 空值的最佳结果，我需要它至少低于 47%。 有什么建议或解决方案来改进这个哈希代码吗？我将非常感谢任何帮助。如果您需要更多信息或详细信息，请告诉我。谢谢！！！

Answer 1

我用随机数做了一些实验：在 [0， 599] 范围内生成 400 个均匀分布的随机数，并检查该范围内有多少值未生成。事实证明，平均有51.3%的值没有生成。所以你的48.3%已经比预期的要好了。 47%的目标似乎不切实际，除非使用某种形式的完美哈希。

如果您想自己进行一些实验，这里是程序。

public static void main(String[] args) {
Random r = new Random();
int[] counts = new int[600];
for (int i = 0; i < 400; i++) {
counts[r.nextInt(600)]++;
}
int n = 0;
for (int i = 0; i < 600; i++) {
if (counts[i] == 0) {
n++;
}
}
System.out.println(100.0 * n / 600);
}

Answer 2

我会使用哈希算法的JAVA实现：

Hava a look at open-jdk HashMap

static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

请注意，您还添加了模运算，以确保该值不会大于 600

---

编辑 1

>>> is logical shift right

例：

10000000 >>> 2 = 00100000