内网桌面监控软件中的Java跳表算法应用解析

import java.util.Random;
/**
 * 适配内网桌面监控软件的日志存储跳表实现
 * 存储结构：终端ID、操作时间戳、操作内容
 */
public class MonitorLogSkipList {
    // 跳表最大层级
    private static final int MAX_LEVEL = 16;
    // 随机层级生成器
    private final Random random = new Random();
    // 跳表表头（哨兵节点）
    private final SkipListNode head;
    // 当前跳表最高层级
    private int currentMaxLevel;
    // 跳表节点类
    private static class SkipListNode {
        String terminalId;       // 终端ID
        long timestamp;          // 操作时间戳（用于排序）
        String operationContent; // 操作内容
        // 各层级的下一个节点指针
        SkipListNode[] nextNodes;
        // 节点构造器
        public SkipListNode(String terminalId, long timestamp, String operationContent, int level) {
            this.terminalId = terminalId;
            this.timestamp = timestamp;
            this.operationContent = operationContent;
            this.nextNodes = new SkipListNode[level];
        }
    }
    // 跳表构造器
    public MonitorLogSkipList() {
        this.head = new SkipListNode(null, -1, null, MAX_LEVEL);
        this.currentMaxLevel = 1;
    }
    /**
     * 随机生成新节点的层级
     * 层级概率遵循几何分布，降低高层级节点占比
     */
    private int randomLevel() {
        int level = 1;
        // 50%概率提升层级，不超过最大层级
        while (random.nextDouble() < 0.5 && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }
    /**
     * 插入日志数据到跳表（按时间戳有序插入）
     * @param terminalId 终端ID
     * @param timestamp 操作时间戳
     * @param operationContent 操作内容
     */
    public void insert(String terminalId, long timestamp, String operationContent) {
        // 存储各层级待更新节点的前驱节点
        SkipListNode[] prevNodes = new SkipListNode[MAX_LEVEL];
        SkipListNode current = head;
        // 从最高层向下查找，定位插入位置
        for (int i = currentMaxLevel - 1; i >= 0; i--) {
            while (current.nextNodes[i] != null && current.nextNodes[i].timestamp< timestamp) {
                current = current.nextNodes[i];
            }
            prevNodes[i] = current;
        }
        // 生成新节点层级
        int newLevel = randomLevel();
        // 若新层级高于当前最高层级，补充前驱节点为表头
        if (newLevel > currentMaxLevel) {
            for (int i = currentMaxLevel; i < newLevel; i++) {
                prevNodes[i] = head;
            }
            currentMaxLevel = newLevel;
        }
        // 创建新节点并插入各层级
        SkipListNode newNode = new SkipListNode(terminalId, timestamp, operationContent, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode.nextNodes[i] = prevNodes[i].nextNodes[i];
            prevNodes[i].nextNodes[i] = newNode;
        }
    }
    /**
     * 按时间戳查询日志数据
     * @param timestamp 目标时间戳
     * @return 对应日志节点，无匹配时返回null
     */
    public SkipListNode search(long timestamp) {
        SkipListNode current = head;
        // 从最高层向下查找
        for (int i = currentMaxLevel - 1; i >= 0; i--) {
            while (current.nextNodes[i] != null && current.nextNodes[i].timestamp < timestamp) {
                current = current.nextNodes[i];
            }
        }
        // 定位到最底层，判断是否匹配
        current = current.nextNodes[0];
        return current != null && current.timestamp == timestamp ? current : null;
    }
    // 测试方法
    public static void main(String[] args) {
        MonitorLogSkipList skipList = new MonitorLogSkipList();
        // 模拟内网桌面监控软件采集的3条终端日志
        skipList.insert("TERM-001", 1758067200000L, "打开桌面文档：工作计划.docx");
        skipList.insert("TERM-002", 1758067500000L, "访问内网服务器：192.168.1.100");
        skipList.insert("TERM-001", 1758067800000L, "关闭浏览器进程：Chrome.exe");
        // 按时间戳查询日志
        SkipListNode log = skipList.search(1758067500000L);
        if (log != null) {
            System.out.println("查询到日志：");
            System.out.printf("终端ID：%s，时间戳：%d，操作内容：%s%n",
                    log.terminalId, log.timestamp, log.operationContent);
        } else {
            System.out.println("未查询到对应日志");
        }
    }
}