java - 数组大小为 600 且冲突最少的哈希码

Question

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

因为长度为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

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

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);
}