字典，又称为符号表（symbol table），关联数组（associative array）或者映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。
字典的实现
Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
4.1.1 哈希表
Redis 字典所使用的哈希表由dict.h/dictht结构定义：
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
table 是一个元素为dictEntry的数组，每个dictEntry包含一个键值对。size属性记录了哈希表的大小，也就是table的大小；used表示哈希表现有节点的数量（table中有多少个元素已使用）；sizemask总等于size-1，这个属性和哈希值一起决定了一个键应该被放到table数组中哪个索引上。
4.1.2 哈希表的节点
哈希表节点使用dictEntry 结构表示，每个dictEntry结构都保存着一个键值对：
typedef struct dictEntry {
void *key;
union{
void *val;
uint64_tu64;
int64_ts64;
} v;
struct dictEntry *next;
} dictEntry;
key记录的是键；v保存的是值，可以是指针，也可以是uint64_t 或者 int64_t 的整数；next属性是指向另一个哈希表节点的指针，将多个哈希值相同的键值对连接在一起，以此来解决键冲突的问题。
4.1.3 字典
Redis中字典由 dict.h/dict 结构来表示：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
in trehashidx;
} dict;
type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的；
- type 属性是一个指向dictType 结构的指针，每个dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
- 而privdata属性则保存了需要传给那些类型特定函数的可选参数。
typedef struct dictType {
unsigned int (*hashFunction) (const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *obj);
} dictType;
一般字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]进行rehash时使用。另一个跟rehash有关的属性就是rehashidx，它记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。
4.2 哈希算法
作为数据库底层实现，或者哈希键的底层实现时，使用MurmurHash2（最新版本为3）来计算哈希值。
4.3 解决键冲突
链地址法解决键冲突，但是由于没有指向链表尾的指针，为了速度考虑，总是将新节点加到表头位置。
4.4 rehash
- 如果是扩展，则ht[1]大小为第一个大于等于ht[0].used*2的2n；如果时收缩，则为第一个大于等于ht[0].used的2n
- 将保存在ht[0]上的值重新hash后放在ht[1]
- 释放ht[0]，将ht[1]设置为ht[0]，在ht[1]上新建空白哈希表。
扩展条件：
- 没有执行BGSAVE 或者BGREWRITEAOF时，负载因子大于等于1
- 执行BGSAVE 或者BGREWRITEAOF时，负载因子大于等于5
因为大多数操作系统都采用的写时复制来优化子进程的使用效率，所以在子进程存在时，提高标准，尽量避免在子进程存在期间进行哈希表扩展操作，节约内存。
收缩条件
- 负载因子小于0.1
4.5 渐进式 rehash
4.6 字典API
欢迎大家关注我的公众号
