跳跃表数据结构与算法分析

时间：2023-01-16 12:12:35

作者：京东物流 纪卓志

目前市面上充斥着大量关于跳跃表结构与Redis的源码解析，但是经过长期观察后发现大都只是在停留在代码的表面，而没有系统性地介绍跳跃表的由来以及各种常量的由来。作为一种概率数据结构，理解各种常量的由来可以更好地进行变化并应用到高性能功能开发中。本文没有重复地以对现有优秀实现进行代码分析，而是通过对跳跃表进行了系统性地介绍与形式化分析，并给出了在特定场景下的跳跃表扩展方式，方便读者更好地理解跳跃表数据结构。

跳跃表[1,2,3]是一种用于在大多数应用程序中取代平衡树的概率数据结构。跳跃表拥有与平衡树相同的期望时间上界，并且更简单、更快、是用更少的空间。在查找与列表的线性操作上，比平衡树更快，并且更简单。

概率平衡也可以被用在基于树的数据结构[4]上，例如树堆（Treap）。与平衡二叉树相同，跳跃表也实现了以下两种操作

  1. 通过搜索引用[5]，可以保证从任意元素开始，搜索到在列表中间隔为k的元素的任意期望时间是O(logk)
  2. 实现线性表的常规操作（例如_将元素插入到列表第k个元素后面_）

这几种操作在平衡树中也可以实现，但是在跳跃表中实现起来更简单而且非常的快，并且通常情况下很难在平衡树中直接实现（树的线索化可以实现与链表相同的效果，但是这使得实现变得更加复杂[6]）

预览

最简单的支持查找的数据结构可能就是链表。Figure.1是一个简单的链表。在链表中执行一次查找的时间正比于必须考查的节点个数，这个个数最多是N。

跳跃表数据结构与算法分析

Figure.1 Linked List

Figure.2表示一个链表，在该链表中，每个一个节点就有一个附加的指针指向它在表中的前两个位置上的节点。正因为这个前向指针，在最坏情况下最多考查⌈N/2⌉+1个节点。

跳跃表数据结构与算法分析

Figure.2 Linked List with fingers to the 2nd forward elements

Figure.3将这种想法扩展，每个序数是4的倍数的节点都有一个指针指向下一个序数为4的倍数的节点。只有⌈N/4⌉+2个节点被考查。

跳跃表数据结构与算法分析

Figure.3 Linked List with fingers to the 4th forward elements

这种跳跃幅度的一般情况如Figure.4所示。每个2i节点就有一个指针指向下一个2i节点，前向指针的间隔最大为N/2。可以证明总的指针最大不会超过2N（见空间复杂度分析），但现在在一次查找中最多考查⌈logN⌉个节点。这意味着一次查找中总的时间消耗为O(logN)，也就是说在这种数据结构中的查找基本等同于二分查找（binary search）。

跳跃表数据结构与算法分析

Figure.4 Linked List with fingers to the 2ith forward elements

在这种数据结构中，每个元素都由一个节点表示。每个节点都有一个高度（height）或级别（level），表示节点所拥有的前向指针数量。每个节点的第i个前向指针指向下一个级别为i或更高的节点。

在前面描述的数据结构中，每个节点的级别都是与元素数量有关的，当插入或删除时需要对数据结构进行调整来满足这样的约束，这是很呆板且低效的。为此，可以_将每个2i节点就有一个指针指向下一个2i节点_的限制去掉，当新元素插入时为每个新节点分配一个随机的级别而不用考虑数据结构的元素数量。

跳跃表数据结构与算法分析

跳跃表数据结构与算法分析

Figure.5 Skip List

数据结构

到此为止，已经得到了所有让链表支持快速查找的充要条件，而这种形式的数据结构就是跳跃表。接下来将会使用更正规的方式来定义跳跃表

  1. 所有元素在跳跃表中都是由一个节点表示。
  2. 每个节点都有一个高度或级别，有时候也可以称之为阶（step），节点的级别是一个与元素总数无关的随机数。规定NULL的级别是∞。
  3. 每个级别为k的节点都有k个前向指针，且第i个前向指针指向下一个级别为i或更高的节点。
  4. 每个节点的级别都不会超过一个明确的常量MaxLevel。整个跳跃表的级别是所有节点的级别的最高值。如果跳跃表是空的，那么跳跃表的级别就是1。
  5. 存在一个头节点head，它的级别是MaxLevel，所有高于跳跃表的级别的前向指针都指向NULL。

