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

其返回CCD_ 4和CCD_。但是，在不使用Integer.hashMap(key)的情况下，我如何用Java自己编写一个将整数映射到某个索引的哈希函数呢？程序也很好，我真的不需要代码。

Answer 1

散列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转化为分数，并且比使用%更快

Answer 2

Integer.hashCode(key)只返回key作为结果。你可以写：

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

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

如果没有看到您的类ListNode，您的MyHashMap结构可能会出现问题，因为您将许多元素设置为同一个数组元素。例如，密钥3和1003将被保存在同一节点元素中。您必须将MyHashMap设计为列表列表(或列表数组或类似内容(。

Answer 3

首先，hash是唯一的或很少重复的值。

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

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