面试官：你看过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; 

（编辑：PHP编程网 - 黄冈站长网）

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