java代码如何实现跳表及查找插入操作 java代码跳表结构的应用实现方法​

// 解决方案：跳表的Java实现及查找插入操作

import java.util.Random;

/**
 * 跳表节点
 */
class SkipListNode<T extends Comparable<T>> {
    T value;
    // forward[i] 指向当前节点在第 i 层的下一个节点
    SkipListNode<T>[] forward;

    @SuppressWarnings("unchecked")
    public SkipListNode(T value, int level) {
        this.value = value;
        this.forward = new SkipListNode[level + 1]; // level是从0开始的
    }
}

/**
 * 跳表实现
 */
class SkipList<T extends Comparable<T>> {
    private static final double P = 0.5; // 概率因子，通常取0.5或0.25
    private static final int MAX_LEVEL = 32; // 最大层数，可以根据数据量调整

    private SkipListNode<T> head; // 头节点
    private int level; // 当前跳表的最高层级
    private Random random;

    @SuppressWarnings("unchecked")
    public SkipList() {
        this.head = new SkipListNode<>(null, MAX_LEVEL); // 头节点的值为null，层数设为最大
        this.level = 0;
        this.random = new Random();
    }

    /**
     * 随机生成新节点的层级
     * 抛硬币，直到出现反面，每出现一次正面层级加1
     */
    private int randomLevel() {
        int lvl = 0;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

    /**
     * 插入操作
     */
    @SuppressWarnings("unchecked")
    public void insert(T value) {
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<T> current = head;

        // 从最高层开始，找到每一层插入位置的前一个节点
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
            update[i] = current; // 记录下这一层需要更新的节点
        }

        // 如果值已经存在，通常选择不插入或更新，这里选择不插入
        if (current.forward[0] != null && current.forward[0].value.compareTo(value) == 0) {
            // System.out.println("Value " + value + " already exists.");
            return;
        }

        // 生成新节点的随机层级
        int newLevel = randomLevel();

        // 如果新层级超过当前跳表的最高层级，需要更新头节点指向
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head; // 新增的层级，头节点就是前一个节点
            }
            level = newLevel; // 更新跳表的最高层级
        }

        // 创建新节点
        SkipListNode<T> newNode = new SkipListNode<>(value, newLevel);

        // 调整指针，将新节点插入到每一层
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
        // System.out.println("Inserted: " + value + " at level " + newLevel);
    }

    /**
     * 查找操作
     */
    public SkipListNode<T> search(T value) {
        SkipListNode<T> current = head;

        // 从最高层开始向下查找
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
        }

        // 到达0层，检查下一个节点是否是目标值
        current = current.forward[0];

        if (current != null && current.value.compareTo(value) == 0) {
            // System.out.println("Found: " + value);
            return current;
        } else {
            // System.out.println("Not Found: " + value);
            return null;
        }
    }

    /**
     * 删除操作（为完整性提供，但重点在查找插入）
     */
    @SuppressWarnings("unchecked")
    public void delete(T value) {
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<T> current = head;

        // 查找待删除节点，并记录每一层的前一个节点
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        current = current.forward[0];

        // 如果找到了目标值
        if (current != null && current.value.compareTo(value) == 0) {
            // 调整指针，跳过待删除节点
            for (int i = 0; i <= level; i++) {
                if (update[i].forward[i] != current) {
                    // 如果这一层的update[i]的下一个节点不是current，说明current不在这一层，跳过
                    continue;
                }
                update[i].forward[i] = current.forward[i];
            }

            // 检查并降低跳表的最高层级
            while (level > 0 && head.forward[level] == null) {
                level--;
            }
            // System.out.println("Deleted: " + value);
        } else {
            // System.out.println("Value " + value + " not found for deletion.");
        }
    }

    // 辅助方法：打印跳表（可选）
    public void printList() {
        System.out.println("SkipList (Current Level: " + level + "):");
        for (int i = level; i >= 0; i--) {
            System.out.print("Level " + i + ": ");
            SkipListNode<T> node = head.forward[i];
            while (node != null) {
                System.out.print(node.value + " -> ");
                node = node.forward[i];
            }
            System.out.println("NULL");
        }
        System.out.println("---");
    }
}

ConcurrentSkipListMap

ConcurrentSkipListSet

P

MAX_LEVEL

P

0.5

0.25

P = 0.5

MAX_LEVEL

0.5

MAX_LEVEL

32

64