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