基础 / JavaSE
39 分钟 读完 (大约 5903 个字) 0次访问

HashMap的putVal和resize

重要声明：由于本人内功不够，本文未有涉及红黑树如何添加元素，仅用简明思路和方法来了解HashMap的存值过程，备以今后面试等场景。以博客记之，便于后续翻阅，不适深究者

putVal 方法解析

其实HashMap的简单存储过程已经在前面一篇文章演示过了，这里主要是来看一下putVal方法。

首先，先看一下putVal方法的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//resize 扩容 [无参，第一次put，初始化为16]
    if ((p = tab[i = (n - 1) & hash]) == null)
        //创建一个节点，放置在tab的第i个位置上。
        tab[i] = newNode(hash, key, value, null);
    else {//如果不为null，即表示当前数组位置上已经存在了值，发生了Hash冲突。
        Node<K,V> e; K k;
        //p就是冲突的第一个位置。hash值相同，key相同，或者equals。表示key相同。
        //注意：相同的hash可能对应不同的key
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)//树
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//链表[如果不是同一个元素，即hash冲突，但是key不同，并且此时不是树结构，则执行链表结构]
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
                    p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
                    if (binCount >= TREEIFY_THRESHOLD - 1) //  TREEIFY_THRESHOLD - 1 = 7 如果
                        //当链表添加到第9个时，就会触发树型化操作，即将链表转为红黑树。那这里其实可以知道，
                        //链表存在的最长的串就是8个。
                        // 8个节点是一个临界值。
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;//同样，如果存在一样的key，则跳过
                p = e;//相当于p=p.next
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
            //如果指定了onlyIfAbsent为true，则需要oldValue为null，才会进行值的覆盖，即才会存储。(putIfAbsent())
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;//值覆盖
            afterNodeAccess(e);
            return oldValue;//返回oldValue
        }
    }
    ++modCount;//并发操作，fast-fail
    if (++size > threshold)//size+1
        resize();
    afterNodeInsertion(evict);
    return null;
}

咱们来慢慢分析：

1
2
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;//resize 扩容 [无参，第一次put，初始化为16]

这是第一次执行的时候，此时table还是null，可以看到，这里并不是在我们new HashMap就创建了内部数组的，而是采用了懒加载的方式，等到实际使用的时候，才会去创建。既然走到了resize扩容方法，我们先看一下resize扩容方法

resize 方法解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;//null
    int oldCap = (oldTab == null) ? 0 : oldTab.length;//0
    int oldThr = threshold;//0
    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){
            // newCap = oldCap << 1 扩容机制，新的容量是旧容量的2倍，新的阈值也是旧的阈值的两倍
            newThr = oldThr << 1;
        }
    } else if (oldThr > 0){
        newCap = oldThr;//8
    } else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;//16 * 0.75 = 12
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//12
    }
    threshold = newThr;//24
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建一个Node类型的数组。
    table = newTab;//复制给HashMap的table属性
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {//遍历数组
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {//数组的第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;//low
                    Node<K,V> hiHead = null, hiTail = null;//high
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {//如果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;
}

首先我们看第一个判断：

1
2
3
4
5
6
7
8
9
if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY){
        // newCap = oldCap << 1 扩容机制，新的容量是旧容量的2倍，新的阈值也是旧的阈值的两倍
        newThr = oldThr << 1;
    }
}

在第一次是不成立，因为 int oldCap = (oldTab == null) ? 0 : oldTab.length;//0 是为0. 但是当我们第二次进行初始化的时候，就会走到这个判断，首先判断是不是大于最大容量static final int MAXIMUM_CAPACITY = 1 << 30; ,如果是，则将阈值赋为int类型的最大值,即 2的31次方减1. 否则，将新的容量扩容到原来的两倍。左移一位；

1
2
0001 0000 => 16
0010 0000 => 32  16经过左移一位，其实就是在右边补0.

(newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY 这个条件表示，新的容量需要小于最大容量，并且老容量要大于static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16.

即：如果我们第一次使用指定容量的构造方法来实例化对象的话，如果指定的是3，我们知道经过处理，初始化容量是4，此时的阈值是3. 但是下一次扩容时，可以发现当newCap变为8的时候，由于oldCap 不大于默认初始化容量16.则不会将阈值乘2. 即此时阈值还是3. 这样的目的是为了让table的容量更加快的扩容到16.

继续：

1
2
3
else if (oldThr > 0){
    newCap = oldThr;//8
}

表示原来oldThr已经被初始化了，这种情况会出现在，指定了初始化容量的时候。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        //如果初始化容量大于最大容量，则仅初始化为最大容量。
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

可以看到，这里将处理后的初始化容量initialCapaciry赋值给了阈值threshold。而等到put值的时候，此时oldCap为0，但是oldThr大于0.所以会走到这句。

继续：

这里判断执行是，表示oldCap和oldThr的值都不大于0.所以会走到这里。

1
2
3
4
else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;//16
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
}

