C# 跳表SkipList实现方法 C#如何实现一个高效的有序集合

来源：这里教程网时间：2026-02-21 17:40:31 作者：

为什么不用 SortedSet 而要手写 SkipList

因为

SortedSet<t></t>

底层是红黑树，增删查都是 O(log n)，但它是单线程安全的（不支持并发修改），且不支持按索引随机访问（比如“取第 5 小的元素”）。SkipList 在平均情况下同样 O(log n)，但实现天然支持概率性分层，插入时无需旋转/重平衡，代码更易理解，也更容易扩展为线程安全版本。

SkipList 的核心结构怎么组织

每个节点不是只存一个

Next

指针，而是用数组

Forward[]

存多个层级的后继引用。层级数由随机决定（通常用抛硬币：每次成功则继续升层，直到失败，最大层数常设为 32）。头节点（

Head

）必须有完整层级，每层形成一个有序链表，越高层跳得越远。

关键点：

Level
是当前节点实际拥有的层数（≤ 最大层数），不是固定值 查找时从最高层开始，向右走不动就降层，类似“快速定位 + 精调” 插入前必须先做一次查找，记录每层最后停靠的节点（即
Update[]
数组），用于后续指针修复 删除同理，也要先查再改指针，不能只删节点对象

如何控制层级生成避免退化

层级不能全靠

Random.Next()

取模——这会破坏概率分布，导致某些层过密或过空。正确做法是用独立伯努利试验模拟抛硬币：

private int RandomLevel()
{
    int level = 1;
    while (level < MaxLevel && random.NextDouble() < 0.5)
        level++;
    return level;
}

这里

0.5

是晋升概率，对应标准 SkipList；若设为

0.25

，平均层数更低、内存更省，但常数因子略大。别用

new Random()

在循环里反复创建——它基于时间戳，高频调用会导致重复种子，应复用单例

Random

实例。

与 ConcurrentDictionary 或 ReaderWriterLock 配合的陷阱

纯 SkipList 本身不带锁。若想支持并发读写，不要直接套

lock(this)

——会严重串行化。可行路径有二：

对每层链表单独加细粒度锁（如每层一个
object
锁），但实现复杂且易死锁更实用的是：用
ConcurrentDictionary<tkey tvalue></tkey>
存数据，另起一个只读 SkipList 做快照索引（适合读多写少）或者直接放弃手写，改用
System.Collections.Concurrent.ConcurrentSkipList<t></t>
（.NET 6+ 内置，但仅限
IComparable<t></t>
类型，且不公开底层操作）

真正需要自定义行为（比如带范围查询回调、自定义比较器生命周期管理）时，才值得投入 SkipList 实现——否则，