有序表所有的操作都是 有序表 - 跳表 - 图1 的。有很多数据结构可以实现有序表，如：红黑树、AVL（Self-Balancing Binary Search Tree）、SBT（Size-Balance-Tree）、跳表（skip-List）等。

AVL，SBT，红黑树都可以参考 各种树 。

跳表

对于一个跳表来说，依次插入数据：3，20，40，50，10，30，100，15

image.png
插入 3，roll 到层高为 3，找到比 3 小的最右节点为 null，head 的层高为 0， 0<3，将 head 的层高增加到 3 层，并将每层都指向 3 节点
image.png

插入 20，roll 到层高为 5，找到比 20 小的最右节点为 3，head 的层高为 3， 3<5，将 head 的层高增加到 5 层，3 节点所有层指向 20 节点，head 节点的最高两层指向 20 节点

image.png
插入 40，roll 到层高为 4，找到比 40 小的最右节点为 20，head 的层高为 5， 5>4，head 层高不变，20 节点 4 个层指向 40 节点
image.png
插入 50，roll 到层高为 5，找到比 50 小的最右节点为 50，head 的层高为 5， 5==5，head 层高不变，40 节点所有层指向 50 节点，20 节点的最高层指向 50节点
image.png
插入 10，roll 到层高为 2，找到比 10 小的最右节点为 3，head 的层高为 5， 5>2，head 层高不变，3 节点 0、1 层指向 10 节点，10 节点的所有层指向 20节点
image.png
插入 30，roll 到层高为 1，找到比 30 小的最右节点为 20，head 的层高为 5， 5>1，head 层高不变，20 节点 0 层指向 30 节点，30 节点的所有层指向 40 节点
image.png
插入 100，roll 到层高为 6，找到比 100 小的最右节点为 50，head 的层高为 6， 5<6，head 层高增加到 6，50 节点的所层点指向 100 节点，head 节点的 5 层指向 100 节点
image.png
插入 15，roll 到层高为 4，找到比 15 小的最右节点为 10，head 的层高为 6， 6>4，head 层高不变，10 节点所有层指向 15 节点，3 节点的 2 层指向 15 节点， head 的 3 层执行 15 节点
image.png
至此，所有节点插入完成。在这个过程中，最重要的过程有两个：

  1. 如何找到小于插入值的最大值？
  2. 找到该值要插入的地方后如果修改

例如：在插入 10 节点时
image.png

  • 先遍历 head 节点，从最高层遍历：
    • 第 4 层 —> 20，20 > 10
    • 第 3 层 —> 20，20 > 10
    • 第 2 层 —> 3，3 < 10
  • 开始遍历 3 节点：
    • 第 2 层 —> 20，20 > 10
  • 遍历结束，小于 10 的最大值为 3，就将 10 插入到 3 节点后

10 的层高为 2，3 节点的 0、1 两层要指向 10 节点，10 节点指向 20 节点

结果为：
image.png

例如：插入 15 时：
image.png

  • 从 head 节点最高层开始遍历：
    • 第 5 层 —> 100，100 > 15
    • 第 4 层 —> 20，20 > 15
    • 第 3 层 —> 20，20 > 15
    • 第 2 层 —> 3，3 < 15
  • 从 3 节点开始遍历：
    • 第 2 层 —> 20，20 > 15
    • 第 1 层 —> 10，10 < 15
  • 遍历结束，15 要插入到 10 后面

15 的层高为 4，10 节点的0、1要指向 15 节点， 3 节点的 2 层要指向 15 节点，head 的 3 层要指向15 节点；15 节点指向 20 节点

结果为：
image.png

