Loading... 在Prometheus推送监控指标到Pushgateway上的时候，需要先在本地做一个缓存减少开销，这时候的缓存通常用的类型就是跳表，即 `ConcurrentSkipListMap`。 <!--more--> ## 数据结构 传统意义的单链表是一个线性结构，向有序的链表中插入一个节点需要 `O(n)`的时间，查找操作需要 `O(n)`的时间。 而跳表可以抽象的看成是一个有“层次”水平结构的链表集，不仅可以向右还能向下走，宛如第四象限的坐标轴。 跳表分为**许多层(level)**，每一层都可以看作是数据的**索引**，这些索引的意义就是加快跳表查找数据速度。每一层的数据都是**有序**的，上一层数据是下一层数据的**子集**，并且**第一层(level 1)包含了全部的数据**；层次越高，跳跃性越大，包含的数据越少。 ### 源码分析 以ConcurrentSkipListMap为例： ```java static class Index<K,V> { final Node<K,V> node;//索引节点关联的数据节点 final Index<K,V> down;//下一级别索引节点（关联的数据节点相同） volatile Index<K,V> right;//当前索引级别中，后继索引节点 …… } static final class Node<K,V> { final K key; volatile Object value;//value值 volatile Node<K,V> next;//后继数据节点 …… } ``` 抽象成图形大概就是这样子：  每个index都有一个向右和向下的index指针，边界的话则为null。 同时，每个index都指向一个Node的指针，同一列的index指向同一个Node节点。（你也可以理解为同一纵的index都是同一分身） ### 查找流程 通过这图应该能加深上述结构的理解：  该图整个方方为Index，左边数值为Node、右边分别是rightIndex和downIndex。level为2，我们要找到19。 先从原点开始，按最上面的level2出发，发现level2上的第一个节点的Node值为6比19小，所以走。 同样的方法在level2层走到17，发现下一个level2的对应值为21，比19大，不往右走，往下一级的level走，到level1。 发现level1下的17Index的下一个值就是19，刚好相等，走过去，结束。 ## 跳表、哈希表、红黑树 ### 关于跳表 跳表其实也是一种通过“**空间来换取时间**”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。 在跳表中，对于一个链表内每一个结点包含多少个指向后续元素的指针，是通过一个随机函数生成器得到。 这就是说，跳表使用**概率均衡技术**而不是使用强制性均衡技术。因此，对于**插入**和**删除**结点比传统上的平衡树算法更为简洁高效。 `LevelDB`、Redis`的底层存储结构就是用的SkipList。 SkipList底层是用链表实现的，可以实现为lock free（基于CAS的无锁编程），同时它还有着不错的性能（单线程下只比红黑树略慢） ### 三者比较 * **Hash表**：插入、查找最快，为 `O(1)`；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。（不适合迭代） * **红黑树**：插入、查找为 `O(logn)`，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。（不适合并发） * **SkipList**：插入、查找为 `O(logn)`，但常数项比红黑树要大；底层结构为链表，可无锁实现；数据天然有序。 跳表和红黑树的性能相当，最主要的优势就是当调整(插入或删除)时，红黑树需要使用旋转来维护平衡性，这个操作需要动多个节点，在并发时候很难控制。而跳表插入或删除时只需定位后插入，插入时只需添加插入的那个节点及其多个层的复制，以及定位和插入的原子性维护。所以它更加可以利用CAS操作来进行无锁编程。 当我们希望**快速存取**<Key, Value>键值对时我们可以使用 `HashMap`。 当我们希望在多线程**并发存取**<Key, Value>键值对时，我们会选择 `ConcurrentHashMap`。 `TreeMap`则会帮助我们保证数据是按照Key的自然顺序或者compareTo方法指定的排序规则进行**排序**。 当我们需要多线程**并发存取**<Key, Value>数据**且保证数据有序时**，`ConcurrentSkipListMap`也许可以满足我们的需求。 ## CurrentSkipListMap ConcurrentSkipListMap持有跳表的特点，它是**线程安全的有序的哈希表，适用于高并发的场景。** **ConcurrentSkipListMap和TreeMap**： 两者虽然都是有序的哈希表，但是ConcurrentSkipListMap是线程安全且由跳表实现；而TreeMap是线程不安全且由红黑树实现。 在**非多线程**的情况下，应当尽量使用 `TreeMap`。此外对于**并发性相对较低**的并行程序可以使用 `Collections.synchronizedSortedMap`将TreeMap进行包装，也可以提供较好的效率。对于**高并发**程序，应当使用 `ConcurrentSkipListMap`，能够提供更高的并发度。 --- 主要是整合了关于跳表的知识点同时完善了结构图。 后面CurrentSkipListMap的具体操作可以看这里：[ConcurrentSkipListMap分析和使用](https://www.cnblogs.com/java-zzl/p/9767255.html) Last modification：August 21, 2022 © Allow specification reprint Like 0 喵ฅฅ