引言
链表一直是一个非常常用的数据结构，它的插入和删除时间复杂度是O（1）就代表了这个数据结构不会差。但是查询一直是一个苦恼的地方，需要一个一个的找，所以时间复杂度是O（n）。那有没有方法可以减少这个时间复杂度呢？我们的灵感来源于平衡二叉树和二分查找，我们的目的就是可以跳过一些没有必要查询的数据，尽量减少访问量，也就有了现在的跳表。
数据结构
跳表的整体结构：
层级结构 (Level 3 为最高层，Level 1 为数据层)
|
Level 3: HEAD ——————————>25 ——————————> NIL
| |
Level 2: HEAD ————–> 15 ——–> 25 ———> 35 ——–> NIL
| | | |
Level 1: HEAD –> 5 –> 10 –> 15 –> 20 –> 25 –> 30 –> 35 –> 40 –> 45 –> NIL
在第一层，我们存储的就是我们所有的数据。而每次往上一层，数据就会变少，但是这些数据仍然来自于前一层的数据，然后组成了一个新的链表。所以如果某一层里的某一个数据存在，那么说明在这一层的前面所有层里，这个数据都存在，不然这个数据就不会在这一层出现。
那我们这个有什么优势呢？
模拟过程
首先提示一下，我们这里的所有数都是key值，不是value值，我们只比较key值
假设我们要查询20这个数，我们先从最高层（第三层）开始，先发现header的下一个是25，和20比较之后发现20比25小，于是往下沉，到第二层找到15，发现20大于15，继续往后找，下一个是25，发现比20大，于是从15往下沉，然后继续相同的操作，最后找到20。
所以在这个过程里面，我们其实仅仅遍历了15，20，25这三个数，就找到了我们的目标值。
所以这个过程是不是有一点二分的意思了，从最高层向下找，然后不断地比较，下沉，直到找到目标值
实现思路
所以实现这个数据结构地思路是十分重要的。第一点就是这个数据结构是动态的，因为随着插入的数据不断地增加，如果数据结构地层次不发生变化，很可能过一段时间之后这个时间复杂度又变成了O（n）。那我们怎么维护这个数据结构呢？我们选择地是在插入数据地时候改变这个数据结构。但是一个数据应该有多少层，有应该怎么办呢？一个数据有多少层不看这个数据地大小，也不看这个数据地位置，而是看运气。
我们可以简单地拿投硬币来说明一下，如果硬币是正面，上一层，反面就停止。所以我们用一个循环来记录一个数据地层次。这个样子就可以保证第一层100%，第二层50%，第三层25%。。。。概率依次降低
代码
既然大致地思路说清了，那么对于细节我们必须要好好研究一下了
首先一个结点必须要记录的是这个结点的层数，node_level
第二也就是我们最关键的点，我们一个普通的链表，我们一般用*next来表示这个结点的下一个结点，但是这里好像不是那个样子，这个结点不仅有x轴，还存在y轴，所以我们需要用两个指针来表示这个结点的上下结点吗？当然不是。我们这里选择的是一个指针数组，forward[0]表示的就是在第0层的*next指针，forward[1]表示的就是在第0层的*next指针，而我们每一次改变层数，其实也就是改变forward[i]里面的i。
所以我们的结点其实至始至终只有一个，而next因为forward[i]的存在有无数个，表示的是每一层next的指针指向了谁。
template<typename K, typename V>
class Node{
public:
Node() {}
~Node() {delete[] forward;} // 删除这个结点对应的一整列数组
Node(K key, V value, int node_level);
K getKey() const {return key;}
V getValue() const {return value;}
void setValue(V value) {this->value = value;}
int node_level;
Node<K, V>** forward; // 二维数组，每个元素是一个指针
private:
K key;
V value;
};
template<typename K, typename V>
Node<K, V>::Node(K key, V value, int node_level)
: node_level(node_level),
forward(nullptr),
key(key),
value(value) {
forward = new Node*[node_level + 1];
for (int i = 0; i <= node_level; i++) {
forward[i] = nullptr;
}
}
然后就是SkipList的大致结构：
template<typename K, typename V>
class SkipList{
private:
std::mutex mutex_;
int max_level; // 跳表允许的最大层数
Node<K, V>* header; // 跳表的头节点
int element_count; // 跳表的节点数量
int skip_list_level; // 跳表表示的当前层数
std::ofstream file_writer; // 文件写入流
std::ifstream file_reader; // 文件读取流
std::random_device rd;
std::mt19937 gen{rd()};
public:
SkipList(int max_level);
~SkipList();
int get_random_level(); // 获取结点的随机层级
Node<K, V>* create_node(K key, V value, int node_level);
int insert_element(K key, V value);
void display_list(); // 展示结点
bool search_element(K key); // 搜索元素
void delete_element(K key); // 删除结点
void dump_file(); // 持久化数据到文件
void load_file(); // 从文件加载数据
void clear();
int size(); // 跳表中结点的数量
private:
bool is_valid_string(const std::string& str);
void get_key_value_from_string(const std::string& str, std::string* key, std::string* value);
};
层数的随机
我们开始的层数一定是从1开始，但是注意的是我们有一个最高层的限制，我们需要保证不要超过最高层
template<typename K, typename V>
int SkipList<K, V>::get_random_level()
{
// 每个结点的最低层级都是1，如果设为0的话，那后面的判断永远是0
int level = 1;
while(gen() % 2 == 0) {
level++;
}
// 最大值的限制
level = (level > max_level) ? max_level : level;
return level;
}
插入元素。
我们首先找到头节点，从最高层向下开始遍历，因为插入的过程一开始就是一个查询的过程，然后每到一层就对那一层进行遍历，找到要插入结点的前驱结点，用update数组记录下这个指针，以便于之后的插入。这个时候，大家可能会有疑惑，为什么不先用随机数把层数确定下来，然后直接从那一层开始遍历呢？因为这样会把问题变得复杂，因为这个随机层如果比目前最高的层数还要高，那么就要分开讨论，分开记录，还不如把这个问题放在插入的时候，直接从下到上一起插入。
等记录完所有前驱结点之后，我们直接从下到上进行插入，大家水平都比我要高，所以插入的过程相比也不必我多说了吧~~
template<typename K, typename V>
int SkipList<K, V>::insert_element(K key, V value)
{
std::lock_guard<std::mutex> lock(mutex_);
Node<K, V>* current = header;
// 用于更新各层的指针数组的前驱结点
Node<K, V>* update[max_level + 1];
for(int i = 0; i < max_level + 1; i++) {
update[i] = nullptr;
}
// 从最高层开始遍历
for(int i = skip_list_level; i >= 0; i–) {
while(current->forward[i] != nullptr && current->forward[i]->getKey() < key) {
current = current->forward[i];
}
// 保存每一个结点的前驱结点，以便后续更新指针
update[i] = current;
}
// 在最下面一层移动一个结点，准备插入的操作
current = current->forward[0];
// 如果当前结点的key等于要插入的key，说明已经存在了，直接返回1
if(current != nullptr && current->getKey() == key) {
return 1;
}
if(current == nullptr || current->getKey() != key) {
int random_level = get_random_level();
// 如果新的结点的高度比现在的层数要高，那么就更新
if(random_level > skip_list_level) {
for(int i = skip_list_level; i <= random_level; i++){
update[i] = header;
}
// 更新跳表目前的最高级别的层数
skip_list_level = random_level;
}
Node<K, V>* inserted_node = create_node(key, value, random_level);
for(int i = 0; i <= random_level; i++){
inserted_node->forward[i] = update[i]->forward[i];
update[i]->forward[i] = inserted_node;
}
element_count++;
}
return 0;
}
搜寻节点
这个过程就很简单了，在插入的过程之中，我们已经体会过了
template<typename K, typename V>
bool SkipList<K, V>::search_element(K key)
{
Node<K, V>* current = header;
for(int i = skip_list_level; i >= 0; i–) {
while(current->forward[i] != nullptr && current->forward[i]->getKey() < key) {
current = current->forward[i];
}
// 当前结点的下一个结点键值大于查找的key，进行下沉到下一层
// 下沉的操作通过i–实现
}
// 检查当前层（最底层）的下一个结点是不是目标值
current = current->forward[0];
if(current != nullptr && current->getKey() == key) {
return true;
}
return false;
}
删除元素
删除元素我们的思路也是一样的，先找到我们要删除的元素。在这个寻找的过程中，我们记录所有可能的前驱结点，然后当我们从下到上开始删除元素的时候，就比较的方便。但这里为什么是可能呢？因为这个结点不一定每一层都存在，但是一个结点如果在某一层存在，那么就一定说明这个在结点的下面所有层都存在。所以当发现有一层没有这个结点的时候，我们break就好了
最后要注意的是，如果把这个结点删除了，这一层没节点了，那么就把层数减减
template<typename K, typename V>
void SkipList<K, V>::delete_element(K key)
{
std::lock_guard<std::mutex> lock(mutex_);
Node<K, V>* current = header;
Node<K, V>* update[max_level + 1];
for(int i = 0; i < max_level + 1; i++){
update[i] = nullptr;
}
// 从最高层往下删除结点
for(int i = skip_list_level; i >= 0; i–) {
while(current->forward[i] != nullptr && current->forward[i]->getKey() < key) {
current = current->forward[i];
}
update[i] = current;
}
current = current->forward[0]; // 锁定到目标结点
// 确认找到了删除的结点
if(current != nullptr && current->getKey() == key) {
for(int i = 0; i <= skip_list_level; i++){
if(update[i]->forward[i] != current) { // 并不是所有层都有这一个指针的，一旦没有，说明后面层也没有了
break;
}
update[i]->forward[i] = current->forward[i];
}
// 调整跳表的层级
while(skip_list_level > 0 && header->forward[skip_list_level] == nullptr) {
skip_list_level–;
}
delete current; // 在虚拟空间里面相当于删除了一整个数组，物理空间里面是一个结点
element_count–;
}
因为内存在断电之后数据会消失，所以我们的存储就必须写入磁盘
我们写入磁盘的形式是 key ：value
一下是几个必要的工具
template<typename K, typename V>
bool SkipList<K, V>::is_valid_string(const std::string& str) // 保证是有效的数据存储方式 key ：value
{
return !str.empty() && str.find(delimiter) != std::string::npos;
}
template<typename K, typename V>
void SkipList<K, V>::get_key_value_from_string(const std::string& str, std::string* key, std::string* value)
{
if(!is_valid_string(str)) {
return;
}
*key = str.substr(0, str.find(delimiter));
*value = str.substr(str.find(delimiter) + 1, str.length());
}
这两个就是写入文件和读出文件的函数，代码比较容易理解，大家看一下
template<typename K, typename V>
void SkipList<K, V>::dump_file()
{
file_writer.open(STORE_FILE); // 打开文件
Node<K, V>* node = header->forward[0]; // 从头节点开始遍历
while(node != nullptr) {
file_writer << node->getKey() << " " << node->getValue() << std::endl;
node = node->forward[0];
}
file_writer.flush(); // 刷新缓冲区，保证数据完全写入文件
file_writer.close(); // 关闭文件
}
template<typename K, typename V>
void SkipList<K, V>::load_file()
{
file_reader.open(STORE_FILE);
std::string line;
std::string *key = new std::string(); // 开辟一个空间
std::string *value = new std::string();
while(getline(file_reader, line)) {
get_key_value_from_string(line, key, value); // 把key和value提取出来
if(key->empty() || value->empty()) { // 如果这个数据有一个不效，就跳过这个数据
continue;
}
insert_element(stoi(*key), *value); // stoi将key转换为整数类型，这个操作相当于是把这些数据保存在内存上
std::cout << "key:" << *key << " value:" << *value << std::endl;
}
delete key;
delete value;
file_reader.close();
}
主要的代码实现就是这一些
总结
跳表是一种很高效的数据结构，redis就是采取了这个结构，而且它的并发性比较好，大家也看到了，我的代码里面加锁的地方只有增加和删除的位置，事实上，也只有这两个位置需要加锁。时间复杂度也比较低，但是空间的占用是比较大的，这也是没办法的事情。天底下没有十全十美的事情嘛~~~
感谢大家的阅读，希望可以帮助大家更好的理解！！！！
