企业官网建设流程全解析

前言

跳跃表（skip list）是一种用「多层链表」实现有序集合的数据结构。它在链表的基础上给每个节点随机分配若干层向前指针，查找时从最高层开始，能跳就跳，不能跳就下降一层。这样平均查找、插入、删除的复杂度都是 O(log n)，而实现难度远低于红黑树、AVL 树这类平衡树。

它的「平衡」不靠旋转维护，而靠随机化：每个节点的层数按几何分布随机生成，层数越高节点越少。这也让它在并发场景下有优势——插入和删除只影响局部几个指针。Redis 的有序集合就使用了跳跃表（细节以 Redis 官方文档为准）。

本文给出一个完整的 C++17 实现，再讨论复杂度与常见错误。代码中的随机数使用<random>，不依赖第三方库。

一、从单层链表到多层链表

有序单链表的查找必须从头逐个比较，复杂度 O(n)。如果每隔几个节点抽出一个「索引节点」形成第二层链表，查找时就能先在索引层跳过一段，再落到下一层细找。跳跃表就是这个思路的多层版本：第 0 层包含全部节点，往上每层节点更少、作为下一层的索引。

每个节点有一个「层数」，表示它出现在第 0 层到第level-1层。查找时从当前最高层开始：下一个节点存在且值小于目标就向前移动，否则下降一层；到第 0 层后再比较一次，判断是否命中。

二、节点与随机层数

// 适用于 C++17
#include <cstddef>
#include <random>
#include <vector>

class SkipList {
private:
struct Node {
int value;
std::vector<Node*> next; // next[i] 是第 i 层的后继

Node(int v, std::size_t level)
: value(v), next(level, nullptr) {}
};

static constexpr int kMaxLevel = 16; // 层数上限
static constexpr double kBranching = 0.25; // 每层向上晋升的概率

Node* head_; // 头节点，不存有效值，next 长度固定为 kMaxLevel
int level_; // 当前实际使用的层数，至少为 1
std::size_t size_;
std::mt19937 rng_;

int randomLevel() {
int lvl = 1;
std::uniform_real_distribution<double> dist(0.0, 1.0);
while (lvl < kMaxLevel && dist(rng_) < kBranching) {
++lvl;
}
return lvl;
}

几个设计决定：

• 
  
• 头节点固定kMaxLevel个指针，这样新节点比现有节点都高时也不需重新分配头节点；它的value不参与比较，只作为起点。
• 
  
• 层数从 1 开始计数，level_是当前有效层数，查找从level_ - 1开始。
• 
  
• 晋升概率 0.25、层数上限 16。概率越小越省空间，但下降次数越多；0.25 和 0.5 都常见。16 层按 p=0.25 足以支撑到 4¹⁶ ≈ 4.3×10⁹ 个节点的期望规模，上限也防止随机数连续命中导致层数失控。
• 
  

std::mt19937是标准库的梅森旋转引擎，头文件<random>，种子在构造函数里指定，便于复现。

三、查找

// 适用于 C++17
bool contains(int value) const {
const Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] != nullptr && cur->next[i]->value < value) {
cur = cur->next[i];
}
}
cur = cur->next[0];
return cur != nullptr && cur->value == value;
}

外层循环从最高层往下，内层循环在当前层尽可能向右走，走不动就下降一层。全部层走完后，cur是第 0 层上「最后一个小于目标值的节点」，它的下一个节点才可能是目标。判断条件用<而不是<=，遇到相等就停下、最后统一比较，与插入和删除的前驱定位保持一致。

复杂度期望 O(log n)：每层大约跳过 1/p 个节点，层数是 log₁/ₚ n 量级。

四、插入

插入分三步：定位每一层的前驱、生成新节点的层数、把新节点接到每一层。

// 适用于 C++17
void insert(int value) {
std::vector<Node*> update(kMaxLevel, nullptr);

Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] != nullptr && cur->next[i]->value < value) {
cur = cur->next[i];
}
update[i] = cur; // 第 i 层上最后一个小于 value 的节点
}

Node* next = cur->next[0];
if (next != nullptr && next->value == value) {
return; // 已存在，不重复插入
}

const int newLevel = randomLevel();
if (newLevel > level_) {
for (int i = level_; i < newLevel; ++i) {
update[i] = head_; // 新增的层，前驱都是头节点
}
level_ = newLevel;
}

