跳表是一种概率型数据结构，通过给有序链表添加多层索引，大幅提升了链表的查找效率，其平均时间复杂度为O(log n)，和平衡二叉搜索树相当，但实现难度更低，非常适合用来实现高效的有序集合。在C#中我们可以手动实现跳表，替代部分场景下对内置有序集合的使用。
跳表核心原理
跳表的基础结构是一个有序的多层链表，最底层是完整的有序链表，上层链表是下层链表的索引，每个节点会随机生成所在层数，层数越高表示该节点出现在越多的索引层中。查找时从最高层索引开始遍历，遇到比目标值大的节点就下降到下一层继续查找，直到找到目标节点或者确认节点不存在。
跳表节点设计
跳表的每个节点需要存储当前节点的值、指向下一个节点的指针数组，指针数组的长度就是节点所在的层数。我们首先定义跳表节点的泛型类：
using System;
using System.Collections.Generic;
namespace SkipListDemo
{
/// <summary>
/// 跳表节点类
/// </summary>
/// <typeparam name="T">节点存储的值类型，需要支持比较</typeparam>
public class SkipListNode<T> where T : IComparable<T>
{
/// <summary>
/// 节点存储的值
/// </summary>
public T Value { get; set; }
/// <summary>
/// 节点的前向指针数组，索引i表示第i层的下一个节点
/// </summary>
public SkipListNode<T>[] Forward { get; set; }
/// <summary>
/// 节点所在的最大层数
/// </summary>
public int Level { get; set; }
public SkipListNode(T value, int level)
{
Value = value;
Level = level;
Forward = new SkipListNode<T>[level];
}
}
}
跳表核心实现
跳表的实现需要包含初始化、随机层数生成、查找、插入、删除、遍历这几个核心功能，下面我们逐步实现这些功能。
跳表初始化与随机层数生成
跳表需要有一个头节点，头节点的层数可以设置为最大允许的层数，方便后续操作。随机层数生成采用概率算法，每次有50%的概率增加一层，直到达到最大层数限制。
public class SkipList<T> where T : IComparable<T>
{
// 跳表最大层数
private readonly int _maxLevel;
// 跳表当前最大层数
private int _currentLevel;
// 头节点，不存储实际值
private readonly SkipListNode<T> _head;
// 随机数生成器，用于生成节点层数
private readonly Random _random;
// 概率因子，这里设置为0.5，即每层晋升的概率
private readonly double _probability;
public SkipList(int maxLevel = 16, double probability = 0.5)
{
_maxLevel = maxLevel;
_currentLevel = 1;
// 头节点的值设为默认值，不影响实际逻辑
_head = new SkipListNode<T>(default, maxLevel);
_random = new Random();
_probability = probability;
}
/// <summary>
/// 随机生成节点的层数
/// </summary>
private int RandomLevel()
{
int level = 1;
// 每次随机生成0-1之间的数，小于概率因子则层数加1，直到达到最大层数
while (_random.NextDouble() < _probability && level < _maxLevel)
{
level++;
}
return level;
}
}
查找操作实现
查找操作从最高层开始，逐层向下遍历，记录每一层最后一个小于等于目标值的节点，最终如果最底层的下一个节点等于目标值，则查找成功。
/// <summary>
/// 查找目标值是否存在于跳表中
/// </summary>
public bool Contains(T target)
{
SkipListNode<T> current = _head;
// 从最高层开始向下遍历
for (int i = _currentLevel - 1; i >= 0; i--)
{
// 当前层的节点值小于目标值则继续向后移动
while (current.Forward[i] != null && current.Forward[i].Value.CompareTo(target) < 0)
{
current = current.Forward[i];
}
}
// 遍历到最底层后，检查下一个节点是否为目标值
current = current.Forward[0];
return current != null && current.Value.CompareTo(target) == 0;
}
插入操作实现
插入操作首先需要找到每一层插入位置的前驱节点，然后随机生成新节点的层数，更新前驱节点的指针指向新节点，同时更新跳表的当前最大层数。
/// <summary>
/// 向跳表中插入值
/// </summary>
public void Insert(T value)
{
// 记录每一层插入位置的前驱节点
SkipListNode<T>[] update = new SkipListNode<T>[_maxLevel];
SkipListNode<T> current = _head;
// 从最高层开始找到每一层的前驱节点
for (int i = _currentLevel - 1; i >= 0; i--)
{
while (current.Forward[i] != null && current.Forward[i].Value.CompareTo(value) < 0)
{
current = current.Forward[i];
}
update[i] = current;
}
// 检查值是否已经存在，跳表默认不允许重复值
current = current.Forward[0];
if (current != null && current.Value.CompareTo(value) == 0)
{
return;
}
// 随机生成新节点的层数
int newLevel = RandomLevel();
// 如果新节点的层数超过当前最大层数，更新前驱节点和当前最大层数
if (newLevel > _currentLevel)
{
for (int i = _currentLevel; i < newLevel; i++)
{
update[i] = _head;
}
_currentLevel = newLevel;
}
// 创建新节点
SkipListNode<T> newNode = new SkipListNode<T>(value, newLevel);
// 更新每一层的指针
for (int i = 0; i < newLevel; i++)
{
newNode.Forward[i] = update[i].Forward[i];
update[i].Forward[i] = newNode;
}
}
删除操作实现
删除操作同样先找到每一层待删除节点的前驱节点，然后检查最底层的下一个节点是否为待删除节点，如果是则逐层更新前驱节点的指针，移除待删除节点。
/// <summary>
/// 从跳表中删除值
/// </summary>
public bool Remove(T value)
{
// 记录每一层待删除节点的前驱节点
SkipListNode<T>[] update = new SkipListNode<T>[_maxLevel];
SkipListNode<T> current = _head;
// 从最高层开始找到每一层的前驱节点
for (int i = _currentLevel - 1; i >= 0; i--)
{
while (current.Forward[i] != null && current.Forward[i].Value.CompareTo(value) < 0)
{
current = current.Forward[i];
}
update[i] = current;
}
// 检查待删除节点是否存在
current = current.Forward[0];
if (current == null || current.Value.CompareTo(value) != 0)
{
return false;
}
// 逐层更新指针，移除待删除节点
for (int i = 0; i < _currentLevel; i++)
{
if (update[i].Forward[i] != current)
{
break;
}
update[i].Forward[i] = current.Forward[i];
}
// 如果删除的节点是最高层的节点，更新当前最大层数
while (_currentLevel > 1 && _head.Forward[_currentLevel - 1] == null)
{
_currentLevel--;
}
return true;
}
遍历操作实现
遍历操作只需要从最底层的头节点开始，依次向后访问所有节点即可，因为最底层是完整的有序链表。
/// <summary>
/// 获取跳表中所有值的有序集合
/// </summary>
public List<T> GetAll()
{
List<T> result = new List<T>();
SkipListNode<T> current = _head.Forward[0];
while (current != null)
{
result.Add(current.Value);
current = current.Forward[0];
}
return result;
}
使用示例
下面我们通过一个简单的示例来演示跳表的使用：
class Program
{
static void Main(string[] args)
{
SkipList<int> skipList = new SkipList<int>();
// 插入数据
skipList.Insert(3);
skipList.Insert(1);
skipList.Insert(5);
skipList.Insert(2);
skipList.Insert(4);
// 遍历输出所有值
Console.WriteLine("跳表中的所有值：");
foreach (var item in skipList.GetAll())
{
Console.Write(item + " ");
}
Console.WriteLine();
// 查找值
Console.WriteLine("是否包含3：" + skipList.Contains(3));
Console.WriteLine("是否包含6：" + skipList.Contains(6));
// 删除值
skipList.Remove(3);
Console.WriteLine("删除3后是否包含3：" + skipList.Contains(3));
Console.WriteLine("删除3后的所有值：");
foreach (var item in skipList.GetAll())
{
Console.Write(item + " ");
}
}
}
跳表与内置SortedSet的对比
C#内置的SortedSet<T>底层采用的是红黑树实现，同样能提供O(log n)的插入、删除、查找效率，和跳表的效率相当。跳表的优势在于实现逻辑更简单，调试起来更容易，且在范围查询场景下遍历效率更高；而红黑树的性能更稳定，最坏情况下也能保证O(log n)的时间复杂度，跳表的性能依赖随机算法，极端情况下可能退化为普通链表。开发者可以根据实际场景选择使用内置的有序集合还是自定义跳表。