转载

【Redis基本数据结构】字典实现

字典, 又称为符号表关联数组或者映射,是一种保存键值对的抽象数据结构.字典作为一种常用数据结构被内置在许多程序语言中,由于 C 语言没有内置这种数据结构, Redis 构建了自己的字典实现.

字典在 Redis 中的应用相当广泛, 比如 Redis 的数据库就是使用字典作为底层实现的, 对数据库的增删改查操作也是构建在对字典的操作之上的.

除了用作数据库之外, 字典还是哈希键的底层之一, 当一个哈希键包含的键值对较多,欧哲键值对中的元素都是比较长的字符串时, Redis 就会使用字典作为哈希键的底层实现.

字典的实现

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:

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

table 属性是一个数组, 数组中每个元素都是一个指向 dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对.
size 属性记录了哈希表的大小,也就是 table 数组的大小
sizemask 属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面

哈希表节点

哈希表节点使用 dictEntry 表示,每个 dictEntry 结构保存着一个键值对

typedef struct dictEntry {     void *key;          //键     union {             //值         void *val;         uint_64 u64;         int64_t s64;     } v;                         sturct dictEntry *next; //指向下个哈希表节点,形成链表 } dictEntry;

注意这里 v 属性保存着键值对中的值,其中的键值可以是指针,或是 uint_64 整数,又或者是 int64_t 整数.
next 属性是指向另一个哈希表节点的指针,这个指针将多个哈希值相同的键值对连接在一起,以此来解决键值冲突(collision)问题.

字典

Redis 中的字典由 dict.h/dict 结构表示:

typedef struct dict {     dictType *type;     //类型特定函数     void *privdata;     //私有数据     dictht ht[2];       //哈希表     int rehashdx;      //rehash 索引,当 rehash 不在进行时,值为-1 } dict;

type 和 privdata 是针对不同类型的键值对,为创建多态字典而设置的

`type`指向一个 `dictType` 结构的指针, 每个` dictType` 结构保存了一簇用于操作特作特定类型键值对的函数, Redis 会为用途不同的字典设置不同的类型特定函数.  而` pridata` 则保存了需要传给那些特定类型函数看可选参数.

ht 属性,包含两个数组,数组的每一项都是一个 dictht 哈希表,一般情况下字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对哈希表进行 rehash 时使用.
rehashidex 记录了 rehash 当前的进度,如果没有进行 rehash, 值就为-1.

下图展示了一个普通状态下的字典(没有 rehash 进行)

【Redis基本数据结构】字典实现

哈希算法

当要将一个新的键值对添加到字典里面时,程序会根据键计算出哈希值和索引值,然后再根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上.Redis 计算哈希值和索引的方法如下:

hash = dict->type->hashFunction(k); index = hash & dict->ht[0].sizemask

假设,要将上图中键值对 k1和v1添加到字典中,使用 hashFunction 计算出 k1 的哈希值为9,那么

 index = 9 & 3 = 1;

Redis 使用 MurmurHash2 算法来计算键的哈希值.

解决键冲突

当有两个或两个以上的键被分配到了哈希表数组的同一索引上时,称这些键发生了冲突( collision )

Redis 的哈希表使用链地址法来解决冲突,每个哈希表节点都有一个 next 指针,多个哈希表节点可以用 next 指针构成一个单项链表,被分配到同一个索引上的多个节点可以用这个对单向链表连接起来,这就解决了键冲突的问题.

如前面的字典示意图所示, 键 k0 和 k1 的索引值均为1,这里只需用 next 指针将两个节点连接起来.

,因为 dictEntry 节点组成的链表没有表尾指针,为了速度考虑,程序总是将新节点调价到链表的表头位置,排在其他已有节点的前面,这样插入的复杂度为$ O(1)$.

Rehash

随着操作的不断进行, 哈希表保存的键值对会逐渐地增多或减少,为了让哈希表的负载因子维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩.这个过程叫做 rehash .

Redis 对字典的哈希表执行 rehash 的步骤如下:

为字典的 ht[1] 哈希表分配空间,空间的大小取决于要执行的操作,以及 ht0] 当前包含的键值对数量( used 属性值):

如果执行的是扩展操作,那么 ht[1] 的大小为第一个大于等于 ht0].used*2 的 $2^n$ .
如果执行的是收缩操作,那么 ht[1] 的大小为打一个大于等于 ht[0].used 的$2^n$.

将保存在 ht[0] 中所有键值对 rehash 到 ht[1] 上面: 任何事指的是重新计算键的哈希值和索引值,然后键键值对放到 ht[1] 哈希表的指定位置.
当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后, 释放 ht[0] , 再将 ht[1] 设置为 ht[0] ,并在 ht[1] 后面创建一个空白的哈希表.

举个例子,假设程序要对下图的 `ht[0] 进行扩展操作

【Redis基本数据结构】字典实现

ht[0].used 当前值为4 , $2^3$ 恰好是第一个大于等于 4*2 的值,所以 ht[1] 哈希表的大小设置为8,下图展示了 ht[1] 分配了空间之后字典的样子.
```
![此处输入图片的描述][4] 
```
将 ht[0] 包含的四个键值对 rehash 到 ht[1], 图下图所示:
```
![此处输入图片的描述][5] 
```
释放 ht[0], 将 ht[1] 设置为 ht[0]. 再分配一个空哈希表. 哈希表的大小由原来的4 扩展至8.
```
![此处输入图片的描述][6] 
```

渐进式 rehash

上一节说过, 扩展或收缩哈希表需要将 ht[0] 里的所有键值对 rehash 到 ht[1] 中,但是这个 rehash

动作并不是一次性,集中式完成的,而是分多次,渐进式完成的.

这么做的原因是,当哈希表里保存的键值对多至百万甚至亿级别时,一次性地全部 rehash 的话,庞大的计算量会对服务器性能造成严重影响.

以下是渐进式 rehash 的步骤:

为 ht[1] 分配空间
在字典中维持一个索引计数器变量 rehashidx , 将它的值设置为0,表示 rehash 正式开始
在 rehash 进行期间,每次对字典进行增删改查时,顺带将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 中,同时将 rehashidx 加 1.
随着操作不断进行,最终在某个时间点上, ht[0] 所有的键值对全部 rehash 到 ht[1] 上,这是讲 rehashidx 属性置为 -1,,表示 rehash操作完成.