章
目
录
Java HashMap是Java集合框架的一部分，用于存储键值对。每个键都映射到一个值，不允许重复的键。在本教程中，我们将学习HashMap如何在内部存储键-值对以及如何防止重复的键。
1.HashMap的快速回顾
HashMap存储键-值对。它将提供的键与值关联起来，因此以后我们可以使用键来检索值。
HashMap<String, String> map = new HashMap<>();
map.put("key", "value"); //存储
map.get("key"); // 返回 "value"
在内部，键-值对被存储为Map.entry实例，由Node表示。Node类的每个实例包含提供的键、值、键对象的哈希值以及对下一个Node的引用（如果有的话，就像在LinkedList中一样）。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//...
}
生成的键对象的哈希值也被存储，以避免在比较过程中每次计算哈希，从而提高整体性能。
2.HashMap的内部实现
HashMap是Map接口的基于HashTable的实现。它在内部维护一个数组，也称为“桶数组”。桶数组的大小由HashMap的初始容量决定，默认值为16。
transient Node<K,V>[] table;
数组中的每个索引位置都是一个桶，可以使用LinkedList容纳多个Node对象。
如上所示，多个键可能会产生将它们映射到单个桶的哈希。这就是为什么Map条目存储为LinkedList的原因。
但当单个桶中的条目达到阈值（TREEIFY_THRESHOLD，默认值为8）时，Map会将桶的内部结构从链表转换为红黑树（JEP 180）。所有Entry实例都会转换为TreeNode实例。
基本上，当一个桶变得太大时，HashMap会动态地用Tree的自定义实现来替代它。这样，与悲观的O(n)性能相比，我们获得了更好的O(log n)。
请注意，当桶中的节点少于UNTREEIFY_THRESHOLD时，树再次转换为LinkedList。这有助于在性能和内存使用之间取得平衡，因为TreeNodes比Map.Entry实例占用更多内存。因此，Map仅在以内存浪费换取明显性能提升时使用Tree。
3.哈希如何用于定位桶？
哈希在其最简单的形式中是一种在将其属性应用于对象之后为任何对象分配唯一代码的方法。真正的哈希函数应该在将函数应用于相同或相等对象时每次都返回相同的哈希代码。换句话说，两个相等的对象必须一致地产生相同的哈希代码。
在Java中，所有对象继承了Object类中定义的hashCode()函数的默认实现。它通常通过将对象的内部地址转换为整数来生成哈希码，从而为所有不同的对象生成不同的哈希码。
public class Object {
public native int hashCode();
}
Java设计者了解到，用户创建的对象可能不会产生均匀分布的哈希码，因此Map类在内部对键的hashCode()再次应用了另一轮哈希函数，以使它们合理分布。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这是从Key对象的初始哈希生成的最终哈希，它是在数组中查找Node的索引。
4.HashMap.put()操作
到目前为止，我们了解到每个Java对象都有一个与之关联的唯一哈希码，并且这个哈希码用于决定在HashMap中存储键-值对的桶位置。
在进入put()方法的实现之前，非常重要的是了解Node类的实例存储在一个数组中。数组中的每个索引位置被视为一个桶：
transient Node<K,V>[] table;
为了存储键值对，我们调用put()API如下：
V put(K key, V value);
put()API在内部首先使用key.hashCode()方法计算初始哈希，然后使用上一节中讨论的hash()方法计算最终哈希。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
最终哈希值最终用于计算数组或桶位置的索引。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
一旦找到桶，HashMap就会将Node存储在其中。
5.相同桶中的冲突如何解决？
现在主要部分来了，我们知道两个不相等的对象可能具有相同的哈希码值，那么如何将两个不同的对象存储在称为桶的相同数组位置中呢？
如果您记得，Node类有一个属性”next”。该属性始终指向链中的下一个对象。因此，所有具有相等键的节点以LinkedList的形式存储在相同的数组索引中。
当需要在特定索引处存储Node对象时，HashMap会检查数组索引是否已经存在Node对象。如果该索引上没有Node，则当前Node对象将存储在此位置。如果已经有对象位于计算的索引上，将检查它的next属性。如果next为null，当前Node对象成为LinkedList中的下一个节点。如果next变量不为null，将重复该过程，直到next评估为null。
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
break;
}
请注意，当在节点上进行迭代时，如果现有节点和新节点的键相等，那么现有节点的值将被新节点的值替换。请注意，如果桶中的第一个节点是TreeNode类型，则将使用TreeNode.putTreeVal()来在红黑树中插入新节点。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
总之，我们可以说：
- 如果桶是空的，Node将直接存储在计算的索引处的数组中。
- 如果桶不为空，即已经存在一个Node，则以LinkedList方式遍历当前Node，直到next节点为空或键匹配。一旦找到next为空，将当前Node存储在LinkedList的末尾。
6.HashMap.get()操作
Map.get() API以键对象作为方法参数，并返回关联的值，如果在Map中找到的话。
String val = map.get("key");
与put()API类似，查找桶位置的逻辑与get()API相似。一旦找到桶位置，将检查索引位置上的第一个节点。
如果第一个节点是TreeNode类型，那么将使用TreeNode.getTreeNode(hash, key) API来搜索相等的键对象。如果找到了这样的TreeNode，将返回值。
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
如果第一个节点不是TreeNode，那么搜索将以LinkedList方式进行，并在每次迭代中检查next属性，直到找到一个Node的键对象匹配。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
7.结论
本Java教程讨论了HashMap类的内部工作原理。它讨论了如何计算哈希值的两个步骤，以及最终哈希如何用于在Node数组中查找桶位置。我们还了解了在重复键对象的情况下如何解决冲突。
