replaceNode方法

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/**
    * Implementation for the four public remove/replace methods:
    * Replaces node value with v, conditional upon match of cv if
    * non-null.  If resulting value is null, delete.
    * 删除/替换的操作
    *
    */
   final V replaceNode(Object key, V value, Object cv) {
       //发散hash
       int hash = spread(key.hashCode());
       //迭代表
       for (Node<K,V>[] tab = table;;) {
           Node<K,V> f; int n, i, fh;
           //如果表为空，且键所在节点为空，跳出循环
           if (tab == null || (n = tab.length) == 0 ||
               (f = tabAt(tab, i = (n - 1) & hash)) == null)
               break;
           //如果key所在节点的hash值为MOVED
           else if ((fh = f.hash) == MOVED)
               //如果还在进行扩容操作就先进行扩容
               tab = helpTransfer(tab, f);
           else {
               V oldVal = null;
               //是否检验
               boolean validated = false;
               //锁当前节点
               synchronized (f) {
                   //确认节点
                   if (tabAt(tab, i) == f) {
                       //节点的hash值大于0
                       if (fh >= 0) {
                           //校验
                           validated = true;
                           for (Node<K,V> e = f, pred = null;;) {
                               K ek;
                               //找到键位置
                               if (e.hash == hash &&
                                   ((ek = e.key) == key ||
                                    (ek != null && key.equals(ek)))) {
                                   //老的值
                                   V ev = e.val;
                                   //删除节点
                                   if (cv == null || cv == ev ||
                                       (ev != null && cv.equals(ev))) {
                                       oldVal = ev;
                                       if (value != null)
                                           e.val = value;
                                       else if (pred != null)
                                           pred.next = e.next;
                                       else
                                           setTabAt(tab, i, e.next);
                                   }
                                   break;
                               }
                               pred = e;
                               if ((e = e.next) == null)
                                   break;
                           }
                       }
                       //是树形节点
                       else if (f instanceof TreeBin) {
                           validated = true;
                           TreeBin<K,V> t = (TreeBin<K,V>)f;
                           TreeNode<K,V> r, p;
                           //找到删除的key
                           if ((r = t.root) != null &&
                               (p = r.findTreeNode(hash, key, null)) != null) {
                               V pv = p.val;
                               if (cv == null || cv == pv ||
                                   (pv != null && cv.equals(pv))) {
                                   oldVal = pv;
                                   if (value != null)
                                       p.val = value;
                                   //删除树节点
                                   else if (t.removeTreeNode(p))
                                       setTabAt(tab, i, untreeify(t.first));
                               }
                           }
                       }
                   }
               }
               //检查
               if (validated) {
                   if (oldVal != null) {
                       if (value == null)
                           //数量减一
                           addCount(-1L, -1);
                       return oldVal;
                   }
                   break;
               }
           }
       }
       return null;
   }

此方法通过以下三处实现多线程的并发访问：

  1. 头节点的synchronized锁。
  2. Node节点的volatile Node<K,V> next属性，用了volatile读。
  3. Node节点的volatile V val属性，用了volatile读。

再盗取一张图：
remove.png

如图所示：删除的node节点的next依然指着下一个元素。此时若有一个遍历线程正在遍历这个已经删除的节点，这个遍历线程依然可以通过next属性访问下一个元素。从遍历线程的角度看，他并没有感知到此节点已经删除了，这说明了ConcurrentHashMap提供了弱一致性的迭代器。