查询HashMap的内部实现

Question

我将介绍HashMap的实现，并引用以下链接：Java如何实现哈希表？我发现"HashMap包含一个bucket数组，以便包含它的条目"。所以，我有几个问题-

1. bucket数组的类型是什么
2. 既然数组有缺点(例如，固定大小和只允许同质数据(。那么，为什么我们使用数组，尽管有这些缺点

3.如果密钥或冲突的哈希代码相同，则使用链表。它如何获得(搜索(第二、第三节点等的引用

在广告中谢谢

Answer 1

1. bucket数组的类型是什么

这取决于你制作的地图，如果你制作了HashMap<Integer, String>，那么桶将是这些类型的，能够包含这些类型的对象

2. 因为数组有缺点(例如，固定大小和只允许同质数据(。那么，为什么我们使用数组，尽管有这些缺点

因为与性能增益相比，缺点是值得的。因为数组是固定大小的，所以可以跳过很多检查(即，该索引是否存在？(。你可以在这里阅读更多关于这方面的信息；https://en.wikiversity.org/wiki/Java_Collections_Overview以及为什么不总是在Java中使用ArrayLists，而不是普通的ol'；阵列？

3. 如果密钥或冲突的哈希代码相同，则使用链表。它如何获得(搜索(第二个、第三个节点的引用等

这里解释得比我更好；当一个重复的密钥被放入一个HashMap中时会发生什么？

Answer 2

1. 它是一个内部对象，包含关键字、值和对bucket中下一个节点的引用(实现单个链表(
2. 阵列需要2的幂的固定大小。给定键的数组索引基于键的哈希代码和数组大小的逻辑AND(&(，数组大小是哈希表的实际"魔力">
3. bucket中的链表是处理hashcode冲突所必需的。这就是HashMap.get((的O(n(的最坏情况复杂性的原因——如果所有键都有相同的哈希代码，并且搜索到的键是bucket中的最后一个键，就会发生这种情况

如果hashmaps增长，就会有一个非常昂贵的rehash函数，因为数组也必须增长到2的下一次方。在这种情况下，每个bucket都必须重新分配其索引。在这种情况下，将构建一个新的阵列。这意味着不需要动态数据结构。

如果创建一个具有适当容量参数的新哈希映射，则可以避免重复哈希。

Answer 3

来自OpenJDK8的代码源：

1. 存储箱是Lists或Trees，具体取决于它们所包含的元素数量
2. 在这种情况下，阵列的同质性不是问题，访问速度高于调整阵列大小的成本
3. HashMap总是使用相同的哈希迭代所有值，测试它们是否具有正确的密钥：

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}