跳表通过多层链表实现快速查找，C++中以随机层级和指针数组构建，支持高效插入、删除与搜索，平均时间复杂度O(log n)，代码简洁但需注意线程安全。
跳表（Skip List）是一种基于概率的动态数据结构，用来快速查找、插入和删除元素，平均时间复杂度为 O(log n)。相比平衡树，跳表实现更简单，同时具备良好的性能。在C++中实现跳表，需要理解其层级链表结构和随机层级生成机制。
跳表的基本原理
跳表通过多层链表实现快速跳跃访问：
- 底层是有序链表，包含所有元素
- 每一层都是下一层的“快照”，只包含部分节点
- 查找时从顶层开始，横向跳跃，遇到更大值则下降一层
- 每个节点有一定概率晋升到上一层（通常为50%）
定义跳表节点结构
每个节点包含多个向右指针，层数在创建时随机决定：
template <typename K, typename V>
class SkipListNode {
public:
K key;
V value;
std::vector<SkipListNode*> forward;
<pre class='brush:php;toolbar:false;'>SkipListNode(K k, V v, int level)
: key(k), value(v), forward(level, nullptr) {}};
立即学习“C++免费学习笔记（深入）”；
说明： forward 是一个指针数组，forward[i] 指向第 i 层的下一个节点。
跳表类的基本框架
实现核心操作：查找、插入、删除、层级生成等：
template <typename K, typename V>
class SkipList {
private:
static const int MAX_LEVEL = 16;
int currentLevel;
SkipListNode<K, V>* header;
<pre class='brush:php;toolbar:false;'>int randomLevel();
void displayList();public: SkipList(); ~SkipList();
SkipListNode<K,V>* search(K key); void insert(K key, V value); void remove(K key); void display();
};
立即学习“C++免费学习笔记（深入）”；
关键成员解释：
- MAX_LEVEL： 最大层数限制，避免无限增长
- currentLevel： 当前跳表最高非空层
- header： 头节点，每层都有一个指向第一个有效节点的指针
随机生成节点层级
使用随机数决定新节点应有多少层：
template <typename K, typename V>
int SkipList<K, V>::randomLevel() {
int level = 1;
while (rand() % 2 && level < MAX_LEVEL) {
level++;
}
return level;
}
说明： 每次有50%的概率继续向上加一层，直到达到最大限制。
查找操作实现
从顶层开始，向右走到底再往下走：
template <typename K, typename V>
SkipListNode<K,V>* SkipList<K, V>::search(K key) {
SkipListNode<K,V>* curr = header;
for (int i = currentLevel; i >= 1; i--) {
while (curr->forward[i] && curr->forward[i]->key < key) {
curr = curr->forward[i];
}
}
curr = curr->forward[1];
if (curr && curr->key == key) {
return curr;
}
return nullptr;
}
插入操作详解
先搜索路径记录每层最后到达的节点，再逐层更新指针：
template <typename K, typename V>
void SkipList<K, V>::insert(K key, V value) {
std::vector<SkipListNode<K,V>*> update(MAX_LEVEL + 1, nullptr);
SkipListNode<K,V>* curr = header;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel; i >= 1; i--) {
while (curr->forward[i] && curr->forward[i]->key < key) {
curr = curr->forward[i];
}
update[i] = curr;
}
curr = curr->forward[1];
if (curr && curr->key == key) {
curr->value = value;
return;
}
int newLevel = randomLevel();
if (newLevel > currentLevel) {
for (int i = currentLevel + 1; i <= newLevel; i++) {
update[i] = header;
}
currentLevel = newLevel;
}
SkipListNode<K,V>* newNode = new SkipListNode<K,V>(key, value, newLevel);
for (int i = 1; i <= newLevel; i++) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}}
删除节点操作
找到节点后，将其从各层链表中移除，并清理空层：
template <typename K, typename V>
void SkipList<K, V>::remove(K key) {
std::vector<SkipListNode<K,V>*> update(MAX_LEVEL + 1, nullptr);
SkipListNode<K,V>* curr = header;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel; i >= 1; i--) {
while (curr->forward[i] && curr->forward[i]->key < key) {
curr = curr->forward[i];
}
update[i] = curr;
}
curr = curr->forward[1];
if (!curr || curr->key != key) return;
for (int i = 1; i <= currentLevel; i++) {
if (update[i]->forward[i] != curr) break;
update[i]->forward[i] = curr->forward[i];
}
delete curr;
while (currentLevel > 1 && header->forward[currentLevel] == nullptr) {
currentLevel--;
}}
构造与析构函数
初始化头节点并释放内存：
template <typename K, typename V>
SkipList<K, V>::SkipList() : currentLevel(1) {
header = new SkipListNode<K,V>(K(), V(), MAX_LEVEL);
}
<p>template <typename K, typename V>
SkipList<K, V>::~SkipList() {
SkipListNode<K,V><em> curr = header->forward[1];
while (curr) {
SkipListNode<K,V></em> next = curr->forward[1];
delete curr;
curr = next;
}
delete header;
}</p>打印跳表结构
便于调试，显示每层节点：
template <typename K, typename V>
void SkipList<K, V>::display() {
for (int i = currentLevel; i >= 1; i--) {
SkipListNode<K,V>* node = header->forward[i];
std::cout << "Level " << i << ": ";
while (node) {
std::cout << node->key << "(" << node->value << ") ";
node = node->forward[i];
}
std::cout << std::endl;
}
}
基本上就这些。C++实现跳表的关键在于管理多级指针和维护搜索路径。虽然不如STL中的set/map底层高效（红黑树或B+树），但跳表代码清晰、易于扩展（如支持范围查询、计数等），适合学习和特定场景使用。注意线程安全问题，若需并发访问，应添加锁机制。
