Python无内置跳表，因sortedcontainers等非跳表结构无法兼顾O(log n)查找与O(1)均摊插入；须手写SkipListNode（含forward指针数组）、正确实现random_level（抛硬币法）及搜索/插入/删除逻辑。
Python 没有内置跳表，必须手写；用 sortedcontainers 或 blist 代替会失效——它们不是跳表，不提供 O(log n) 查找 + O(1) 均摊插入的组合优势。
为什么不能直接 pip install 一个跳表
Python 标准库和主流第三方包里，bisect 只支持数组二分，sorteddict 底层是红黑树，sortedlist（来自 sortedcontainers）本质是分块数组。这些结构：
- 查找快，但插入/删除要移动数据或重平衡，不是均摊 O(1)
- 不具备跳表特有的“随机层级指针数组”结构，无法复现其概率索引行为
- 无法满足高并发下低锁粒度的有序集合需求（比如仿 Redis Sorted Set 的轻量内存索引）
所以，真要跳表，就得自己定义节点、维护多层 forward 指针、实现带层级的搜索路径。
SkipListNode 和 forward 数组怎么设计
每个节点必须携带一个指针列表，而非单个 next：
class SkipListNode:
def __init__(self, key, value, level):
self.key = key
self.value = value
self.forward = [None] * (level + 1) # level 从 0 开始，共 level+1 层指针
关键点：
- self.forward[i] 表示该节点在第 i 层指向的下一个节点
- 插入时若新节点高度为 h，就要在 0 到 h 层都设置 forward，不能只设最高层
- 删除时必须逐层断开，漏掉某一层会导致后续搜索跳过目标节点
- 头节点 header 高度应设为最大允许层数（如 16），避免每次插入都要 realloc 指针数组
random_level() 的概率陷阱
常见错误是写成固定层数或简单 randint(1, max_level)，这会破坏跳表的期望性能：
- 正确做法是模拟“抛硬币”：每轮以概率
p（通常取0.5）决定是否升层，直到失败或达到max_level - 错误写法：
random.randint(1, max_level)→ 各层概率均等，高层节点过多，空间爆炸 - 更糟写法：
int(math.log2(n)) + 1→ 依赖当前长度，插入时需全局扫描，退化成 O(n) - 生产环境建议加限高：即使随机结果超限，也截断到
max_level，防止极端情况拉垮内存
参考实现：
让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限
def random_level(self):
level = 0
while random.random() <h3>搜索时为什么必须从 <code>self.level</code> 而非 <code>self.max_level</code> 开始</h3><p>因为 <code>self.level</code> 是当前跳表实际使用的最高层（动态变化），而 <code>self.max_level</code> 是预分配上限：</p>
- 刚初始化时
self.level == 0，若硬从self.max_level（比如 16）开始遍历，会空跑 16 层None指针，徒增开销 - 插入新节点后，若其高度超过当前
self.level，才更新self.level = max(self.level, new_node.level) - 删除节点不会降低
self.level—— 降级需全表扫描，得不偿失；保留高位不影响正确性，只是略微浪费几层空指针
所以搜索循环必须是：
for i in range(self.level, -1, -1): # 注意是 self.level，不是 self.max_level
真正的复杂点不在算法逻辑，而在于：指针数组的内存布局、层级更新的时机、以及随机过程与实际层数的松耦合——这些细节稍错一点，O(log n) 就变成 O(n) 或内存泄漏。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
