面试官：你看过Redis数据结构底层实现吗？（上）

面试中，redis也是很受面试官亲睐的一部分。我向在这里讲的是redis的底层数据结构，而不是你理解的五大数据结构。你有没有想过redis底层是怎样的数据结构呢，他们和我们java中的HashMap、List、等使用的数据结构有什么区别呢。

1. 字符串处理(string)

我们都知道redis是用C语言写，但是C语言处理字符串和数组的成本是很高的，下面我分别说几个例子。

没有数据结构支撑的几个问题

1. 极其容易造成缓冲区溢出问题，比如用strcat()，在用这个函数之前必须要先给目标变量分配足够的空间，否则就会溢出。

2. 如果要获取字符串的长度，没有数据结构的支撑，可能就需要遍历，它的复杂度是O(N)

3. 内存重分配。C字符串的每次变更(曾长或缩短)都会对数组作内存重分配。同样，如果是缩短，没有处理好多余的空间，也会造成内存泄漏。
   

好了，Redis自己构建了一种名叫Simple dynamic string(SDS)的数据结构，他分别对这几个问题作了处理。我们先来看看它的结构源码：

struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串
     char buf[];
}

再来说说它的优点：

1. 开发者不用担心字符串变更造成的内存溢出问题。
   
2. 常数时间复杂度获取字符串长度len字段。
   
3. 空间预分配free字段，会默认留够一定的空间防止多次重分配内存。
   

更多了解：https://redis.io/topics/internals-sds

这就是string的底层实现，更是redis对所有字符串数据的处理方式(SDS会被嵌套到别的数据结构里使用)。

2. 链表

Redis的链表在双向链表上扩展了头、尾节点、元素数等属性。

2.1 源码

ListNode节点数据结构：

typedef  struct listNode{
       //前置节点
       struct listNode *prev;
       //后置节点
       struct listNode *next;
       //节点的值
       void *value;  
}listNode

链表数据结构：

typedef struct list{
     //表头节点
     listNode *head;
     //表尾节点
     listNode *tail;
     //链表所包含的节点数量
     unsigned long len;
     //节点值复制函数
     void (*free) (void *ptr);
     //节点值释放函数
     void (*free) (void *ptr);
     //节点值对比函数
     int (*match) (void *ptr,void *key);
}list;

从上面可以看到，Redis的链表有这几个特点：

1. 可以直接获得头、尾节点。
   
2. 常数时间复杂度得到链表长度。
   
3. 是双向链表。

3. 字典(Hash)

Redis的Hash，就是在数组+链表的基础上，进行了一些rehash优化等。

3.1 数据结构源码

哈希表：

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

Hash表节点：

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;  // 单链表结构
} dictEntry;

字典：

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

可以看出：

1. Reids的Hash采用链地址法来处理冲突，然后它没有使用红黑树优化。
   
2. 哈希表节点采用单链表结构。
   
3. rehash优化。
   

下面我们讲一下它的rehash优化。

3.2 rehash

当哈希表的键对泰国或者太少，就需要对哈希表的大小进行调整，redis是如何调整的呢？

1. 我们仔细可以看到dict结构里有个字段dictht ht[2]代表有两个dictht数组。第一步就是为ht[1]哈希表分配空间，大小取决于ht[0]当前使用的情况。

2. 将保存在ht[0]中的数据rehash(重新计算哈希值)到ht[1]上。

3. 当ht[0]中所有键值对都迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并ht[1]初始化，为下一次rehash做准备。

3.3 渐进式rehash

我们在3.2中看到，redis处理rehash的流程，但是更细一点的讲，它如何进行数据迁的呢？

这就涉及到了渐进式rehash，redis考虑到大量数据迁移带来的cpu繁忙(可能导致一段时间内停止服务)，所以采用了渐进式rehash的方案。步骤如下：

1. 为ht[1]分配空间，同时持有两个哈希表(一个空表、一个有数据)。

2. 维持一个技术器rehashidx，初始值0。

3. 每次对字典增删改查，会顺带将ht[0]中的数据迁移到ht[1],rehashidx++(注意：ht[0]中的数据是只减不增的)。

4. 直到rehash操作完成，rehashidx值设为-1。
   

它的好处：采用分而治之的思想，将庞大的迁移工作量划分到每一次CURD中，避免了服务繁忙。

4. 跳跃表

这个数据结构是我面试中见过最多的，它其实特别简单。学过的人可能都知道，它和平衡树性能很相似，但为什么不用平衡树而用skipList呢?