Redis源码阅读笔记之字典（哈希表）
所谓字典，就是一系列的key-value键值对，在redis中，不仅整个数据库的操作以字典为基础（key-value键值对），而且对于redis的数据库的增删改查都是建立在字典之上，redis中的hash数据结构底层实现也使用了字典，当一个哈希键包含较多的键值对或者键值对的内容包含比较长的字符串时都会使用字典来实现。
由于C语言中并没有字典这一数据结构，因此redis利用结构体实现了自己的自字典结构。
redis中的字典由dict.h中dict结构体来表示，源码如下：
/*
* 字典
*/
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;
在字典结构体中有一个指向dictType结构体的指针，它为每一个字典提供了一系列的特定类型的函数操作，其中dictType函数的源码如下：
/*
* 字典类型特定函数
*/
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 *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
在字典中，初始化了大小为2的哈希表dictht（ dictht ht[2];），dictht是一个结构体，它包含了一个哈希表的大小，当前已有的节点数，哈希表数组以及哈希表的掩码大小。初始化了两个哈希表，一个用于正常使用（ht[0]），另一个用于rehash使用（ht[1]）。其中dictht结构体的源码如下：
/*
* 哈希表
*
* 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
*/
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
对于redis中的字典，类似于Java中的HashMap（Java7），使用链地址发解决哈希冲突，因此每一个哈希表的索引对于一个单链表，用来存放相同哈希值的键值对。
在redis中，使用MurmurHash2算法来计算一个键值对的哈希值，首先它会利用键值对的键计算出哈希值，然后利用哈希值与哈希表的掩码计算出该键值对索引，将键值对防止到对用哈希索引的节点上。计算源码如下：
// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
// 计算新哈希表的哈希值，以及节点插入的索引位置
//ht[x]一般 情况下ht[0]，只有在rehash时才有可能是ht[1]哈希表
h = dictHashKey(d, de->key) & d->ht[x].sizemask;
上面已经提到，对于redis中字典的哈希冲突，使用链地址法来解决哈希冲突，即当拥有相同索引的键值对会连接成一条单向链表。由于在dictEntry结构体中没有提供访问链表尾的指针，因此为了提高插入链表的效率，总是会将冲突的键值对插入到链表头：
// 将新节点插入到链表表头
entry->next = ht->table[index];
ht->table[index] = entry;
redis中它会初始化两个哈希表，一个用于正常使用，一个用于rehash，那么它是如何rehash？为什么要rehash呢？
为什么要rehash？
由于对于redis字典的频繁操作，哈希表中的键值对不断的增加或者减少，为了减少哈希表的负担，使得哈希表的负载因子（load factor）在一个合理的范围中，因此在哈希表中的键值对太多或者太少的情况下，程序要适当的对哈希表的大小进行适当的增大和缩小，因此需要rehash。
如何rehash？
主要分为以下步骤：
- 首先为ht[1]哈希表分配空间大小，取决于进行的操作以及ht[0]中哈希表的大小。
- 如果是扩展哈希表，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次幂的大小。如，ht[0]的大小为，要进行扩展操作，那么ht[0]*2=8(2的3次幂)，正好是大于等于8的2的n次幂，因此ht[1]的大小为8.
- 如果是缩小哈希表，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次幂的大小。
- 将ht[0]哈希表上的所有键值对rehash到ht[1]哈希表上（rehash是指重新计算键值对的哈希值以及索引，重新放置到ht[1]的相应位置上）。
- 全部键值对迁移完毕之后，释放ht[0]哈希表，将ht[1]设置为ht[0]，然后重新初始化一个空的哈希表ht[1]，为下一次rehash做准备。
其中哈希表的负载因子可以使用下面公式计算得到：
load_factor=ht[0].used/ht[0].size（哈希表的键值对/哈希表的大小）
在以下两种情况下会进行哈希表的扩展操作：
- 服务器没有执行BGSAVE或者BGREWRITEAOF操作，并且负载因子大于等于1。
- 服务器没有执行BGSAVE或者BGREWRITEAOF操作，并且负载因子大于等于5。
当哈希表的负载因子小于0.1时，会自动进行缩小操作。
对于哈希表的rehash操作，并不是一次性完成，如果一次性完成，那么在数据量大的时候会严重的影响性能，redis使用渐进式的方式，利用分而治之的思想，将rehash操作依赖于每一次的增删改查操作进行，每进行一次操作就rehash一次，直到全部rehash完成。它在内部维护这一个rehashidx索引计数器变量，当rehashidx为0时表示rehash正式开始，当每进行一次rehash该索引计数器变量加1，直到rehash完毕，将该计数器设置为-1。
在rehash期间，对于数据库的每一个操作都会在两个哈希表上进行操作，比如查找操作，如果在ht[0]哈希表上没有查找到，就会去ht[1]哈希表中查找。在操作时只会对ht[0]中的键值对进行减操作，不会进行增加操作，所有增加的键值对都会添加到ht[1]哈希表中，以保证rehash的完成。
整个rehash的源码如下：
/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned.
*
* 执行 N 步渐进式 rehash 。
*
* 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表，
* 返回 0 则表示所有键都已经迁移完毕。
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table.
*
* 注意，每步 rehash 都是以一个哈希表索引（桶）作为单位的，
* 一个桶里可能会有多个节点，
* 被 rehash 的桶里的所有节点都会被移动到新哈希表。
*
* T = O(N)
*/
int dictRehash(dict *d, int n) {
// 只可以在 rehash 进行中时执行
if (!dictIsRehashing(d)) return 0;
// 进行 N 步迁移
// T = O(N)
while(n--) {
dictEntry *de, *nextde;
/* Check if we already rehashed the whole table... */
// 如果 0 号哈希表为空，那么表示 rehash 执行完毕
// T = O(1)
if (d->ht[0].used == 0) {
// 释放 0 号哈希表
zfree(d->ht[0].table);
// 将原来的 1 号哈希表设置为新的 0 号哈希表
d->ht[0] = d->ht[1];
// 重置旧的 1 号哈希表
_dictReset(&d->ht[1]);
// 关闭 rehash 标识
d->rehashidx = -1;
// 返回 0 ，向调用者表示 rehash 已经完成
return 0;
}
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
// 确保 rehashidx 没有越界
assert(d->ht[0].size > (unsigned)d->rehashidx);
// 略过数组中为空的索引，找到下一个非空索引
while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
// 指向该索引的链表表头节点
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
// 将链表中的所有节点迁移到新哈希表
// T = O(1)
while(de) {
unsigned int h;
// 保存下个节点的指针
nextde = de->next;
/* Get the index in the new hash table */
// 计算新哈希表的哈希值，以及节点插入的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 插入节点到新哈希表
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
// 更新计数器
d->ht[0].used--;
d->ht[1].used++;
// 继续处理下个节点
de = nextde;
}
// 将刚迁移完的哈希表索引的指针设为空
d->ht[0].table[d->rehashidx] = NULL;
// 更新 rehash 索引
d->rehashidx++;
}
return 1;
}
在字典中还提供了许多API函数对字典进行操作，具体查看dict.c源文件。
