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

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呢?

4.1 skipList & AVL 之间的选择

1.  从算法实现难度上来较量，skiplist比均衡树要简朴得多。
2.  均衡树的插入和删除操纵也许激发子树的调解，逻辑伟大，而skiplist的插入和删除只必要修改相邻节点的指针，操纵简朴又快速。
3.  查找单个key，skiplist僻静衡树的时刻伟大度都为O(log n)，概略相等。
4.  在做范畴查找的时辰，均衡树比skiplist操纵要伟大。
5.  skiplist和各类均衡树（如AVL、红黑树等）的元素是有序分列的。

可以看到，skipList中的元素是有序的，以是跳跃表在redis顶用在有序荟萃键、集群节点内部数据布局

4.2 源码

跳跃表节点：

typedef struct zskiplistNode {  
    // 退却指针  
    struct zskiplistNode *backward;  
    // 分值  
    double score;  
    // 成员工具  
    robj *obj;  
    // 层  
    struct zskiplistLevel {  
        // 提高指针  
        struct zskiplistNode *forward;  
        // 跨度  
        unsigned int span;  
    } level[];  
} zskiplistNode; 

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!