企业官网建设流程全解析

在单线程场景下，HashMap适用于key为无序的键值对存放场景，而TreeMap适用于key为有序的键值对存放场景。

在高并发场景下，ConcurrentHashMap适用于key为无序的键值对存场景，但对于高并发且要求key有序的场景下，TreeMap非线程安全显然无法满足此场景， 在Concurrent包里面只有跳表：ConcurrentSkipListMap可以满足"基于乐观锁高性能的并发读写、key有序"的需求，而且其设计不会像ConcurrentHashMap这么复杂，但确有着恰当的应用场景，例如对于时序流式数据的存放（最近比较热门的物联网大数据引擎TDengine），可以将乱序的记录以时间戳作为key插入到跳表中，跳表内部处理插入时会比较key的hash值大小以找到节点合适的插入位置，那么在读取时跳表返回的记录就是有序了。

jdk1.8的ConcurrentSkipListMap在本文简写为CSM，Dung Lea在源代码开头的注释详细介绍了CSM总体设计思路并给出字符型展示的CSM结构图，如下：

*HeadnodesIndexnodes*+-+right+-++-+*|2|---------------->||--------------------->||->null*+-++-++-+*|down||*v v v*+-++-++-++-++-++-+*|1|----------->||->||------>||----------->||------>||->null*+-++-++-++-++-++-+*v|||||*Nodesnext v v v v v*+-++-++-++-++-++-++-++-++-++-++-++-+*||->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null*+-++-++-++-++-++-++-++-++-++-++-++-+

CSM源代码解析文章说明：由于CSM解析内容较多，因此全文分为“深度讨论高并发跳表数据结构ConcurrentSkipListMap的源代码实现（上）”和“深度讨论高并发跳表数据结构ConcurrentSkipListMap的源代码实现（下）”两篇文章
上篇关注的重点：CSM数据结构设计原理、doGet、doPut核心方法解析
下篇关注的中断：doRemove核心方法解析、总结

CSM的基本用法

importjava.util.ArrayList;importjava.util.Comparator;importjava.util.List;importjava.util.Objects;importjava.util.concurrent.ConcurrentSkipListMap;publicclassSkipListDemo{publicstaticvoidmain(String[]args)throwsInterruptedException{// ConcurrentHashMap<String,Integer> sm= new ConcurrentHashMap<>();ConcurrentSkipListMap<String,Integer>sm=newConcurrentSkipListMap<>();List<Thread>list=newArrayList<>();for(inti=0;i<10;i++){Threadt=newThread(newRunnable(){@Overridepublicvoidrun(){sm.put(Thread.currentThread().getName(),(int)Thread.currentThread().getId());}});list.add(t);}for(Threadthread:list){thread.start();}for(Threadthread:list){thread.join();}System.out.println(sm);}}

使用CHM输出的结果为无序结果：

{Thread-3=12, Thread-4=13, Thread-5=14, Thread-6=15, Thread-7=16, Thread-8=17, Thread-9=18, Thread-0=9, Thread-1=10, Thread-2=11}

使用CSM输出的结果为有序结果：

{Thread-0=9, Thread-1=10, Thread-2=11, Thread-3=12, Thread-4=13, Thread-5=14, Thread-6=15, Thread-7=16, Thread-8=17, Thread-9=18}

CSM 数据结构图

这个跳表结构有四层，其中base-level层是完整的数据节点链表，在base-level层上面的三层都是索引节点构成的索引链，从图中可以直观看到：上层的索引链表是下层索引链表的“快车道”

从这种图也可以总结出跳表（这里是泛指跳表结构不是指Java的CSM）的基本特征：

• 由最底层的完整数据节点链表层+上面的多层索引层组成。
• 每一层都是一个有序的链表
• 如果一个key出现在第n层中，则它在最底层以及1到第n-1层也都会出现

而对于jdk1.8实现的功能完整的ConcurrentSikpListMap，可按上面的结构图进行简单说明各个元素的构成（最底层到最顶层）：

• Node节点：存放数据的节点，只在最底层的数据层链表出现，在插入操作时，可能会被随机算法选中上升为“index索引节点”

• base-level：指代数据层链表的位置，此层存放的是完整数据节点链表，该层的所有节点都是Node类型，不含有Index类型节点！

• BASE_HEADER：这个节点不是数据层链表的第一个数据节点，它是辅助节点，可以看做是数据层链表的“索引节点”，但它是Node类型：new Node<K,V>(null, BASE_HEADER, null)

• Index节点：位于索引层的节点，采用随机算法把它插入在数据层上方的索引层链表上。

• HeadIndex节点：作为辅助节点，非数据节点，是当前索引层链表的头节点，它也会指向下一层index节点索引链表的头节点。Dung Lea称它是dummy node

• level：索引节点所在层序号，从level=1开始计数，最高不超过31（含31层），文章后面给出了计算解释。

• right指针：HeadIndex、Index节点专有字段，可以使得遍历链表的方向向右移动

• down指针：HeadIndex、Index节点专有字段，可以使得遍历链表的方向向下移动

• head节点：所有线程的读写操作都是这个头节点开始作为遍历入口，就像“迷宫的入口点，然后根据向右边还是向下移动，直到走到适合索引节点位置”，它指向最顶层索引层的HeadIndex节点。

• node指针：此指针最特殊！！ 因为每个数据节点，它垂直上方的所有索引节点的node指针都指向数据节点本身，new Index<K,V>(node=新插入的数据节点,down=下一层索引节点, right=当前索引节点的后继索引节点)，注意到上图结构图中，level=1层的索引节点与base-level数据层的数据节点之间不是通过down指针连接的，而是通过node指针连接的，这点务必在后面源码分析反复想起，否则理解错了CSM结构图，那么就无法正确解析源代码设计。

还有marker标记型节点，它在删除节点的时机会被使用。

相关节点的定义：

数据节点：

Node类除了构造器，还定义了一些基本读写方法，具体如下：

/** node是数据节点，内部存放了key和value，node节点能构成有序链表 * 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. */staticfinalclassNode<K,V>{finalKkey;// 注意final修饰volatileObjectvalue;// 注意volatile修饰，因为cas会操作它volatileNode<K,V>next;// 注意volatile修饰，因为cas会操作它/** 用于创建正常的数据节点，可以看到它没有right字段和down字段，因为它就是位于底层的数据链表中，是最熟悉链表普通节点 * Creates a new regular node. */Node(Kkey,Objectvalue,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类型创建marker节点（在删除操作会被使用），和数据节点的区别：无key，且value指向自己。Node(Node<K,V>next){this.key=null;this.value=this;this.next=next;}