逐行分析 HashMap 的 put() 方法源码

Image result for hashmap works internally in java

HashMap 是底层结构是数组 + 链表,数组是存放 Node(Entry)的数组 Entry[],链表是 Node 组成的链表,充分利用了 Node 的特性。链表的头结点存放在数组中。

put 方法的大致思路

  1. 调用 hash(key) 方法,根据 key 对象的 hashCode 计算出 kay 的 hash,根据 hash 计算出其在 tab 数组中的 index,将键和值放入 Node(Entry) 中;
  2. 如果 index 位置的 Node 为空,称为没碰撞,直接 Node 放入数组中;
  3. 如果碰撞(index 位置存在 Node),先跟头结点比较,key 不相等时,循环链表比较,如果 key 已经存在,替换 old value,否则将 Node 链接到链表最后。
  4. 如果碰撞导致链表的长度大于等于 7,将链表的结构转换为红黑树。
  5. 如果 bucket 存放的 current capacity(当前容量)超过容量的 load factor(0.75),就 resize,容量扩大为两倍。

源码分析

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
int h;
// 使用 16 位无符号右位移 (>>>) 异或 (^) 混合生成一个 hash,替代 key 的 hashCode,hash 混合 hashCode 的高位和低位,以此来加大低位的随机性,用于减少碰撞。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
* @param onlyIfAbsent 如果为 true,不改变已经存在的 value
* @param evict 如果为 false, 该表处于创建模式。
* @return 先前的值,或者为 null 如果没有
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; // 存放链表头结点的数组,数组的每个元素相当于一个桶,好像这个链表就存放于一个元素的空间中
Node<K,V> p; // 存放于数组 i 处的(头)节点
int n;// 数组 tab 的长度
int i; // 数组 tab 的下标值
// 刚开始 table 是 null 或空的时候,调用 resize() 方法,初始化一个长度为 16 的 tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 用 (n - 1) & hash 计算出插入点在数组的下标。如果插入点为 null,将此节点存放于此。(& 为长运算符,使用在计算 boolean 表达式时,会强制计算 & 两边的算式。此处用作位运算,即将 n-1 及 hash 均转为二进制数,相加,同为 1 则结果为 1,否则为 0,结果始终在 [0,n-1])
//(第 2 个 key 跟第 1 个 key 相同时,必定 hash 值相同,index 也相同)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);// 键值对的 next 为空
// 否则就会发生碰撞
else {
Node<K,V> e; // 相当于一个 temp,一个暂时存放键值对的节点
K k; // 一个 temp,暂时存放 key 的值
// 跟数组头结点 p 比较,如果 key 的 hash 值相等,key 对象也相等。为什么要两者都满足,因为根据不同 key 对象的 hashCode 计算出来的 hash 可能相等,所以还需要通过比较引用 ("==") 或者比较对象 ("equals") 的方式判断。
// 你可能要说那可以直接比较 key 对象就行,因为 key 相同,hash 肯定相同。我们根据 hash 不同(p.hash == hash 为 false),可以判断出不是同一个 key,我们知道符号 "&&" 有短路功能,所以整体为 false,不用每次都去比较 key,提高了效率。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// 我们将数组的头结点 p 赋给 e,用于更改头结点的 value
// 我们可以从下一个 else 中知道,一个桶只能存放 8 个节点,大于八个将转成红黑树存储。根据桶中的 Entry 数,判断 p 的类型是否是 TreeNode 类的实例
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 如果是,使用 putTreeVal 方法插入 Entry
// 碰撞后,满足与桶中的第一个 entry 不等,且此时桶中 Entry 小于等于 8 个
else {
for (int binCount = 0; ; ++binCount) {// 没有条件,通过 break 跳出循环
if ((e = p.next) == null) {// 当 p 后没有节点时满足条件,此时桶中就一个 Entry;或者此时 p 为桶中最后一个 Entry
p.next = newNode(hash, key, value, null);// 新建 Entry 链接上,此时 e 为 null
if (binCount >= TREEIFY_THRESHOLD - 1) //-1 for 1st// 当桶中存放第 8 个元素时,将链表转换成红黑树。
treeifyBin(tab, hash);
break;
}
// 上面的 if 判断是否跟桶中的第一个 Entry 相等,而这个 if 是依次跟桶中的 Entry 比较
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;// 如果此时桶中有多个 Entry, 执行完两个 if 后还没跳出循环,e=p.next, 相当于 p=p.next. 继续循环。这个 else 最重要的一点是要理解 --- 利用 e, 依次比较桶中的 Entry.
}
}
if (e != null) { //existing mapping for key//e 不等于 null 的条件是桶中存在相同的 Entry 提前跳出循环
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//onlyIfAbsent 默认为 false,oldValue 可以为 null
e.value = value;// 替换 value
afterNodeAccess(e);//LinkedHashMap 继承 HashMap, 此方法在 LinkedHashMap 中被重写。在这里没什么用,但是在 LinkedHashMap 中此处调用此方法将节点链接到有序链表的最后.
return oldValue;// 存在相同 Entry 时返回 oldValue. 我原来使用 put 方法时没想到还有返回值,所以还是要看看源码
}
}
//HashMap 继承 Serializable, 当 HashMap 被序列化时,transient 变量不会被序列化
++modCount;//(当前元素的格式)modCout 是 transient 变量
//size 也是 transient 变量,指 Map 中包含的键值对的数量。threshold 默认为 16*0.75
if (++size > threshold)// 如果数组中的 Entry 大于等于 length*0.75
resize();// 调用 resize 方法将 tab 数组扩大为两倍
afterNodeInsertion(evict);//LinkedHashMap 继承 HashMap,此方法在 LinkedHashMap 中被重写.
return null;// 默认返回空
}

测试代码

public static void main(String[] args) {
HashMap<String, String> map = new HashMap<>();
for (int i = 0; i <= 20; i++) {
String key = "key" + i;
String value = "value" + i;
map.put(key, value);
}
for (int i = 10; i <= 20; i++) {
String key = "key" + i;
String value = "value" + i + 1;
map.put(key, value);
}

for (int i = 0; i <= 20; i++) {
String key = "key" + i + 1;
String value = "value" + i + 1;
map.put(key, value);
}
}

参考

DeppWang wechat
个人公众号