Redis设计与实现读书笔记二

• 接读书笔记（一）

3. 字典

• C 语言中没有内置字典，Redis 数据库拿字典作为底层实现，需要构建字典结构及其增删查改 API。在 Redis 中，字典的底层是哈希表，dictionary hash table。dictht 定义如下。

• 这里的 table 是一个数组，数组中每个元素都是指向 dictEntry 的指针。dictEntry 保存着键值对，其定义如下。

• 上边字段中，含义或者作用比较模糊的就是 *next 指针了。这个字段的作用是解决键冲突的。示例如下。

• 好，铺垫完了，开始进入字典结构。

• 这里的每个字段都有重要的作用。type 和 privdata 指针支持了字典的多态。实现多态的原理：type 为 dictType 结构的指针，而 dictType 则是保存了用于处理特定键值对的类型特定函数，privdata 保存了需要传给类型特定函数的可选参数。

• ht 字段保存了两个哈希表，第一个表是正常使用，第二个则是 rehash 的时候使用。rehashidx 字段也是 rehash 进度相关，没有进行 rehash 的时候，值为 -1。完整的字典，普通状态下的示意图如下。

• 添加键值对到字典的步骤：

  1. 根据键值对计算哈希值和索引值
  2. 根据索引值找到哈希表数组（dictEntry[]）的指定索引
  3. 将键值对信息存放在 dictEntry 里边
• 上边的三个步骤逻辑上存在一个问题——索引冲突！
• 根据哈希算法的不同，哈希碰撞的概率不同。键值对 A 和键值对 B 被分配到相同的索引，怎么办！
• 链地址法，这也就是 dictEntry 里边有个 next 指针的原因了。后添加的会被添加到表头。示意图如下。

• 至此，字典的功能实现基本完成，但是，工程实现还没有！什么意思？工程的意思是对字典的操作是持续不断的，大量的。这个时候就需要 rehash，优化哈希表。比如，dictEntry 数组的有些索引没有值，有些存在比较长的链。
• 所以，从工程的角度考虑，rehash 这个步骤必不可少。dict 结构中有几个字段是用于 rehash 的。rehash 的细节可以看原书或者别的资料。