Redis之跳表与面试挑战（redis 面试跳表）

Redis之跳表与面试挑战

跳表是一种常见的数据结构，它通常在许多研发环境，尤其是Redis中使用。跳跃表是一种有序的链表结构，允许添加，删除和搜索操作，但是与普通的链表不同，跳跃表具有极其快速的搜索性能和稳定性。

在Redis中，跳跃表用于实现有序集合（set）结构，它有助于快速搜索指定区间内的元素。有序集合是Redis中重要的结构之一，它的实现主要基于跳表，因此在Redis的工程师面试中，经常会问到跳表的相关知识点。

那么关于跳表，经常会问到哪些内容呢？其实，包括以下三大点：

1. 跳表是如何进行检索的？

跳表通过两个层级的跳跃，即索引层和数据层之间的跳跃，来检索元素。检索步骤如下：在索引层从左到右，逐级查找目标元素，找到后转入下一层搜索，直到在数据层搜索到目标元素为止。这样就能够实现极快的检索速度。

2. 跳表的插入、删除操作是如何进行的？

插入操作：插入操作主要有两步：首先在索引层中找到要插入的位置，然后建立指针。接着在数据层插入新的元素，并建立指向下一个元素的指针；

删除操作：删除操作也有两步，首先在索引层中找到要删除的元素，然后将其指针置为空；其次在数据层删除要删除的元素，并修改其前后元素间的指针。

3. 如何确保跳表总是进行有序排列？

一般来讲，插入和删除操作时都会保证跳表仍然是有序的，要保证有序排列，跳表还需要采用一种随机性质的“穿插”技术，即可以在算法添加随机性后按照一定规则进行查找，维持跳表的有序排列，以及在连续插入较多元素时削平跳表水平，使得跳跃表仍然保持有序性。

回顾上面提到的知识点，我们可以拿出以下一段测试代码，来誊明如何使用跳表来测试有序集合的功能性：

#include

#include

#include

#include

using namespace std;

// 测试跳表

void TestSkipList(){

Vector vecData;

vecData.push_back(1);

vecData.push_back(3);

vecData.push_back(18);

vecData.push_back(19);

vecData.push_back(25);

// 创建有序的set

set> setInt(vecData.begin(),vecData.end());

// 通过跳表进行查找

set>::iterator itLow,itHigh;

itLow = setInt.lower_bound(20); //大于等于20

itHigh = setInt.upper_bound(15); //小于15

// 打印出结果

cout

cout

}

int mn(){

TestSkipList();

return 0;

}

以上就是关于Redis的跳表，以及面试中常问的相关知识点。在跳表的运用上，只要掌握了前面提到的几个核心概念，编写代码也就相当容易了。