字典，又称符号表，是保存键值对的抽象数据结构。很多语言都内置字典这种常用的数据结构，但是C语言没有内置，所以redis自己来实现了字典。
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会为用途不同的字典设置不同的特定处理函数。
privdata则保存了传给那些特定处理函数的可选参数的信息。 -
ht属性包含两个数组，这两个数组都是一个dictht哈希表，一般情况下字典只使用ht[0]这个哈希表，ht[1]只会在对哈希表进行rehash时才会使用。
-
rehashdx记录了rehash当前的进度，如果没有进行rehash，则 rehashdx值为-1
可以看到，字典dict结构中，最重要的就是dictht 这种类型的ht哈希表(平时都是ht[0]在起作用)，哈希表的数据结构dictht定义为：
typedef struct dictht {
dictEntry **table; //哈希表数组
unsigned long size; //哈希表大小
unsigned long sizemask; //用于计算索引值,
//总是等于 size - 1
unsigned long used; //哈希表已有节点数量
} dictht;
- table属性是一个数组，数组中每个元素都是指向一个dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
- size属性记录了hash表的大小，也就是table这个数组的大小。
- sizemask属性和哈希值共同决定了一个键应该被放到数组的哪个索引上。
可以看到，哈希表结构dictht中，最重要的就是table中元素指向的哈希表节点dictEntry这种键值对结构，hash表节点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属性是指向另一个哈希表节点的指针，这个指针把多个哈希值相同的节点连接在一起，来解决hash碰撞问题。
下图是普通状态(不是在rehash状态)下的字典：
Paste_Image.png
在这个字典中，ht[0]这个hashtable中，table数组中有4个哈希节点(ditcEntry)，其中哈希值为0和3的节点无键值对，哈希值为1的节点有两个键值对，用next指针相连，哈希值为2的节点有一个键值对。
还可以看到，字典在普通状态下，ht[1]这个hashtable里面，table这个数组没有元素，为空。
哈希算法
当要将一个新的键值对添加到字典里面时，程序会根据键计算出哈希值和索引值，然后再根据索引值将新键值对放到哈希表数组指定的索引上。
解决键冲突
可能存在这样一种情况：两个不同的键值对，计算出的哈希值和索引值是一样的。这就叫hash碰撞。怎么解决hash碰撞的问题呢？？我们想到了每个hash节点都有一个next指针，借助于这个next指针，我们可以将哈希值一样的节点串起来，形成一个单链表。
rehash
随着键值对的逐渐增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对太多或者太少时，程序需要对哈希表进行相应的扩展或者收缩，这个过程叫做rehash。
Redis 对字典的哈希表执行 rehash 的步骤如下:
- 为字典的 ht[1] 哈希表分配空间,空间的大小取决于要执行的操作,以及ht[0]当前包含的键值对数量( used 属性值):
如果执行的是扩展操作,那么 ht[1] 的大小为第一个大于等于ht[0].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].used 当前值为4 , $2^3$ 恰好是第一个大于等于 4*2 的值,所以 ht1 哈希表的大小设置为8,下图展示了 ht1 分配了空间之后字典的样子.
此处输入图片的描述
将 ht[0] 包含的四个键值对 rehash 到 ht1, 图下图所示:
此处输入图片的描述
释放 ht[0], 将 ht1 设置为 ht[0]. 再分配一个空哈希表. 哈希表的大小由原来的4 扩展至8.
此处输入图片的描述
渐进式rehash
拓展或者收缩哈希表需要将ht[0]里所有的键值对重新hash到ht[1]中，但是这个rehash动作并不是一次性集中式完成的。而是分多次渐进式完成的。原因也很清楚，就是键值对过多时，一次性rehash肯定会消耗服务器大量的计算资源，可能会对服务器的性能造成影响。
以下是渐进式rehash的步骤：
- 为ht[1]分配空间
- 在字典中维持一个索引计数器变量 rehashidx，将它的值设置为0，表示rehash正式开始。
- 在rehash进行期间，每次对字典进行增删改查时，顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]中，同时将rehashidx增加1
- 随着rehash的不断进行，最终在某个时间点上，ht[0]上的所有键值对都rehash到ht[1]上了，这时将rehashidx属性置为-1，表示rehash操作完成。
网友评论