JDK版本：AdoptOpenJDK 11.0.10+9
1 基本概念
ConcurrentSkipListMap是在JDK 1.6中新增的，为了对高并发场景下的有序Map提供更好的支持，它有几个特点：
- 高并发场景
key是有序的- 添加、删除、查找操作都是基于跳表结构（
Skip List）实现的 key和value都不能为null
2 跳表（Skip List）
跳表（
Skip List）是一种类似于链表的数据结构，其查询、插入、删除的时间复杂度都是O(logn)。
在传统的单链表结构中，查找某个元素需要从链表的头部按顺序遍历，直到找到目标元素为止，查找的时间复杂度为O(n)。
而跳表结合了树和链表的特点，其特性如下：
- 跳表由很多层组成；
- 每一层都是一个有序的链表；
- 最底层的链表包含所有元素；
- 对于每一层的任意一个节点，不仅有指向其下一个节点的指针，也有指向其下一层的指针；
- 如果一个元素出现在
Level n层的链表中，则它在Level n层以下的链表也都会出现。
Skip List例子：
下图是一种可能的跳表结构：
如图，[1]和[40]节点有3层，[8]和[18]节点有2层。每一层都是有序的链表。
如果要查找目标节点[15]，大致过程如下：
- 首先查看
[1]节点的第1层，发现[1]节点的下一个节点为[40]，大于15，那么查找[1]节点的下一层； - 查找
[1]节点的第2层，发现[1]节点的下一个节点为[8]，小于15，接着查看下一个节点，发现下一个节点是[18]，大于15，因此查找[8]节点的下一层； - 查找
[8]节点的第2层，发现[8]节点的下一个节点是[10]，小于15，接着查看下一个节点[13]，小于15，接着查看下一个节点[15]，发现其值等于15，因此找到了目标节点，结束查询。
跳表实际上是一种 空间换时间 的数据结构。
3 ConcurrentSkipListMap结构
ConcurrentSkipListMap用到了两种结构的节点。
Node节点代表了真正存储数据的节点，包含了key、value、指向下一个节点的指针next：
static final class Node<K,V> {
final K key; // 键 V val; // 值 Node<K,V> next; // 指向下一个节点的指针 Node(K key, V value, Node<K,V> next) {
this.key = key; this.val = value; this.next = next; } } Index节点代表了跳表的层级，包含了当前节点node、下一层down、当前层的下一个节点right：
static final class Index<K,V> {
final Node<K,V> node; // 当前节点 final Index<K,V> down; // 下一层 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; } } 如图所示，Node节点将真实的数据按顺序链接起来，Index节点组成了跳表中多层次的索引结构。
4 使用案例
下面是对ConcurrentSkipListMap的简单使用的一个例子：
public class ConcurrentSkipListMapTest {
public static void main(String[] args) {
ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>(); map.put(4, "4"); map.put(5, "5"); map.put(1, "1"); map.put(6, "6"); map.put(2, "2"); System.out.println(map.keySet()); System.out.println(map); System.out.println(map.descendingKeySet()); System.out.println(map.descendingMap()); } } 输出为：
[1, 2, 4, 5, 6] {1=1, 2=2, 4=4, 5=5, 6=6} [6, 5, 4, 2, 1] {6=6, 5=5, 4=4, 2=2, 1=1} 源码解析可以看看这篇文章：Java多线程进阶（二五）—— J.U.C之collections框架：ConcurrentSkipListMap
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230159.html原文链接：https://javaforall.net
