目录
6、remove / replace / replaceAll / clear
ConcurrentSkipListSet是基于ConcurrentSkipListMap实现的线程安全的NavigableSet接口实现类，与之对应的线程不安全的实现类就是基于TreeMap实现的TreeSet；ConcurrentNavigableMap是基于SkipList跳跃表实现的线程安全的NavigableMap实现类，后者对应的线程不安全的实现类就是基于红黑树实现的TreeMap。本篇博客就详细探讨这两类的实现细节。
一、ConcurrentSkipListSet
ConcurrentSkipListSet的类继承关系如下：
其实现的核心接口NavigableSet的另一个典型实现类就是TreeSet，跟TreeSet基于TreeMap实现一样， ConcurrentSkipListSet的实现基于ConcurrentSkipListMap的，添加和删除元素，元素遍历等都是基于ConcurrentSkipListMap方法的，value固定为Boolean.TRUE，其常用方法实现如下：
-
public ConcurrentSkipListSet() {
-
m =
new ConcurrentSkipListMap<E,Object>();
-
}
-
-
public ConcurrentSkipListSet(Comparator<? super E> comparator) {
-
m =
new ConcurrentSkipListMap<E,Object>(comparator);
-
}
-
-
-
public boolean add(E e) {
-
return m.putIfAbsent(e, Boolean.TRUE) ==
null;
-
}
-
-
public boolean remove(Object o) {
-
return m.remove(o, Boolean.TRUE);
-
}
-
-
public Iterator<E> iterator() {
-
return m.navigableKeySet().iterator();
-
}
-
-
public Iterator<E> descendingIterator() {
-
return m.descendingKeySet().iterator();
-
}
二、ConcurrentSkipListMap
1、定义
ConcurrentSkipListMap的类继承关系如下：
从上图可知，ConcurrentNavigableMap继承自ConcurrentMap和NavigableMap，后者的典型实现类就是TreeMap，纯粹是基于红黑树实现的，可以参考《java8 TreeMap接口实现源码解析》。ConcurrentNavigableMap没有添加新的方法，只是改写了父类接口的方法定义，如下：
这些方法的用途可以参考API，会挑选其中典型的方法研究其实现细节。该类包含的属性如下：
-
//头索引节点
-
private
transient
volatile HeadIndex<K,V> head;
-
-
//比较大小的比较器
-
final Comparator<?
super K> comparator;
-
-
//key视图，下面这些视图都是在请求相关方法时才会创建
-
private
transient KeySet<K> keySet;
-
//键值对视图
-
private
transient EntrySet<K,V> entrySet;
-
//value视图
-
private
transient Values<V> values;
-
//倒序遍历的视图
-
private
transient ConcurrentNavigableMap<K,V> descendingMap;
包含的静态常量如下：
-
//初始化head属性时使用，表示一个空节点
-
private
static
final Object BASE_HEADER =
new Object();
-
-
private
static
final
int EQ =
1;
-
private
static
final
int LT =
2;
-
private
static
final
int GT =
0;
// Actually checked as !LT
包含的静态属性通过static代码块初始化，如下：
2、Node / Index / HeadIndex
这三个都是内部类，其中Node表示一个键值对，其定义如下：
-
static
final
class Node<K,V> {
-
//键值对的key和value
-
final K key;
-
volatile Object value;
-
//链表中的下一个节点
-
volatile Node<K,V> next;
-
-
Node(K key, Object value, Node<K,V> next) {
-
this.key = key;
-
this.value = value;
-
this.next = next;
-
}
-
-
Node(Node<K,V> next) {
-
this.key =
null;
-
this.value =
this;
-
this.next = next;
-
}
-
-
//cas修改value
-
boolean casValue(Object cmp, Object
val) {
-
return UNSAFE.compareAndSwapObject(
this, valueOffset, cmp,
val);
-
}
-
-
//cas修改next
-
boolean casNext(Node<K,V> cmp, Node<K,V>
val) {
-
return UNSAFE.compareAndSwapObject(
this, nextOffset, cmp,
val);
-
}
-
-
boolean isMarker() {
-
return value ==
this;
-
}
-
-
boolean isBaseHeader() {
-
return value == BASE_HEADER;
-
}
-
-
//插入一个value指向自己的节点，next为f的节点
-
//删除某个节点时会将其value置为null，然后调用此方法在该节点后插入一个marker，将该节点从next链表中移除
-
//marker在这里是打一个标识同时保存下一个节点的引用，保证将其从next链表中移除失败，即cas修改前一个节点的next属性失败的情形下该节点可以被正常移除
-
boolean appendMarker(Node<K,V> f) {
-
return casNext(f, new Node<K,V>(f));
-
}
-
-
//在查询或者修改节点时，发现某个节点的value已经是null了，会调用此方法
-
//b是前一个节点，f是next节点
-
void helpDelete(Node<K,V> b, Node<K,V> f) {
-
if (f == next &&
this == b.next) {
-
//再次检查链表关系
-
if (f ==
null || f.value != f)
-
//该节点未插入marker节点，此处重新插入，下次调用时进入else分支
-
casNext(f, new Node<K,V>(f));
-
else
-
//f是一个marker节点
-
//将this和f都从链表中移除
-
b.casNext(
this, f.next);
-
}
-
}
-
-
-
V getValidValue() {
-
Object v = value;
-
if (v ==
this || v == BASE_HEADER)
//value是无效
-
return
null;
-
@SuppressWarnings("unchecked") V vv = (V)v;
-
return vv;
-
}
-
-
-
AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
-
Object v = value;
-
if (v ==
null || v ==
this || v == BASE_HEADER)
//value是无效
-
return
null;
-
@SuppressWarnings("unchecked") V vv = (V)v;
-
return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv);
-
}
-
-
//获取属性偏移量
-
private static
final sun.misc.Unsafe UNSAFE;
-
private static
final long valueOffset;
-
private static
final long nextOffset;
-
-
static {
-
try {
-
UNSAFE = sun.misc.Unsafe.getUnsafe();
-
Class<?> k = Node.
class;
-
valueOffset = UNSAFE.objectFieldOffset
-
(k.getDeclaredField(
"value"));
-
nextOffset = UNSAFE.objectFieldOffset
-
(k.getDeclaredField(
"next"));
-
}
catch (Exception e) {
-
throw new Error(e);
-
}
-
}
-
}
Index是HeadIndex的父类，都表示SkipList中的索引节点，其实现如下：
-
static
class Index<K,V> {
-
//关联的node节点
-
final Node<K,V> node;
-
//down指向的节点的node和当前节点的node是同一个，但是down节点位于下一个层级，层级越往下包含的节点数越多，最底层包含了所有的node节点
-
final Index<K,V> down;
-
//right指向的节点的key大于当前节点，跟当前节点位于同一个层级，沿着right属性构成的链表遍历，node的key值越来越大
-
volatile Index<K,V> right; ，
-
-
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
-
this.node = node;
-
this.down = down;
-
this.right = right;
-
}
-
-
//cas修改right属性
-
final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
-
return UNSAFE.compareAndSwapObject(
this, rightOffset, cmp, val);
-
}
-
-
final boolean indexesDeletedNode() {
-
return node.value ==
null;
-
}
-
-
//将新节点插入到当前节点的rigth链表中，原right节点的前面
-
final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
-
Node<K,V> n = node;
-
newSucc.right = succ;
-
//node的vlue不为空时，将right由succ修改成newSucc
-
return n.value !=
null && casRight(succ, newSucc);
-
}
-
-
//将succ从right链表中移除
-
final boolean unlink(Index<K,V> succ) {
-
//node的vlue不为空时，将right由succ修改成succ.right
-
return node.value !=
null && casRight(succ, succ.right);
-
}
-
-
//获取right属性偏移量
-
private
static
final sun.misc.Unsafe UNSAFE;
-
private
static
final
long rightOffset;
-
static {
-
try {
-
UNSAFE = sun.misc.Unsafe.getUnsafe();
-
Class<?> k = Index.class;
-
rightOffset = UNSAFE.objectFieldOffset
-
(k.getDeclaredField(
"right"));
-
}
catch (Exception e) {
-
throw
new Error(e);
-
}
-
}
-
}
-
-
-
static
final
class HeadIndex<K,V> extends Index<K,V> {
-
//level记录层级
-
final
int level;
-
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right,
int level) {
-
super(node, down, right);
-
this.level = level;
-
}
-
}
3、SkipList 跳跃表
跳跃表是一种改进自链表的数据结构，用于存储有序的数据，通过空间换时间的方法来提高数据检索的速度。 普通的链表或者数组插入和删除的效率都是O(1)，但是查找的效率是O(n)，如果是有序链表或者有序数组，则可以通过二分法快速查找，复杂度是O(logn)。跳跃表在理想情况下是O（logn），最差的情况下是O（n），因为跳跃表“跳跃”的下一个节点是完全随机的。其数据结构如下图：
如图所示，跳跃表是有多个层级的，每个层级都是一个有序的链表，越往上的层级节点数越少，最底层则包含了所有的节点，每一层的节点的起始节点都是head节点。
如图所示，跳跃表的节点有两种，一种是最底层的，层级是0的节点，跟普通链表的节点一样，通过next属性构成链表，就是上面的Node类；一种是索引节点，就是上面的Index类，索引节点包含对Node的引用，除此之外还有两个属性，down属性保存下一层级节点的引用，即图中向下的箭头引用，right属性保存同一层级中比当前节点指向的Node大的的节点，即图中向右的箭头引用，注意通过down属性链接起来的节点其指向的Node都是同一个且这些节点都是在Node节点创建时根据Node节点的层级一起创建的。还有一种特殊的索引节点，图中的head节点，会额外保存当前跳跃表的层级，即HeadIndex类中的level属性，在插入新节点时会判断新节点的层级是否大于当前head节点的层级，如果是，需要相应的增加一个head节点，另外，元素遍历时也是通过左上角的head节点开始遍历的，先往右查找，如果碰到比自己大的节点，则在下一层级继续往右查找，直到找到最底层的节点，再通过next属性遍历，找到匹配的节点。跳跃的实现相比普通链表增加了索引节点，通过索引节点跳过一些中间节点，从而提高查找的效率，这就是所谓的空间换时间了。
注意，跳跃表的层级是取决于所有节点的最大层级的，即如果某个节点的层级大于当前跳跃表的层级，会将当前跳跃表的层级加1，同时创建一个新的head节点，新head节点的right属性指向该节点。而新节点所属的层级是随机的，在插入时通过随机算法确定的，50%的概率是0，25%的概率是1，12.5%的概率是2，层级越高的概率越低。
理解上述逻辑，可以通过如下测试用例Debug：
-
@Test
-
public void test() throws Exception {
-
Random random=
new Random();
-
Map<Integer,Integer> test=
new ConcurrentSkipListMap<>();
-
for(
int i=
0;i<
90;i++){
-
test.put(random.nextInt(
90),
1);
-
}
-
test.put(random.nextInt(
100),
1);
-
test.put(random.nextInt(
100),
1);
-
test.put(random.nextInt(
100),
1);
-
test.put(random.nextInt(
100),
1);
-
for(
int key:test.keySet()){
-
System.out.println(key);
-
}
-
}
在后面的test.put处打断点，然后进入到doPut方法调试，前面插入的90个节点保证跳跃表已经形成了多个层级； 如果想要查看层级非0的节点的插入逻辑，则直接在doPut方法内已经算出随机数的地方打断点。下图是进入doPut方法后，打印的head节点：
从图中可知，通过down属性链接的多个节点指向同一个Node节点。
4、构造方法
-
public ConcurrentSkipListMap() {
-
this.comparator =
null;
-
initialize();
-
}
-
-
public ConcurrentSkipListMap(Comparator<? super K> comparator) {
-
this.comparator = comparator;
-
initialize();
-
}
-
-
public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
-
this.comparator =
null;
-
initialize();
-
//使用父类AbstractMap的实现，遍历m中的键值对，通过put方法添加到当前map中
-
putAll(m);
-
}
-
-
public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
-
this.comparator = m.comparator();
-
initialize();
-
buildFromSorted(m);
-
}
-
-
private void initialize() {
-
keySet =
null;
-
entrySet =
null;
-
values =
null;
-
descendingMap =
null;
-
head =
new HeadIndex<K,V>(
new Node<K,V>(
null, BASE_HEADER,
null),
-
null,
null,
1);
-
}
-
-
//该方法是在构造方法中调用的，不会被并行访问，所以构建跳跃表的过程中没有使用CAS
-
private void buildFromSorted(SortedMap<K, ? extends V> map) {
-
if (map ==
null)
-
throw
new NullPointerException();
-
-
HeadIndex<K,V> h = head;
-
Node<K,V> basepred = h.node;
-
-
ArrayList<Index<K,V>> preds =
new ArrayList<Index<K,V>>();
-
//初始化数组元素的
-
for (
int i =
0; i <= h.level; ++i)
-
preds.
add(
null);
-
-
Index<K,V> q = h;
-
//将每一层的head节点保存到preds中，下面的while循环过程中会把同一层级的最右侧的节点保存到preds中
-
for (
int i = h.level; i >
0; --i) {
-
preds.
set(i, q);
-
q = q.down;
-
}
-
-
Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
-
map.entrySet().iterator();
-
//因为SortedMap中的节点是已经排序好了，所以这里直接构建跳跃表即可，不需要为新节点查找插入位置
-
while (it.hasNext()) {
-
Map.Entry<? extends K, ? extends V> e = it.next();
-
//生成一个随机数
-
int rnd = ThreadLocalRandom.current().nextInt();
-
int j =
0;
-
//计算新节点的层级
-
if ((rnd &
0x80000001) ==
0) {
//如果rnd是一个偶数
-
do {
-
++j;
-
}
while (((rnd >>>=
1) &
1) !=
0);
//将rnd右移1位，即除以2，如果结果是偶数就终止循环，否则继续
-
//如果大于head的level
-
if (j > h.level) j = h.level +
1;
-
}
-
K k = e.getKey();
-
V v = e.getValue();
-
if (k ==
null || v ==
null)
-
throw
new NullPointerException();
-
Node<K,V> z =
new Node<K,V>(k, v,
null);
-
basepred.next = z;
-
basepred = z;
-
if (j >
0) {
-
Index<K,V> idx =
null;
-
//从层级1开始往上逐一处理
-
for (
int i =
1; i <= j; ++i) {
-
idx =
new Index<K,V>(z, idx,
null);
-
if (i > h.level)
-
//创建一个新的head节点
-
h =
new HeadIndex<K,V>(h.node, h, idx, i);
-
-
if (i < preds.size()) {
-
preds.
get(i).right = idx;
//index作为上一个节点的right节点
-
preds.
set(i, idx);
//更新i，即当前节点是这一层级中的最右边的节点
-
}
else
-
//i>h.level的情形
-
preds.
add(idx);
-
}
-
}
-
}
-
//更新head
-
head = h;
-
}
5、put / putIfAbsent
上述两个方法的实现都是doPut方法，该方法的实现整体上可以分为两步，第一步是从最高层级的head索引节点开始往右查找，如果碰到一个比自己大的节点，则进入下一个层级继续往右查找，直到该节点是最底层的索引节点了为止，再根据该索引节点指向的链表节点，通过next属性往后遍历找到一个合适的位置，当前节点大于前面的节点小于后面的节点，然后插入到next链表中。第二步是计算当前节点所属的层级，如果层级不是0，则构建每一层级对应的索引节点，各索引节点通过down属性链接起来且都指向新创建的链表节点，然后从高层级往下遍历，将各索引节点同同一层级的节点建立关联关系，这期间如果新节点的层级高于head节点的层级，需要将当前head节点的层级加1，并创建一个对应的head节点，新的head节点的right属性指向该新节点对应的同一层级的索引节点。
-
public V put(K key, V value) {
-
if (
value ==
null)
-
throw
new NullPointerException();
-
return doPut(key,
value,
false);
-
}
-
-
public V putIfAbsent(K key, V value) {
-
if (
value ==
null)
-
throw
new NullPointerException();
-
return doPut(key,
value,
true);
-
}
-
-
private V doPut(K key, V value, boolean onlyIfAbsent) {
-
Node<K,V> z;
// added node
-
if (key ==
null)
-
throw
new NullPointerException();
-
Comparator<? super K> cmp = comparator;
-
//在next链表中找到合适的位置，将新节点插入进去
-
outer:
for (;;) {
-
//findPredecessor方法返回当前Map中小于key的最大的一个索引节点所指向的节点，且该索引节点位于最底层了，然后遍历通过next属性构成的链表
-
//直到找到一个大于key的节点，即下面c小于0的情形，将新节点插入到该节点的前面
-
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)
//next节点变了，终止内层for循环，通过外层的for循环重新获取b和n
-
break;
-
if ((v = n.
value) ==
null) {
//n被删除了
-
n.helpDelete(b, f);
-
break;
-
}
-
if (b.
value ==
null || v == n)
//b被删除了，下一次findPredecessor会将b从链表中移除
-
break;
-
if ((c = cpr(cmp, key, n.key)) >
0) {
//如果key大于n.key,继续遍历通过next属性构成的链表中的下一个节点
-
b = n;
-
n = f;
-
continue;
-
}
-
if (c ==
0) {
-
//如果找到key相等的节点，
-
if (onlyIfAbsent || n.casValue(v,
value)) {
-
//onlyIfAbsent为true表示不需要修改，为false则修改value，返回原来的value
-
@SuppressWarnings(
"unchecked") V vv = (V)v;
-
return vv;
-
}
-
break;
//如果cas修改失败，则继续for循环尝试修改，直到修改成功为止
-
}
-
//c小于0会进入下面的new Node
-
}
-
//如果n为null或者c小于0，c小于0时，b.key < key <n.key
-
//创建一个新节点，插入到b和n的中间
-
z =
new Node<K,V>(key,
value, n);
-
if (!b.casNext(n, z))
-
break;
//如果修改失败则重试
-
break outer;
//终止外层的for循环
-
}
//内层for循环
-
}
//外层for循环
-
-
int rnd = ThreadLocalRandom.nextSecondarySeed();
-
if ((rnd &
0x80000001) ==
0) {
//如果是偶数
-
//level表示新节点的层级，从1开始增加，0表示最底层的一个层架
-
int level =
1, max;
-
while (((rnd >>>=
1) &
1) !=
0)
//将rnd除以2以后，如果是奇数level加1
-
++level;
-
//idx表示当前节点通过down属性构成的一个链表，所有节点都指向新节点z
-
Index<K,V> idx =
null;
-
HeadIndex<K,V> h = head;
-
if (level <= (max = h.level)) {
//如果level小于head的level，则创建一个通过down属性构成的Index链表
-
for (
int i =
1; i <= level; ++i)
-
//idx是作为新节点的down节点的
-
idx =
new Index<K,V>(z, idx,
null);
-
}
-
else {
//如果level大于head的level，需要增加head节点的层级
-
level = max +
1;
//比head大的话，只能在原来的基础上加1
-
//创建一个Index数组
-
@SuppressWarnings(
"unchecked")Index<K,V>[] idxs =
-
(Index<K,V>[])
new Index<?,?>[level+
1];
//加1是为了加上底层0对应的Index
-
//初始化数组元素
-
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)
//初始状态下level肯定大于oldLevel
-
break;
-
HeadIndex<K,V> newh = h;
-
Node<K,V> oldbase = h.node;
-
//创建新层级对应的head节点，down节点指向原来的head，right节点指向新节点z对应的索引节点
-
//通常oldLevel就比level小1，即只创建一个HeadIndex节课
-
for (
int j = oldLevel+
1; j <= level; ++j)
-
newh =
new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
-
if (casHead(h, newh)) {
//cas修改head，如果修改失败说明其他线程在修改head，则重新for循环读取head
-
h = newh;
//使用最新的head
-
idx = idxs[level = oldLevel];
//此处level等于oldLevel
-
break;
-
}
-
}
-
}
-
//如果新节点z对应的level不是0，则创建对应层级的down链表，如果层级大于head的还需要调整head的层级，创建新的head节点，新层级的head节点的right节点
-
//就指向新节点z
-
// find insertion points and splice in
-
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) {
//r节点是无效的
-
if (!q.unlink(r))
//将r从q的right链表中移除，移除失败重新读取q
-
break;
-
r = q.right;
//获取新的right节点
-
continue;
-
}
-
if (c >
0) {
//key大于n.key，则继续遍历下一个right
-
q = r;
-
r = r.right;
-
continue;
-
}
-
}
-
//如果c小于等于0，即key小于等于n.key,或者r等于null
-
//初始状态j肯定是大于insertionLevel，后面没for循环一次，j减1，j就会等于insertionLevel
-
if (j == insertionLevel) {
-
if (!q.link(r, t))
//将t插入到q的right链表中，插入到r的前面
-
break;
//link失败，重新读取h
-
//link成功
-
if (t.node.
value ==
null) {
//正常不可能为null，极端并发下可能为null，因为此时已经将新节点插入到链表中了，有可能被其他某个线程给删除了
-
findNode(key);
//通过findNode将该节点移除，然后终止外层for循环
-
break splice;
-
}
-
//如果相等了，j和insertionLevel都会减1，后面的for循环中两个都会相等，如果不等则只是j减1
-
if (--insertionLevel ==
0)
//到底层节点了，终止外层for循环
-
break splice;
-
}
-
-
-
if (--j >= insertionLevel
//j肯定大于等于insertionLevel
-
&& j < level)
//如果j大于level，说明未遍历到新节点所在的最高层级，小于level了说明上一个层级的right节点处理好了，需要遍历下一个层级
-
t = t.down;
-
//遍历下一个层级的节点
-
q = q.down;
-
r = q.right;
-
}
//内层for循环
-
}
//外层for循环
-
}
//if结束
-
return
null;
-
}
-
-
//从head节点开始遍历，找到小于key的最大的一个索引节点指向的节点
-
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
-
if (key ==
null)
-
throw
new NullPointerException();
// don't postpone errors
-
for (;;) {
-
//从head开始往后遍历
-
for (Index<K,V> q = head, r = q.right, d;;) {
-
if (r !=
null) {
-
Node<K,V> n = r.node;
-
K k = n.key;
-
if (n.
value ==
null) {
//r节点即将被删除
-
//将r从q的right链表中移除，如果q的node的value为null或者cas失败都会则返回false
-
if (!q.unlink(r))
-
break;
//终止内层for循环，通过外层的for循环重新开始，重新读取head
-
r = q.right;
//如果unlink成功，重新读取r
-
continue;
-
}
-
//n.value不为null
-
if (cpr(cmp, key, k) >
0) {
-
//如果key大于k，继续遍历下一个right
-
q = r;
-
r = r.right;
-
continue;
-
}
-
}
-
//如果key小于k 或者r等于null
-
//如果down节点为null，说明已经到最下面的一层节点了，如果不为null，则继续遍历下一层节点
-
//最简单的一个场景，head只有一个层级，即down为null，right不为null，会沿着right属性构成的链表一直遍历直到遇到一个大于key的节点
-
//此时q就是小于key的最大的一个节点
-
//如果down不为null，则遍历down节点的right，注意down节点和q节点指向的node是同一个，同样的沿着right属性构成的链表一直遍历直到遇到
-
//一个大于key的节点,q就是上一个小于key的最大的节点
-
if ((d = q.down) ==
null)
-
return q.node;
-
//如果down不为null，则继续用down的right节点跟key比
-
q = d;
-
r = d.right;
-
}
-
}
-
}
-
//c不为空null，通过c比较大小，否则强转成Comparable比较
-
static final int cpr(Comparator c, Object x, Object y) {
-
return (c !=
null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
-
}
-
-
private Node<K,V> findNode(Object key) {
-
if (key ==
null)
-
throw
new NullPointerException();
// don't postpone errors
-
Comparator<? super K> cmp = comparator;
-
outer:
for (;;) {
-
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
-
Object v;
int c;
-
if (n ==
null)
//没有匹配的节点，终止外层循环，返回null
-
break outer;
-
Node<K,V> f = n.next;
-
if (n != b.next)
//重新读取b
-
break;
-
if ((v = n.
value) ==
null) {
//n被删除了
-
n.helpDelete(b, f);
-
break;
-
}
-
if (b.
value ==
null || v == n)
//b呗删除了
-
break;
-
if ((c = cpr(cmp, key, n.key)) ==
0)
//找到目标节点
-
return n;
-
if (c <
0)
//没有匹配节点，终止外层循环，返回null
-
break outer;
-
//c大于0，继续遍历下一个节点
-
b = n;
-
n = f;
-
}
-
}
-
return
null;
-
}
-
-
private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
-
return UNSAFE.compareAndSwapObject(
this, headOffset, cmp, val);
-
}
-
6、remove / replace / replaceAll / clear
remove方法的核心实现是doRemove，先按照同样的方式遍历找到目标节点，然后将该节点的value置为null，紧接着在该节点后插入一个空的marker节点，如果成功了则将该节点和之前插入对的marker节点一起从链表中移除，插入marker节点的原因就是为了保证后面的从链表移除的动作可以顺利完成，最后再移除该节点对应的索引节点，将其从同一层级的前一个节点的right链表中移除。 最后两步的移除动作，也可以并行的被其他线程执行，他们判断所引用的Node节点的value为null，会自动执行对应的删除动作，所以删除动作都是CAS实现的。
-
public V remove(Object key) {
-
return doRemove(key,
null);
-
}
-
-
public boolean remove(Object key, Object value) {
-
if (key ==
null)
-
throw
new NullPointerException();
-
return
value !=
null && doRemove(key,
value) !=
null;
-
}
-
-
//将等于key的节点的value替换成指定值，返回替换前的值，相当于put方法
-
public V replace(K key, V value) {
-
if (key ==
null ||
value ==
null)
-
throw
new NullPointerException();
-
for (;;) {
-
Node<K,V> n; Object v;
-
if ((n = findNode(key)) ==
null)
-
return
null;
//如果没有找到目标节点
-
//校验n.value不为空是为了避免该节点被删除了
-
//然后cas修改value
-
if ((v = n.
value) !=
null && n.casValue(v,
value)) {
-
@SuppressWarnings(
"unchecked") V vv = (V)v;
-
return vv;
//返回以前的值
-
}
-
}
-
}
-
-
//要求key和value都相等才替换，返回替换是否成功
-
public boolean replace(K key, V oldValue, V newValue) {
-
if (key ==
null || oldValue ==
null || newValue ==
null)
-
throw
new NullPointerException();
-
for (;;) {
-
Node<K,V> n; Object v;
-
if ((n = findNode(key)) ==
null)
-
return
false;
-
if ((v = n.
value) !=
null) {
-
if (!oldValue.
equals(v))
//如果当前值不是oldValue返回false
-
return
false;
-
if (n.casValue(v, newValue))
//如果cas修改成功，返回true
-
return
true;
-
}
-
}
-
}
-
-
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
-
if (function ==
null)
throw
new NullPointerException();
-
V v;
-
//获取第一个有效节点后，通过next遍历所有的节点
-
for (Node<K,V> n = findFirst(); n !=
null; n = n.next) {
-
while ((v = n.getValidValue()) !=
null) {
//获取有效value
-
V r = function.apply(n.key, v);
-
//返回值为空，抛出异常
-
if (r ==
null)
throw
new NullPointerException();
-
if (n.casValue(v, r))
//cas修改value成功则终止内层while循环，处理下一个节点
-
break;
-
}
-
}
-
}
-
-
//获取第一个有效节点，其实就是head.node.next
-
final Node<K,V> findFirst() {
-
for (Node<K,V> b, n;;) {
-
if ((n = (b = head.node).next) ==
null)
-
return
null;
//如果next为null，返回null
-
if (n.
value !=
null)
-
return n;
-
//如果n.value为null，则删除该节点
-
n.helpDelete(b, n.next);
-
}
-
}
-
-
final V doRemove(Object key, Object value) {
-
if (key ==
null)
-
throw
new NullPointerException();
-
Comparator<? super K> cmp = comparator;
-
outer:
for (;;) {
-
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
-
Object v;
int c;
-
if (n ==
null)
//没有匹配的节点，终止外层for循环，返回null
-
break outer;
-
Node<K,V> f = n.next;
-
if (n != b.next)
//next节点被修改了，重新读取b
-
break;
-
if ((v = n.
value) ==
null) {
//n被删除了
-
n.helpDelete(b, f);
//删除节点n
-
break;
-
}
-
if (b.
value ==
null || v == n)
// b被删除了，重新读取b
-
break;
-
if ((c = cpr(cmp, key, n.key)) <
0)
//key小于n.key，不会有匹配的节点了
-
break outer;
-
if (c >
0) {
//key大于n.key，继续遍历下一个next节点
-
b = n;
-
n = f;
-
continue;
-
}
-
//c等于0
-
if (
value !=
null && !
value.
equals(v))
//value不为空跟当前节点的value不一致，终止外层for循环，返回null
-
break outer;
-
if (!n.casValue(v,
null))
//cas修改失败，内层for循环重试
-
break;
-
//casValue成功，在n和f之间插入一个空节点，如果成功则将b的next节点修改成f
-
if (!n.appendMarker(f) || !b.casNext(n, f))
-
//value已经置为null，其他线程不可能修改n的next属性，此时只有修改b的next属性会失败
-
findNode(key);
//上述操作有一个失败则执行findNode，借此清除节点和关联的索引节点
-
else {
-
//修改成功，通过findPredecessor清理关联的Index节点
-
findPredecessor(key, cmp);
// clean index
-
if (head.right ==
null)
//如果head的right节点为null，则尝试减少层级
-
tryReduceLevel();
-
}
-
@SuppressWarnings(
"unchecked") V vv = (V)v;
-
return vv;
-
}
-
}
-
return
null;
-
}
-
-
public void clear() {
-
for (;;) {
-
Node<K,V> b, n;
-
HeadIndex<K,V> h = head, d = (HeadIndex<K,V>)h.down;
-
if (d !=
null)
-
casHead(h, d);
//修改head，原head的right链表就都被移除了
-
//d为null，遍历到最底层的节点了
-
else
if ((b = h.node) !=
null && (n = b.next) !=
null) {
-
Node<K,V> f = n.next;
// remove values
-
if (n == b.next) {
//b未改变
-
Object v = n.
value;
-
if (v ==
null)
//n被删除了
-
n.helpDelete(b, f);
-
//v不为null，将n的value置为null并插入marker，将b的next由n修改成f
-
else
if (n.casValue(v,
null) && n.appendMarker(f))
-
b.casNext(n, f);
//如果cas成功，则n从链表中移除了，如果失败了，假如此时其他线程在并行的往b后面插入一个节点，则下次遍历到n时通过helpDelete将其从链表中移除
-
}
-
}
-
else
-
break;
-
}
-
}
-
-
private void tryReduceLevel() {
-
HeadIndex<K,V> h = head;
-
HeadIndex<K,V> d;
-
HeadIndex<K,V> e;
-
if (h.level >
3 &&
-
(d = (HeadIndex<K,V>)h.down) !=
null &&
-
(e = (HeadIndex<K,V>)d.down) !=
null &&
-
e.right ==
null &&
-
d.right ==
null &&
-
h.right ==
null &&
//从head往下连续三个层级的right都为null
-
casHead(h, d) &&
//将head从h修改成d
-
h.right !=
null)
// 最后一次检查，如果不为null则恢复
-
casHead(d, h);
// try to backout
-
}
7、get / getOrDefault
其底层实现doGet方法的实现和findNode方法是基本一致的，如下：
-
public V
get(Object key) {
-
return doGet(key);
-
}
-
-
public V getOrDefault(Object key, V defaultValue) {
-
V v;
-
return (v = doGet(key)) ==
null ? defaultValue : v;
-
}
-
-
//doGet方法的实现和findNode方法是基本一致的
-
private V doGet(Object key) {
-
if (key ==
null)
-
throw new NullPointerException();
-
Comparator<?
super K> cmp = comparator;
-
outer:
for (;;) {
-
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
-
Object v; int c;
-
if (n ==
null)
//没有匹配节点
-
break outer;
-
Node<K,V> f = n.next;
-
if (n != b.next)
//重新读取b
-
break;
-
if ((v = n.value) ==
null) {
//n被删除了
-
n.helpDelete(b, f);
-
break;
-
}
-
if (b.value ==
null || v == n)
// b被删除了
-
break;
-
if ((c = cpr(cmp, key, n.key)) ==
0) {
//找到目标节点
-
@SuppressWarnings("unchecked") V vv = (V)v;
-
return vv;
-
}
-
if (c <
0)
-
break outer; 没有匹配节点
-
//c大于0，则遍历下一个next节点
-
b = n;
-
n = f;
-
}
-
}
-
return
null;
-
}
转载：https://blog.csdn.net/qq_31865983/article/details/105586590
查看评论