SYSTEM
字典
src/content/notes/system/字典.md 字典
哈希表
Redis 字典使用的哈希表结构:
typedef struct dictht {
// 哈希表数组,数组中每个元素指向 dictEntry 结构
dictEntry **table;
// 哈希表大小,数组的长度
unsigned long size;
// 哈希表大小掩码,用于计算索引值,总是等于 【size-1】
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
哈希表节点结构:
typedef struct dictEntry {
// 键
void *key;
// 值,可以是一个指针,或者整数
union {
void *val; // 指针
uint64_t u64;
int64_t s64;
}
// 指向下个哈希表节点,形成链表,用来解决冲突问题
struct dictEntry *next;
} dictEntry;

字典结构
字典,又称为符号表、关联数组、映射(Map),用于保存键值对的数据结构,字典中的每个键都是独一无二的。底层采用哈希表实现,一个哈希表包含多个哈希表节点,每个节点保存一个键值对
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表,数组中的每个项都是一个dictht哈希表,
// 一般情况下字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用
dictht ht[2];
// rehash 索引,当 rehash 不在进行时,值为 -1
int rehashidx;
} dict;
type 属性和 privdata 属性是针对不同类型的键值对, 为创建多态字典而设置的:
- type 属性是指向 dictType 结构的指针, 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数, Redis 会为用途不同的字典设置不同的类型特定函数
- privdata 属性保存了需要传给那些类型特定函数的可选参数

哈希冲突
Redis 使用 MurmurHash 算法来计算键的哈希值,这种算法的优点在于,即使输入的键是有规律的,算法仍能给出一个很好的随机分布性,并且算法的计算速度也非常快
将一个新的键值对添加到字典里,需要先根据键 key 计算出哈希值,然后进行取模运算(取余):
index = hash & dict->ht[x].sizemask
当有两个或以上数量的键被分配到了哈希表数组的同一个索引上时,就称这些键发生了哈希冲突(collision)
Redis 的哈希表使用链地址法(separate chaining)来解决键哈希冲突, 每个哈希表节点都有一个 next 指针,多个节点通过 next 指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向链表连接起来,这就解决了键冲突的问题
dictEntry 节点组成的链表没有指向链表表尾的指针,为了速度考虑,程序总是将新节点添加到链表的表头位置(头插法),时间复杂度为 O(1)

负载因子
负载因子的计算方式:哈希表中的节点数量 / 哈希表的大小(长度)
load_factor = ht[0].used / ht[0].size
为了让哈希表的负载因子(load factor)维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时 ,程序会自动对哈希表的大小进行相应的扩展或者收缩
哈希表执行扩容的条件:
-
服务器没有执行 BGSAVE 或者 BGREWRITEAOF 命令,哈希表的负载因子大于等于 1
-
服务器正在执行 BGSAVE 或者 BGREWRITEAOF 命令,哈希表的负载因子大于等于 5
原因:执行该命令的过程中,Redis 需要创建当前服务器进程的子进程,而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程的使用效率,通过提高执行扩展操作的负载因子,尽可能地避免在子进程存在期间进行哈希表扩展操作,可以避免不必要的内存写入操作,最大限度地节约内存
哈希表执行收缩的条件:负载因子小于 0.1(自动执行,servreCron 中检测)
重新散列
扩展和收缩哈希表的操作通过 rehash(重新散列)来完成,步骤如下:
- 为字典的 ht[1] 哈希表分配空间,空间大小的分配情况:
- 如果执行的是扩展操作,ht[1] 的大小为第一个大于等于 $ht[0].used * 2$ 的 $2^n$
- 如果执行的是收缩操作,ht[1] 的大小为第一个大于等于 $ht[0].used$ 的 $2^n$
- 将保存在 ht[0] 中所有的键值对重新计算哈希值和索引值,迁移到 ht[1] 上
- 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后(ht[0] 变为空表),释放 ht[0],将 ht[1] 设置为 ht[0],并在 ht[1] 创建一个新的空白哈希表,为下一次 rehash 做准备
如果哈希表里保存的键值对数量很少,rehash 就可以在瞬间完成,但是如果哈希表里数据很多,那么要一次性将这些键值对全部 rehash 到 ht[1] 需要大量计算,可能会导致服务器在一段时间内停止服务
Redis 对 rehash 做了优化,使 rehash 的动作并不是一次性、集中式的完成,而是分多次,渐进式的完成,又叫渐进式 rehash
- 为 ht[1] 分配空间,此时字典同时持有 ht[0] 和 ht[1] 两个哈希表
- 在字典中维护了一个索引计数器变量 rehashidx,并将变量的值设为 0,表示 rehash 正式开始
- 在 rehash 进行期间,每次对字典执行增删改查操作时,程序除了执行指定的操作以外,还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1],rehash 完成之后将 rehashidx 属性的值增一
- 随着字典操作的不断执行,最终在某个时间点 ht[0] 的所有键值对都被 rehash 至 ht[1],将 rehashidx 属性的值设为 -1
渐进式 rehash 采用分而治之的方式,将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,从而避免了集中式 rehash 带来的庞大计算量
渐进式 rehash 期间的哈希表操作:
- 字典的查找、删除、更新操作会在两个哈希表上进行,比如查找一个键会先在 ht[0] 上查找,查找不到就去 ht[1] 继续查找
- 字典的添加操作会直接在 ht[1] 上添加,不在 ht[0] 上进行任何添加