定义
字典又称为符号表，映射或关联数组，是一种用于保存键值对的抽象数据结构
由于C语言中并没有内置这种数据结构，因此Redis构建了自己的字典实现
字典实现
Redis中的字典实现采用哈希表作为底层实现，一个哈希表中有多个哈希表节点，而每一个哈希表节点中保存着字典中所指的一个键值对
字典结构定义
typedef struct dict {
// 哈希表
dictht ht[2];
// rehash 索引,当rehash不在进行时，值为-1
int rehashidx;
}
可见其内部定义了一个哈希表数组ht，其包含两个哈希表，另一个参数为rehashidx，该参数在后续的rehash时会重点分析
接下来看看哈希表dictht结构定义是什么样的
哈希表结构定义
typedef struct dictht {
// 哈希表节点Entry数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 该哈希表已有节点数量
unsigned long used;
}
哈希表结构内部主要是一个Entry数组，另外还有一些哈希数组长度，已有节点数等参数，下面看看哈希表节点结构定义
哈希表节点结构定义
哈希表节点使用dictEntry结构表示，每一个dictEntry结构都保存着一个键值对
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
unint64_t u64;
int64_t s64;
} v;
// 指向下一个哈希表节点，形成单向链表结构，当hash冲突时使用
struct dictEntry *next;
}
普通字典结构图
没有进行rehash的字典结构图
哈希算法
当向字典中新增一个键值对时，Redis程序会
-
Redis根据哈希算法计算出键key的哈希值
-
根据哈希值和哈希表的sizemask属性计算出索引值（采用取模的形式）
-
构建新的键值对节点实例dictEntry
-
将节点索引放到哈希表数组的指定索引上
Redis使用MurmurHash2算法来计算键的哈希值，该算法最初由08年被Austin Appleby发明，算法具有很好的随机分布性以及非常快的计算速度
Redis如何解决键冲突
当有两个或以上数量的键被分配到哈希表的同一个索引上的时候，就发生了键冲突
Redis采用链地址法来解决键冲突，即每一个哈希表节点都有一个next指针，来指向被分配到同一个哈希表索引上的其他节点，形成一个单向链表。
为了考虑添加冲突节点速度，Redis程序总是将新Entry节点添加到表头位置，这样添加的时间复杂度就为O(1)，新节点会排在已有节点的前面
何为Rehash？
当操作的不断进行，字典的hash表中保存的键值对会逐渐增加或者逐渐减少，为了让哈希表的负载因子控制在一个合理的范围内，Redis程序需要对整个hash表进行相应的扩展或者收缩
那么既然要扩容或者收缩（哈希表的size会变化，将导致sizemask的变化，最终导致每一个键索引计算发生变化），就需要进行重新散列，重新计算hash值以及索引值，而重新散列的过程就是Rehash，Redis中的rehash步骤可分为以下：
-
为字典的ht[1]分配空间
-
将保存在ht[0]中的所有键值对rehash到ht[1]中，rehash指的是重新计算ht[0]中键的hash值以及索引值，将重新计算后的键值对放到ht[1]哈希表的相应位置上
-
当ht[0]的所有键值对都完成迁移工作后，释放ht[0]，将ht[1]设置为ht[0]，而原来的ht[0]就成为了一个空白的ht[1]，为下一次的rehash作准备
负载因子
load_factory = ht[0].used /ht[0].size
指的是哈希表中已有节点数量/哈希表大小的值
例如一个大小为512的哈希表，包含有256个键值对，该哈希表的负载因子即为0.5
-
当哈希表的负载因子大于1，且没有执行BGSAVE OR BGREWRITEAOF命令时会自动进行扩容操作
-
当哈希表的负载因子小于0.1时，会自动进行收缩操作
何为渐进式Rehash？
以上我们知道，hash表的扩容或收缩操作需要将ht[0]中的所有键值对rehash到ht[1]中，但是如果该字典中有大量的键值对，那么一次性，集中式的完成整个rehash操作的过程就需要Redis程序耗费大量时间，以及中途不能进行任何的redis服务了，为了避免集中式rehash对redis服务器造成影响，redis服务器并不是一次性将ht[0]内的所有键值对全部rehash到ht[1]，而是分多次，渐进式的rehash
渐进式rehash过程如下：
-
ht[1]分配空间，字典同时持有ht[0] 和 ht[1]两个哈希表
-
字典中维持一个索引计数器rehashidx（未进行rehash时值为-1），将其值设为0，表示rehash工作正式开始
-
每一次对字典进行添加，删除，查找，更新，redis程序除了执行指定的操作之外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]上，当这一步的rehash工作完成之后，redis程序会将rehashidx属性的值加1
-
随着字典操作的不断进行，最终会在某个时间点上，ht[0] 的所有键值对都会被rehash到ht[1]上，而此时redis会将rehashidx的值设为-1，表示rehash操作完成
由于在渐进式rehash的过程中，字典会同时持有两个哈希表，故在其rehash期间
字典查找：会先从ht[0]中查询，没有的话再去ht[1]中查询，删除/更新操作类似处理
字典新增：一律保存在ht[1]中，ht[0]不会再进行任何的添加操作，从而保证ht[0]中的键值对只减不增，并最终变为空表
总结
-
字典再redis中被用于实现数据库
-
redis中的字典采用hash表作为其底层实现，每个字典有两个哈希表，一个平时使用，另一个仅用于rehash
-
redis采用MurmurHash2算法计算键的哈希值，同时采用取模hash表size的方式计算索引
-
当redis发生键冲突时，会采用单向链表的形式进行处理
-
当对哈希表进行扩容或收缩时，需要将现有哈希表中的所有键值对rehash到新的哈希表中，rehash的过程是渐进式的，并非一次性完成
网友评论