面试官：你看过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的流程，但是更细一点的讲，它如何进行数据迁的呢？

（编辑：衢州站长网）

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