稍后将会提到，节点的查找过程是在头节点从*别的指针开始，沿着这个级别一直走，直到找到大于正在寻找的节点的下一个节点（或者是NULL），在此过程中除了头节点外并没有使用到每个节点的级别，因此每个节点无需存储节点的级别。

在跳跃表中，级别为1的前向指针与原始的链表结构中next指针的作用完全相同，因此跳跃表支持所有链表支持的算法。

对应到高级语言中的结构定义如下所示（后续所有代码示例都将使用C语言描述）

#define SKIP_LIST_KEY_TYPE     int
#define SKIP_LIST_VALUE_TYPE   int
#define SKIP_LIST_MAX_LEVEL    32
#define SKIP_LIST_P            0.5

struct Node {
  SKIP_LIST_KEY_TYPE    key;
  SKIP_LIST_VALUE_TYPE  value;
  struct Node          *forwards[]; // flexible array member
};

struct SkipList {
  struct Node *head;
  int          level;
};

struct Node *CreateNode(int level) {
  struct Node *node;
  assert(level > 0);
  node = malloc(sizeof(struct Node) + sizeof(struct Node *) * level);
  return node;
}

struct SkipList *CreateSkipList() {
  struct SkipList *list;
  struct Node     *head;
  int              i;

  list = malloc(sizeof(struct SkipList));
  head = CreateNode(SKIP_LIST_MAX_LEVEL);
  for (i = 0; i < SKIP_LIST_MAX_LEVEL; i++) {
    head->forwards[i] = NULL;
  }
  list->head = head;
  list->level = 1;

  return list;
}

从前面的预览章节中，不难看出MaxLevel的选值影响着跳跃表的查询性能，关于MaxLevel的选值将会在后续章节中进行介绍。在此先将MaxLevel定义为32，这对于232个元素的跳跃表是足够的。延续预览章节中的描述，跳跃表的概率被定义为0.5，关于这个值的选取问题将会在后续章节中进行详细介绍。

算法

搜索

在跳跃表中进行搜索的过程，是通过Z字形遍历所有没有超过要寻找的目标元素的前向指针来完成的。在当前级别没有可以移动的前向指针时，将会移动到下一级别进行搜索。直到在级别为1的时候且没有可以移动的前向指针时停止搜索，此时直接指向的节点（级别为1的前向指针）就是包含目标元素的节点（如果目标元素在列表中的话）。在Figure.6中展示了在跳跃表中搜索元素17的过程。

跳跃表数据结构与算法分析

Figure.6 A search path to find element 17 in Skip List

整个过程的示例代码如下所示，因为高级语言中的数组下标从0开始，因此forwards[0]表示节点的级别为1的前向指针，依此类推

struct Node *SkipListSearch(struct SkipList *list, SKIP_LIST_KEY_TYPE target) {
  struct Node *current;
  int          i;

  current = list->head;
  for (i = list->level - 1; i >= 0; i--) {
    while (current->forwards[i] && current->forwards[i]->key < target) {
      current = current->forwards[i];
    }
  }

  current = current->forwards[0];
  if (current->key == target) {
    return current;
  } else {
    return NULL;
  }
}

插入和删除

在插入和删除节点的过程中，需要执行和搜索相同的逻辑。在搜索的基础上，需要维护一个名为update的向量，它维护的是搜索过程中跳跃表每个级别上遍历到的最右侧的值，表示插入或删除的节点的左侧直接直接指向它的节点，用于在插入或删除后调整节点所在所有级别的前向指针（与朴素的链表节点插入或删除的过程相同）。

当新插入节点的级别超过当前跳跃表的级别时，需要增加跳跃表的级别并将update向量中对应级别的节点修改为head节点。

