per K> cmp = comparator; outer: for (;;) { for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { //查找前继节点 if (n != null) { //查找到前继节点 Object v; int c; Node<K,V> f = n.next; //获取后继节点的后继节点 if (n != b.next) //发生竞争,两次节点获取不一致,并发导致 break; if ((v = n.value) == null) { // 节点已经被删除 n.helpDelete(b, f); break; } if (b.value == null || v == n) break; if ((c = cpr(cmp, key, n.key)) > 0) { //进行下一轮查找,比当前key大 b = n; n = f; continue; } if (c == 0) { //相等时直接cas修改值 if (onlyIfAbsent || n.casValue(v, value)) { @SuppressWarnings("unchecked") V vv = (V)v; return vv; } break; // restart if lost race to replace value } // else c < 0; fall through } z = new Node<K,V>(key, value, n); //9. n.key > key > b.key if (!b.casNext(n, z)) //cas修改值 break; // restart if lost race to append to b break outer; } } int rnd = ThreadLocalRandom.nextSecondarySeed(); //获取随机数 if ((rnd & 0x80000001) == 0) { // test highest and lowest bits int level = 1, max; while (((rnd >>>= 1) & 1) != 0) // 获取跳表层级 ++level; Index<K,V> idx = null; HeadIndex<K,V> h = head; if (level <= (max = h.level)) { //如果获取的调表层级小于等于当前最大层级,则直接添加,并将它们组成一个上下的链表 for (int i = 1; i <= level; ++i) idx = new Index<K,V>(z, idx, null); } else { // try to grow by one level //否则增加一层level,在这里体现为Index<K,V>数组 level = max + 1; // hold in array and later pick the one to use @SuppressWarnings("unchecked")Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1]; for (int i = 1; i <= level; ++i) idxs[i] = idx = new Index<K,V>(z, idx, null); for (;;) { h = head; int oldLevel = h.level; if (level <= oldLevel) // lost race to add level break; HeadIndex<K,V> newh = h; Node<K,V> oldbase = h.node; for (int j = oldLevel+1; j <= level; ++j) //新添加的level层的具体数据 newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); if (casHead(h, newh)) { h = newh; idx = idxs[level = oldLevel]; break; } } } // 逐层插入数据过程 splice: for (int insertionLevel = level;;) { int j = h.level; for (Index<K,V> q = h, r = q.right, t = idx;;) { if (q == null || t == null) break splice; if (r != null) { Node<K,V> n = r.node; // compare before deletion check avoids needing recheck int c = cpr(cmp, key, n.key); if (n.value == null) { if (!q.unlink(r)) break; r = q.right; continue; } if (c > 0) { q = r; r = r.right; continue; } } if (j == insertionLevel) { if (!q.link(r, t)) break; // restart if (t.node.value == null) { findNode(key); break splice; } if (--insertionLevel == 0) break splice; } if (--j >= insertionLevel && j < level) t = t.down; q = q.down; r = q.right; } } } return null; } 这里的插入方法很复杂,可以分为3大步来理解:第一步获取前继节点后通过CAS来插入节点;第二步对level层数进行判断,如果大于最大层数,则插入一层;第三步插入对应层的数据。整个插入过程全部通过CAS自旋的方式保证并发情况下的数据正确性。
总结
JDK中提供了丰富的并发容器供我们使用,文章中介绍的也并不全面,重点是要通过了解各种并发容器的原理,明白他们各自独特的使用场景。这里简单做个总结:当并发读远多于修改的场景下需要使用List和Set时,可以考虑使用CopyOnWriteArrayList和CopyOnWriteArraySet;当需要并发使用<Key, Value>键值对存取数据时,可以使用ConcurrentHashMap;当要保证并发<Key, Value>键值对有序时可以使用ConcurrentSkipListMap。
|