1 字典

字典是符号表，是一种用于保存键值对的抽象数据结构。字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点保存了字典中的一个键值对。

1.1哈希表的实现

typedef struct dictht{
    //哈希表数组redis设计与实现
    dictEntry **table;
    
    //哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码,用于计算索引值
    unsigned long sizemask;
    
    // 该哈希表已有节点的数量
    unsigned long used;
    
}dictht;

• size 属性记录了哈希表的大小
• used 属性则记录了哈希表目前已有节点的数量
• sizemask 属性的值总是等于size-1

1.2哈希表节点的实现

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

• key 属性保存键值对中的键

• v 属性保存键值对中的值

• next 属性指向另一个哈希表节点的指针，此指针将多个哈希值相同的键值对链接在一起，解决键冲突的问题。

1.3 字典的实现

typedef struct dict{
    //  类型特定函数
    dictType *type;
    
    //私有数据
    void *privata;
    
    // 哈希表
    dictht ht[2];
    
    //rehash 索引
    int rehashidx;
    
    
}dict;

• type 属性是一个指向dictType结构的指针，dictType结构保存了用于操作特定类型键值对的函数
• privdata 属性保存了需要传给那些类型特定函数的可选参数
• ht 属性是一个包含两个项的数组，每一个项中都是哈希表，字典只使用ht[0]哈希表，ht[1]哈希表只会在对 h[0]rehash时才使用
• rehashidx 记录了rehash目前的进度，没有则为-1;

typedef struct dictType{
    // 计算哈希值函数
    unsigned int (*hashFunction) (const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privata,const void *key);
    //复制值的函数
    void *(*valDup)(void *privata,const void *obj);
    //对比键的函数
    int （*keyCompare）(void *privata,const void *key1,const void *key2);
    //销毁键的函数
    void (*keyDestructor)(void *privata,void *key);
    //销毁值的函数
    void (*valDestructor)(void *privata,void *obj);
    
}dictType;

2 哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

// 使用字典设置hash函数计算key的哈希值
hash=dict->type->hashFunction(key);

//使用哈希表的sizemask属性和哈希值，计算出索引值
index=hash & dict->ht[x].sizemask;

3 解决键冲突

redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成单向链表，被分配到同一个索引上的多个节点可以用这个单向链表链接起来，这就解决了键冲突。

4 rehash

哈希表保存的键值对会逐渐地增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多，或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展或收缩可以通过重新散列操作来完成，redis对hash表执行rehash的步骤：

1 为字典的ht[1]哈希表分配空间，空间的大小取决于要执行的操作。

• 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于 ht[0].used*2的2的n次方幂
• 如果执行的是 收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂

2 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，并将键值对放到ht[1]哈希表

3 当ht[0] 为空表后，释放ht[0],将ht[1]设置为ht[0] ,并为ht[1]新创建一个空白哈希表。

4.1哈希表的扩展与收缩

哈希表负载因子 = 哈希表已保存节点数量 / 哈希表大小

• 服务器没有执行BGSAVE命令，并且哈希表的负载因子大于等于1 执行扩展操作

• 当哈希表的负载因子 小于0.1 时，执行收缩操作。

4.2 渐进式rehash

为了避免rehash对服务器性能造成影响，服务器不是一次将ht[0]里面所有键值对全部rehash到ht[1],而是分多次，渐进式将里面键值对rehash到ht[1],

1 为ht[1] 分配空间

2 在字典中维持一个索引计数器变量 rehashidx ,并将它的值设置为0,表示rehash开始

3 在rehash进行间，每次对字典进行添加，删除，查找,更新操作时，程序除了执行指定的操作外还会顺带将ht[0] 哈希表在rehashidx 索引上的所有键值对rehash到ht[1],rehash 工作完成后，将其属性值加一

4 当所有键值对都被rehash到ht[1],程序将rehashidx属性值设为-1,rehash更新完成

在渐进式rehash进行期间，字典的删除，查找，更新操作是在两个哈希表上进行，如查找操作程序会先在ht[0]里面进行查找，没找到就会到ht[1] 进行查找。

此外添加操作，会被保存到ht[1]里面，而ht[0]包含的键值对数量会只减不增。

5 重点

• 每个字典带有两个哈希表，一个平时使用，另一个尽在rehash使用

• 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值会连接成一个单向链表

• 在对哈希表进行扩展或者收缩时，不是一次性完成，而是渐进式完成的