跳表

简介: 跳表通过多层指针实现二分查找式访问,每层以不同步长连接节点,高层加速遍历,低层精确定位。查找时从高层开始,逐步降层逼近目标,时间复杂度O(log n)。为避免频繁调整结构,插入时用随机函数决定新节点层数,保证概率上的平衡性,兼顾效率与实现简便性。

跳表是如何进行二分查找的?

除了二叉检索树,有序链表还有其他快速访问中间节点的改造方案吗?我们知道,链表之所以访问中间节点的效率低,就是因为每个节点只存储了下一个节点的指针,要沿着这个指针遍历每个后续节点才能到达中间节点。那如果我们在节点上增加一个指针,指向更远的节点,比如说跳过后一个节点,直接指向后面第二个节点,那么沿着这个指针遍历,是不是遍历速度就翻倍了呢?

同理,如果我们能增加更多的指针,提供不同步长的遍历能力,比如一次跳过 4 个节点,甚至一半的节点,那我们是不是就可以更快速地访问到中间节点了呢?

这当然是可以实现的。我们可以为链表的某些节点增加更多的指针。这些指针都指向不同距离的后续节点。这样一来,链表就具备了更高效的检索能力。这样的数据结构就是 跳表(Skip List)。

一个理想的跳表,就是从链表头开始,用多个不同的步长,每隔 2^n 个节点做一次直接链接(n 取值为 0,1,2……)。跳表中的每个节点都拥有多个不同步长的指针,我们可以在每个节点里,用一个数组 next 来记录这些指针。next 数组的大小就是这个节点的层数,next[0]就是第 0 层的步长为 1 的指针,next[1]就是第 1 层的步长为 2 的指针,next[2]就是第 2 层的步长为 4 的指针,依此类推。你会发现,不同步长的指针,在链表中的分布是非常均匀的,这使得整个链表具有非常平衡的检索结构。

a7a1asa6a8a9a4a2a3

理想的跳表

举个例子,当我们要检索 k=a6 时,从第一个节点 a1 开始,用最大步长的指针开始遍历,直接就可以访问到中间节点 a5。但是,如果沿着这个最大步长指针继续访问下去,下一个节点是大于 k 的 a9,这说明 k 在 a5 和 a9 之间。那么,我们就在 a5 和 a9 之间,用小一个级别的步长继续查询。这时候,a5的下一个元素是 a7,a7 依然大于 k 的值,因此,我们会继续在 a5 和 a7 之间,用再小一个级别的步长查找,这样就找到 a6 了。这个过程其实就是二分查找。时间代价是 O(log n)。

跳表的检索空间平衡方案

不知道你有没有注意到,我在前面强调了一个词,那就是 「理想的跳表」。为什么要叫它「理想」的跳表呢?难道在实际情况下,跳表不是这样实现的吗?的确不是。当我们要在跳表中插入元素时,节点之间的间隔距离就被改变了。如果要保证理想链表的每隔 2^n 个节点做一次链接的特性,我们就需要重新修改许多节点的后续指针,这会带来很大的开销。

所以,在实际情况下,我们会在检索性能和修改指针代价之间做一个权衡。为了保证检索性能,我们不需要保证跳表是一个理想的平衡状态,只需要保证它在大概率上是平衡的就可以了。因此,当新节点插入时,我们不去修改已有的全部指针,而是仅针对新加入的节点为它建立相应的各级别的跳表指针。具体的操作过程,我们一起来看看。

首先,我们需要确认新加入的节点需要具有几层的指针。我们通过随机函数来生成层数,比如说,我们可以写一个函数 RandomLevel() ,以 (1/2)^n 的概率决定是否生成第 n 层。这样,通过简单的随机生成指针层数的方式,我们就可以保证指针的分布,在大概率上是平衡的。

在确认了新节点的层数 n 以后,接下来,我们需要将新节点和前后的节点连接起来,也就是为每一层的指针建立前后连接关系。其实每一层的指针链接,你都可以看作是一个独立的单链表的修改,因此我们只需要用单链表插入节点的方式完成指针连接即可。

这么说,可能你理解起来不是很直观,接下来,我通过一个具体的例子进一步给你解释一下。

