第 4 章 字典

字典在 Redis 的应用：数据库、哈希键的底层实现之一

4.1 字典的实现

4.1.1 哈希表

哈希表由 dict.h/dictht 结构定义

• table 是一个数组，每个元素都是一个指向 dict.h/dictEntry 结构的指针，而每个 dictEntry 保存着一对键值对

• size 是记录哈希表大小，即 table 数组大小

• used 记录已有节点的数量

• sizemask = size - 1，与哈希值一起决定键应该放在哪个 table 数组的索引上面

4.1.2 哈希表节点

• key：键值对中的键
• v：值，可以是指针，可以是 uint64_t 整数或 int64_t 整数
• next：指向另一个哈希表节点的指针，解决哈希冲突，链地址法

4.1.3 字典

字典由 dict.h/dict 结构表示：

type 和 private 是针对不同类型的键值对，为多态字典设置的

• type：指向 dictType 结构的指针，每个 dictType 结构 保存了一簇用于操作特定类型键值对的函数，用途不同的字典设置不同的类型特定函数
  • 
• 保存了需要传给类型特定函数的可选参数

ht：包含两个项的数组，数组中每个项都是一个 dictht 哈希表，一般情况下字典使用 ht[0] 哈希表，ht[1] 哈希表只在 rehash 时使用

rehashidx：与 rehash 有关，记录 rehash 进度，没有进行则为 -1

普通状态下的字典：

4.2 哈希算法

Redis 计算哈希值与索引值：

例子：

当字典被用作数据库底层或哈希表底层时，Redis3.0 使用 MurmurHash 算法计算哈希值

优点：即使输入的键是有规律的，但仍能给出很好的随机分布性，计算快

4.3 解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面，则发生了冲突

Redis 的哈希表使用链地址法解决链冲突，每个节点都有 next 指针，分配到同一索引的节点连接成单向链表

dictEntry 节点组成的链表没有指向链表表尾的指针，一般总是将新节点添加到链表的表头位置，时间复杂度 O(1)，排在其他已有节点前面

4.4 rehash

为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存点 键值对数量过多或多少时，程序需要通过 rehash(重新散列) 对哈希表的大小进行相应的扩展或者收缩

步骤：

• 为字典的 ht[1] 哈希表分配空间，大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量，即 ht[0].used

  • 如果是扩展，ht[1] 大小为第一个大于等于 ht[0].used * 2 的 2^n

  • 如果是收缩，ht[1] 大小为第一个大于等于 ht[0].used 的 2^n

• 将保存在 ht[0] 中的所有键值对放置在 ht[1] 哈希表的指定位置上，rehash 指的是重新计算键的哈希值和索引值，将键值对放置在 ht[1] 指定的位置上

• 当 ht[0] 的键值对都迁移到 ht[1] 上后，释放 ht[0]，将 ht[1] 设置 为 ht[0] ，并在 ht[1] 新创建一个新的空白哈希表，准备下一次 rehash

哈希表的扩展与收缩

以下条件满足一个时，自动开始扩展操作：

• 服务器目前没有执行 BESAVE 或 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 1

• 服务器目前正在执行 BGSAVE 或者 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 5

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

load_factory = ht[0].used / ht[0].size

根据是否执行 BGSAVE 或者 BGREWRITEAOF 命令，负载因子也不同，执行过程中，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程的使用效率，所以子进程存在时，服务器会提高执行扩展操作的负载因子，从而避免在子进程存在期间进行哈希表扩展操作，可以避免不必要的内存写入操作，节约内存

4.5 渐进式 rehash

扩展或收缩 ht[0] 里面的所有键值对 rehash 到 ht[1] 中，但此动作是多次地、渐进式地完成

原因是键值对多时可能导致服务器在一段时间内停止服务

详细步骤

1. 为 ht[1] 分配空间
2. 在字典中维持索引计数器 rehashinx，值为 0 ，表示 rehash 工作正式开始
3. rehash 中，每次对字典执行添加、删除、查找、更新操作时，除了执行指定的操作外，还会顺带将 ht[0] 哈希表在 rehashinx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 结束时，rehashinx 属性的值增 1
4. 在某个时间点 ht[0] 的所有键值对都会被 Rehash 至 ht[1] 上，此时 rehash 的值为 -1。表示操作完成

好处：

? 采取分而治之的方式，将 rehash 键值对所需的计算工作平均摊到对字典的每个添加、删除、查找、更新操作上，避免庞大计算量

渐进式 rehash 执行期间的哈希表操作

过程中会同时使用 ht[0] 和 ht[1]，删除、查找、更新等操作会在两个哈希表上进行

而新添加到字典的键值对一律被保存到 ht[1] 中，保证 ht[0] 的数量只减不增，最终成为空表

4.6 字典 API

Redis设计与实现 第 4 章 字典

原文：https://www.cnblogs.com/zephxu/p/14886814.html