Java 中 HashMap 的内部实现

Question

我正在尝试在 Java 中创建 HashMap() 的数据结构。 HashMap 最多只能进行 N = 1000 次操作，并且键只能是正整数。我所做的如下：

class MyHashMap {
        final ListNode[] nodes = new ListNode[1000];
        // "put", "get" and "remove" methods which take
        // collisions into account using "chaining".
}

决定我的新键值对在 nodes 中的位置我总是需要计算一个索引。我使用函数：

 public int getIndex(int key) { return Integer.hashCode(key) % nodes.length;}

其中 returns 是介于 0 和 nodes.length 之间的整数。但是，我如何在不使用 Integer.hashMap(key) 的情况下自行编写 Java 中的哈希函数，将整数映射到某个索引？程序也很好，我真的不需要代码。

Answer 1

结果

Integer.hashCode(key) returns key。你可以写：

public int getIndex(int key) { 
    return key % nodes.length;
}

这样，您就不用 Integer.hashCode(key)。

没有看到您的 class ListNode，您的 MyHashMap 结构可能有问题，因为您将许多元素设置为同一个数组元素。例如键 3 和 1003 将保存在同一个节点元素中。您必须将 MyHashMap 设计为列表的列表（或列表的数组或类似的东西）。

Answer 2

嗯，首先 hash 是独一无二的或很少重复的值。

假设您的值将均匀分布，您可以使用除法的余数作为密钥的哈希值。

public int get(int key) {
    return (-1 ^ key) % nodes.length;
}

Answer 3

散列 int 值的一个简单策略是乘以一个大常数。如果您不使用常量，根据您的密钥分布，您可能会得到非常差的冲突率。仍然有可能获得较差的密钥分布，但真实数据的可能性较小。

注意：除非你知道密钥不能为负，否则你应该使用Math.abs来确保它是非负的。

static final int K = 0x7A646E4D; // some large prime.

public int getIndex(int key) { 
    return Math.abs(key * K % nodes.length);
}

一个更快的解决方案是放弃使用 % 使用乘法和移位。例如

public int getIndex(int key) { 
    return (int) ((key * K & 0xFFFF_FFFFL) * nodes.length >>> 32);
}

这样做是将 key * K 变成分数，并且比使用 %

更快

Java 中 HashMap 的内部实现

Internal implementation of HashMap in Java

java

hash-function

hashmap