其实就是初始化时，选用的是无参数的构造方法，当第一次put值的时候就会执行到这。将newCap设置为默认初始化容量16. 然后通过默认初始化容量DEFAULT_INITIAL_CAPACITY和默认初始化负载因子DEFAULT_LOAD_FACTOR计算出newThr，新阈值。

继续：

下面这个判断需要成立的话，即表示前面都没有给这个newThr赋值。

1
2
3
4
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;//16 * 0.75 = 12
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//12
}

存在于两处：

第一：

1
2
3
4
if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
}

这个判断；但是这里直接返回了，不会走到后面，所以这个判断不是为这里准备的。还有一个地方：
第二：

1
2
3
else if (oldThr > 0){
    newCap = oldThr;//8
}

就是这；当初始化时指定了初始化容量，表示oldThr已经复制了，并且newCap也有值了，但是没有计算出新的阈值newThr. 所以这里计算出新的阈值。

继续：

1
threshold = newThr;//24

将新计算出来的阈值，复制给当前对象的threshold属性。

1
2
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建一个Node类型的数组。
table = newTab;//复制给HashMap的table属性

上面这句就是关键的一句了。我们都知道HashMap底层的数据结构是数组+链表+红黑树。这就是创建数组的地方。创建一个长度为newCap，类型为Node的数组。然后将新创建的数组复制给当前对象的table属性。

继续：

下面就是在非第一次扩容（即初始化数组） 的时候需要进行的数组重新排布的过程。由于HashMap是通过数组做成一个一个的桶的，所以外层通过for循环来遍历数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {//遍历数组
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {//数组的第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;//low
                Node<K,V> hiHead = null, hiTail = null;//high
                Node<K,V> next;
                do {
                    next = e.next;
                    if ((e.hash & oldCap) == 0) {//如果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;
                }
            }
        }
    }
}

当遇到为null的位置就跳过；

1
if ((e = oldTab[j]) != null) {//数组的第j个位置不为null

在重新分布位置的时候，存在三种情况：

  • ① 同一个数组下标下，只存在一个元素，即没有发生hash碰撞
  • ② 当前数组下标位置上是链表结构，即链表长度没有超过8，还没有形成红黑树
  • ③ 当前数组下标位置上的结构是红黑树。

第一种：没有发生hash碰撞的

1
2
if (e.next == null)
    newTab[e.hash & (newCap - 1)] = e;//重新分布位置

可以看到这里在重新计算位置。即使用当前节点的hash值与新的容量进行取模。【为什么不用%来取模，后面文章会有，其实就是为什么HashMap的初始化容量一定要是2的n次方】；

我们假设oldCap是16，即newCap是32. 并且假设e.hash为18。

1
2
3
4
5
6
7
8
9
10
11
原来的位置在：
0000 0000 0000 0000 0000 0001 0010
0000 0000 0000 0000 0000 0000 1111
----------------------------------
0000 0000 0000 0000 0000 0000 0020 =>即当数组容量是16的时候，hash值为18的元素在下标为2的位置。
    
新的位置：
0000 0000 0000 0000 0000 0001 0010
0000 0000 0000 0000 0000 0001 1111
----------------------------------
0000 0000 0000 0000 0000 0001 0010 => 即当数组容量扩容到32时，hash值都为18的元素因为放在下标为18的地方。

首先我们先不纠结为什么不是用%来取模，这里可以看到，其实就是重新计算hash值与容量的模。来获取到新的位置。

第二种：产生hash碰撞，此时已经是链表结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
else { // preserve order 保护顺序 [链表]
    Node<K,V> loHead = null, loTail = null;//low
    Node<K,V> hiHead = null, hiTail = null;//high
    Node<K,V> next;
    do {
        next = e.next;
        if ((e.hash & oldCap) == 0) {//如果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;
    }
}

这里由于已经形成了链表，需要重新分布位置，所以需要将原来的一条链拆分为两条链。do…while循环用于遍历链表。分别定义了loHead低位链和hiHead高位链，我们主要来看一下怎么将其区分是高位链的节点还是低位链的节点：

1
if ((e.hash & oldCap) == 0)

这个判断和上面的计算位置相似，但是可以看到，上面计算位置是-1.这里没有减一，即此时oldCap转为二进制其实就是最高位为1，其他为均为0，这样做与&运算，其实就是判断hash值与oldCap最高的1对应的位置是不是1. 如不是1，则计算结果为0，放置在低位链上，如果非0，则放置在高位链上。

1
2
3
4
0000 0000 0000 0000 0000 0000 0001 0010 =>18
0000 0000 0000 0000 0000 0000 0001 0000 =>16
--------------------------------------- => &
0000 0000 0000 0000 0000 0000 0001 0000 => 结果不为0，放置在高位上

通过上面的判断，我们知道如何进行链表拆分了。后面就是把低位链放置在原来对应的位置上，即table[index]，把高位链放置在table[index+oldCap]位置上。

第三种：链表的长度超过了8，已经形成了红黑树

1
2
else if (e instanceof TreeNode)//已经是树型，重新分布，即断树
    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

通过判断，此时的节点已经是TreeNode类型的节点，所以已经是红黑树了，需要执行拆分方法split。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    //虽然此时是树形，但是保持了原有链表的结构，依旧可以遍历
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {// 同样判断是高位还是低位
            //高低位重新组建新的链表
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;//记录low位的节点数
        } else {//低位
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;//记录high位的节点数
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)//如果小于等于6，则进行解树形化
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                //hiHead不为null，表示经过扩容以及重新分布，已经拆出一部分节点到对应的高位了，所以需要重新树形化。
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)//同样，如果拆过来的节点小于等于6个，需要解树形化[树->链表]
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)//同样，如果扩容以及重新分布之后，不是全部拆到了高位，则需要重新树形化。
                hiHead.treeify(tab);
        }
    }
}

