跳跃表和ConcurrentSkipListMap

跳跃表

跳跃表是什么

1. 跳跃表是一种有序的数据结构，通过每个节点维持指向多个其他节点的指针，来达到快速访问节点，
2. 查找复杂度： 平均O(log n) 最坏 O(n) ，在大部分情况下，效率与平衡树相差不大，
3. 跳跃表就通过在一个 有序数组中 ，随机找出一半的索引，而在这一半的索引里面又随机抽出一半的索引，这样每次查找数据，就不需要没有都便利整个列表，只需要跟着跳跃表一步一步的找，
4. 每一次的添加，都会从最底层开始抛硬币，来决定这个节点是否为需要提拔为索引

5. 跳跃表在redis中也有应用，redis中的有序集合的实现方式之一是跳跃表，当一个有序集合包含元素多，或者元素的成员为比较长的字符串的时候，redis就会使用跳跃表来作为底层数据结果实现，redis中另一个使用是集群节点作为内部数据结构（待了解）

   
   image.png

ConcurrentSkipListMap

使用场景：

存取数据量大，增删改查频繁，且对数据没有强一致性要求的高并发场景

特点：

1. 基于跳跃表实现，具有弱一致性
2. key 不能为null
3. 主要实现包含 HeadIndex Index Node 三个类。通过HeadIndex来维护索引层次，通过index从上往下，一直到最底层Node节点的时候，就只需要比较比较少的一部分数据。

     *
     * 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
     * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+

put方法