【Redis底层解析】字典类型

【Redis底层解析】字典类型

文章目录

​​字典​​​​1. 数据结构​​

​​1.1 哈希表​​​​1.2 哈希表节点​​​​1.3 字典​​

​​2. 哈希算法​​​​3. 解决键冲突​​​​4. rehash (重新散列)​​

字典

字典，是一种保存键值对的抽象数据类型。

字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对等等。

1. 数据结构

1.1 哈希表

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

typedef struct dictht{ dictEntry **table;// 哈希表数组 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码 unsigned long used; //该哈希表已有节点的数量}dictht;

​​table 属性​​​ 是一个数组，数组中的每个元素都是一个指向 ​​dict.h/dictEntry​​​ 结构的指针，每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小，也即是table数组的大小，而 used 属性则记录了哈希表目前已有节点（键值对）的数量。​​sizemask​​​ 属性的值，总是等于​​size-1​​ 。这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。

1.2 哈希表节点

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

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

Key 属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值，可以是一个指针，或是一个 ​​uint64_t​​​ 整数，又或者是一个 ​​int64_t​​ 整数。

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

下图就是如何通过 next 指针，将两个索引值相同的键 k1 和 k0 连接在一起。

连在一起的 ​​键 K1​​​ 和 ​​键 K0​​ 。

1.3 字典

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

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

​​type 属性​​​ 和 ​​privdate 属性​​ 是针对不同类型的键值对，为创建多态字典而设置的：

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

typedef struct dictType{// 计算哈希值的函数unsigned int (*hashFunction)(const void *key);// 复制键的函数void *(*keyDup)(void *privdata,const void *key);// 复制值的函数void *(*keyDup)(void *privdata,const void *obj);// 对比键的函数void *(*keyCompare)(void *privdata,const void *key1,const void *key2);// 销毁键的函数void *(*keyDestructor)(void *privdata,const void *key);// 销毁值的函数void *(*valDestructor)(void *privdata,const void *obj);}dictType;

​​ht 属性​​​是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 只会对 ht[0] 哈希表进行​​rehash​​时使用。

下面展示一个普通状态下（没有进行rehash）的字典。

2. 哈希算法

当要将一个新的键值对，添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

Redis 计算哈希值和索引值的方法如下：

使用字段设置的哈希函数，计算键key的哈希值。

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

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

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

举个例子： 如果我们要将一个键值对 k0 和 v0 添加到字典里面，那么程序会先使用的语句：

hash = dict->type->hashFunction(k0);

计算键 k0 的哈希值。假设计算出来的哈希值是 8 ，那么程序会继续使用语句：

index = hash&dict->ht[0].sizemask=8&3=0;

计算出键 k0 的索引值 0 ，这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引 0 位置上。如下图所示：

3. 解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突。

Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都由一个 next指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以 ​​用在这个单向链表连接起来​​

举个例子：

现有以下结构的时候，也就是dictEntry数组中的 0 和 2 都有了对应的值。

当此时有一个 ​​k2，v2​​​ 要进来了，如果计算出索引值为 ​​2​​ 的时候，就会有冲突，此时就会构建一个 next 链来解决冲突。

4. rehash (重新散列)

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或是减少，为了让哈希表地负载因子维持在一个合理的范围内，当哈希表保持的键值对 ​​数量太多或者太少​​

扩展和收缩哈希表的工作可以通过 rehash 重新散列。

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

如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于​​ht[0].used*2 的$2^{n}$​​（2的n次方幂）如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于​​ht[0].used的$2^{n}$​​

将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面， rehash 值得是重新计算键的哈希值和索引值，然后将键值对放置 ht[1] 哈希表的指定位置上。当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。