字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。
字典的实现
redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
哈希表
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;
解释
table 属性是一个数组，数组中美国元素都是一个指向dictEntry结构的指针。
size 记录了哈希表的大小，即table的大小。
used 记录了哈希表目前已有的节点（键值对）的数量。
sizemask 用于计算索引
哈希表节点
实际就是dictEntry结构
typedef struct dictEntry {
//键
void *key;
//值
union{
void *val;
uint64_t u64;
int64_t s64;
} v;
//指向下一个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
解释
v属性保存着键值对中的值，其可以是一个指针、uint64_t整数、int64_t整数。
字典
typedef struct dict {
//类型特定函数
dictType *type;
//私有函数
void *privdata;
//哈希值
dictht ht[2];
//rehash 索引，当rehash不在进行时，值为-1
int trehashidx;
}
解释
tpye属性和privdata属性是针对不同类型的键值对，为创建多台字典而设置的：
type：指向dictTpye结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，redis会为用途不同的字段设置不同的类型特定函数。
privdata：保存了需要传给那些类型特定函数的可选参数。
ht：包含两个项的数组，数组中每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
哈希算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，一般是先计算出哈希值，再通过哈希值生成索引值，放入哈希表里。
解决键冲突
当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突。
redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多高哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以使用这个单向链表连接起来，这就解决了键冲突的问题。
rehash
随着操作的不断执行，哈希表保存的键值对会逐渐的增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成，具体步骤如下：
1、位字典的ht【1】哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht【0】当前包含的键值对数量：
如果执行的是扩展操作，那么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】设置为ht【0】，并在ht【1】新创建一个空白哈希表，为下一次rehash做准备。
总结
字典被广泛用于实现redis的各种功能，其中包括数据库和哈希键。
redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时用，另一个仅在进行rehash时使用。
当字典被用作数据库的底层实现，或者哈希键的底层实现，redis商用MurmurHash2算法来计算键的哈希值。
哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
在对哈希表进行扩展或者收缩操作时，程序需要将现在有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性完成的，而是渐进式的。
网友评论