SkipList(跳表)

在看《Redis设计与实现》的时候看到有涉及跳表（SkipList）的相关应用，就想了解一下。作记录如下。 跳表其实就是一个同时维护多条链表的数据结构。换句话说，就是为了加快查询速度，而占用更多的空间来储存数据,算是空间换时间了。 结构看起来是这样的：  ## 结构 在一般的链表里，会有next或这forward/backward这类的指针来指向其他节点，跳表 就厉害了 它有一排（level，redis中跳表节点的level的数量是1~32）这种指针，而且这些指针指向的节点的位置一般也不同（跨度不一样）。 ### 节点定义 一个最基本的节点的属性是这样的。Key和Value，以及前向指针的数量和保存他们的数组 ``` java public class Node { private Long key; private T data; private int level; private Node[] forwards; } ``` ### 数据结构 SkipList的结构包括头尾节点、最大的level高度，添加节点时，节点的高度由 `getRandomLevel()`方法提供 ``` java public class SkipList { private int MAX_LEVEL; private Node head; private Node tail; /** * 构造函数 * * @param level */ public SkipList(int level) { } /** * 获取新节点的层数， * 不大于最大节点 * * @return */ public int getRandomLevel() { int count = 0; Random random = new Random(System.currentTimeMillis()); while (Math.abs(random.nextLong()) % 2 == 1) { if (count < MAX_LEVEL - 1) { count += 1; } else { break; } } if (count > MAX_LEVEL - 1) { count = MAX_LEVEL - 1; } return count; } } ``` ### 添加数据 添加数据的关键在于，找到添加的位置的前置节点，而且是，同时维护的这么多层的前置节点。 ``` java Node[] update = new Node[MAX_LEVEL]; Node tempHead = head; ``` 一个用来保存前置节点的数组，和临时变量用于遍历 ```java for (int i = MAX_LEVEL - 1; i >= 0; i--) { if (tempHead.getForwards()[i] == tail || tempHead.getForwards()[i].getKey() > key) { update[i] = tempHead; } else { while (tempHead.getForwards()[i] != tail && tempHead.getForwards()[i].getKey() < key) { tempHead = tempHead.getForwards()[i]; } if (tempHead.getForwards()[i] != tail && tempHead.getForwards()[i].getKey() == key) { tempHead.getForwards()[i].setData(data); return; } update[i] = tempHead; } } ``` 从最高层开始遍历，最高层的跨越较快。当 当前节点的下一个节点是尾部或者key大于要插入的key时，将当前节点保存为这一层的结果。 保存完后进入下一层。 如果不符合上面的条件，就接着在那一层横向遍历 `tempHead = tempHead.getForwards()[i];`直到尾部或key大于目标key,key相等就覆盖然后提前返回。 然后保存结果` update[i] = tempHead;` 最后更新链表 创建链表节点时，要由前向层数（level）, level的大小不超过Head的大小，而且level的数值时按概率来的，这里是 - 1 ：1/2 - 2 ：1/4 - 3 ：1/8 - .. level加一的概率是1/2 > redis 取的是 level: 1/4 和 MAX : 32 ``` java Node node = new Node<>(); node.setKey(key); node.setData(data); node.setForwards(new Node[level + 1]); int level = getRandomLevel(); node.setLevel(level); /** * 链接新节点 */ for (int i = 0; i <= level; i++) { if (update[i] != null) { node.getForwards()[i] = update[i].getForwards()[i]; update[i].getForwards()[i] = node; } } ``` ### 查找 查找和插入差不多 横向和纵向分别遍历，找到就返回 ``` java public T getData(Long key) { Node tempHead = head; for (int i = MAX_LEVEL - 1; i >= 0; i--) { if (tempHead.getForwards()[i] == tail || tempHead.getForwards()[i].getKey() > key) { continue; } else { while (tempHead.getForwards()[i] != tail && tempHead.getForwards()[i].getKey() < key) { tempHead = tempHead.getForwards()[i]; } if (tempHead.getForwards()[i] != null) { if (tempHead.getForwards()[i].getKey() != null) { if (tempHead.getForwards()[i].getKey().equals(key)) { return tempHead.getForwards()[i].getData(); } } } } } return null; } ``` ### 复杂度 由于每个节点的前向高度都是随机的，所以比较难算。 ##### 时间复杂度 - 最差是 O(n) - 查找 O(lgn) 的概率较高 ##### 空间复杂度 - S < 2n ### 被吊打 和java的HashMap比了一下（膨胀）,被吊打了