说说 Redis 中的字典？数据库松生的博客-

个人学习 Redis 的总结学习笔记，参考资料都在文末给出，建议阅读
内容较多，不迷路~

字典

概述

Redis 使用C来实现，Redis的数据库使用字典来作为底层的实现，对数据库的增、删、改、查操作都是构建在对字典的操作之上的。

哈希表

Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，每个哈希表节点就保存了一个字典中的一个键值对。

typedef struct dictht {     dictEntry **table; //哈希表数组 unsigned long size; //哈希表大小 unsigned long sizemask; //哈希表大小掩码，用于计算索引值，等于 size - 1 unsigned long used; //该哈希表已有节点的数量 } dictht; 

• table：数组，每个元素都是指针，指向 dict.h/dictEntry 结构，每个 dict.h/dictEntry 结构保存一个键值对。
• size：记录哈希表（table 数组）的大小。
• used：记录已有节点（键值对）的数量。
• sizemask：等于 size – 1，和哈希值一起决定一个键应该被放到 table 的哪个索引上。

哈希表节点

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

• next：指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突问题。

字典

Redis 的字典 dict 中包含两个哈希表 dictht，这是为了方便进行 rehash 操作。在扩容时，将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上面，完成之后释放空间并交换两个 dictht 的角色。

typedef struct dict {     dictType *type; //类型特定函数     void *privdata; //私有数据     dictht ht[2];//哈希表     long rehashidx; //rehash 索引，当 rehash 不在进行时，值为 -1 unsigned long iterators; /* number of iterators currently running */ } dict; 

• type：一个指向 dicType 的结构指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。
• private：保存需要传给哪些类型特定函数的可选参数。
• ht：数组中每个项都是一个 dicthth 哈希表，一般只使用 ht[0]，ht[1] 只会在对 ht[0] 进行 rehash 时使用。
• rehashidx：记录了 rehash 的进度，如果没有在进行 rehash，则为 -1。

哈希算法

当字典被用作数据库或哈希键的底层实现时，Redis 使用 MurmurHash2 算法来计算键的哈希值。

计算

1. 使用字典设置的哈希函数，计算键 key 的哈希值

hash = dict->type->hashFunction(key) 

2. 使用哈希表的 sizemask 属性和哈希值，计算出索引值。根据情况不同，ht[x]可以是ht[0]或者ht[1]

index = hash & dict->ht[x].sizemask 

键冲突

Redis 的哈希表采用链地址法解决哈希冲突，DictEntry 节点组成的链表没有尾指针，所以新结点会被添加到链表头。

Rehash

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

rehash 操作不是一次性完成，而是采用渐进方式，这是为了避免一次性执行过多的 rehash 操作给服务器带来过大的负担。

渐进式 rehash 通过记录 dict 的 rehashidx 完成，它从 0 开始，然后每执行一次 rehash 都会递增。例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。

在 rehash 期间，每次对字典执行添加、删除、查找或者更新操作时，都会执行一次渐进式 rehash。

在 rehash 期间，新的键值对一律被保存到 ht[1]中，ht[0] 不再执行任何添加操作，最终 ht[0] 会变成空表。

采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上，因此对字典的查找操作会先到 ht[0] 中查找，查找不到才会去 ht[1]。

字典API

如果对你有帮助，请点个赞，加个噢！

参考资料

《Redis设计与实践》
cyc2018