redis数据结构(三)：字典 dict

redis的字典使用哈希表作为底层实现。
hash表的数据结构

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

hash表节点数据结构

typedef struct dictht {
    
    // 键
    void *key;
    
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    
    // 指向下个节点的指针，形成链表
    struct dicEntry *next;
} dictht;

这里看到链表了吧。redis的hash表，是通过链表发解决冲突的。

字典的数据结构

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

主要看后面两个。有两个哈希表。ht[0]，ht[1]。
正常情况下，只会用到ht[0]；

ht[1] 和 trehashidx 在rehash的时候会用到。

为什么要这么设计？？？

当数据量很大的时候，一次rehash会耗时很久，redis是一个性能要求很高的数据库，不可能让rehash这么长时间无法正常工作。

所以，当触发rehash后。

1. ht[1]先分配内存，大小为第一个大于等于ht[0].used * 2 的 2 的 n次幂。什么意思呢？比如ht[0].used现在是5，乘2之后就是10，第一个大于10的 2的n次幂 是 2的4次幂16。所以ht[1]分配16个格。

2. 将保存在ht[0]中的键值对，rehash到ht[1]上。这里不可能是一次性rehash。所以每次hash的动作，都附属在对字典的增删改查中。什么意思呢？当对字典进行增删改查后，做一次rehash。将rehash的触发世纪分配到每次操作中。那么怎么知道rehash过了哪些值呢。trehashidx这个东西就派上用场了，每次记录rehash的index。
   那么问题来了，两个hash表，读的时候读哪个呢？答：先读新的ht[1]，没查到，再读旧的ht[0]。

3. 当rehash结束的时候，将trehashidx设置为-1。将ht[1]设置为ht[0]，并把新的ht[1]置空，为下一次rehash做准备.

tips： redis就不怕链表挂太多么。比如java变红黑树。理由还是那句话，redis是通过key查询value。不会对value做查询的。