[toc]
在java Concurrnet包中，还有另外一个Map，这就是ConcurrentSkipListMap。这是一种采用了跳表的数据结构，也是redis中最常用的数据结构，今天来分析下这个并发容器。
1.类的基本结构及其成员变量
1.1 类的基本结构
ConcurrentSkipListMap也是java并发包下面的重要容器，其类的继承结构如下：
ConcurrentSkipListMap类的基本结构
可以看到，ConcurrentSkipListMap的类的继承结构会比ConcurrentHashMap复杂一些。除了要继承AbstractMap类之外，还需要实现ConcurrentNavigableMap、Cloneable、Serializable等接口。ConcurrentNavigableMap接口是NavigableMap和ConcurrentMap功能的结合体，需要既能够实现线程安全，又能够提供导航搜素子Map视图的功能。
/**
* A scalable concurrent {@link ConcurrentNavigableMap} implementation.
* The map is sorted according to the {@linkplain Comparable natural
* ordering} of its keys, or by a {@link Comparator} provided at map
* creation time, depending on which constructor is used.
*
* <p>This class implements a concurrent variant of <a
* href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a>
* providing expected average <i>log(n)</i> time cost for the
* {@code containsKey}, {@code get}, {@code put} and
* {@code remove} operations and their variants. Insertion, removal,
* update, and access operations safely execute concurrently by
* multiple threads.
*
* <p>Iterators and spliterators are
* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
*
* <p>Ascending key ordered views and their iterators are faster than
* descending ones.
*
* <p>All {@code Map.Entry} pairs returned by methods in this class
* and its views represent snapshots of mappings at the time they were
* produced. They do <em>not</em> support the {@code Entry.setValue}
* method. (Note however that it is possible to change mappings in the
* associated map using {@code put}, {@code putIfAbsent}, or
* {@code replace}, depending on exactly which effect you need.)
*
* <p>Beware that, unlike in most collections, the {@code size}
* method is <em>not</em> a constant-time operation. Because of the
* asynchronous nature of these maps, determining the current number
* of elements requires a traversal of the elements, and so may report
* inaccurate results if this collection is modified during traversal.
* Additionally, the bulk operations {@code putAll}, {@code equals},
* {@code toArray}, {@code containsValue}, and {@code clear} are
* <em>not</em> guaranteed to be performed atomically. For example, an
* iterator operating concurrently with a {@code putAll} operation
* might view only some of the added elements.
*
* <p>This class and its views and iterators implement all of the
* <em>optional</em> methods of the {@link Map} and {@link Iterator}
* interfaces. Like most other concurrent collections, this class does
* <em>not</em> permit the use of {@code null} keys or values because some
* null return values cannot be reliably distinguished from the absence of
* elements.
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @author Doug Lea
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
* @since 1.6
*/
public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
}
在类的开始部分，有大段的注释，其大意为：ConcurrnetSkipListMap是一个可扩展的并发Map的实现。其元素是根据Comparable的自然顺序进行排序的。排序或者由Comparator在创建map的时候提供。这取决于使用的构造函数。
这个类是SkipLists的并发版本实现，提供了平均时间复杂度为log(n)的containsKey、get、put和remove的操作及其变体，插入、访问、删除和更新操作以线程安全的方式在多线程的情况下执行。
Iterators和spliterators是弱一致性的，通过升序进行的迭代操作比降序要快。
所有Map.Entry类中的方法及其视图返回的对表示对Map操作时候的快照。他们不支持 Entry.setValue方法。但是请注意，可以使用put、putIfAbsent、replace更改关联Map中的映射。这取决于你需要的效果。
需要注意的是，与大多数集合操作不同的是，size方法不是一个恒定时间的操作。因为这些map的异步性，确定当前的数字的元素需要遍历所有元素，所以如果该集合在遍历的过程中被修改，则会导致size的结果不准确。
此外，批量操作putAll,equals、toArray、containsValue、clear是不能保证原子性的。例如，与putAll同时进行的迭代操作可能只能看到一些新添加的元素。
这个类及其视图和迭代器实现了Map和linkIterator接口的所有可选的方法，与大多数其他并发集合一样，这个类不允许使用null做为key和value，因为某些null返回值无法可靠的与缺少元素区分开。
这个类也是集合框架成员之一。
另外，在成员变量之前也有一大段注释：
/*
* This class implements a tree-like two-dimensionally linked skip
* list in which the index levels are represented in separate
* nodes from the base nodes holding data. There are two reasons
* for taking this approach instead of the usual array-based
* structure: 1) Array based implementations seem to encounter
* more complexity and overhead 2) We can use cheaper algorithms
* for the heavily-traversed index lists than can be used for the
* base lists. Here's a picture of some of the basics for a
* possible list with 2 levels of index:
*
* Head nodes Index nodes
* +-+ right +-+ +-+
* |2|---------------->| |--------------------->| |->null
* +-+ +-+ +-+
* | down | |
* v v v
* +-+ +-+ +-+ +-+ +-+ +-+
* |1|----------->| |->| |------>| |----------->| |------>| |->null
* +-+ +-+ +-+ +-+ +-+ +-+
* v | | | | |
* Nodes next v v v v v
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
*
* The base lists use a variant of the HM linked ordered set
* algorithm. See Tim Harris, "A pragmatic implementation of
* non-blocking linked lists"
* http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
* Michael "High Performance Dynamic Lock-Free Hash Tables and
* List-Based Sets"
* http://www.research.ibm.com/people/m/michael/pubs.htm. The
* basic idea in these lists is to mark the "next" pointers of
* deleted nodes when deleting to avoid conflicts with concurrent
* insertions, and when traversing to keep track of triples
* (predecessor, node, successor) in order to detect when and how
* to unlink these deleted nodes.
*
* Rather than using mark-bits to mark list deletions (which can
* be slow and space-intensive using AtomicMarkedReference), nodes
* use direct CAS'able next pointers. On deletion, instead of
* marking a pointer, they splice in another node that can be
* thought of as standing for a marked pointer (indicating this by
* using otherwise impossible field values). Using plain nodes
* acts roughly like "boxed" implementations of marked pointers,
* but uses new nodes only when nodes are deleted, not for every
* link. This requires less space and supports faster
* traversal. Even if marked references were better supported by
* JVMs, traversal using this technique might still be faster
* because any search need only read ahead one more node than
* otherwise required (to check for trailing marker) rather than
* unmasking mark bits or whatever on each read.
*
* This approach maintains the essential property needed in the HM
* algorithm of changing the next-pointer of a deleted node so
* that any other CAS of it will fail, but implements the idea by
* changing the pointer to point to a different node, not by
* marking it. While it would be possible to further squeeze
* space by defining marker nodes not to have key/value fields, it
* isn't worth the extra type-testing overhead. The deletion
* markers are rarely encountered during traversal and are
* normally quickly garbage collected. (Note that this technique
* would not work well in systems without garbage collection.)
*
* In addition to using deletion markers, the lists also use
* nullness of value fields to indicate deletion, in a style
* similar to typical lazy-deletion schemes. If a node's value is
* null, then it is considered logically deleted and ignored even
* though it is still reachable. This maintains proper control of
* concurrent replace vs delete operations -- an attempted replace
* must fail if a delete beat it by nulling field, and a delete
* must return the last non-null value held in the field. (Note:
* Null, rather than some special marker, is used for value fields
* here because it just so happens to mesh with the Map API
* requirement that method get returns null if there is no
* mapping, which allows nodes to remain concurrently readable
* even when deleted. Using any other marker value here would be
* messy at best.)
*
* Here's the sequence of events for a deletion of node n with
* predecessor b and successor f, initially:
*
* +------+ +------+ +------+
* ... | b |------>| n |----->| f | ...
* +------+ +------+ +------+
*
* 1. CAS n's value field from non-null to null.
* From this point on, no public operations encountering
* the node consider this mapping to exist. However, other
* ongoing insertions and deletions might still modify
* n's next pointer.
*
* 2. CAS n's next pointer to point to a new marker node.
* From this point on, no other nodes can be appended to n.
* which avoids deletion errors in CAS-based linked lists.
*
* +------+ +------+ +------+ +------+
* ... | b |------>| n |----->|marker|------>| f | ...
* +------+ +------+ +------+ +------+
*
* 3. CAS b's next pointer over both n and its marker.
* From this point on, no new traversals will encounter n,
* and it can eventually be GCed.
* +------+ +------+
* ... | b |----------------------------------->| f | ...
* +------+ +------+
*
* A failure at step 1 leads to simple retry due to a lost race
* with another operation. Steps 2-3 can fail because some other
* thread noticed during a traversal a node with null value and
* helped out by marking and/or unlinking. This helping-out
* ensures that no thread can become stuck waiting for progress of
* the deleting thread. The use of marker nodes slightly
* complicates helping-out code because traversals must track
* consistent reads of up to four nodes (b, n, marker, f), not
* just (b, n, f), although the next field of a marker is
* immutable, and once a next field is CAS'ed to point to a
* marker, it never again changes, so this requires less care.
*
* Skip lists add indexing to this scheme, so that the base-level
* traversals start close to the locations being found, inserted
* or deleted -- usually base level traversals only traverse a few
* nodes. This doesn't change the basic algorithm except for the
* need to make sure base traversals start at predecessors (here,
* b) that are not (structurally) deleted, otherwise retrying
* after processing the deletion.
*
* Index levels are maintained as lists with volatile next fields,
* using CAS to link and unlink. Races are allowed in index-list
* operations that can (rarely) fail to link in a new index node
* or delete one. (We can't do this of course for data nodes.)
* However, even when this happens, the index lists remain sorted,
* so correctly serve as indices. This can impact performance,
* but since skip lists are probabilistic anyway, the net result
* is that under contention, the effective "p" value may be lower
* than its nominal value. And race windows are kept small enough
* that in practice these failures are rare, even under a lot of
* contention.
*
* The fact that retries (for both base and index lists) are
* relatively cheap due to indexing allows some minor
* simplifications of retry logic. Traversal restarts are
* performed after most "helping-out" CASes. This isn't always
* strictly necessary, but the implicit backoffs tend to help
* reduce other downstream failed CAS's enough to outweigh restart
* cost. This worsens the worst case, but seems to improve even
* highly contended cases.
*
* Unlike most skip-list implementations, index insertion and
* deletion here require a separate traversal pass occurring after
* the base-level action, to add or remove index nodes. This adds
* to single-threaded overhead, but improves contended
* multithreaded performance by narrowing interference windows,
* and allows deletion to ensure that all index nodes will be made
* unreachable upon return from a public remove operation, thus
* avoiding unwanted garbage retention. This is more important
* here than in some other data structures because we cannot null
* out node fields referencing user keys since they might still be
* read by other ongoing traversals.
*
* Indexing uses skip list parameters that maintain good search
* performance while using sparser-than-usual indices: The
* hardwired parameters k=1, p=0.5 (see method doPut) mean
* that about one-quarter of the nodes have indices. Of those that
* do, half have one level, a quarter have two, and so on (see
* Pugh's Skip List Cookbook, sec 3.4). The expected total space
* requirement for a map is slightly less than for the current
* implementation of java.util.TreeMap.
*
* Changing the level of the index (i.e, the height of the
* tree-like structure) also uses CAS. The head index has initial
* level/height of one. Creation of an index with height greater
* than the current level adds a level to the head index by
* CAS'ing on a new top-most head. To maintain good performance
* after a lot of removals, deletion methods heuristically try to
* reduce the height if the topmost levels appear to be empty.
* This may encounter races in which it possible (but rare) to
* reduce and "lose" a level just as it is about to contain an
* index (that will then never be encountered). This does no
* structural harm, and in practice appears to be a better option
* than allowing unrestrained growth of levels.
*
* The code for all this is more verbose than you'd like. Most
* operations entail locating an element (or position to insert an
* element). The code to do this can't be nicely factored out
* because subsequent uses require a snapshot of predecessor
* and/or successor and/or value fields which can't be returned
* all at once, at least not without creating yet another object
* to hold them -- creating such little objects is an especially
* bad idea for basic internal search operations because it adds
* to GC overhead. (This is one of the few times I've wished Java
* had macros.) Instead, some traversal code is interleaved within
* insertion and removal operations. The control logic to handle
* all the retry conditions is sometimes twisty. Most search is
* broken into 2 parts. findPredecessor() searches index nodes
* only, returning a base-level predecessor of the key. findNode()
* finishes out the base-level search. Even with this factoring,
* there is a fair amount of near-duplication of code to handle
* variants.
*
* To produce random values without interference across threads,
* we use within-JDK thread local random support (via the
* "secondary seed", to avoid interference with user-level
* ThreadLocalRandom.)
*
* A previous version of this class wrapped non-comparable keys
* with their comparators to emulate Comparables when using
* comparators vs Comparables. However, JVMs now appear to better
* handle infusing comparator-vs-comparable choice into search
* loops. Static method cpr(comparator, x, y) is used for all
* comparisons, which works well as long as the comparator
* argument is set up outside of loops (thus sometimes passed as
* an argument to internal methods) to avoid field re-reads.
*
* For explanation of algorithms sharing at least a couple of
* features with this one, see Mikhail Fomitchev's thesis
* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
* (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
* thesis (http://www.cs.chalmers.se/~phs/).
*
* Given the use of tree-like index nodes, you might wonder why
* this doesn't use some kind of search tree instead, which would
* support somewhat faster search operations. The reason is that
* there are no known efficient lock-free insertion and deletion
* algorithms for search trees. The immutability of the "down"
* links of index nodes (as opposed to mutable "left" fields in
* true trees) makes this tractable using only CAS operations.
*
* Notation guide for local variables
* Node: b, n, f for predecessor, node, successor
* Index: q, r, d for index node, right, down.
* t for another index node
* Head: h
* Levels: j
* Keys: k, key
* Values: v, value
* Comparisons: c
*/
我们来查看其大意：
ConcurrentSkipListMap实现了一个类似于树的二位链接跳表，其中索引级别在与保存数据的基础节点不同的节点中表示。采用这种方法而不是通常基于数组的结构有两个原因：1.基于数组的实现会遇到更加复杂的开销。2.对于频繁遍历索引的列表，我们可以使用比基本列表开销更低的算法。下面是一张包含两个级别索引的可能的一些基本要素的图片：
* Head nodes Index nodes
* +-+ right +-+ +-+
* |2|---------------->| |--------------------->| |->null
* +-+ +-+ +-+
* | down | |
* v v v
* +-+ +-+ +-+ +-+ +-+ +-+
* |1|----------->| |->| |------>| |----------->| |------>| |->null
* +-+ +-+ +-+ +-+ +-+ +-+
* v | | | | |
* Nodes next v v v v v
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
*
基本的列表使用HM链接有序集算法的变体。非链接列表的实现，http://www.cl.cam.ac.uk/~tlh20/publications.html 以及Maged Michael的高性能动态无锁哈希表和基于列表的集合http://www.research.ibm.com/people/m/michael/pubs.htm。这些列表的基本思想是标记删除时删除节点以避免与并发冲突插入，并在遍历时跟踪三元组，前置、节点、后继以便检测时间和方式取消这些已删除的节点链接。
不使用标记位来标记列表删除，使用AtomicMarkedReference可能会很慢并且占用大量的空间，节点使用直接可解析的next指针。删除的时候，他们不会标记指针，而是拼接到另外一个指针中，该节点可以认为代表标记的指针，通过使用其他不可能的字段值来表示这一点。使用普通节点的行为大致类似于标记指针的装箱实现，但是仅在删除节点的时候才使用新节点，而不是针对每个链接。 这样就实现了利用更少的空间来支持更快的遍历，即使jvm更好的支持标记引用，使用这种技术遍历仍然可能更快，因为任何搜素只需要比其他需要的节点多读一个节点，以检查尾随标记，而不是每次读取的时候取消标记位或者其他内容。
该方法保留了HM算法中所需的基本属性，即改变删除节点的下一个指针，从而使得该节点的CAS以及其他操作失效。但是通过改变指针指向另外一个节点而不是通过标记来实现的。虽然可以通过定义标记节点不具有的key/value字段进一步压缩空间，但是这种额外的开销是不值得的。在遍历期间很少遇到删除标记，因为通常很快会被GC回收。请注意，这种技术在没用GC的系统中不会很好的工作。
除了使用删除标记之外，列表还使用值字段的空值来指示删除，其风格类似于典型的延迟删除方案。如果一个节点值为空，那么它将认为是逻辑删除并被忽略。即使它任然是可以访问的。这可以保持对并发replace和delete操作的正确控制，如果delete通过清空字段来击败他，则尝试的replace必须失败，而delete必须返回字段中保存的最后一个非null值。注意，这里的值字段使用NULL，而不是一些特殊的标记，因为它正好符合Map API的要求，即使如果没有映射，get方法将返回Null，这使得节点即使正在删除时也能保持并发的可读性，在这里使用其他任何的标记值都会导致混乱。
下面是删除节点n的事件序列：
* +------+ +------+ +------+
* ... | b |------>| n |----->| f | ...
* +------+ +------+ +------+
1.CAS n的value从非空变成null，从这个点开始，遇到该节点的任何公共操作都不会认为该节点的映射存在，但是，其他正在进行插入和删除的操作可能仍然会修改n的下一个指针。
2.CAS n的下一个指针指向一个新的标记节点，从现在起，不能再向n中添加其他节点，避免基于case的链表中的删除错误。
* +------+ +------+ +------+ +------+
* ... | b |------>| n |----->|marker|------>| f | ...
* +------+ +------+ +------+ +------+
*
3.CAS b的下一个指针在n和它的标记上。从此时起，没有新的遍历会遇到n。它最终可以被GC回收。
* +------+ +------+
* ... | b |----------------------------------->| f | ...
* +------+ +------+
*
如果步骤1中失败将导致重试，因为与另外一个操作的竞争中失败了。步骤2-3可能会失败，因为其他线程在遍历具有空值节点的时候会注意到，并通过标记和/或取消链接来帮助完成。这种帮助将可以确保没有线程在等待删除线程的进程中被卡住。标记节点使得帮助代码复杂化了，因为遍历必须跟踪多达4个节点，（b、n、marker、f）的一致读取，而不仅仅是（b、n、f）尽管标记的下一个字段是不可变的，并且一旦下一个字段指向一个标记，它就再也不会改变了，所以这需要更少的关注。
跳表将索引添加到该方案中，以便基本遍历开始于查找，插入或者删除附近，通常基本级别的遍历只遍历几个节点。这不会改变基本算法，除非确实要确保基本的遍历没有从结构上删除前置任务，（这里是b）开始，否则在处理删除后进行重试。
索引级别被维护在变量next字段中，使用CAS进行链接和取消链接。在索引列表操作中允许竞争。这些操作可能无法链接到索引节点或者索引删除节点。我们当然不能对数据节点进行这个操作。但是，即使发生这种情况，索引列表仍然保持排序，因此可以正确的充当索引。这可能会影响性能。因为跳过列表是一个概率性的行为，最终结果是在竞争情况下，有效的p值可能低于其所标的值。而竞争会被控制在足够小的范围内，在实践中这些失败是很少见的，即使在很多争论中也如此。
事实上，对于基本列表和索引列表而言，重试操作开销相对较低，这一事实允许对重试逻辑进行一些小的简化。遍历重新启动是大多数帮助案例之后执行的。这并不是绝对必要的。但是隐含的退避操作有助于减少其下游失败的cas，这些失败的cas操作足以超过重启成本。这使得在最坏的情况下更加恶化，但是似乎改善了高度竞争的情况。
与大多数跳表的实现不同，这里索引插入和删除需要在基本级别的操作之后进行单独的遍历，以添加和删除节点，这增加了单线程的开销，但通过缩小干扰窗口提高了多线程锁竞争的性能。并允许删除以确保从公共删除操作中返回时所有的索引节点都无法干扰，从而避免不必要的垃圾保留。因为在其他节点中，用户引用数据能比其他节点遍历更重要。
索引使用的跳表的参数，这些参数在使用比通常稀疏的索引的时候保持良好的搜素性能。硬连接参数k=1,p=0.5,参见doPut方法。意味着大约四分之一的节点有索引。其中一半有一个等级，四分之一有两个等级，以此类推，映射的预期总空间低于当前实现前的java.util.TreeMap。
更改索引的级别，即树状结构的高度也使用CAS操作。头部索引的初始级别高度为1，创建一个高度大于当前级别的索引的时候，通过在新的最顶端添加一个级别，从而为头部索引添加一个级别。为了多次删除之后保持良好的性能，删除方法会尝试在最高层显示为空时降低高度，这可能会遇到这样的情况，在一个等级即将包含一个索引的时候，它可能但很少见降低并失去一个等级，这样永远不会遇到，这样不会造成结构性损害，而且在实践中，似乎一个比水平无限制增长的更好的选择。
所有这一切的代码比你想象的要冗长，大多数数据操作都需要定位到元素或者插入元素的位置。执行此操作的代码不能很好的分解出来。因为后续的使用需要前置或者后继项和/或值字段的快照。这些字段不能一次性都返回，至少在不创建另外一个对象来保存他们的情况下，创建这样的小对象对基本的内部搜素来说是一个特别糟糕的主意，因为它增加了GC的开销。这是我为数不多的几次希望java有宏，相反，一些遍历代码被交错在其中插入或者移除操作。处理所有重试条件的控制逻辑有时是曲折的，大多数搜素分为两部分。findPreProcessor()只搜素索引节点,返回key的基本前置节点。findNode()完成基本搜素。即使这种因子分解，也有相当数量的代码接近重复来处理变量。
为了在产生随机值的时候排除线程的干扰，我们在JDK线程中使用本地随机支持，通过辅助种子，以避免干扰用户级别的ThreadLocalRandom。
这个类的前一个版本将不可比较的key与其比较器包装在一起，以便使用comparators和comparable的时候模拟可比项。然而，jvm现在似乎能更好的处理将comparator与comparable注入搜索循环中的问题。静态方法cpr(comparator,x,y)用于所有比较，只要comparator参数设置在循环外部，因此有时做为参数传递给内部方法即可正常工作。以避免字段的重复。
对于算法的解释，至少这几个算法共享几个特性，请参阅 Mikhail Fomitchev的论文http://www.cs.yorku.ca/~mikhail/，Keir Fraser的论文http://www.cl.cam.ac.uk/users/kaf24/以及Hakan Sundell的论文http://www.cs.chalmers.se/~phs/。
考虑到使用类似树的索引节点，你可能想知道为什么不使用某种类型的搜索树，这样可以支持更快的搜索操作。原因是没有已知的有效搜索树无锁插入和删除算法。索引节点向下链接的不变性，与真实树中可变的左字段相反，使得仅使用cas操作就可以处理这个问题。
局部变量指南：
| 类型 | 变量 | 说明 |
|---|---|---|
| Node | b, n, f | 前置、当前节点和后继节点 |
| Index | q, r, d，t | 索引节点、右节点、下层节点，另外一个节点 |
| Head | h | |
| Keys | k,keys | |
| Values | v,value | |
| Comparisons | c |
1.2 成员变量及常量
ConcurrentSkipListMap提供的变量如下：
private static final long serialVersionUID = -8627078645895051609L;
/**
* Special value used to identify base-level header
*/
private static final Object BASE_HEADER = new Object();
/**
* The topmost head index of the skiplist.
*/
private transient volatile HeadIndex<K,V> head;
/**
* The comparator used to maintain order in this map, or null if
* using natural ordering. (Non-private to simplify access in
* nested classes.)
* @serial
*/
final Comparator<? super K> comparator;
/** Lazily initialized key set */
private transient KeySet<K> keySet;
/** Lazily initialized entry set */
private transient EntrySet<K,V> entrySet;
/** Lazily initialized values collection */
private transient Values<V> values;
/** Lazily initialized descending key set */
private transient ConcurrentNavigableMap<K,V> descendingMap;
| 变量/常量 | 类型 | 说明 |
|---|---|---|
| BASE_HEADER | static final Object | 用于标识head的特殊值 |
| head | transient volatile HeadIndex<K,V> | SkipList最顶端的索引 |
| comparator | final Comparator<? super K> | 比较器，用于进行排序 |
| keySet | private transient KeySet<K> | 懒加载的key视图类集合 |
| entrySet | private transient EntrySet<K,V> | 懒加载的entry视图集合 |
| values | private transient Values<V> | 懒加载的value集合 |
| descendingMap | private transient ConcurrentNavigableMap<K,V> | 懒加载的降序集 |
可以看到，在这个类中，实际上只有一个head索引，指向整个SkipList，而整个ConcurrentSkipListMap实际上是通过链表指针组织起来的一种特殊的数据格式。
1.3 构造函数
ConcurrentSkipListMap与ConcurrentHashMap不一样的是，只提供了少数几种构造函数，无法像ConcurrentHashMap那样可以指定一系列参数。实际上ConcurrentSkipList本身也没有这些参数。
1.3.1 ConcurrentSkipListMap()
首先是无参构造函数：
/**
* Constructs a new, empty map, sorted according to the
* {@linkplain Comparable natural ordering} of the keys.
*/
public ConcurrentSkipListMap() {
this.comparator = null;
initialize();
}
调用的是initialize方法：
/**
* Initializes or resets state. Needed by constructors, clone,
* clear, readObject. and ConcurrentSkipListSet.clone.
* (Note that comparator must be separately initialized.)
*/
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);
}
可以看到在initialize方法中，实际上初了new了一个HeadIndex节点之外，没有任何其他的操作，这个HeadIndex的level为1。
1.3.2 ConcurrentSkipListMap(Comparator<? super K> comparator)
指定比较器的构造函数：
/**
* Constructs a new, empty map, sorted according to the specified
* comparator.
*
* @param comparator the comparator that will be used to order this map.
* If {@code null}, the {@linkplain Comparable natural
* ordering} of the keys will be used.
*/
public ConcurrentSkipListMap(Comparator<? super K> comparator) {
this.comparator = comparator;
initialize();
}
实际上唯一的区别就是加入了比较器类。
1.3.3 ConcurrentSkipListMap(Map<? extends K, ? extends V> m)
可以传入一个Map之后重新构造一个ConcurrentSkipListMap。
/**
* Constructs a new map containing the same mappings as the given map,
* sorted according to the {@linkplain Comparable natural ordering} of
* the keys.
*
* @param m the map whose mappings are to be placed in this map
* @throws ClassCastException if the keys in {@code m} are not
* {@link Comparable}, or are not mutually comparable
* @throws NullPointerException if the specified map or any of its keys
* or values are null
*/
public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
this.comparator = null;
initialize();
putAll(m);
}
putAll方法实际上是遍历了执行put操作。
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
此反方法是继承的AbstarctMap中的方法，并没有重新实现。
1.3.4 ConcurrentSkipListMap(SortedMap<K, ? extends V> m)
提供支持sortedMap进行插入：
/**
* Constructs a new map containing the same mappings and using the
* same ordering as the specified sorted map.
*
* @param m the sorted map whose mappings are to be placed in this
* map, and whose comparator is to be used to sort this map
* @throws NullPointerException if the specified sorted map or any of
* its keys or values are null
*/
public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
this.comparator = m.comparator();
initialize();
buildFromSorted(m);
}
由于Map已经是sorted之后的map,在之前putAll方法中实际上是遍历出来之后一个个的put，这样效率比较低。对于已经生成的List，则可以直接构造skipList。
buildFromSorted方法实际上是直接构造SkipList的方法。
private void buildFromSorted(SortedMap<K, ? extends V> map) {
//map不能为null
if (map == null)
throw new NullPointerException();
//定义head索引和basepred节点。
HeadIndex<K,V> h = head;
Node<K,V> basepred = h.node;
// Track the current rightmost node at each level. Uses an
// ArrayList to avoid committing to initial or maximum level.
//在list中定义index
ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
//初始化
// initialize
for (int i = 0; i <= h.level; ++i)
preds.add(null);
Index<K,V> q = h;
//初始化最右边的head节点
for (int i = h.level; i > 0; --i) {
preds.set(i, q);
q = q.down;
}
//定义entry的迭代器
Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
map.entrySet().iterator();
//迭代遍历
while (it.hasNext()) {
//取出next
Map.Entry<? extends K, ? extends V> e = it.next();
//随机数
int rnd = ThreadLocalRandom.current().nextInt();
int j = 0;
//用随机数 将随机数截取之后右移动再和1取模
if ((rnd & 0x80000001) == 0) {
do {
++j;
} while (((rnd >>>= 1) & 1) != 0);
if (j > h.level) j = h.level + 1;
}
//上述部分根据随机数计算level判断节点index的层数
K k = e.getKey();
V v = e.getValue();
//k v不能为null
if (k == null || v == null)
throw new NullPointerException();
//new一个node 并将basepred指向这个节点
Node<K,V> z = new Node<K,V>(k, v, null);
basepred.next = z;
basepred = z;
//根据层数 进行构造
if (j > 0) {
Index<K,V> idx = null;
for (int i = 1; i <= j; ++i) {
idx = new Index<K,V>(z, idx, null);
if (i > h.level)
h = new HeadIndex<K,V>(h.node, h, idx, i);
if (i < preds.size()) {
preds.get(i).right = idx;
preds.set(i, idx);
} else
preds.add(idx);
}
}
}
head = h;
}
可以看出，实际上构造这个SkipList是根据一个随机数来确定的，每个节点是否需要增加index，需要根据随机数计算。
1.4 static代码部分
另外，由于大部分变更节点都采用cas，所以在代码中定义了一个静态代码区：
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);
}
}
}
UNSAFE 是全局使用的cas的类。
valueOffset 在compareAndSet value的时候用到，casValue方法中。
nextOffset同样在ompareAndSet next field的时候使用，casNext方法。
2.内部构成及基本原理
2.1 构成的内部类
ConcurrentSkipListMap内部主要有三种类型，主要是HeadIndex、Index和Node。
2.1.1 Node
Node是最基础的节点，除了携带key、value属性之外，此外还是一个单向链表，通过next节点指向下一个节点。
/**
* Nodes hold keys and values, and are singly linked in sorted
* order, possibly with some intervening marker nodes. The list is
* headed by a dummy node accessible as head.node. The value field
* is declared only as Object because it takes special non-V
* values for marker and header nodes.
*/
static final class Node<K,V> {
final K key;
volatile Object value;
volatile Node<K,V> next;
/**
* Creates a new regular node.
*/
Node(K key, Object value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
/**
* Creates a new marker node. A marker is distinguished by
* having its value field point to itself. Marker nodes also
* have null keys, a fact that is exploited in a few places,
* but this doesn't distinguish markers from the base-level
* header node (head.node), which also has a null key.
*/
Node(Node<K,V> next) {
this.key = null;
this.value = this;
this.next = next;
}
}
另外，Node类还提供了一些列的cas方法，在此不做详细介绍。
2.1.2 Index
Index是SkipList的索引节点。其内部有两个指针，down指向下一层，right指向右边的index。另外还有一个指针node指上面的node节点。
static class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
/**
* Creates index node with given values.
*/
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
/**
* compareAndSet right field
*/
final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
}
/**
* Returns true if the node this indexes has been deleted.
* @return true if indexed node is known to be deleted
*/
final boolean indexesDeletedNode() {
return node.value == null;
}
/**
* Tries to CAS newSucc as successor. To minimize races with
* unlink that may lose this index node, if the node being
* indexed is known to be deleted, it doesn't try to link in.
* @param succ the expected current successor
* @param newSucc the new successor
* @return true if successful
*/
final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
Node<K,V> n = node;
newSucc.right = succ;
return n.value != null && casRight(succ, newSucc);
}
/**
* Tries to CAS right field to skip over apparent successor
* succ. Fails (forcing a retraversal by caller) if this node
* is known to be deleted.
* @param succ the expected current successor
* @return true if successful
*/
final boolean unlink(Index<K,V> succ) {
return node.value != null && casRight(succ, succ.right);
}
// Unsafe mechanics
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);
}
}
}
Index提供了一些列的cas操作。
2.1.3 HeadIndex
headIndex是Index的子类：
headIndex
其内部就增加了一个属性level。这个节点只在头部使用。
/**
* Nodes heading each level keep track of their level.
*/
static final class HeadIndex<K,V> extends Index<K,V> {
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;
}
}
2.2 ConcurrentSkipListMap的基本原理
ConcurrentSkipListMap底层采用SkipList的数据结构。所谓SkipList，实际上有如下特点：
- 由很多层结构组成，level是通过随机产生。
- 每一层都是一个有序链表。默认是升序。也可以创建自定义的Comparator比较器。
- 最底层的链表包含所有元素。
- 如果一个元素出现在level i层中，则他在level i 以下的层也会出现。
- 每个索引节点至少包含两个指针，一个指向同一链表中的下一个元素，一个指向下一层的元素。
那么ConcurrentSkipListMap的存储结构就可以画图如下:
ConcurrentSkipListMap的存储结构
虚线实际上也是强引用，此处为了画图方便，表示node的引用关系。红色表示该节点的该属性性为null。上图表示了一个层高为2的SkipList的存储结构。
3.重要的方法
3.1 get
get方法的代码如下：
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key} compares
* equal to {@code k} according to the map's ordering, then this
* method returns {@code v}; otherwise it returns {@code null}.
* (There can be at most one such mapping.)
*
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
*/
public V get(Object key) {
return doGet(key);
}
实际上执行的是doGet方法：
/**
* Gets value for key. Almost the same as findNode, but returns
* the found value (to avoid retries during re-reads)
*
* @param key the key
* @return the value, or null if absent
*/
private V doGet(Object key) {
//key不能为空
if (key == null)
throw new NullPointerException();
//比较器
Comparator<? super K> cmp = comparator;
//死循环
outer: for (;;) {
//内层循环 next
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
//首先查找next如果为空则重新开始
if (n == null)
break outer;
Node<K,V> f = n.next;
//如果next与n不等 则break
if (n != b.next) // inconsistent read
break;
//如果n的value为null 则是已删除的节点调用delete
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
//如果b的value为null 那么同理删除b
if (b.value == null || v == n) // b is deleted
break;
//cpr方法返回v
if ((c = cpr(cmp, key, n.key)) == 0) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
//重新开始循环
if (c < 0)
break outer;
b = n;
n = f;
}
}
return null;
}
cpr方法实际上采用的是comparator：
/**
* Compares using comparator or natural ordering if null.
* Called only by methods that have performed required type checks.
*/
@SuppressWarnings({"unchecked", "rawtypes"})
static final int cpr(Comparator c, Object x, Object y) {
return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
}
其查找过程如下图绿色箭头所示：
get方法过程
3.2 put
同样主要的逻辑也在doPut中：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with the specified key, or
* {@code null} if there was no mapping for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
return doPut(key, value, false);
}
doPut方法：
/**
* Main insertion method. Adds element if not present, or
* replaces value if present and onlyIfAbsent is false.
* @param key the key
* @param value the value that must be associated with key
* @param onlyIfAbsent if should not insert if already present
* @return the old value, or null if newly inserted
*/
private V doPut(K key, V value, boolean onlyIfAbsent) {
Node<K,V> z; // added node
//key不能为null
if (key == null)
throw new NullPointerException();
//定义比较器
Comparator<? super 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;
//n不等于next 则返回
if (n != b.next) // inconsistent read
break;
//如果v为null触发删除
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
//如果b为null触发删除
if (b.value == null || v == n) // b is deleted
break;
//cpr查找
if ((c = cpr(cmp, key, n.key)) > 0) {
b = n;
n = f;
continue;
}
//c==0 设置值
if (c == 0) {
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
}
//new一个新节点
z = new Node<K,V>(key, value, n);
if (!b.casNext(n, z))
break; // restart if lost race to append to b
break outer;
}
}
//计算这个新节点的随机数
int rnd = ThreadLocalRandom.nextSecondarySeed();
//根据随机数计算level
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 = 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)
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
if (casHead(h, newh)) {
h = newh;
idx = idxs[level = oldLevel];
break;
}
}
}
// 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) {
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;
}
增加过程如下图，下图中绿色节点即为需要增加的节点，那么计算出来假定level为3，则head节点需要增加一层。Node对应的每层的节点都需要增加。
put方法过程
绿色箭头表示新增的指针关系。
3.3 remove
remove提供了几个remove方法，实际上底层都是调用的doRemove方法。
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key for which mapping should be removed
* @return the previous value associated with the specified key, or
* {@code null} if there was no mapping for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
*/
public V remove(Object key) {
return doRemove(key, null);
}
doRemove方法源码如下：
/**
* Main deletion method. Locates node, nulls value, appends a
* deletion marker, unlinks predecessor, removes associated index
* nodes, and possibly reduces head index level.
*
* Index nodes are cleared out simply by calling findPredecessor.
* which unlinks indexes to deleted nodes found along path to key,
* which will include the indexes to this node. This is done
* unconditionally. We can't check beforehand whether there are
* index nodes because it might be the case that some or all
* indexes hadn't been inserted yet for this node during initial
* search for it, and we'd like to ensure lack of garbage
* retention, so must call to be sure.
*
* @param key the key
* @param value if non-null, the value that must be
* associated with key
* @return the node, or null if not found
*/
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;
//n为null则返回
if (n == null)
break outer;
Node<K,V> f = n.next;
//如果不等则返回
if (n != b.next) // inconsistent read
break;
//如果v为null则触发删除
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
//如果b为null则触发删除b
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
if (c > 0) {
b = n;
n = f;
continue;
}
if (value != null && !value.equals(v))
break outer;
if (!n.casValue(v, null))
break;
if (!n.appendMarker(f) || !b.casNext(n, f))
findNode(key); // retry via findNode
else {
findPredecessor(key, cmp); // clean index
if (head.right == null)
tryReduceLevel();
}
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
}
return null;
}
上述过程如下图所示：
remove方法过程
按图中红线进行查找，之后将需要删除的红色节点删除，并按绿色箭头重新连接。
3.4 findPredecessor
在上述所有的方法中，均用到了遍历所需的方法findPredecessor：
/**
* Returns a base-level node with key strictly less than given key,
* or the base-level header if there is no such node. Also
* unlinks indexes to deleted nodes found along the way. Callers
* rely on this side-effect of clearing indices to deleted nodes.
* @param key the key
* @return a predecessor of key
*/
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
//key不能为空
if (key == null)
throw new NullPointerException(); // don't postpone errors
//死循环
for (;;) {
//二级死循环
for (Index<K,V> q = head, r = q.right, d;;) {
//right如果不为空
if (r != null) {
Node<K,V> n = r.node;
K k = n.key;
//如果value为null 则执行unlink
if (n.value == null) {
if (!q.unlink(r))
break; // restart
r = q.right; // reread r
continue;
}
//通过cmp方法比较
if (cpr(cmp, key, k) > 0) {
q = r;
r = r.right;
continue;
}
}
if ((d = q.down) == null)
return q.node;
q = d;
r = d.right;
}
}
}
3.5 size
与ConcurrentHashMap相比，ConcurrentSkipListMap并没有使用一个Counter计数器来进行计数。
public int size() {
long count = 0;
for (Node<K,V> n = findFirst(); n != null; n = n.next) {
if (n.getValidValue() != null)
++count;
}
return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
}
可以从代码中看到，每次计算size都是一个从前到后的遍历操作。直接从head找到Node节点，根据node的next进行遍历。因此在注释中也重点说， 与其他集合不同的是，这个size方法不是恒定时间。随着链表中的数据的增多耗时增长。
4.总结
ConcurrentSkipListMap是Concurrent下的一个支持并发的SkipList结构。这个类中全部都是采用cas的方式实现。没有任何地方使用到synchronized和lock。这是我们在写代码的过程中值得借鉴和学习的地方。
另外ConcurrentSkipListMap的size方法每次都是一个新的遍历，这样会导致时间不是恒定的，可能随着插入的过程这个计算时间会过长。
总的来看，ConcurrentSkipListMap类的过程还是比较简单的，与ConcurrentHashMap相比非常简单。不过redis的skipList结构可能最底层是双向链表。我们将在后续逐步分析这些数据结构。
ConcurrentSkipListMap的存取时间都恒定在log(N)，和并发的线程数无关。也就是说，在数据量一定的情况下，并发的线程越多，就越能体现ConcurrentSkipListMap的优势。
最后需要注意的是，使用随机数的方法ThreadLocalRandom.current().nextInt(); 这也是阿里开发手册所推荐的。