这个split方法又是不简单，声明已经说了，这里不讨论红黑树生成的过程，这样这个过程可能稍微简单一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//虽然此时是树形，但是保持了原有链表的结构，依旧可以遍历
for (TreeNode<K,V> e = b, next; e != null; e = next) {
    next = (TreeNode<K,V>)e.next;
    e.next = null;
    if ((e.hash & bit) == 0) {// 同样判断是高位还是低位
        //高低位重新组建新的链表
        if ((e.prev = loTail) == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
        ++lc;//记录low位的节点数
    } else {//低位
        if ((e.prev = hiTail) == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
        ++hc;//记录high位的节点数
    }
}

这里跟前面的链表过程相似，因为TreeNode是Node节点的子类，同时除了维护parent,left,right三个属性外，还维护了prev，即TreeNode维护了一个双向链表【后面由链表转为红黑树的过程可以看到】。而链表是一个单向链表.

通过与前面相似的判断之后，形成了高位链表和低位链表，并且统计了相应的个数。

1
2
3
4
5
6
7
8
9
10
if (loHead != null) {
    if (lc <= UNTREEIFY_THRESHOLD)//如果小于等于6，则进行解树形化
        tab[index] = loHead.untreeify(map);
    else {
        tab[index] = loHead;
        if (hiHead != null) // (else is already treeified)
            //hiHead不为null，表示经过扩容以及重新分布，已经拆出一部分节点到对应的高位了，所以需要重新树形化。
            loHead.treeify(tab);
    }
}

从上面的判断得知，首先判断低位链是不是存在，即如果低位链上没有元素，那其实就是整个红黑树的搬移，不用进行处理低位链了。

  • 如果非null, 并且此时低位链节点的个数小于等于【UNTREEIFY_THRESHOLD】6，需要执行解树形化，即将红黑树转为链表【单向】。并将链表放置在低位上table[index].
  • 如果大于6个并且高位链不为null，即表示原来的一棵红黑树，现在需要拆分：拆分为低位红黑树，高位链表。或者是低位红黑树高位也是红黑树。并且此时由于一份为二，低位节点个数又大于6，需要重新调整红黑树的结构，执行树形化方法【treeify】

而高位和低位上相互对应的：

1
2
3
4
5
6
7
8
9
if (hiHead != null) {
    if (hc <= UNTREEIFY_THRESHOLD)//同样，如果拆过来的节点小于等于6个，需要解树形化[树->链表]
        tab[index + bit] = hiHead.untreeify(map);
    else {
        tab[index + bit] = hiHead;
        if (loHead != null)//同样，如果扩容以及重新分布之后，不是全部拆到了高位，则需要重新树形化。
            hiHead.treeify(tab);
    }
}

如果高位的节点不为空并且节点个数小于等于6，则解树形化，并放置在高位。如果高位节点个数大于6并且低位存在元素，则重新执行treeify方法调整二叉树结构。至于如果实现树形化，此处不再讨论，详情请看文首声明。

至此，我们resize扩容方法就看得差不多了。我们回去putVal方法

回来才发现，看完这么多，putVal方法才走3行。唉 img

继续：抛开扩容的方法

1
2
3
4
5
6
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;//resize 扩容 [无参，第一次put，初始化为16]
if ((p = tab[i = (n - 1) & hash]) == null)
    //创建一个节点，放置在tab的第i个位置上。
    tab[i] = newNode(hash, key, value, null);

我们看第二个if判断，这里的(n - 1) & hash 与元素就不再赘述了，就是计算位置。即当前添加进来的key的hash值所计算得计算需要放置的位置上是否已经有元素了。如果为null，表示没有元素，直接创建一个Node节点放置在位置i上即可。

如果i位置上的元素不为null，即发生了hash碰撞，走else

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
else {//如果不为null，即表示当前数组位置上已经存在了值，发生了Hash冲突。
    Node<K,V> e; K k;
    //p就是冲突的第一个位置。hash值相同，key相同，或者equals。表示key相同。
    //注意：相同的hash可能对应不同的key
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)//树
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {//链表[如果不是同一个元素，即hash冲突，但是key不同，并且此时不是树结构，则执行链表结构]
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
                p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
                if (binCount >= TREEIFY_THRESHOLD - 1) //  TREEIFY_THRESHOLD - 1 = 7 如果
                    //当链表添加到第9个时，就会触发树型化操作，即将链表转为红黑树。那这里其实可以知道，链表存在的最长的串就是8个。
                    // 8个节点是一个临界值。
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                break;//同样，如果存在一样的key，则跳过
            p = e;//相当于p=p.next
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        //onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
        //如果指定了onlyIfAbsent为true，则需要oldValue为null，才会进行值的覆盖，即才会存储。(putIfAbsent())
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;//值覆盖
        afterNodeAccess(e);
        return oldValue;//返回oldValue
    }
}

此时else里面的代码分为三个部分；

第一：位置i的元素的key的hash值与put进行的hash值是一样的，并且key也相等；即下面的条件为true。

1
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

可以判断此时put进来的key是已经存在的，是否覆盖后续再看。

第二：已经不是第一次碰撞了，已经形成了红黑树结构

1
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

已经是树的结构，需要执行putTreeVal方法。此时不做深究。

第三：已经是链表，还未形成树结构

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
        p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
        if (binCount >= TREEIFY_THRESHOLD - 1) //  TREEIFY_THRESHOLD - 1 = 7 如果
            //当链表添加到第9个时，就会触发树型化操作，即将链表转为红黑树。那这里其实可以知道，链表存在的最长的串就是8个。
            // 8个节点是一个临界值。
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
        break;//同样，如果存在一样的key，则跳过
    p = e;//相当于p=p.next
}

