【資料結構】跳表SkipList代碼解析(C++)

跳表SkipList解析

• 原項目連結——​​基于跳表實作的輕量級鍵值資料庫​​
• 添加注釋後——​​SkipList​​

什麼是跳表

這裡不做介紹，詳見:

• ​​跳表──沒聽過但很犀利的資料結構​​
• ​​拜托，面試别再問我跳表了！​​

代碼解析

主要了解點

• 先來張圖

1. 各個節點是如何相連接配接(關聯)的？

• 通過每個節點的​

  ​forward​

  ​數組，forward數組存儲目前節點，在每一層的下一個節點。
• 以頭節點為例，頭結點的forward存儲的是每一層的第一個節點。然後通過第一個節點的forward[level],拿到該層的後面元素...... 以次類推，即可周遊該層所有節點。
• 與普通單連結清單的差別，我們可以大概了解為，上面多了幾層簡化的結果，如上面動畫所示。

1. ​

   ​update​

   ​存的是什麼?

• 每層中最後一個key小于要插入節點key的節點。

1. 節點生成的level是多少，該節點就從0層到level層一直都出現。
2. ​

   ​其它詳見具體代碼中的注釋​

   ​。

相關類&成員函數

節點類Node

template<typename K, typename V> 
class Node {
public:
    // 無參構造
    Node() {} 
    // 有參構造-最後一個參數為層數
    Node(K k, V v, int); 
    // 析構
    ~Node();
    // 拿到目前節點key值
    K get_key() const;
    // 拿到目前節點value值
    V get_value() const;
    // 設定value值
    void set_value(V); 
    // forward-存儲目前結點在i層的下一個結點。
    Node<K, V> **forward;
    //所在層級
    int node_level;
private:
    K key;
    V value;
};      

跳表類SkipList

template <typename K, typename V> 
class SkipList {

public: 
    // 有參構造-參數為最大層數
    SkipList(int);
    // 析構
    ~SkipList();
    // 生成随機層數
    int get_random_level();
    // 建立節點-最後一個參數為所在層數
    Node<K, V>* create_node(K, V, int);
    // 插入資料
    int insert_element(K, V);
    // 列印資料-每層都列印
    void display_list();
    // 查找元素
    bool search_element(K);
    // 删除元素
    void delete_element(K);
    // 存入檔案
    void dump_file();
    // 加載檔案
    void load_file();
    // 傳回節點個數
    int size();

private:
    // 從檔案中的一行讀取key和value
    void get_key_value_from_string(const std::string& str, std::string* key, std::string* value);
    // 是否為有效的string
    bool is_valid_string(const std::string& str);

private:    
    // 該跳表最大層數
    int _max_level;

    // 該跳表目前層數
    int _skip_list_level;

    // 跳表頭節點
    Node<K, V> *_header;

    // 檔案操作
    std::ofstream _file_writer;
    std::ifstream _file_reader;

    // 該跳表目前的元素數
    int _element_count;
};      

詳解insert函數

節點的插入周遊拿到update數組

Node<K, V> *update[_max_level+1];//使用_max_level+1開辟，使空間，肯定夠，因為建立節點的時候，會對随機生成的key進行限制。
memset(update, 0, sizeof(Node<K, V>*)*(_max_level+1));  

// 從跳表左上角開始查找——_skip_list_level為目前所存在的最高的層(一共有多少層則需要+1,因為是從level=0層開始的)
for(int i = _skip_list_level; i >= 0; i--) {//控制目前所在層，從最高層到第0層

    //從每一層的最左邊開始周遊，如果該節點存在并且，key小于我們要插入的key,繼續在該層後移。
    while(current->forward[i] != NULL && current->forward[i]->get_key() < key) {//是不是繼續往後面走
        current = current->forward[i]; //提示: forward存儲該節點在目前層的下一個節點
    }
    update[i] = current;//儲存
    //切換下一層
}

//将current指向第0層第一個key大于要插入節點key的節點。
//下面用current用來判斷要插入的節點存key是否存在
//即,如果該key不存在的話，準備插入到update[i]後面。存在，則修改該key對應的value。
current = current->forward[0];      

更新層次

// 為目前要插入的節點生成一個随機層數
int random_level = get_random_level();

//如果随機出來的層數大于目前連結清單達到的層數，注意:不是最大層，而是目前的最高層_skip_list_level。
//更新層數，更新update,準備在每層([0,random_level]層)插入新元素。
if (random_level > _skip_list_level) {
    for (int i = _skip_list_level+1; i < random_level+1; 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++) {
    //在每一層([0,random_level])
    //先将原來的update[i]的forward[i]放入新節點的forward[i]。
    //再将新節點放入update[i]的forward[i]。
    inserted_node->forward[i] = update[i]->forward[i];//新節點與後面相連結
    update[i]->forward[i] = inserted_node;//新節點與前面相連結
}
//std::cout << "Successfully inserted key:" << key << ", value:" << value << std::endl;
_element_count++;//元素總數++      

相關參考

• ​​Skip List | Set 2 (Insertion)​​
• ​​什麼是跳表skiplist​​
• ​​基于跳表的資料庫伺服器和用戶端​​
• 以及知識星球中牲活老哥的相關分享。