第 7 篇：跳表 (Skip List)：简单务实的概率性选手
前面几篇我们都在探讨各种基于“树”结构的有序表实现，它们通过精巧的平衡策略（高度、颜色、大小）和核心的“旋转”操作来保证 O(log N) 的性能。今天，我们要介绍一位画风完全不同的选手——跳表 (Skip List)。它不依赖树形结构，也不需要复杂的旋转，而是巧妙地利用概率和多层链表，同样实现了平均 O(log N) 的高效查找、插入和删除。
核心思想：链表 + 多级“快车道”索引
跳表的设计灵感非常直观，可以类比我们之前提到的地铁系统：
- 基础层 (Level 0): 就是一条普通的有序链表，包含所有的数据元素。这是“站站停”的慢车线，保证了数据的完整性和有序性。
- 多级索引层 (Higher Levels): 在基础层之上，随机地抽取一部分节点，形成更高一层的“稀疏”链表，作为索引。层级越高，节点越稀疏，跨度越大，就像地铁的“快车线”、“特快线”。
Level 2: H --------------------------------> 50 ------------> null| |
Level 1: H --------> 25 ------------------> 50 --------> 75 -> null| | | |
Level 0: H --> 10 --> 25 --> 30 --> 38 --> 50 --> 60 --> 75 --> 90 --> null
(H 代表头节点 Head)
- 查找过程: 从最高层的“特快线” (Level 2) 开始，向右查找，直到找到最后一个小于目标值的节点（比如要找 65，在 Level 2 找到 50）。然后从该节点下降到下一层“快车线” (Level 1)，继续向右查找（从 50 开始，找到 50）。再下降到“慢车线” (Level 0)，继续向右查找（从 50 开始，找到 60）。发现下一个节点 75 大于 65，查找结束（如果需要精确查找，则检查 60 的下一个节点是否是 65）。
通过这种方式，高层索引帮助我们快速“跳过”大量节点，大幅减少了查找所需的比较次数。
平衡的“魔法”：随机化层高 (The Magic of Randomness)
跳表是如何决定哪些节点可以进入“快车道”，以及一个节点应该出现在多少层“快车道”上的呢？答案是——随机化 (Randomization)！
当插入一个新节点时：
- 它首先肯定会被插入到 Level 0 的基础链表中。
- 然后，进行一次“抛硬币”（比如生成一个 0 到 1 的随机数）。如果结果满足某个条件（比如小于概率 p，通常 p=0.5 或 p=0.25），那么这个节点也被提升到 Level 1，并插入到 Level 1 的链表中。
- 如果成功提升到 Level 1，就再次抛硬币，决定是否提升到 Level 2。
- 以此类推，直到抛硬币结果不再满足提升条件，或者达到了预设的最大层级 MAX_LEVEL。
这个随机化的过程，使得：
- 平均来看，大约有 p 比例的 Level i 的节点会出现在 Level i+1。
- 层级越高，节点越稀疏。
- 虽然单个节点的层高是随机的，但从整体上看，这种多层结构在概率上是平衡的，能够保证查找、插入、删除操作的平均时间复杂度达到 O(log N)。
权衡与优缺点
-
优点:
- 实现相对简单: 相比平衡树复杂的旋转逻辑，跳表的插入和删除主要涉及链表节点的指针修改，逻辑更清晰，代码更容易编写和理解。
- 插入/删除高效: 操作通常只影响局部节点，平均性能很好，且在并发场景下更容易实现高效的锁策略（相比整棵树可能需要调整的平衡树）。
- 范围查询友好: 底层是有序链表，执行范围查询非常自然和高效。
-
缺点:
- 概率性保证: 它的 O(log N) 性能是平均情况下的，虽然概率极低，但理论上存在性能退化到 O(n) 的最坏情况（比如所有节点都只停留在 Level 0）。而平衡树提供的是确定性的 O(log N) 最坏情况保证。
- 空间开销: 每个节点平均包含 1 / (1 - p) 个 right 指针（加上 down 指针），相比平衡树的固定 2 个子节点指针，其空间开销通常会稍大一些（但仍然是 O(n) 级别）。
一句话选型总结 (跳表)
跳表: 实现内存有序表时，若看重实现简单性、写性能和范围查询效率，且能接受概率性性能保证，跳表是优秀选择。
实际项目思考 (Java & Beyond)
- Redis 的 ZSet (Sorted Set): 这是跳表最著名、最成功的应用案例之一！ZSet 需要支持按 Score 排序、快速增删改成员、按 Score 范围查询、按排名查询等多种操作。跳表完美地契合了这些需求，其简单的实现和良好的综合性能是 Redis 选择它的重要原因。
- LevelDB / RocksDB 的 MemTable: 这些键值存储引擎在内存中使用跳表来组织数据（MemTable），因为跳表支持快速写入和高效的范围扫描，便于后续将数据刷写到磁盘。
- 高并发有序数据结构: 在一些需要高并发读写的有序场景下，跳表基于链表的操作特性使得其锁粒度更容易控制（例如，可以只锁住相关的节点），相比需要旋转可能影响更大范围节点的平衡树，更容易设计出高性能的并发实现。Java 的 java.util.concurrent.ConcurrentSkipListMap 和 ConcurrentSkipListSet 就是基于跳表实现的线程安全的有序集合。
跳表以其独特的设计哲学——用简单的概率机制代替复杂的确定性平衡算法——在数据结构的世界里占据了一席之地。它证明了在很多时候，“足够好”的概率性保证加上实现的简单性，比追求理论上的完美更具工程价值。
下一篇，我们将把目光投向处理海量数据、面向磁盘存储场景的王者——B/B+ 树。
相关文章：
：简单务实的概率性选手)
第 7 篇：跳表 (Skip List)：简单务实的概率性选手
前面几篇我们都在探讨各种基于“树”结构的有序表实现，它们通过精巧的平衡策略（高度、颜色、大小）和核心的“旋转”操作来保证 O(log N) 的性能。今天，我们要介绍一位画风完全不同的选手——跳表 (Skip List)。它不依赖树形结构&a…...
sys目录介绍
文章目录 1. 前言2. 目录层次3. 目录介绍3.1 devices 目录3.2 block 目录3.3 bus 目录3.4 class 目录3.5 dev 目录3.6 firmware目录3.7 fs 目录3.8 kernel目录3.9 module 目录3.10 power 目录 sys目录介绍 1. 前言 linux 下一切皆文件，文件的类型也很多，…...
基于DQN的自动驾驶小车绕圈任务
1.任务介绍 任务来源: DQN: Deep Q Learning ｜自动驾驶入门（？） ｜算法与实现 任务原始代码: self-driving car 最终效果： 以下所有内容，都是对上面DQN代码的改进&#…...
源码安装SRS4
Ubuntu20安装好SRS后，（源码安装） 注意：在trunk目录SRS ./objs/srs -c conf/srs.conf 以上为启动srs命令，-c 为指定配置文件， 查看SRS进程 ps aux | grep srs 查看端口： netstat -ano | gre…...
OrbitControls
OrbitControls 3D虚拟工厂在线体验 描述 Orbit controls（轨道控制器）可以使得相机围绕目标进行轨道运动。 Constructor OrbitControls( object : Camera, domElement : HTMLDOMElement ) 参数类型描述objectCamera（必须）将要…...
【数据库】四种连表查询：内连接，外连接，左连接，右连接
在数据库操作中，连表查询是处理多表关联的核心技术。以下是四种主要连接方式的详细介绍、快速掌握方法及实际应用指南： 目录 **一、四种连表查询详解****1. 内连接（INNER JOIN）****2. 左连接（LEFT JOIN / LEFT OUTER J…...
Redis怎么避免热点数据问题
使用 RedisTemplate 避免热点数据问题的解决方案、场景及示例： 1. 数据分片（Sharding） 场景：高频读写的计数器（如文章阅读量统计） 原理：将数据分散到多个子键，降低单个 Key 的压…...
完整的 VS Code + CMake + Qt + GCC 项目构建方案：EXE 程序与多个 DLL 库
完整的 VS Code CMake Qt GCC 项目构建方案：EXE 程序与多个 DLL 库 在本文中，我们将介绍如何构建一个包含 EXE 程序和多个 DLL 库的项目，适用于 VS Code CMake Qt GCC 开发环境。这个方案为一个模块化的项目结构，使得代码清…...
：智能流失预警 - 融合文本反馈)
Python 数据智能实战 (7)：智能流失预警 - 融合文本反馈
写在前面 —— 不再错过关键预警！结合用户行为与 LLM 文本洞察，构建更精准的流失预测模型 在之前的探索中，我们学习了如何利用大语言模型 (LLM) 对用户评论进行深度挖掘，提取情感、发现主题，并将非结构化的文本信息转化为有价值的特征 (如 Embeddings)。 现在，我们要将…...
Flutter - 概览
Hello world ⌘ shift p 选择 Empty Application 模板 // 导入Material风格的组件包 // 位置在flutter安装目录/packages/flutter/lib/material.dart import package:flutter/material.dart;void main() {// runApp函数接收MainApp组件并将这个Widget作为根节点runApp(cons…...
及Excel表格列名操作详细分享)
Python-pandas-操作Excel文件(读取数据/写入数据)及Excel表格列名操作详细分享
Python-pandas-操作Excel文件(读取数据/写入数据) 提示：帮帮志会陆续更新非常多的IT技术知识，希望分享的内容对您有用。本章分享的是pandas的使用语法。前后每一小节的内容是存在的有：学习and理解的关联性。【帮帮志系列文章】：每…...
手写 Vue 源码 === Vue3 设计思想
1.声明式框架 Vue3 是声明式的框架，用起来简单。 命令式和声明式区别 早在 JQ 的时代编写的代码都是命令式的，命令式框架重要特点就是关注过程声明式框架更加关注结果。命令式的代码封装到了 Vuejs 中，过程靠 vuejs 来实现声明式代码更加简单，不需要关注实现，按照要求填代…...
Android WebView加载h5打开麦克风与摄像头的权限问题
目录 快速处理 app向系统申请录音与相机权限h5向app申请录音和相机权限 详细解答 app权限与h5权限录音与麦克风默许的风险最佳实践 Android webview h5 麦克风权限，摄像头（相机）权限实现与填坑。 快速处理 app向系统申请录音与相机权限 …...
三种计算最小公倍数的方法分析
三种计算最小公倍数的方法分析与比较 一.引言 最小公倍数（Least Common Multiple, LCM）是数学中的一个基本概念，指能够被两个或多个整数整除的最小的正整数。在编程中，我们有多种方法可以计算两个数的最小公倍数。本文将分析三种…...
PDF转换工具xpdf-tools-4.05
XPDF是一个开源的PDF查看、提取和转换工具套件，使用C编写，支持多种操作系统，包括Linux、Unix、OS/2、Windows和Mac OS X1。XPDF不仅是一个PDF查看器，还包含多个实用工具，如文本提取器、图像转换器和HTML转换器等&a…...
 image-content-search)
