1. 题目
你需要一个有序字典，支持按键搜索、插入、删除和范围扫描。数据量会动态增长，面试官要求平均操作接近 O(log N)，但不要求实现 AVL 或红黑树。请设计 Skip List 并分析随机性、边界和内存布局。
2. 约束与澄清
- 明确键是否唯一；若重复，定义覆盖、计数或稳定顺序。
- 设定最大层数和每层晋升概率
p，通常从底层链表开始向上建立索引。 - 搜索、插入和删除需要维护每一层的前驱节点；范围遍历只需沿底层链表前进。
- 先讨论单线程结构；若要并发，需要额外的锁、版本或无锁算法证明。
3. 核心思路
每个节点拥有高度随机的 forward 指针数组。搜索从最高层头节点开始：若下一个键仍小于目标，就沿当前层前进；否则下降一层。插入先记录每层前驱，再随机生成新高度并逐层接入。删除同样使用前驱数组断开指针。随机层高使高层节点稀疏，期望总指针数为 O(N)，搜索、插入和删除的期望时间为 O(log N)。
4. 参考实现
text
randomLevel(rng, p, maxLevel):
level = 1
while level < maxLevel and rng.uniform01() < p:
level += 1
return level
findPredecessors(key):
update = array(maxLevel)
node = head
for level from maxLevel - 1 down to 0:
while node.forward[level] != nil and node.forward[level].key < key:
node = node.forward[level]
update[level] = node
return update
insert(key, value):
update = findPredecessors(key)
if update[0].forward[0].key == key:
update[0].forward[0].value = value
return
node = Node(key, value, randomLevel(rng, p, maxLevel))
for level in 0 .. node.height - 1:
node.forward[level] = update[level].forward[level]
update[level].forward[level] = node实现中必须先检查 nil 再读取键，并保证新节点的高度不超过 maxLevel。删除时把所有指向目标节点的层级一次性接到后继节点；最高层为空后可降低当前有效层数，但不必移动节点。
5. 复杂度与最坏情况
当晋升概率固定且随机源独立时，层数和路径长度的期望为对数级，空间期望为 O(N)。随机性失效或敌手能预测层高时，结构可能退化成单链表，操作变为 O(N)。可使用高质量随机源、限制最大高度、定期重建或采用确定性平衡树来处理对抗性工作负载。
6. 验证与并发取舍
- 用有序、重复、空结构和极端键测试搜索、更新、删除及范围遍历。
- 统计不同 N 下的高度分布、平均路径长度和指针数量，检查是否符合预期。
- 做随机操作序列，与标准有序映射对拍，验证内容和顺序一致。
- 并发版本要说明读写锁粒度、删除标记、内存回收和 ABA 风险；不能只把指针写入包在一个锁里就宣称无锁安全。
7. 常见误区
- 只写搜索，不维护每层前驱，导致插入或删除退化为重新扫描。
- 忽略重复键策略，插入后范围遍历顺序不稳定。
- 把期望
O(log N)当作最坏保证，未讨论随机源和对抗性输入。 - 用固定高度数组浪费内存，或允许高度无界导致数组越界。
8. 面试评分点
能从高层向下搜索
应说明每层前进条件、下降时机，以及为什么底层链表包含全部元素。
能正确维护前驱
应在插入和删除中保存各层 update 数组，处理覆盖、空指针和最高层收缩。
能解释概率复杂度
应给出 O(log N) 期望时间、O(N) 期望空间和退化到 O(N) 的条件。
能识别并发边界
应讨论锁、版本、标记删除、内存回收与 ABA，而不是把单线程代码直接当作并发实现。