跳表

跳表 (Skip List)

redis中用到了跳表

5. 跳表（Skip List）

• 定义：一种随机化数据结构，通过在原始链表上建立多级索引，加速查询。

• 性质：

  • 查询 / 插入 / 删除平均时间复杂度 (O(\log n))，最坏 (O(n))。
  • 空间复杂度 (O(n))（期望），每个节点可能出现在多层。
  • 无需维护平衡（如红黑树），实现简单。

• Java 实现：

  class SkipNode {
      int data;
      SkipNode[] forward; // 指向各层的后继节点
      
      SkipNode(int data, int level) {
          this.data = data;
          this.forward = new SkipNode[level + 1];
      }
  }
  
  class SkipList {
      private int maxLevel; // 最大层数
      private int level;    // 当前层数
      private SkipNode header; // 头节点
      
      public SkipList(int maxLevel) {
          this.maxLevel = maxLevel;
          this.level = 0;
          this.header = new SkipNode(-1, maxLevel);
      }
      
      // 生成随机层数（1~maxLevel）
      private int randomLevel() {
          int level = 1;
          while (Math.random() < 0.5 && level < maxLevel) {
              level++;
          }
          return level;
      }
      
      // 插入节点
      public void insert(int key) {
          SkipNode[] update = new SkipNode[maxLevel + 1];
          SkipNode current = header;
          
          // 查找插入位置
          for (int i = level; i >= 0; i--) {
              while (current.forward[i] != null && current.forward[i].data < key) {
                  current = current.forward[i];
              }
              update[i] = current;
          }
          
          current = current.forward[0];
          
          // 若key已存在则不插入
          if (current == null || current.data != key) {
              int newLevel = randomLevel();
              
              // 调整当前层数
              if (newLevel > level) {
                  for (int i = level + 1; i <= newLevel; i++) {
                      update[i] = header;
                  }
                  level = newLevel;
              }
              
              // 创建新节点并插入
              SkipNode newNode = new SkipNode(key, newLevel);
              for (int i = 0; i <= newLevel; i++) {
                  newNode.forward[i] = update[i].forward[i];
                  update[i].forward[i] = newNode;
              }
          }
      }
  }