if条件if ((e = p.next) == null), 表示循环到最后一个节点，即采用尾插法，【同样，如果途中遇到相同的hash和key，则退出循环，后续处理】。当遍历到最后一个节点，此时链表长度是8，加上newNode，其实是添加第9个元素的时候，触发树形化的。当binCount大于等于7时，会将链表转为红黑树，即执行treeifyBin方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

首先判断tab是否为null，或者此时数组的长度是否大于最小树形化容量【MIN_TREEIFY_CAPACITY = 64;】。否则不会转为树，而是进行扩容。else表示满足条件。do…while循环做的事就是先将原来链表转为TreeNode类型的双向链表。

1
2
3
4
5
6
7
8
9
10
do {
    TreeNode<K,V> p = replacementTreeNode(e, null);
    if (tl == null)
        hd = p;
    else {
        p.prev = tl;
        tl.next = p;
    }
    tl = p;
} while ((e = e.next) != null);

而replacementTreeNode方法就是将Node初始化为TreeNode:

1
2
3
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

通过下面的代码可以知道，这里就是在维护双向链表的前驱和后继。

1
2
p.prev = tl;
tl.next = p;

结束后就是想链表转为树，不做深究。

我们回来看：

1
2
3
4
5
6
7
8
9
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    //onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
    //如果指定了onlyIfAbsent为true，则需要oldValue为null，才会进行值的覆盖，即才会存储。(putIfAbsent())
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;//值覆盖
    afterNodeAccess(e);
    return oldValue;//返回oldValue
}

当我们在遍历的过程中，发现已经存在相同的key了，则需要通过判断来确地是否进行值的覆盖。

最后：

size+1. 并判断是否超过了阈值，否则就进行扩容。 afterNodeInsertion空方法。

1
2
3
4
++modCount;//并发操作，fast-fail
if (++size > threshold)//size+1
    resize();
afterNodeInsertion(evict);

至此，putVal方法就基本看完了

#
HashMap的get，containKey, containsValue方法
初试HashMap的put存储过程

评论

关注我

链接

分类

标签云

JavaSE Redis feign gateway hessian idea mybatis mysql nacos rabbitmq ribbon sentinel spring spring4x springboot 新冠肺炎

最新文章

归档

标签

JavaSE 9
Redis 15
feign 3
gateway 5
hessian 1
idea 1
mybatis 9
mysql 1
nacos 10
rabbitmq 1
ribbon 1
sentinel 7
spring 1
spring4x 11
springboot 14
新冠肺炎 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×