并发容器ConcurrentSkipList原理解析（二十四）

迈不过友情╰ 2022-12-31 02:27 128阅读 0赞

今天进行并发容器ConcurrentSkipList原理解析：其有两个重要的子类；

ConcurrentSkipListMap  有序 的  Map 和ConcurrentSkipListSet 有序 的 Set。

TreeMap  和  TreeSet  使用红黑树按照  key  的顺序（自然顺序、自定义顺序） 来使得键值对有序存储*，* 但是只能在单线程下安全使用；多线程下想要使键值对 按照 key  的顺序来存储，则需要使用  ConcurrentSkipListMap  和 ConcurrentSkipListSet，分别用以代替  TreeMap  和  TreeSet ，存入的数据按  key  排 序。在实现上，ConcurrentSkipListSet  本质上就是  ConcurrentSkipListMap 。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

**1、什么是**  **SkipList呢** **？**

***这就涉及到二分查找和***  ***AVL***  ***树查找原理***

二分查找要求元素可以随机访问，所以决定了需要把元素存储在连续内存。 这样查找确实很快，但是插入和删除元素的时候，为了保证元素的有序性，就需 要大量的移动元素了。 如果需要的是一个能够进行二分查找，又能快速添加和删除元素的数据结构， 首先就是二叉查找树，二叉查找树在最坏情况下可能变成一个链表。 于是，就出现了平衡二叉树，根据平衡算法的不同有 AVL  树， B-Tree ， B+Tree ， 红黑树等，但是 AVL  树实现起来比较复杂，平衡操作较难理解，这时候就可以用 SkipList 跳跃表结构。

***2、什么是跳表呢？***

传统意义的单链表是一个线性结构，向有序的链表中插入一个节点需要  O(n) 的时间，查找操作需要 O(n) 的时间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

如果我们使用上图所示的跳跃表，就可以减少查找所需时间为  O(n/2) ，因为 我们可以先通过每个节点的最上面的指针先进行查找，这样子就能跳过一半的节 点。比如我们想查找 50 ，首先和  20  比较，大于  20  之后，在和  40  进行比较，然 后在和 70  进行比较，发现  70  大于  50 ，说明查找的点在  40  和  50  之间，从这个 过程中，我们可以看出，查找的时候跳过了 30 。 跳跃表其实也是一种通过“空间来换取时间”的一个算法，令链表的每个结 点不仅记录 next 结点位置，还可以按照  level  层级分别记录后继第  level  个结点。 此法使用的就是“ **先大步查找确定范围，再逐渐缩小迫近** ” 的思想进行的查找。跳 跃表在算法效率上很接近红黑树。 跳跃表又被称为概率，或者说是随机化的数据结构，目前开源软件 Redis  和 lucence 都有用到它。 都是线程安全的 Map  实现， ConcurrentHashMap  的性能和存储空间要优于 ConcurrentSkipListMap，但是  ConcurrentSkipListMap  有一个功能： 它会按照键的 顺序进行排序。

可参考补充： [https://www.cnblogs.com/crazymakercircle/p/13928386.html][https_www.cnblogs.com_crazymakercircle_p_13928386.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221120/2ab2e93a81a644f2bb48c3548243819a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221120/61ee60b3fd2a463eb0f8c8a8d421d776.png
[https_www.cnblogs.com_crazymakercircle_p_13928386.html]: https://www.cnblogs.com/crazymakercircle/p/13928386.html