putVal=>resize=>putVal=>返回
建议粘贴到工具里方便阅读
/**
* Implements Map.put and related methods
* put方法调用.
* onlyIfAbsent参数用于putIfAbsent方法调用时使用true,表示是否替换
*
* @paramhash后的key值
* @param 原来的key
* @param value值
* @param 如果为true，则不更改现有值（key重复不覆盖原有的值）
* @param 钩子方法，这在HashMap中是个空方法，但是在其子类LinkedHashMap中会被Override
* @return 返回null 或者上一次的值
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/* 第一次 下面用①走标识第一次 */
Node<K, V>[] tab; /* ①走：空 */
Node<K, V> p; /* ①走：空 */
int n, i;/* ①走：0 */
if ((tab = table) == null || (n = tab.length) == 0)/* ①走： */
n = (tab = resize()).length;/* ①走： n=16 ;tab扩容为16 */ // 若当前哈希数组table的长度为0，则进行扩容
if ((p = tab[i = (n - 1) & hash]) == null)// 【(n - 1) & hash】：且运算 确定输入的hash在哈希数组中对应的下标i；
// 注意这是随意的算出来的值可能是3，可能是6但是肯定在0-15之间
// 若数组该位置之前没有被占用，则新建一个节点放入，插入完成。
/* ①走： 存值 */
tab[i] = newNode(hash, key, value, null);
else {// 桶内已经有元素情况
// 走这一步条件如下
/**
* 对应上面第一次举例
* map.put(195,"1");1111&11000011
* map.put(67,"1");1111&1000011
* 就会产生第一个链表
*/
Node<K, V> e;
K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// 放入元素和头元素相同,进行替换
else if (p instanceof TreeNode)// 不相同,则判断是否为TreeNode
/**
* 若该位置的第一个节点p为TreeNode类型，说明这里存放的是一棵红黑树，p为根节点。
* 于是交给putTreeVal方法来完成后续操作，该方法下文会有详述
**/
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
// 走到这里，说明p不匹配且是一个链表的头结点，该遍历链表了
// 链表的情况,这里是先进行循环,在循环的过程中判断出元素超过TREEIFY_THRESHOLD则进行treeifyBin操作
for (int binCount = 0;; ++binCount) {
/** e指向p的下一个节点 **/
if ((e = p.next) == null) {
// 当next是null的时候就是尾部了,这里就是把新放入的元素加到链表尾部的操作
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// treeifyBin操作 转换成tree结构
/**
* 若插入后，该桶中的节点个数已达到了树化阈值
* 则对该桶进行树化。该部分源码下文会有详述
**/
treeifyBin(tab, hash);
break;
}
// 这里判断已经有相同key的元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
/**
* 匹配成功，我们需要用新的value来覆盖e节点
**/
break;
p = e; // 循环继续
}
}
// 若执行到此时e不为空，则说明在map中找到了与key相匹配的节点e
if (e != null) { // existing mapping for key
V oldValue = e.value;// 暂存e节点当前的值为oldValue
// 这里处理onlyIfAbsent,先新建一个node,然后再判断onlyIfAbsent,来决定是否替换原来的元素.
// 注意如果原来的元素的value是会替换掉的!
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 钩子方法 LinkedHashMap使用
afterNodeAccess(e);
return oldValue;
}
}
/**** --执行到此处说明没有匹配到已存在节点，一定是有新节点插入-- ****/
++modCount; // 结构操作数加一
// 触发resize
if (++size > threshold)
resize();// 插入后，map中的节点数加一，若此时已达阈值，则扩容
afterNodeInsertion(evict);// 同样的钩子方法，通知子类有新节点插入
return null;// 同样的钩子方法，通知子类有新节点插入
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
* 初始化或倍增table的长度,因为长度遵守2的幂,所以元素的在resize后的新位置要么在远处要么移动2的幂次位置.
* resize是map核心算法之一,它决定这map在扩容时的性能.如果是一个膨胀速度快的map,对resize的要求就很高了.
*
* @return the table
*/
final Node<K, V>[] resize() {
/* ①走 ： */
Node<K, V>[] oldTab = table;/* ①走 ：空 */
int oldCap = (oldTab == null) ? 0 : oldTab.length;/* ①走：oldCap=0 */
int oldThr = threshold;/* ①走：oldThr =0 */ // map在第一次put值时会初始化化为12
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {// 判断有没有达到最大值
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {// 已第一次（put）举例oldCap << 1 意思：0001左移 0010 ； 就是1=>2
// 就是2任然小于2^30 且 大于2^4（如下）
// 1000=>1 0000: 8=> 16 (塞了16个值正好满足)
newThr = oldThr << 1;// newThr为32
}
} else if (oldThr > 0) { // initial capacity was placed in threshold
newCap = oldThr;
} else { // zero initial threshold signifies using defaults
/* ①走：只会走到这 */
newCap = DEFAULT_INITIAL_CAPACITY;/* ①走：newCap =16 */
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);/* ①走：newThr =12 */
}
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
}
threshold = newThr;/* ①走：threshold=12 */
@SuppressWarnings({ "rawtypes", "unchecked" })
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;/* ①走：table成为长度为16的node */
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
网友评论