字典中，一个键可以和一个值进行关联，这些关联的键和值就成为键值对。字典中的每个键都是独一无二的，程序可以在字典中根据键找到与之关联的值。字典常作为一种数据结构内置在高级编程语言中，但Redis所使用的c语言没有内置这种数据结构，因此Redis构建了自己的字典实现
1.字典的实现
Redis的字典使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。接下来将分别介绍Redis的哈希表、哈希表节点和字典的实现。
1.1哈希表的实现
Redis字典使用的哈希表由dict.h/dictht结构定义：
typedefstructdictht//哈希表数组dictEntry*table; //哈希表大小unsignedlongsize; // 哈希表大小掩码，用于计算索引值//总是等于 size-1unsignedlongsizemask; //该哈希表已有节点的数量unsignedlongused; } dictht:
- table属性是一个数组，数组的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存这一个键值对。
- size记录table数组的大小。
- used记录当前已有节点的数量，即该字典的元素数量
- sizemask的属性总是size - 1，这个属性和哈希值一起决定一个键放在table数组的哪个索引上
1.2哈希表节点的实现
哈希表节点使用dictEntry结构实现，每个dictEntry结构保存着一个键值对。
typedefstructdictEntry { //键void*key: //值union{ void*val; uint64_tu64; int64_ts64; } v: //指向下个哈希表节点，形成链表structdictEntry*next; } dictEntry;
- key表示键
- v表示对应的值，其中键值对中的值可以是一个指针、uint64位整数或者int64位整数
- next属性是指向另外一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接起来，从而解决键冲突的问题。
1.3字典的实现
Redis中的字典由dict.h/dict结构表示：
typedefstructdict { //类型特定函数dictType*type; //私有数据voidsprivdata; //哈希表dicththt[2]: //rehash 索引// 当rehash 不在进行时，值为一1intrehashidx; /*rehashing not in progress if rehashidx */} dict:
type属性和privdate属性是针对不同类型的键值对，为创建多态字典而设置的：
- type属性是一个指向dictType结构的指针，每个底朝天Type结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
typedefstructdictType{ //计算哈希值的西数unsignedint (*hashFunction) (constvoid*key) ; //复制键的函数voida(*keyDup) (void*privdata, constvoid*key); //复制值的函数void• (evalDup) (voideprivdata, constvoid*obj; //对比键的函数int (*keyCompare) (void*privdata, constvoid*key1, constvoid*key2); //销毁键的函数void (*keyDestructor) (voidaprivdata, voidkey); // 销毁值的函数void (*valDestructor) (voidprivdata, void :obi); }dictType;
- privdata保存了需要传给那些类型特定函数的可选参数
- ht是一个包含两个项的数组，每个项都是有一个dictht哈希表。一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
- rehashidx记录了rehash目前的进度，如果没有rehash，那么它的值为-1
2.哈希算法
当要将一个新的键值对添加到字典里时，程序需要先根据键值对的键计算出哈希值和索引值，再根据索引值，将包含新键值对的哈希表节点放到哈希表数组指定的索引上面。
Redis计算哈希值和索引值的方法：
- 使用字典设置的哈希函数，计算key的哈希值
- 使用哈希表的sizemask属性和哈希值，计算索引值
3.解决哈希冲突
Redis的哈希表使用链地址法来解决哈希冲突，每个哈希表节点都有一个next指针，多个哈希表节点使用next指针连接起来构成单向链表，被分配到同一个索引上的多个节点可以用这个链表连接起来。因为dictEntry节点组成的链表没有执行链表表尾的指针，为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O(1)）。
4.rehash
随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子维持在一个合理的范围之内，程序需要对哈希表的大小进行相应的拓展或者收缩，拓展和收缩哈希表的工作通过执行rehash（重新散列）操作来完成，步骤如下：
1）为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含键值对数量（及ht[0].used属性值）：
- 如果执行的是拓展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂
- 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂。
2）将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
3）迁移之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空白哈希表，为下一次rehash做准备。
注意：rehash并不是一次性的，而是根据ht[0]的键值对大小分几次、渐进式rehash。
