跳表：从理论到 Redis 实战，解锁「空间换时间」的终极数据结构

/**
 * 跳表节点
 * @author ken
 */
@Data
public class SkipListNode<T> {
    /**
     * 节点值
     */
    private T value;
    /**
     * 各层指针数组
     */
    private SkipListNode<T>[] next;

    @SuppressWarnings("unchecked")
    public SkipListNode(T value, int level) {
        this.value = value;
        this.next = new SkipListNode[level];
    }
}

/**
 * 跳表实现
 * @author ken
 */
@Slf4j
publicclass SkipList<T extends Comparable<T>> {
    /**
     * 最大层数
     */
    privatestaticfinalint MAX_LEVEL = 16;
    /**
     * 随机层数概率因子（50%）
     */
    privatestaticfinaldouble P = 0.5;
    /**
     * 头节点
     */
    private SkipListNode<T> head;
    /**
     * 当前跳表层数
     */
    privateint currentLevel;

    public SkipList() {
        this.currentLevel = 1;
        this.head = new SkipListNode<>(null, MAX_LEVEL);
    }
}

/**
 * 随机生成节点层数
 * @return 层数
 */
private int randomLevel() {
    int level = 1;
    while (Math.random() < P && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

/**
 * 查找节点
 * @param value 目标值
 * @return 目标节点（null 表示不存在）
 */
public SkipListNode<T> find(T value) {
    if (ObjectUtils.isEmpty(value)) {
        returnnull;
    }
    SkipListNode<T> current = head;
    // 从最高层开始查找，逐层下降
    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current.getNext()[i] != null && current.getNext()[i].getValue().compareTo(value) < 0) {
            current = current.getNext()[i];
        }
    }
    // 检查底层是否存在目标节点
    if (current.getNext()[0] != null && current.getNext()[0].getValue().equals(value)) {
        return current.getNext()[0];
    }
    returnnull;
}

/**
 * 插入节点
 * @param value 节点值
 */
public void insert(T value) {
    if (ObjectUtils.isEmpty(value)) {
        return;
    }
    // 记录每层需要更新的节点
    SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL];
    SkipListNode<T> current = head;

    // 从高层到低层查找插入位置
    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current.getNext()[i] != null && current.getNext()[i].getValue().compareTo(value) < 0) {
            current = current.getNext()[i];
        }
        update[i] = current;
    }

    // 生成新节点层数
    int newLevel = randomLevel();
    // 如果新层数超过当前层数，更新头节点的指针
    if (newLevel > currentLevel) {
        for (int i = currentLevel; i < newLevel; i++) {
            update[i] = head;
        }
        currentLevel = newLevel;
    }

    // 创建新节点并插入
    SkipListNode<T> newNode = new SkipListNode<>(value, newLevel);
    for (int i = 0; i < newLevel; i++) {
        newNode.getNext()[i] = update[i].getNext()[i];
        update[i].getNext()[i] = newNode;
    }
    log.info("插入节点 {}，层数 {}", value, newLevel);
}

/**
 * 删除节点
 * @param value 节点值
 */
public void delete(T value) {
    if (ObjectUtils.isEmpty(value)) {
        return;
    }
    // 记录每层需要更新的节点
    SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL];
    SkipListNode<T> current = head;

    // 从高层到低层查找删除位置
    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current.getNext()[i] != null && current.getNext()[i].getValue().compareTo(value) < 0) {
            current = current.getNext()[i];
        }
        update[i] = current;
    }

    // 检查是否存在目标节点
    current = current.getNext()[0];
    if (current == null || !current.getValue().equals(value)) {
        log.info("节点 {} 不存在", value);
        return;
    }

    // 删除节点（更新各层指针）
    for (int i = 0; i < currentLevel; i++) {
        if (update[i].getNext()[i] != current) {
            break;
        }
        update[i].getNext()[i] = current.getNext()[i];
    }

    // 更新当前跳表层数（如果最高层无节点）
    while (currentLevel > 1 && head.getNext()[currentLevel - 1] == null) {
        currentLevel--;
    }
    log.info("删除节点 {}", value);
}

/**
 * 跳表测试类
 * @author ken
 */
publicclass SkipListTest {
    public static void main(String[] args) {
        SkipList<Integer> skipList = new SkipList<>();
        // 插入节点
        skipList.insert(3);
        skipList.insert(1);
        skipList.insert(5);
        skipList.insert(7);
        skipList.insert(9);

        // 查找节点
        SkipListNode<Integer> node = skipList.find(5);
        System.out.println("查找节点 5：" + (node != null ? node.getValue() : "不存在"));

        // 删除节点
        skipList.delete(7);
        node = skipList.find(7);
        System.out.println("查找节点 7：" + (node != null ? node.getValue() : "不存在"));
    }
}

插入节点 3，层数 1
插入节点 1，层数 2
插入节点 5，层数 1
插入节点 7，层数 3
插入节点 9，层数 1
查找节点 5：5
删除节点 7
查找节点 7：不存在