Node* node = new Node(value, static_cast<std::size_t>(newLevel));
for (int i = 0; i < newLevel; ++i) {
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
++size_;
}

update[i]保存第 i 层上「最后一个值小于value的节点」，即新节点的前驱，一次下降遍历即可全部记录。当newLevel超过level_时，多出来的层在原表中不存在，前驱只能是头节点；漏掉这一步会让循环读到未初始化的指针。

重复值：这里选择「已存在则忽略」。若要允许重复，可改成计数，但查找语义也要跟着调整，并应在接口文档里写清楚。

五、删除

删除同样先定位前驱，然后从第 0 层到目标节点最高层逐个摘链：

// 适用于 C++17
bool erase(int value) {
std::vector<Node*> update(kMaxLevel, nullptr);

Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] != nullptr && cur->next[i]->value < value) {
cur = cur->next[i];
}
update[i] = cur;
}

Node* target = cur->next[0];
if (target == nullptr || target->value != value) {
return false;
}

const std::size_t nodeLevel = target->next.size();
for (std::size_t i = 0; i < nodeLevel; ++i) {
update[i]->next[i] = target->next[i];
}
delete target;

while (level_ > 1 && head_->next[level_ - 1] == nullptr) {
--level_; // 最高层空了，降低层数
}
--size_;
return true;
}

遍历范围用target->next.size()而不是level_：只有目标节点实际存在的层才需要改指针，对它不存在的层强行赋值会破坏结构。

删除后要把空掉的高层降下来，否则level_虚高，查找会从全空的层开始下降，插入时update也会填到没有意义的层上。

六、构造、析构与完整示例

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <random>
#include <vector>

class SkipList {
public:
explicit SkipList(unsigned int seed = 42)
: head_(new Node(0, kMaxLevel)), level_(1), size_(0), rng_(seed) {}

~SkipList() {
Node* cur = head_->next[0];
while (cur != nullptr) {
Node* next = cur->next[0];
delete cur;
cur = next;
}
delete head_;
}

SkipList(const SkipList&) = delete;
SkipList& operator=(const SkipList&) = delete;

bool contains(int value) const {
const Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] != nullptr && cur->next[i]->value < value) {
cur = cur->next[i];
}
}
cur = cur->next[0];
return cur != nullptr && cur->value == value;
}

void insert(int value) {
std::vector<Node*> update(kMaxLevel, nullptr);
Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] != nullptr && cur->next[i]->value < value) {
cur = cur->next[i];
}
update[i] = cur;
}

Node* next = cur->next[0];
if (next != nullptr && next->value == value) return;

const int newLevel = randomLevel();
if (newLevel > level_) {
for (int i = level_; i < newLevel; ++i) update[i] = head_;
level_ = newLevel;
}

Node* node = new Node(value, static_cast<std::size_t>(newLevel));
for (int i = 0; i < newLevel; ++i) {
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
++size_;
}

bool erase(int value) {
std::vector<Node*> update(kMaxLevel, nullptr);
Node* cur = head_;
for (int i = level_ - 1; i >= 0; --i) {
while (cur->next[i] != nullptr && cur->next[i]->value < value) {
cur = cur->next[i];
}
update[i] = cur;
}

Node* target = cur->next[0];
if (target == nullptr || target->value != value) return false;

const std::size_t nodeLevel = target->next.size();
for (std::size_t i = 0; i < nodeLevel; ++i) {
update[i]->next[i] = target->next[i];
}
delete target;

while (level_ > 1 && head_->next[level_ - 1] == nullptr) --level_;
--size_;
return true;
}

std::size_t size() const { return size_; }
int level() const { return level_; }

void dump() const {
for (int i = level_ - 1; i >= 0; --i) {
std::cout << "L" << i << ": ";
for (const Node* p = head_->next[i]; p != nullptr; p = p->next[i]) {
std::cout << p->value << ' ';
}
std::cout << '\n';
}
}

private:
struct Node {
int value;
std::vector<Node*> next;
Node(int v, std::size_t level) : value(v), next(level, nullptr) {}
};

static constexpr int kMaxLevel = 16;
static constexpr double kBranching = 0.25;

Node* head_;
int level_;
std::size_t size_;
std::mt19937 rng_;

int randomLevel() {
int lvl = 1;
std::uniform_real_distribution<double> dist(0.0, 1.0);
while (lvl < kMaxLevel && dist(rng_) < kBranching) ++lvl;
return lvl;
}
};

