Jump table

##### What is a skip list

  1. A skip list is an ordered data structure that allows fast access to nodes by maintaining Pointers to multiple other nodes.
  2. Search complexity: average O(log n) worst O(n), in most cases, the efficiency is not much different from the equilibrium tree,
  3. Skip tables do this by randomly picking up half of the indexes in an ordered array, and randomly picking up half of the indexes in the ordered array, so that every time you look up data, you don’t have to find the whole list, you just follow the skip table step by step.
  4. For each addition, a coin is flipped from the bottom level to determine whether the node should be promoted to the index
  5. Skip lists are also used in Redis. One of the ways to realize ordered sets in Redis is skip lists. When an ordered set contains many elements or the members of elements are relatively long strings, Redis will use skip lists as the underlying data results. Another use in Redis is cluster nodes as internal data structures (to be learned)

ConcurrentSkipListMap

#### Application scenario: A large amount of data is accessed, frequently added, deleted, modified, and searched, and a high degree of data consistency is not required ####

  1. Based on skip list implementation, with weak consistency
  2. The key cannot be null
  3. The main implementation includes three classes: HeadIndex Index Node. The index hierarchy is maintained through HeadIndex, which requires a relatively small amount of data from the top down to the lowest 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
     * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
Copy the code

Put method