环球快看：跳表java实现(可直接运行)

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

环球快看：跳表java实现(可直接运行)

2023-02-03 15:59:15 来源：博客园

(资料图片仅供参考)

跳表类

package com.yjz.example.跳表;/** * @author: yuanjinzhong * @date: 2023/1/28 3:00 PM * @description: *     跳表类，参考项目：https://github.com/wangzheng0822/algo/blob/b2c1228ff915287ad7ebeae4355fa26854ea1557/java/17_skiplist/SkipList2.java#L119 *     跳表里面每个值只有一个节点，每个节点含有该节点在每一层的下一个节点 *          */public class SkipList {  /** 晋升成为索引的概率 ---新插入的节点有{@linkplain SKIP_LIST_P}的概率成为索引； redis设置的是0.25的概率晋升为索引 */  public static final double SKIP_LIST_P = 0.5;  /** 跳表的最大高度，包括原始skipList */  private static final int MAX_LEVEL = 8;  /** 跳表的当前高度 */  private int levelCount = 1;  /** 头节点，每个skipList都需要一个头节点，但是打印的时候不会打印出来 */  public Node head = new Node(MAX_LEVEL);  /**   * 插入元素   *   * @param e   * @return   */  public void insert(int e) {    int level = head.nextInEachLayer[0] == null ? 1 : randomLevel();    /**     * 一层一层的增加索引，     *     * 
若随机的层数比当前最大值大（或者大很多），那么只向上增加一层索引；     *     * 
不然可能出现，其他节点都在同一层，这个新插入的索引，单独七八层     *     * 
不过可以不加，看个人理解     */    if (level > levelCount) {      /** 俩种策略 */      level = ++levelCount;      // levelCount=level;    }    Node newNode = new Node(level);    newNode.data = e;    Node p = head;    for (int i = levelCount - 1; i >= 0; i--) {      /**       * 为啥不比较p.data？因为p是头节点啊，头节点没有值；所以比较：p.nextInEachLayer[i].data       *       * 
p.nextInEachLayer[i].data其实就是第一个真实的节点       */      while (p.nextInEachLayer[i] != null && p.nextInEachLayer[i].data < e) {        p = p.nextInEachLayer[i];      }      /**       * i=levelCount-1，levelCount会大于当前随机出来的level;也就是i会大于level       *       * 
新插入的节点只有level层，高于该层的层数肯定不需要维护后继指针       */      if (level > i) {        /**         * 插入值，就插在{@link p和p的后继 }之间         *         * 
有的实现还判断p.nextInEachLayer[i]是否为空，其实大可不必         */        Node temp = p.nextInEachLayer[i];        p.nextInEachLayer[i] = newNode;        newNode.nextInEachLayer[i] = temp;      }    }  }  /**   * 查找   *   * @param e   * @return   */  public Node find(int e) {    Node p = head;    // 从最高层开始查找    for (int i = levelCount - 1; i >= 0; i--) {      while (p.nextInEachLayer[i] != null && p.nextInEachLayer[i].data < e) {        p = p.nextInEachLayer[i];        System.out.println("查找路径" + p);      }    }    System.out.println("最终确定的节点" + p);    // 肯定是到跳表最下面一层查找    if (p.nextInEachLayer[0] != null && p.nextInEachLayer[0].data == e) {      return p.nextInEachLayer[0];    }    return null;  }  /**   * 删除元素   *   * @param e   */  public void delete(int e) {    Node p = head;    Node[] preNodes = new Node[levelCount];    for (int i = levelCount - 1; i >= 0; i--) {      while (p.nextInEachLayer[i] != null && p.nextInEachLayer[i].data < e) {        p = p.nextInEachLayer[i];      }      // 将目标节点的每一层前驱节点保存下来（这个层数多了，下面数值相等判断过滤了）      preNodes[i] = p;    }    if (p.nextInEachLayer[0] != null && p.nextInEachLayer[0].data == e) {      for (int i = levelCount - 1 - 1; i >= 0; i--) {        if (preNodes[i].nextInEachLayer[i] != null && preNodes[i].nextInEachLayer[i].data == e) {          preNodes[i].nextInEachLayer[i] = preNodes[i].nextInEachLayer[i].nextInEachLayer[i];        }      }    }    // 悬浮在上方的空引用删除    while (levelCount > 1 && head.nextInEachLayer[levelCount] == null) {      levelCount--;    }  }  /**   * 期望建立的索引结构，   *   * 
正金字塔结构 每一层是下一层的1/2的元素数量   *   * 
最下面一层，完整的链表 最下面第二层（1级索引），1/2的节点做索引 最下面第二层（2级索引），1/2的1/2节点做索引   *   * 
新加入一个节点，则有1/2的可能是1级索引 有1/4的可能是2级索引 有1/8的可能是3级索引 (是2级索引的同时肯定也是1级索引，3级索引的同时肯定也是1级和2级索引)   *   * 
该方法会随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），   *   * 
且该方法有 1/2 的概率返回 1、 1/4 的概率返回 2、 1/8的概率返回 3，以此类推   *   * 
1，2，3，4 不是对应 1，2，3，4级索引，需要减1，才等于索引的级别   * 
randomLevel() 方法返回 1 表示当前插入的该元素不需要建索引，只需要存储数据到原始链表即可（概率 1/2）   * 
randomLevel() 方法返回 2 表示当前插入的该元素需要建一级索引（概率 1/4）   * 
randomLevel() 方法返回 3 表示当前插入的该元素需要建二级索引（概率 1/8）   * 
randomLevel() 方法返回 4 表示当前插入的该元素需要建三级索引（概率 1/16）   * 
以此类推。。。   *   *        * 
返回1不建立索引，大于1则必定会建一级索引，大于1的概率为1-1/2=二分之一，   * 
大于2必然会创建二级索引，大于2的概率为1-1/2-1/4=四分之1   * 类推   *   * @return   */  public int randomLevel() {    int level = 1;    /** 随机数连续2次小于1/2才会使得level+1（第一次加1）,即level+1（第一次加1）的概率为1/2乘以1/2= 1/4） */    // 当 level < MAX_LEVEL，且随机数小于设定的晋升概率时，level + 1    while (Math.random() < SKIP_LIST_P && level < MAX_LEVEL) {      level += 1;    }    return level;  }  public void printAll() {    Node p = head;    while (p.nextInEachLayer[0] != null) {      System.out.print(p.nextInEachLayer[0] + " ");      p = p.nextInEachLayer[0];    }    System.out.println();  }  public static void main(String[] args) {    SkipList skipList = new SkipList();    skipList.insert(3);    skipList.insert(1);    skipList.insert(2);    skipList.insert(6);    skipList.insert(9);    skipList.insert(8);    skipList.printAll();    System.out.println("跳表的当前高度:" + skipList.levelCount);    System.out.println("查找到的结果" + skipList.find(6));    System.out.println("++++++++++++++++删除节点之后打印数据++++++++++++++++++");    skipList.delete(6);    skipList.printAll();  }}

节点类

package com.yjz.example.跳表;/** * @author: yuanjinzhong * @date: 2023/1/28 2:49 PM * @description: *     跳表节点，存储正整数 *     
每个值只有一个node节点 *     
如何表示层级关系呢？ *     
使用{@linkplain nextInEachLayer[]}来表示该节点在不同层级的后驱节点 */public class Node {  // 数据域，默认-1，因为想存储正整数嘛  int data = -1;  /**   * 普通的链表使用next或者pre指针指向前驱和后继   *   * 
这里使用{@linkplain nextInEachLayer[]}来表示该节点在不同层级的后驱节点   *   * 数组下标表示层级   */  Node nextInEachLayer[];  // 该节点的最大层级  int maxLevelOfThisNode;  /**   * 新键节点的时候，就已经知道该节点有几层，就知道该节点需要维护几层的后驱节点   *   * @param level   */  Node(int level) {    this.maxLevelOfThisNode = level;    this.nextInEachLayer = new Node[level];  }  @Override  public String toString() {    StringBuilder builder = new StringBuilder();    builder.append("{ data: ");    builder.append(data);    builder.append("; levels: ");    builder.append(maxLevelOfThisNode);    builder.append(" }");    return builder.toString();  }}

关键词：以此类推