共计 4252 个字符，预计需要花费 11 分钟才能阅读完成。
前言
本文是基于 Java 8 的 HashMap 进行分析，主要是分析 HashMap 中的 put() 和 get() 方法。
下面将会分析这部分的源码，如果觉得源码分析内容太啰嗦，可以跳过源码部分，直接看源码下面的总结。
put() 方法源码分析
HashMap 的 put() 方法是我们最常用的方法，但是 put() 方法是怎么工作的呢？
put() 方法
/**
* HashMap 的 put() 方法支持 key/value 为 null
*/
public V put(K key, V value) {
// 实际上是先调用 HashMap 的 hash() 方法获取到 key 的 hash 值
// 然后调用 HashMap 的 putVal() 方法
return putVal(hash(key), key, value, false, true);
}
put() 方法实际上是
调用 hash() 方法获取到 key 的 hash 值
调用 putVal() 方法存储 key-value
核心方法是 putVal() 方法，下面我会先分析一下 hash() 方法，因为这个方法涉及到 hash 值这个关键属性的计算。
hash() 方法
static final int hash(Object key) {
int h;
// key 为 null 时，hash 值为 0
// key 不为 null 时，调用 key 对象的 hashCode() 方法并通过位运算异或和无符号右移将高位分散到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash() 方法指定了 null 的 hash 值为 0。这样就可以支持 key 为 null。
(h = key.hashCode()) ^ (h >>> 16) 这段代码通过位运算异或和无符号右移将高位分散到低位，这样做可以减少哈希碰撞的概率（这块不是很清楚原理，是从方法注释上了解到的）
putVal() 方法
/**
* Map.put() 方法的实际实现
*
* @param hash key 的 hash 值
* @param key 键值对中的 key
* @param value 键值对中的 value
* @param onlyIfAbsent 如果为 true，则键值对中的值已经存在则不修改这个值
* @param evict 如果为 false，则是处于创建模式
* @return 上一次的 value，如果上一次的 value 不存在，则为 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//tab 用于暂存散列表 table。p 为散列表中对应索引的链表的头节点的指针。n 存储 tab 的长度。i 则为命中的散列表的索引
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 给 tab 和 n 赋值
// 当 tab 为 null 或者 tab 的长度 n 为 0 时，触发 resize() 来初始化 tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 使用 (n – 1) & hash（等价于 hash%n）计算命中的散列表索引，同时判断散列表对应索引的链表是否存在
if ((p = tab[i = (n – 1) & hash]) == null)
// 散列表对应索引的链表不存在则创建一个新的链表
tab[i] = newNode(hash, key, value, null);
else {// 散列表对应索引的链表已存在
Node<K,V> e; K k;
// 判断头节点的 hash 值和 key 是否与入参的 hash 值和 key 一致。需要注意，null 的 hash 值为 0
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 对应的键值对已经存在，记录下来
e = p;
else if (p instanceof TreeNode)// 判断对应的链表是否转化为红黑树
// 若是，则直接调用红黑树的 putTreeVal() 方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// 链表的头节点与新的键值对不重复，即没有发生哈希碰撞
for (int binCount = 0; ; ++binCount) {// 遍历链表
if ((e = p.next) == null) {// 遍历到尾节点
// 尾插法添加一个新的节点
p.next = newNode(hash, key, value, null);
// 链表长度大于阈值
if (binCount >= TREEIFY_THRESHOLD – 1) // 从 - 1 开始，所以为阈值 -1
// 将链表转化为红黑树
treeifyBin(tab, hash);
// 中断循环
break;
}
// 判断当前遍历的节点的 hash 值和 key 是否与入参的 hash 值和 key 一致，即 key 是否已经存在
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// key 已经存在，中断循环
break;
// 记录当前遍历的节点
p = e;
}
}
if (e != null) {// Map 中存在重复的 key
V oldValue = e.value;// 记录下旧值
if (!onlyIfAbsent || oldValue == null)// 判断值存在是否可以进行修改以及旧值是否为 null
e.value = value;// 修改该节点的值
afterNodeAccess(e);// 链表节点的回调方法，此处为空方法
return oldValue;// 返回旧值
}
}
// HashMap 发生结构变化，变化次数累加
++modCount;
// 键值对个数自增，同时判断是否达到扩容的阈值
if (++size > threshold)
resize();
// 链表节点的回调方法，此处为空方法
afterNodeInsertion(evict);
// 此处返回 null 是因为链表新增了节点，所以上一次的值必然为 null
return null;
}
putVal() 方法的关键点：
若 table 没有初始化则调用 reszie() 方法初始化。
计算命中的散列表索引位置，公式为 (n – 1) & hash（等价于 hash%n）。其中 n 为散列表长度，hash 为插入的键值对的 key 的哈希值。
判断散列表对应索引中的首节点是否为 null，若为 null，则创建链表，否则进入下一步。
判断该首节点是否与插入的键值对的 key 和 hash 一致，若一致则替换该节点的值为 value，否则进入下一步
判断首节点是否为树节点，若是则调用树节点的 putTreeVal() 方法遍历红黑树，否则遍历链表。
遍历红黑树时，若存在 key 和 hash 相同的节点就替换对应节点的值 value，若不存在则插入新的树节点。
遍历链表时，若存在 key 和 hash 相同的节点就替换对应节点的值为 value。若找不到 key 和 hash 相同的节点，则链表尾部插入节点，同时进入下一步。
若当前链表长度大于或等于树化阈值 TREEIFY_THRESHOLD(8) 时，则将链表转化为红黑树。
get() 方法源码分析
除了 HashMap 的 put() 方法外，get() 方法也是一个我们常用的方法，下面开始分析其关键的源码。
get() 方法
/**
* 返回 key 对应的 value，如果不存在则返回 null
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get() 方法实际上是
调用 hash() 方法获取到 key 的 hash 值
调用 getNode() 方法通过 key 和 hash 获取对应的 value，不存在则返回 null。
核心方法是 getNode() 方法，下面我会先分析一下 getNode() 方法。
getNode() 方法
/**
* Map.get() 方法的实际实现
* @param hash key 的哈希值
* @param key 查询用的 key
* @return 节点或者是节点不存在是返回 null
*/
final Node<K,V> getNode(int hash, Object key) {
//tab 用于暂存散列表 table。first 为散列表中对应索引的链表的头节点的指针。n 存储 tab 的长度。i 则为命中的散列表的索引
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 &&
((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);
}
}
// 不存在对应的 key，返回 null
return null;
}
getNode() 方法的关键点：
若散列表 table 不为 null 且长度大于 0 且其索引为 (n – 1) & hash（等价于 hash%n）的节点不为 null。其中 n 为散列表长度，hash 为插入的键值对的 key 的哈希值。则进入下一步，否则直接返回 null
判断首节点的 key 和 hash 是否与入参一致，若相同则返回首节点，否则进入下一步。
判断节点个数只有 1 个，若是则返回 null，否则进入下一步
判断首节点是否为树节点，若是则遍历红黑树，否则为链表，进入下一步
遍历链表，检索 key 和 hash 与入参相同的节点，若找到则返回该节点，否则返回 null
总结
put() 和 get() 方法是 HashMap 的常用方法，通过学习其源码了解到 HashMap 是如何使用拉链法解决哈希冲突。而下面将会通过两幅图展示 put() 和 get() 的执行过程：
put() 方法图解
get() 方法图解
