Java HashMap的put方法
程序员文章站
2022-03-10 18:37:38
...
实习半年,基本上在写scala和python。很少碰Java了,趁最近闲,补一波Java集合的东西。这篇主要分析HashMap的插入方法。之后再抽时间看下红黑树。
可能出现的几种插入情况:
1、初次插入。
2、插入与任何结点不产生地址冲突。
3、产生地址冲突,table数组下面结点以单链表形式存在,插入时直接挂在单链表最后。
4、产生地址冲突,key值和之前结点一样。
5、产生地址冲突,table数组下面结点以红黑树形式存在,插入时需要在树中查找合适位置。
下面是对代码的分析:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 如果table为空,表明是第一元素插入,则先resize。初次大小默认16。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果要插入结点的位置是空,也就是没有产生Hash地址冲突,直接放入table。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 如果产生了冲突,那么有两种情况。1、key相同。2、key不同。
Node<K,V> e; K k;
// 要插入的结点key值和table现有位置上的结点的key值相同,则直接赋值e。p为当前位置上的元素,e为需要被修改的元素。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 如果p是TreeNode的实例,说明p下面挂着红黑树,需要在树中找到一个合适的位置e插入。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) { // p下面的结点数未超过8,则以单向链表的形式存在。
if ((e = p.next) == null) { // 逐个往下找到空位置
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st -1 0 1 2 3 4 5 6
treeifyBin(tab, hash); // TREEIFY_THRESHOLD=8,当容量超过8则转化成红黑树
break;
}
// 如果与单向链表上的某个结点key值相同,则跳出循环,此时e是需要修改的结点,p是e的前驱结点。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 如果onlyIfAbsent为True则不改变旧值。如果插入中遇见key一样的结点,则保留第一次插入的结果。
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; // 修改次数++
// 如果插入后大小大于threshold,则出发resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}