跳表层级用随机概率而非固定高度，因随机晋升（如p=0.5）可保证平均O(n)空间与O(log n)查找，避免固定层数导致的重平衡、内存浪费和扩展性差。
跳表的层级设计为什么用随机概率而非固定高度
跳表不是靠预设层数来加速查找，而是让每个新节点以 p = 0.5（或 1/4、1/e）的概率向上“晋升”一层。这样能保证平均空间复杂度为 O(n)，同时查找期望时间仍是 O(log n)。硬编码固定层数（比如统一 5 层）会导致：插入时频繁重平衡、内存浪费严重、无法动态适应数据规模。
实践中推荐用 rand() % 2 == 0 模拟 p = 0.5，或更严谨地用 static std::random_device rd; static std::mt19937 gen(rd()); std::bernoulli_distribution d(0.5);。避免用 rand() % k 做多级判断——容易因低比特劣质导致层级分布偏差。
核心结构体怎么组织才便于插入和删除
每个节点必须持有指向**同一层右侧节点**和**下一层同位置节点**的指针，不能只存“下一个”或“下面一个”。典型结构是：std::vector，其中 forward[i] 指向第 i 层的后继节点。头节点（header）需初始化为最大可能层数（如 MAX_LEVEL = 32），但实际使用中每层只在有节点跨越时才有效。
- 插入前必须从顶层开始逐层搜索，记录每层最后访问的节点（即
update[i]），这是删除和插入修正指针的关键 - 删除时只需沿
update数组向下修复指针，无需重新搜索 - 节点构造时用
new Node(level)分配forward数组，避免 vector 动态扩容干扰缓存局部性
如何正确实现 search / insert / delete 的指针更新逻辑
三者共用同一套“搜索路径捕获”逻辑：从 header 出发，对每一层 i 从左到右移动，直到 next->key >= target，记录该层最后停留的节点为 update[i]。区别仅在于后续操作：
立即学习“C++免费学习笔记（深入）”；
Node* SkipList::search(int key) {
Node* x = header;
for (int i = level; i >= 0; i--) {
while (x->forward[i] && x->forward[i]->key < key)
x = x->forward[i];
}
x = x->forward[0];
return x && x->key == key ? x : nullptr;
}
void SkipList::insert(int key, int value) {
std::vector> update(MAX_LEVEL + 1, header);
Node x = header;
for (int i = level; i >= 0; i--) {
while (x->forward[i] && x->forward[i]->key < key)
x = x->forward[i];
update[i] = x;
}
x = new Node(key, value, randomLevel());
if (x->level > level) {
for (int i = level + 1; i <= x->level; i++)
update[i] = header;
level = x->level;
}
for (int i = 0; i <= x->level; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
}
注意：level 是当前跳表最高非空层（从 0 开始计），不是节点数；randomLevel() 返回的是新节点层数（至少为 0），不是全局最大层数。
为什么多线程环境下不能直接加锁整个 insert
对整个跳表加互斥锁（如 std::mutex）会彻底串行化所有操作，失去跳表本应具备的并发优势。实际工程中更常用的是：对**每层链表单独加锁**，或采用无锁（lock-free）设计（如基于 CAS 的原子指针更新）。但无锁实现极难保证正确性——尤其在节点删除后被其他线程误读 forward[i] 指针时，极易出现 ABA 问题或悬垂指针。
简单起见，若必须支持并发，建议：
- 读操作（
search）完全无锁（前提是节点删除后内存不立即释放，可用 RCU 或 epoch-based reclamation） - 写操作按层粒度加锁：插入时只锁涉及的层数（
0..x->level），而非全部MAX_LEVEL层 - 避免在持有锁期间调用用户自定义函数（如比较器），以防死锁
跳表真正难的不是写对单线程版本，而是删掉某节点后，如何让所有层级的 forward 指针同步失效——这点哪怕在教科书实现里也常被简化忽略。