Figure.7和Figure.8展示了在跳跃表中插入元素16的过程。首先，在Figure.7中执行与搜索相同的查询过程，在每个级别遍历到的最后一个元素在对应层级的前向指针被标记为灰色，表示稍后将会对齐进行调整。接下来在Figure.8中，在元素为13的节点后插入元素16，元素16对应的节点的级别是5，这比跳跃表当前级别要高，因此需要增加跳跃表的级别到5，并将head节点对应级别的前向指针标记为灰色。Figure.8中所有虚线部分都表示调整后的效果。

跳跃表数据结构与算法分析

Figure.7 Search path for inserting element 16

跳跃表数据结构与算法分析

Figure.8 Insert element 16 and adjust forward pointers

struct Node *SkipListInsert(struct SkipList *list, SKIP_LIST_KEY_TYPE key, SKIP_LIST_VALUE_TYPE value) {
  struct Node *update[SKIP_LIST_MAX_LEVEL];
  struct Node *current;
  int          i;
  int          level;

  current = list->head;
  for (i = list->level - 1; i >= 0; i--) {
    while (current->forwards[i] && current->forwards[i]->key < target) {
      current = current->forwards[i];
    }
    update[i] = current;
  }

  current = current->forwards[0];
  if (current->key == target) {
    current->value = value;
    return current;
  }

  level = SkipListRandomLevel();
  if (level > list->level) {
    for (i = list->level; i < level; i++) {
      update[i] = list->header;
    }
  }

  current = CreateNode(level);
  current->key = key;
  current->value = value;

  for (i = 0; i < level; i++) {
    current->forwards[i] = update[i]->forwards[i];
    update[i]->forwards[i] = current;
  }

  return current;
}

在删除节点后，如果删除的节点是跳跃表中级别最大的节点，那么需要降低跳跃表的级别。

Figure.9和Figure.10展示了在跳跃表中删除元素19的过程。首先，在Figure.9中执行与搜索相同的查询过程，在每个级别遍历到的最后一个元素在对应层级的前向指针被标记为灰色，表示稍后将会对齐进行调整。接下来在Figure.10中，首先通过调整前向指针将元素19对应的节点从跳跃表中卸载，因为元素19对应的节点是级别最高的节点，因此将其从跳跃表中移除后需要调整跳跃表的级别。Figure.10中所有虚线部分都表示调整后的效果。

跳跃表数据结构与算法分析

Figure.9 Search path for deleting element 19

跳跃表数据结构与算法分析

Figure.10 Delete element 19 and adjust forward pointers

struct Node *SkipListDelete(struct SkipList *list, SKIP_LIST_KEY_TYPE key) {
  struct Node *update[SKIP_LIST_MAX_LEVEL];
  struct Node *current;
  int          i;

  current = list->head;
  for (i = list->level - 1; i >= 0; i--) {
    while (current->forwards[i] && current->forwards[i]->key < key) {
      current = current->forwards[i];
    }
    update[i] = current;
  }

  current = current->forwards[0];
  if (current && current->key == key) {
    for (i = 0; i < list->level; i++) {
      if (update[i]->forwards[i] == current) {
        update[i]->forwards[i] = current->forwards[i];
      } else {
        break;
      }
    }

    while (list->level > 1 && list->head->forwards[list->level - 1] == NULL) {
      list->level--;
    }
  }

  return current;
}

生成随机级别

跳跃表数据结构与算法分析

int SkipListRandomLevel() {
  int level;
  level = 1;
  while (random() < RAND_MAX * SKIP_LIST_P && level <= SKIP_LIST_MAX_LEVEL) {
    level++;
  }
  return level;
}

以下表格为按上面算法执行232次后，所生成的随机级别的分布情况。

1 2 3 4 5 6 7 8
2147540777 1073690199 536842769 268443025 134218607 67116853 33563644 16774262
9 10 11 12 13 14 15 16
8387857 4193114 2098160 1049903 523316 262056 131455 65943
17 18 19 20 21 22 23 24
32611 16396 8227 4053 2046 1036 492 249
25 26 27 28 29 30 31 32
121 55 34 16 7 9 2 1

 

相关文章