字典

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

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

1. 数据结构

1.1 哈希表

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

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

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;
1
2
3
4
5
6
7
8
9

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
}
1
2
3
4
5
6

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

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

2. 哈希算法

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

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

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

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

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

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

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

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

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

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

计算出键 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做准备。