aws(学习笔记第四十课) image-content-search
aws(学习笔记第四十课) image-content-search 使用SQS Lambda集成 数据库（Aurora Serverless） Cognito（用户管理） rekognition（图像解析） 学习内容： 使用SQS Lambda Aurora Serverless Cog…...
GPT-4o 图像生成与八个示例指南
什么是GPT-4o图像生成？ 简单来说，GPT-4o图像生成是集成在ChatGPT内部的一项功能。用户可以直接在对话中，通过文本描述（Prompt）来创建、编辑和调整图像。这与之前的图像生成工具相比，体验更流畅、交互性更强…...
PostgreSQL 查看表膨胀情况的方法
PostgreSQL 查看表膨胀情况的方法 表膨胀(Table Bloat)是PostgreSQL中由于MVCC机制导致的一种常见现象，当大量数据被更新或删除后，表中会积累"死元组"(dead tuples)，这些死元组占据空间但不可见，导致表实际占用的磁盘空…...
从 0 到 1！深度剖析项目实施流程，开启项目管理新视野
一、项目准备 / 前期准备 （一）跟销售进行项目交接 对接人：销售人员交接会议内容： 了解项目背景、客户基本信息、项目版本、具备二次开发功能、接口、了解合同信息等。明确项目情况、客户基本情况、使用软件（版本&…...
书生实战营之沐曦专场
一：实验环境进入和启动实验容器(D.run平台) 1.1首先进入平台进行注册 D.run平台https://console.d.run/ 注册和登录环节就跳过了。 1.2 启动实验容器--详细步骤如下 1.2.1选择容器的名称、区域、镜像（注意镜像必须选择Dlinfer） 1.2.2可以选…...
在运行 Hadoop 作业时，遇到“No such file or directory”，如何在windows里打包在虚拟机里运行
最近在学习Hadoop集群map reduce分布运算过程中，经多方面排查可能是电脑本身配置的原因导致每次运行都会报“No such file or directory”的错误，最后我是通过打包文件到虚拟机里运行得到结果，具体步骤如下： 前提是要保证maven已经…...
基于YOLOV5的目标检测识别
基于YOLOV5的目标检测识别 舰船目标检测口罩目标检测飞机目标检测 舰船目标检测 口罩目标检测 飞机目标检测...
第4篇：服务层抽象与复用逻辑
在业务系统复杂度指数级增长的今天，服务层（Service Layer）的合理设计直接影响着系统的可维护性和扩展性。本文将深入剖析 Egg.js 框架中的服务层架构设计，从基础实现到高级封装，全方位讲解企业级应用的开发实践。 一、…...
多模态大语言模型arxiv论文略读（五十四）
RoboMP 2 ^2 2: A Robotic Multimodal Perception-Planning Framework with Multimodal Large Language Models ➡️ 论文标题：RoboMP 2 ^2 2: A Robotic Multimodal Perception-Planning Framework with Multimodal Large Language Models ➡️ 论文作者ÿ…...
中小企业MES系统详细设计
版本：V1.1 日期：2025年5月2日 一、设备协议兼容性设计 1.1 设备接入框架 #mermaid-svg-PkwqEMRIIlIBPP58 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-PkwqEMRIIlIBPP58 .error-icon{fill…...
)
第二十周:项目开发中遇到的相关问题(一)
自十九周开始，我们便开始着手写项目（关于新闻资讯类的Web项目），当然，在这之中我们也学到了很多高效且有用的好技术，在接下来的内容中将去具体的描述这些好技术，介绍它们的具体用法和应用场景。本…...
WebRtc10: 端对端1v1传输基本流程
媒体能力协商过程 RTCPeerConnection（核心类） 基本格式 pc new RTCPeerConnection([configiration]); RTCPeerConnection方法分类 媒体协商Stream/Track传输相关方法统计相关方法 媒体协商过程 协商状态变化 媒体协商方法 createOffercreateAnswe…...
【云备份】配置文件加载模块
目录 一.为什么要配置文件 二.配置文件的实现 三.单例文件配置类设计 四.源码 一.为什么要配置文件 我们将服务端程序运行中用到的一些关键信息保存到配置文件中，这样可以使程序的运行更加灵活。 这样做的好处是，未来如果我们想要修改一些关键信息&…...
重构之道：识别并替换不合适使用的箭头函数
1、引言 JavaScript 自 ES6 引入了箭头函数（Arrow Function）后，因其简洁的语法和对 this 的词法绑定机制，迅速成为开发者喜爱的写法之一。然而，并不是所有场景都适合使用箭头函数。 在实际开发中，我们常常会因为追求代码简洁而忽视其潜在问题，例如： this 指向错误不适…...
git问题记录-如何切换历史提交分支，且保留本地修改
问题记录 我在本地编写了代码，突然想查看之前提交的代码，并且想保留当前所在分支所做的修改 通过git stash对本地的代码进行暂存 使用git checkout <commit-hash>切换到之前的提交记录。 查看完之后我想切换回来，恢复暂存的本地代码…...
【MySQL】事务管理
事务管理 一. 事务的概念二. 事务的特征三. 事务的版本支持四. 事务的提交方式五. 事务的常见操作六. 事务的隔离级别1. 查看与设置隔离级别2. 读未提交 (Read Uncommitted)3. 读提交 (Read Committed)4. 可重复读 (Repeatable Read)5. 串行化 (Serializable)6. 隔离级别的总结…...
【点对点协议（PPP）全解析】从原理到工程实践
目录 前言技术背景与价值当前技术痛点解决方案概述目标读者说明 一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比 二、实战演示环境配置要求核心配置实现案例1：基础PPP链路建立案例2：CHAP认证配置 运行结果验证 三、性能对比测试…...
环境搭建：开启 Django 开发之旅
一、环境搭建：开启 Django 开发之旅 （一）安装 Python 先确保电脑上装有 Python 3.6 及以上版本，Django 5.1 的话，至少得 Python 3.8 哦。 安装前，先查下有没有装过 Python ，终端（Wi…...
如何配置NGINX作为反向代理服务器来缓存后端服务的响应？
大家好，我是锋哥。今天分享关于【如何配置NGINX作为反向代理服务器来缓存后端服务的响应？】面试题。希望对大家有帮助； 如何配置NGINX作为反向代理服务器来缓存后端服务的响应？ 1000道 互联网大厂Java工程师 精选面试题-Java资源…...
【Java IO流】File类基础详解
参考笔记：java File类基础 万字详解（通俗易懂）-CSDN博客 目录 1.前言 2. File类介绍 3. File类构造方法 4.File类常用的方法案例演示 4.1 创建文件/文件夹的方法 4.2 删除文件/文件夹的方法 4.3 判断文件/文件夹是否存在的方法 4.4 …...
《C#数据结构与算法》—201线性表
线性表的实现方式 顺序表 线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表。 特点：表中相邻的数据元素在内存中存储位置也相邻。 顺序表接口实现： 方法名参数返回值描述GetLen…...
MATLAB绘制局部放大图
今天，我将分享一段 MATLAB 代码，该代码生成了一个主副图结合的可视化展示，用于比较不同控制系统性能表现。 clc; clear; close all;% 生成时间向量 t 0:0.1:12;% 生成模拟数据 zero_feedback 0.5 * ones(size(t)); % 恒定…...
TS 常用类型
JS不会检查变量类型的变化 给变量规定特定的数据类型，错误赋值时会报错 优势：TS会标记出代码中的意外行为，尤其是typeerrors 具体实现：类型注解 JS和TS中数据类型的变化...
)
[Control-Chaos] Toxic Cascade(毒性級鏈)
信息 信息描述靶場名稱Toxic Cascade地址GitHub: Toxic Cascade難度中等人數推薦1人類型CTF、APT 攻擊模擬、故事解謎、化工工程與逆向工程描述Toxic Cascade 是一個結合 CTF、APT 攻擊模擬、故事解謎、化工工程與逆向工程的高度沉浸式靶場。該靶場具有獨特的情境背景與模擬真…...
纳米AI搜索体验：MCP工具的实际应用测试，撰写报告 / 爬虫小红书效果惊艳
1. 引言 近期测试了纳米AI搜索的MCP工具功能，重点体验了其智能体在报告生成和社交媒体数据分析方面的表现。平台整合了100多个MCP工具，通过本地化部署的方式，为用户提供了不同于云端方案的操作体验。本文将分享实际测试结果，包括智…...
React useMemo函数
第一个参数是回调函数，返回计算的结果，第二个参数是依赖项，该函数只监听count1变量的变化 import { useReducer, useState } from react; import ./App.css;// 定义一个Reducer函数 根据不同的action进行不同的状态修改 function reducer(st…...
第 1 篇：起点的选择：为何需要超越数组与链表？
大家好，欢迎来到“数据结构选型指南”系列！在软件开发中，数据是核心，而如何高效地组织和访问这些数据，则是程序性能的关键。选择合适的数据结构，就像为你的 Java 应用选择最优的“引擎零件”。今天…...
MySQL 索引不生效的情况
MySQL 索引不生效的 SQL 查询需要避免的情况 索引是提高 MySQL 查询性能的关键，但某些 SQL 写法会导致索引失效，从而影响查询效率。以下是需要避免的常见情况： 1. 使用 NOT、! 或 <> 操作符 -- 索引可能失效 SELECT * FROM users WH…...
)
【阿里云大模型高级工程师ACP学习笔记】2.9 大模型应用生产实践 (上篇)
特别说明：由于这一章节是2025年3月官方重点更新的部分，新增内容非常多，因此我不得不整理成上、下两篇，方便大家参考。 学习目标 备考阿里云大模型高级工程师ACP认证，旨在全面掌握大模型应用生产实践的专业知识，提升在该领域的实操技能与理论水平，为职业发展增添助力。具…...
STM32 ZIBEE DL-20 无线串口模块
一.配置方法 二.串口中断 u8 i; u16 buf[20],res; u8 receiving_flag 0; // 新增一个标志，用于标记是否开始接收数组 void USART1_IRQHandler(void) {if(USART_GetITStatus(USART1, USART_IT_RXNE) ! RESET) //接收中断{res USART_ReceiveData(USART1);if(receiv…...
【算法基础】选择排序算法 - JAVA
一、算法基础 1.1 什么是选择排序 选择排序是一种简单直观的排序算法，它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小…...
FastAPI 与数据库交互示例
目录 安装必要的包完整代码示例运行应用使用说明API 端点说明代码解析 下面将创建一个简单的 FastAPI 应用程序，演示如何与 SQLite 数据库进行交互。这个例子包括创建、读取、更新和删除（CRUD）操作。 安装必要的包 首先，需要安装…...
（六——下）RestAPI 毛子（Http resilience/Refit/游标分页）
文章目录 项目地址一、Refit1.1 安装需要的包1.2 创建接口IGitHubApi1.3 创建RefitGitHubService1. 实现接口2. 注册服务 1.4 修改使用方法 二、Http resilience2.1 安装所需要的包2.2 创建resilience pipeline简单版2.3 创建全局的resilience处理1. 创建清理全局ResilienceHan…...
Rust 学习笔记：关于枚举与模式匹配的练习题
Rust 学习笔记：关于枚举与模式匹配的练习题 Rust 学习笔记：关于枚举与模式匹配的练习题以下程序能否通过编译？若能，输出是什么？考虑这两种表示结果类型的方式，若计算成功，则包含值 T；…...
父子组件双向绑定
v-model 语法糖实现 vue中我们在input中可以直接使用v-model来完成双向绑定，这个时候 v-model 通常会帮我们完成两件事： v-bind:value的数据绑定@input的事件监听如果我们现在封装了一个组件，其他地方在使用这个组件时，是否也可以使用v-model来同时完成这两个功能呢？ 当我…...