并发编程从零开始（九）-ConcurrentSkipListMapSet

并发编程从零开始（九）-ConcurrentSkipListMap&Set CAS知识点补充：

我们都知道在使用 CAS 也就是使用 compareAndSet（current，next）方法进行无锁自加或者更换栈的表头之类的问题时会出现ABA问题。

Java中使用 AtomicStampedReference 来解决 CAS 中的ABA问题，它不再像一般原子类中的 compareAndSet 方法一样只比较内存中的值也当前值是否相等，而且先比较引用是否相等，然后比较值是否相等，此外还会比对版本戳是否和预期的值相等，这样就避免了ABA问题。

常用API：

//构造方法, 传入引用和戳 public AtomicStampedReference(V initialRef, int initialStamp) //返回引用 public V getReference() //返回版本戳 public int getStamp() //如果当前引用 等于 预期值并且 当前版本戳等于预期版本戳, 将更新新的引用和新的版本戳到内存 public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) //使用方法和compareAndSet相同，但是weakCompareAndSet有可能不是原子的去更新值，这取决于虚拟机的实现。 public boolean weekCompareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) //如果当前引用 等于 预期引用, 将更新新的版本戳到内存 public boolean attemptStamp(V expectedReference, int newStamp) //设置当前引用的新引用和版本戳 public void set(V newReference, int newStamp) 5.6 ConcurrentSkipListMap/Set

ConcurrentHashMap 是一种 key 无序的 HashMap，ConcurrentSkipListMap则是 key 有序的，实现了NavigableMap接口，此接口又继承了SortedMap接口。

5.6.1 ConcurrentSkipListMap

1.为什么要使用kipList实现Map？

在Java的util包中，有一个非线程安全的HashMap，也就是TreeMap，是key有序的，基于红黑树实现。

而在Concurrent包中，提供的key有序的HashMap，也就是ConcurrentSkipListMap，是基于SkipList（跳查表）来实现的。这里为什么不用红黑树，而用跳查表来实现呢？

因为目前计算机领域还未找到一种高效的、作用在树上的、无锁的、增加和删除节点的办法。

那为什么SkipList可以无锁地实现节点的增加、删除呢？这要从无锁链表的实现说起。

2. 无锁链表

在前面讲解AQS时，曾反复用到无锁队列，其实现也是链表。究竟二者的区别在哪呢？

前面讲的无锁队列、栈，都是只在队头、队尾进行CAS操作，通常不会有问题。如果在链表的中间进行插入或删除操作，按照通常的CAS做法，就会出现问题！

关于这个问题，Doug Lea的论文中有清晰的论述，此处引用如下：

操作1：在节点10后面插入节点20。如下图所示，首先把节点20的next指针指向节点30，然后对节点10的next指针执行CAS操作，使其指向节点20即可。

操作2：删除节点10。如下图所示，只需把头节点的next指针，进行CAS操作到节点30即可。

但是，如果两个线程同时操作，一个删除节点10，一个要在节点10后面插入节点20。并且这两个操作都各自是CAS的，此时就会出现问题。如下图所示，删除节点10，会同时把新插入的节点20也删除掉！这个问题超出了CAS的解决范围。

为什么会出现这个问题呢？

究其原因：在删除节点10的时候，实际受到操作的是节点10的前驱，也就是头节点。节点10本身没 有任何变化。故而，再往节点10后插入节点20的线程，并不知道节点10已经被删除了！

针对这个问题，在论文中提出了如下的解决办法，如下图所示，把节点 10 的删除分为两2步：

第一步，把节点10的next指针，mark成删除，即软删除；

第二步，找机会，物理删除。

做标记之后，当线程再往节点10后面插入节点20的时候，便可以先进行判断，节点10是否已经被删 除，从而避免在一个删除的节点10后面插入节点20。这个解决方法有一个关键点:“把节点10的next指针指向节点20（插入操作）”和“判断节点10本身是否已经删除（判断操作），必须是原子的，必须在1 个CAS操作里面完成！

具体的实现有两个办法：

办法一：AtomicMarkableReference

保证每个 next 是 AtomicMarkableReference 类型。但这个办法不够高效，Doug Lea 在ConcurrentSkipListMap的实现中用了另一种办法(即Mark节点方法)。

办法2：Mark节点