相关文章
|
算法 NoSQL API
SpringCloud&Gateway网关限流
SpringCloud&Gateway网关限流
1922 7
|
前端开发 Java 测试技术
java通用分页(后端)
1.通用分页是什么? Java通用分页是指在Java编程语言中实现的一种通用分页功能。它通常用于在Java Web应用中展示大量数据或查询结果,并将其分页显示给用户。
667 1
|
9月前
|
Kubernetes 应用服务中间件 nginx
最全的kubectl命令用法
本文系统讲解kubectl命令行工具:详解所有子命令(创建、查询、部署、调试等)、API资源列表、自动补全配置,并通过大量实操示例(如创建/查看/编辑/删除资源、扩缩容、回滚、标签管理等)助你快速掌握Kubernetes集群管理核心技能。(239字)
1261 143
|
3月前
|
Kubernetes 应用服务中间件 nginx
Kubernetes (K8s) 从入门到实战:命名空间、Pod、Controller、Service,图文并茂
本文是K8s初学者的实战笔记,系统讲解命名空间(隔离资源、环境划分、权限控制)、Pod(最小调度单元、多容器、标签、生命周期、探针、资源限制)、控制器(Deployment灰度发布/回滚、StatefulSet/Job/DaemonSet)及Service(ClusterIP/NodePort、负载均衡、多端口)等核心概念与操作,附带丰富命令示例和原理剖析。
Kubernetes (K8s) 从入门到实战:命名空间、Pod、Controller、Service,图文并茂
|
11月前
|
存储 Serverless
哈希冲突
哈希冲突可通过优化哈希函数或采用冲突解决策略应对。开放寻址法通过线性、二次探查或双散列寻找空位,但易导致聚集,影响效率;链表法则在冲突位置构建链表,避免抢占,更适应动态数据,是常用方案之一。
|
8月前
|
存储 人工智能 网络安全
保姆级教程:OpenClaw 阿里云/本地部署及集成 Skills 步骤,立即让 AI 干活!
如果说OpenClaw与大模型的组合是给AI助理赋予了“智能大脑”,那么Skills就是为它装上了“灵活手脚”。作为OpenClaw的核心扩展能力,Skills是可安装、可卸载的功能模块,能够让基础版OpenClaw突破原生限制,解锁网页浏览、邮件管理、文件处理、多平台交互等复杂操作。截至2026年2月,Clawhub(OpenClaw官方技能市场)已收录超过5700个各类Skills,覆盖办公、开发、娱乐、生活等多场景,安装量最高的技能下载量突破2000次,成为提升OpenClaw实用性的关键。
3087 8
|
7月前
|
存储 安全 前端开发
【微服务】微服务安全:OAuth2.0、JWT、SSO单点登录、RBAC权限模型
本文系统梳理微服务安全四大核心:OAuth2.0(授权协议)、JWT(无状态凭证)、SSO(统一认证)、RBAC(权限模型),从边界定位、原理剖析、落地规范到协同架构四维展开,厘清分层职责与互补关系,提供企业级可落地的安全闭环实践指南。
1362 1
|
数据采集 前端开发 Java
职责分离的艺术:剖析主从Reactor模型如何实现极致的并发性能
Reactor单线程模型中,I/O操作由单一线程处理,但业务逻辑若同步执行会阻塞线程,影响性能。为此,引入工作者线程池模型,将非I/O任务剥离至独立线程池,提升响应速度。进一步发展为主从多线程模型:MainReactor处理连接建立,SubReactor多线程管理读写,并结合过滤器链实现数据预处理,异步编程提升并发效率。该架构职责分明、扩展性强,广泛应用于Netty等高性能框架,支持百万级并发。
515 11
|
11月前
|
存储 弹性计算 人工智能
大模型应用开发
大模型应用开发指通过API与大模型交互,构建智能化应用。不同于传统Java开发,其核心在于调用部署在云端或本地的大模型服务。企业可选择开放API、云平台或本地服务器部署,各具成本、安全与性能权衡。本章将详解部署方式与开发实践,助你快速入门。
|
11月前
|
存储 NoSQL 关系型数据库
Geohash 编码
Geohash编码将经纬度转换为字符串,通过不断二分地球经纬度区间,交叉组合生成区域编码,再转为Base32简化表示。它用于高效存储和查询地理位置,广泛应用于Redis、MySQL等系统,具有相同前缀的编码代表相近区域,便于空间索引与检索。