c++如何实现跳表(skiplist)

    引言

    二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了吗?实际上,只需要对链表稍加改造,就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。

    定义

    跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n),优于普通队列的O(n)。性能上和红黑树,AVL树不相上下,但跳表的原理非常简单,目前Redis和LevelDB中都有用到。
    跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡,而不是严格平衡。因此,跟平衡二叉树相比,跳表的插入和删除操作要简单得多,执行也更快。

    C++简单实现

    下面实现过程主要是简单实现跳表的过程,不是多线程安全的,LevelDB实现的跳表支持多线程安全,用了std::atomic原子操作,本文主要是为了理解跳表的原理,所以采用最简单的实现。

    
    #ifndef SKIPLIST_H
    #define SKIPLIST_H
    
    #include <ctime>
    #include <initializer_list>
    #include <iostream>
    #include <random>
    
    template <typename Key>
    class Skiplist {
    public:
     struct Node {
     Node(Key k) : key(k) {}
     Key key;
     Node* next[1]; // C语言中的柔性数组技巧
     };
    
    private:
     int maxLevel;
     Node* head;
    
     enum { kMaxLevel = 12 };
    
    public:
     Skiplist() : maxLevel(1)
     {
     head = newNode(0, kMaxLevel);
     }
    
     Skiplist(std::initializer_list<Key> init) : Skiplist()
     {
     for (const Key& k : init)
     {
      insert(k);
     }
     }
    
     ~Skiplist()
     {
     Node* pNode = head;
     Node* delNode;
     while (nullptr != pNode)
     {
      delNode = pNode;
      pNode = pNode->next[0];
      free(delNode); // 对应malloc
     }
     }
    
     // 禁止拷贝构造和赋值
     Skiplist(const Skiplist&) = delete;
     Skiplist& operator=(const Skiplist&) = delete;
     Skiplist& operator=(Skiplist&&) = delete;
    
    private:
     Node* newNode(const Key& key, int level)
     {
     /*
     * 开辟sizeof(Node) + sizeof(Node*) * (level - 1)大小的空间
     * sizeof(Node*) * (level - 1)大小的空间是给Node.next[1]指针数组用的
     * 为什么是level-1而不是level,因为sizeof(Node)已包含一个Node*指针的空间
     */ 
     void* node_memory = malloc(sizeof(Node) + sizeof(Node*) * (level - 1));
     Node* node = new (node_memory) Node(key);
     for (int i = 0; i < level; ++i)
      node->next[i] = nullptr;
    
     return node;
     }
     /*
     * 随机函数,范围[1, kMaxLevel],越小概率越大
     */ 
     static int randomLevel()
     {
     int level = 1;
     while (rand() % 2 && level < kMaxLevel)
      level++;
    
     return level;
     }
    
    public:
     Node* find(const Key& key)
     {
     // 从最高层开始查找,每层查找最后一个小于key的前继节点,不断缩小范围
     Node* pNode = head;
     for (int i = maxLevel - 1; i >= 0; --i)
     {
      while (pNode->next[i] != nullptr && pNode->next[i]->key < key)
      {
      pNode = pNode->next[i];
      }
     }
    
     // 如果第一层的pNode[0]->key == key,则返回pNode->next[0],即找到key
     if (nullptr != pNode->next[0] && pNode->next[0]->key == key)
      return pNode->next[0];
    
     return nullptr;
     }
    
     void insert(const Key& key)
     {
     int level = randomLevel();
     Node* new_node = newNode(key, level);
     Node* prev[kMaxLevel];
     Node* pNode = head;
     // 从最高层开始查找,每层查找最后一个小于key的前继节点
     for (int i = level - 1; i >= 0; --i)
     {
      while (pNode->next[i] != nullptr && pNode->next[i]->key < key)
      {
      pNode = pNode->next[i];
      }
      prev[i] = pNode;
     }
     // 然后每层将新节点插入到前继节点后面
     for (int i = 0; i < level; ++i)
     {
      new_node->next[i] = prev[i]->next[i];
      prev[i]->next[i] = new_node;
     }
    
     if (maxLevel < level) // 层数大于最大层数,更新最大层数
      maxLevel = level;
     }
    
     void erase(const Key& key)
     {
     Node* prev[maxLevel];
     Node* pNode = head;
     // 从最高层开始查找,每层查找最后一个小于key的前继节点
     for (int i = maxLevel - 1; i >= 0; --i)
     {
      while (pNode->next[i] != nullptr && pNode->next[i]->key < key)
      pNode = pNode->next[i];
      prev[i] = pNode;
     }
     
     // 如果找到key,
     if (pNode->next[0] != nullptr && pNode->next[0]->key == key)
     {
      Node *delNode = pNode->next[0];
      // 从最高层开始,如果当前层的next节点的值等于key,则删除next节点
      for (int i = maxLevel - 1; i >= 0; --i)
      {
      if (prev[i]->next[i] != nullptr && key == prev[i]->next[i]->key)
       prev[i]->next[i] = prev[i]->next[i]->next[i];
      }
      free(delNode); // 最后销毁pNode->next[0]节点
     }
     
     // 如果max_level>1且头结点的next指针为空,则该层已无数据,max_level减一
     while (maxLevel > 1 && head->next[maxLevel] == nullptr)
     {
      maxLevel--;
     }
     }
    };
    
    #endif

    Redis和LevelDB选用跳表而弃用红黑树的原因

    1. Skiplist的复杂度和红黑树一样,而且实现起来更简单。
    2. 在并发环境下Skiplist有另外一个优势,红黑树在插入和删除的时候可能需要做一些rebalance的操作,这样的操作可能会涉及到整个树的其他部分,而skiplist的操作显然更加局部性一些,锁需要盯住的节点更少,因此在这样的情况下性能好一些。

    以上就是c++如何实现跳表的详细内容,更多关于c++ 跳表的资料请关注lingkb其它相关文章!