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

Question

所以我正在处理一个具有 400 个数据值的文件，所有数据值都是整数，值范围从 4 到 20,000。我将所有这些加载到一个大小为 400 的数组中。还有另一个大小为 600 的空 ListNode 数组，我会将数据移动到该数组中，但使用的是自写的哈希码（我将在下面 post 它）。

因为长度为600的数组中的每个索引里面都有一个ListNode，如果有冲突，那么数据值会被添加到ListNode的后面。我还有一个方法 returns 数组中为 null 的百分比。但基本上因为我将 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

我会使用哈希算法的 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

Answer 2

我用随机数做了一些实验：在 [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);
}

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

Hash code for array size 600 with least collisions

java

arrays

hashcode