专栏首页C++的沉思跳表原理及C++实现
原创

跳表原理及C++实现

引言

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

定义

跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n),优于普通队列的O(n)。性能上和红黑树,AVL树不相上下,但跳表的原理非常简单,目前Redis和LevelDB中都有用到。

跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡,而不是严格平衡。因此,跟平衡二叉树相比,跳表的插入删除操作要简单得多,执行也更快。

screenshot_1595202635646.png

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的操作显然更加局部性一些,锁需要盯住的节点更少,因此在这样的情况下性能好一些。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • sds数据结构分析-redis源码阅读笔记(1)

    evenleo
  • KMP算法分析

    KMP 算法是一种改进的字符串匹配算法,KMP 算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 三人提出的,因此人们称它为克努特—莫...

    evenleo
  • 从位图原理到布隆过滤器的实现

    假设一个int占4个字节(32位),40个亿个整数就是160亿个字节,大概相当于16GB,假设一台计算机只有2GB内存,则16GB一次加载不完,需要分8次加载,...

    evenleo
  • 使用CDS view开发SAP Marketing contact的facet追溯工具

    这篇SAP社区博客里,我的一位同事介绍了SAP Marketing里contact facet数据模型的存储表:

    Jerry Wang
  • 基于知识图谱算法的网络故障智能诊断探索

    17年这波AI浪潮推动着各行各业在进行着智能化和AI+的尝试,而当前业界在网络故障智能监控诊断这块到目前为止还没有可参照的成熟案例。知识图谱相对于很火的深度学习...

    jackiefang
  • 结合Scikit-learn介绍几种常用的特征选择方法(上)

    特征选择(排序)对于数据科学家、机器学习从业者来说非常重要。好的特征选择能够提升模型的性能,更能帮助我们理解数据的特点、底层结构,这对进一步改善模型...

    智能算法
  • Kotlin自定义实现支付密码数字键盘的方法实例

    因为每个按键都考虑到需要支持背景设置等其他个性设置和Touch手势的处理, 所以我决定采用 每个按键 对应一个View的思路实现. 否则可以使用Canvas.d...

    砸漏
  • 从零开始搭建「图像处理实验」平台(React&Flask&MongoDB)

    为了争取提前毕业,最近需要做大量图像处理的实验,改代码、调参、存结果,由于专注于实验,所以丝毫没顾及代码质量,又懒得重构,导致今天写的代码明天就忘了什么意思,加...

    刘开心_1266679
  • 服务端 I/O 性能大比拼:Node、PHP、Java、Go哪家强?

    理解应用程序的输入/输出(I/O)模型,意味着其在计划处理负载与残酷的实际使用场景之间的差异。若应用程序比较小,也没有服务于很高的负载,也许它影响甚微。但随着应...

    Java技术栈
  • Vuex数据页面刷新丢失问题解决方案

    用Vue做项目开发很久了,对于vuex能用、会用,但是因为状态脱离页面和刷新丢失两个原因,一直都有种抵触,特别是一些简单的数据都是通过query或者本地存储就解...

    木子墨

扫码关注云+社区

领取腾讯云代金券