代码实现：

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class SkipList {
  6.     public static class SkipListNode<K extends Comparable<K>, V> {
  7.         public K key;
  8.         public V val;
  9.         public List<SkipListNode<K, V>> nextNodes;
  11.         public SkipListNode(K key, V val) {
  12.             this.key = key;
  13.             this.val = val;
  14.             nextNodes = new ArrayList<>();
  15.         }
  17.         /**
  18.          * {@code otherKey} 是否要比 key 小
  19.          *
  20.          * @param otherKey
  21.          * @return
  22.          */
  23.         public boolean isKeyLess(K otherKey) {
  24.             return otherKey != null && (key == null || key.compareTo(otherKey) < 0);
  25.         }
  27.         /**
  28.          * {@code otherKey} 是否 key 相等
  29.          *
  30.          * @param otherKey
  31.          * @return
  32.          */
  33.         public boolean isKeyEqual(K otherKey) {
  34.             return key == null && otherKey == null ||
  35.                     key != null && otherKey != null && key.compareTo(otherKey) == 0;
  36.         }
  37.     }
  39.     public static class SkipListMap<K extends Comparable<K>, V> {
  40.         private static final double PROBABILITY = 0.5;
  41.         private SkipListNode<K, V> head;
  42.         private int size;
  43.         private int maxLevel;
  45.         public SkipListMap() {
  46.             head = new SkipListNode<>(null, null);
  47.             head.nextNodes.add(null);
  48.             size = 0;
  49.             maxLevel = 0;
  50.         }
  52.         /**
  53.          * 是否包含 key
  54.          *
  55.          * @param key
  56.          * @return
  57.          */
  58.         public boolean containsKey(K key) {
  59.             if (key == null) return false;
  61.             SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  62.             SkipListNode<K, V> next = less.nextNodes.get(0);
  63.             return next != null && next.isKeyEqual(key);
  64.         }
  66.         /**
  67.          * 新增数据
  68.          *
  69.          * @param key
  70.          * @param value
  71.          */
  72.         public void put(K key, V value) {
  73.             if (key == null) return;
  75.             SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  76.             SkipListNode<K, V> find = less.nextNodes.get(0);
  78.             if (find != null && find.isKeyEqual(key)) {
  79.                 // 值相同
  80.                 find.val = value;
  81.             } else {
  82.                 // 值不同
  83.                 size++;
  84.                 int newNodeLevel = 0;
  86.                 // roll 层高
  87.                 while (Math.random() < PROBABILITY) {
  88.                     newNodeLevel++;
  89.                 }
  90.                 while (newNodeLevel > maxLevel) {
  91.                     // 新节点的层高 > 最大层高，head 需要增加层高
  92.                     head.nextNodes.add(null);
  93.                     maxLevel++;
  94.                 }
  95.                 // 新节点
  96.                 SkipListNode<K, V> newNode = new SkipListNode<>(key, value);
  97.                 // 初始化层高
  98.                 for (int i = 0; i <= newNodeLevel; i++) {
  99.                     newNode.nextNodes.add(null);
  100.                 }
  101.                 int level = maxLevel;
  102.                 SkipListNode<K, V> pre = head;
  103.                 // 设置前后节点每层的指向
  104.                 while (level >= 0) {
  105.                     pre = mostRightLessNodeInLevel(key, pre, level);
  106.                     if (level <= newNodeLevel) {
  107.                         newNode.nextNodes.set(level, pre.nextNodes.get(level));
  108.                         pre.nextNodes.set(level, newNode);
  109.                     }
  110.                     level--;
  111.                 }
  112.             }
  113.         }
  115.         /**
  116.          * 获取 key 的节点信息
  117.          *
  118.          * @param key
  119.          * @return
  120.          */
  121.         public V get(K key) {
  122.             if (key == null) return null;
  124.             SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  125.             SkipListNode<K, V> next = less.nextNodes.get(0);
  126.             return next != null && next.isKeyEqual(key) ? next.val : null;
  127.         }
  129.         /**
  130.          * 删除 key
  131.          *
  132.          * @param key
  133.          */
  134.         public void remove(K key) {
  135.             if (!containsKey(key)) return;
  137.             size--;
  138.             int level = maxLevel;
  139.             SkipListNode<K, V> pre = head;
  140.             while (level >= 0) {
  141.                 pre = mostRightLessNodeInLevel(key, pre, level);
  142.                 SkipListNode<K, V> next = pre.nextNodes.get(level);
  143.                 // 清除指向
  144.                 if (next != null && next.isKeyEqual(key)) {
  145.                     pre.nextNodes.set(level, next.nextNodes.get(level));
  146.                 }
  147.                 // 判断是否影响最大层高
  148.                 if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
  149.                     head.nextNodes.remove(level);
  150.                     maxLevel--;
  151.                 }
  152.                 level--;
  153.             }
  154.         }
  156.         /**
  157.          * 第一个（最小）节点的 key
  158.          *
  159.          * @return
  160.          */
  161.         public K firstKey() {
  162.             return head.nextNodes.get(0) != null ? head.nextNodes.get(0).key : null;
  163.         }
  165.         /**
  166.          * 返回最后一个（最大）节点 key
  167.          *
  168.          * @return
  169.          */
  170.         public K lastKey() {
  171.             int level = maxLevel;
  172.             SkipListNode<K, V> cur = head;
  173.             while (level >= 0) {
  174.                 // 从最高层遍历，中间可以跳过很多的数据
  175.                 SkipListNode<K, V> next = cur.nextNodes.get(level);
  176.                 while (next != null) {
  177.                     cur = next;
  178.                     next = cur.nextNodes.get(level);
  179.                 }
  180.                 level--;
  181.             }
  182.             return cur.key;
  183.         }
  185.         /**
  186.          * 大于等于 key 的最小值
  187.          *
  188.          * @param key
  189.          * @return
  190.          */
  191.         public K ceillingKey(K key) {
  192.             if (key == null) return null;
  194.             SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  195.             SkipListNode<K, V> next = less.nextNodes.get(0);
  196.             return next != null ? next.key : null;
  197.         }
  199.         /**
  200.          * 小于等于 key 的最大值
  201.          *
  202.          * @param key
  203.          * @return
  204.          */
  205.         public K floorKey(K key) {
  206.             if (key == null) return null;
  208.             SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  209.             SkipListNode<K, V> next = less.nextNodes.get(0);
  210.             return next != null && next.isKeyEqual(key) ? next.key : less.key;
  211.         }
  213.         public int size() {
  214.             return size;
  215.         }
  218.         /**
  219.          * 得到小于 key 的最大（最右侧）的值
  220.          *
  221.          * @param key
  222.          * @return
  223.          */
  224.         private SkipListNode<K, V> mostRightLessNodeInTree(K key) {
  225.             if (key == null) return null;
  227.             int level = maxLevel;
  228.             SkipListNode<K, V> cur = head;
  229.             while (level >= 0) {
  230.                 cur = mostRightLessNodeInLevel(key, cur, level--);
  231.             }
  232.             return cur;
  233.         }
  235.         /**
  236.          * 本层小于 {@code key} 最右的节点
  237.          *
  238.          * @param key
  239.          * @param cur
  240.          * @param level
  241.          * @return
  242.          */
  243.         private SkipListNode<K, V> mostRightLessNodeInLevel(K key, SkipListNode<K, V> cur, int level) {
  244.             SkipListNode<K, V> next = cur.nextNodes.get(level);
  245.             while (next != null && next.isKeyLess(key)) {
  246.                 cur = next;
  247.                 next = cur.nextNodes.get(level);
  248.             }
  249.             return cur;
  250.         }
  251.     }
  253.     // for test
  254.     public static void printAll(SkipListMap<String, String> obj) {
  255.         for (int i = obj.maxLevel; i >= 0; i--) {
  256.             System.out.print("Level " + i + " : ");
  257.             SkipListNode<String, String> cur = obj.head;
  258.             while (cur.nextNodes.get(i) != null) {
  259.                 SkipListNode<String, String> next = cur.nextNodes.get(i);
  260.                 System.out.print("(" + next.key + " , " + next.val + ") ");
  261.                 cur = next;
  262.             }
  263.             System.out.println();
  264.         }
  265.     }
  267.     public static void main(String[] args) {
  268.         SkipListMap<String, String> test = new SkipListMap<>();
  269.         printAll(test);
  270.         System.out.println("======================");
  271.         test.put("A", "10");
  272.         printAll(test);
  273.         System.out.println("======================");
  274.         test.remove("A");
  275.         printAll(test);
  276.         System.out.println("======================");
  277.         test.put("E", "E");
  278.         test.put("B", "B");
  279.         test.put("A", "A");
  280.         test.put("F", "F");
  281.         test.put("C", "C");
  282.         test.put("D", "D");
  283.         printAll(test);
  284.         System.out.println("======================");
  285.         System.out.println(test.containsKey("B"));
  286.         System.out.println(test.containsKey("Z"));
  287.         System.out.println(test.firstKey());
  288.         System.out.println(test.lastKey());
  289.         System.out.println(test.floorKey("D"));
  290.         System.out.println(test.ceillingKey("D"));
  291.         System.out.println("======================");
  292.         test.remove("D");
  293.         printAll(test);
  294.         System.out.println("======================");
  295.         System.out.println(test.floorKey("D"));
  296.         System.out.println(test.ceillingKey("D"));
  297.     }
  298. }