int main() {
SkipList list;
const int values[] = {3, 7, 1, 9, 5, 7, 2, 8, 4, 6};
for (int v : values) {
list.insert(v);
}
list.dump();

std::cout << "contains 5: " << list.contains(5) << '\n';
std::cout << "contains 11: " << list.contains(11) << '\n';
std::cout << "erase 7: " << list.erase(7) << '\n';
std::cout << "erase 7 again: " << list.erase(7) << '\n';
std::cout << "size: " << list.size() << '\n';
list.dump();
return 0;
}

重复的 7 只会插入一次，第二次erase(7)返回false，size()从 9 变成 8。dump()从高层往低层打印，能直观看到「高层稀疏、低层完整」的结构。

析构函数沿第 0 层遍历逐个delete，这依赖「第 0 层包含所有节点」的性质；头节点单独删除。

拷贝构造和拷贝赋值被显式删除：内部持有裸指针，默认浅拷贝会让两个对象共享同一批节点，析构时重复释放。需要拷贝就实现深拷贝，或改用std::unique_ptr管理节点。

七、复杂度与结构对比

跳跃表的复杂度是期望意义上的，依赖随机数；理论上存在层数极不均匀、退化为链表的情况，但通过上限和合适的晋升概率可以把它压到极低。平衡树的最坏情况有严格保证，代价是实现复杂。

空间上，若晋升概率为 p，每个节点平均有 1/(1-p) 个指针，p=0.25 时约 1.33 个，总空间 O(n)。每个节点一次std::vector堆分配的常数开销不小，对内存敏感的场景可以改成定长数组加层数字段，或用内存池。

常见坑点

1. 头节点只分配当前层数个指针

❌head_ = new Node(0, level_)，之后层数增加时越界 ✅ 头节点固定分配kMaxLevel个指针

新节点可能比现有所有节点都高，此时新层的前驱是头节点。头节点如果没有对应层的指针，就会越界访问。

2. 新层的前驱没有填成头节点

❌for (i = 0; i < newLevel; ++i)直接用update[i]，而update只填到level_ - 1✅ 先把update[level_..newLevel-1]全部设为head_

std::vector<Node*>初始化为nullptr，未填的位置解引用就是空指针。这是插入代码里最容易漏的一步。

3. 层数没有上限

❌while (dist(rng_) < p) ++lvl;✅while (lvl < kMaxLevel && dist(rng_) < p) ++lvl;

概率循环理论上可能连续命中很多次。没有上限时，层数可能异常大，浪费内存，也破坏了复杂度的期望值。

4. 查找时用 <= 前进

❌while (cur->next[i] && cur->next[i]->value <= value)✅ 用<，最后再单独比较是否相等

用<=会越过相等节点，之后要么找不到，要么在插入时把重复元素当成新元素插到后面，破坏「每个值最多一个节点」的约定。

5. 删除时按level_遍历改指针

❌for (int i = 0; i < level_; ++i) update[i]->next[i] = target->next[i];✅ 按target->next.size()遍历

目标节点可能不是最高层节点。对它不存在的层，update[i]->next[i]指向的是别的节点或空，强行赋值会破坏链表结构。

6. 删除后不降低层数

❌ 删除最高层唯一节点后保留level_不变 ✅while (level_ > 1 && head_->next[level_ - 1] == nullptr) --level_;

层数虚高不会立即出错，但每次查找都要从空层开始下降，插入时也可能把update填到没有意义的层上，增加出错面。

7. 拷贝对象导致重复释放

❌ 让编译器生成默认拷贝构造函数 ✅ 删除拷贝操作，或实现深拷贝

默认拷贝是浅拷贝，两个对象的head_指向同一批节点，先析构的那个会释放全部节点，后析构的再次释放就是未定义行为。

8. 用 rand() 生成层数

❌while (rand() % 100 < 25) ++lvl;✅ 使用<random>的引擎与分布

rand()的质量和取值范围由实现决定，取模还会引入偏差。层数分布直接影响跳跃表的平衡性，用质量差的随机数会让期望复杂度失去意义。

总结

跳跃表的核心只有一句话：用随机层数代替旋转，用空间换实现上的简单。代码里真正容易出错的不是查找逻辑，而是插入和删除时的边界：新层的前驱必须补成头节点、删除只能改目标节点实际存在的层、删除后要把空掉的最高层降下来。把这三点处理好，其余部分就是普通的链表操作。