字典，又叫映射，是一种用于保存键值对的抽象数据结构
划重点：抽象数据结构
Redisd字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表结点，而每个哈希表结点就保存了字典中的一个键值对
一.哈希表结构
// dictht 哈希表
//每个字典都使用两个哈希表，从而实现渐进式 rehash
typedef struct dictht { // 这是字典的头部 // 哈希表数组, 每个元素都是一条链表
dictEntry **table; // 哈希表大小
unsigned long size; // 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask; // 该哈希表已有节点的数量
unsigned long used; } dictht;
table数组：存放键值对结点
size：哈希表大小，无符号long型
sizemark：恒等于size-1，这个值和哈希值一起决定一个键应该被放到table数组的那个索引上面
used：记录哈希表目前已有键值对的数量
字典使用两个哈希表，从而实现渐进式的rehash扩容！
二.哈希结点结构
// dictEntry 哈希表节点
typedef struct dictEntry {
// 键
void *key; // 值
union {//值v的类型可以是以下三种类型
void *val;
uint64_t u64;
int64_t s64;
} v; // 指向下个哈希表节点，形成链表
struct dictEntry *next; } dictEntry;
key：保存键值对中的键
v：保存键值对中的值，可以是一个指针，可以是unit64_t的一个整数，也可以是int64_t的一个整数
next：下一个哈希表结点的指针
next指针可以将多个哈希值相同的键值对链接在一起，以此结点键冲突的问题
如下，使用链地址法解决哈希冲突的问题
ps：字典中解决hash冲突的方法：链地址法
三.字典的结构
// dict 字典
typedef struct dict { // 类型特定函数
dictType *type; // type里面主要记录了一系列的函数,可以说是规定了一系列的接口 // 私有数据
void *privdata; // privdata保存了需要传递给那些类型特定函数的可选参数 //两张哈希表
dictht ht[];//便于渐进式rehash //rehash 索引，并没有rehash时，值为 -1
int rehashidx; //目前正在运行的安全迭代器的数量
int iterators; } dict;
图上并没有iterators这个属性，应该添加上去！（图片来自这里）
操作字典的特定类型函数，Redis会为用途不同的字典设置不同的类型特定函数，由字典的type属性记录
// 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;
四.哈希算法
1）使用字典设置的哈希函数，计算出key的哈希值
2）使用哈希表的sizemake属性和哈希值，计算出索引值
假设一个key的哈希值=8，resize属性=3，那么该key的索引值为8 & 3=0
Redis使用MurmurHash算法来计算键的hash值
该算法的优点在于即使输入的键是有规律的，算法仍然能给出一个良好的随机分布性，并且算法的计算速度也非常快
一般来说，对任意一类数据存在一个完美的哈希函数，这个完美的哈希函数的定义是没有发生任何碰撞，现实中这种函数很难找到，所以人们对完美哈希函数的要求放宽了：在一个特定的数据集上产生的碰撞最少的哈希函数
所以针对特定的业务，产生的特定的数据集，我们是有可能一个完美的哈希函数的！
五.rehash（重新散列）操作
随着操作的不断执行，哈希表保存的键值对会逐渐的增加或者减少，为了让哈希表的负载因子维持在一个合理的范围内，程序需要对哈希表的大小进行相应的扩展或者收缩
ps：哈希表负载因子=哈希表已经保存结点的数量/哈希表大小
一个字典中存在两张哈希表的原因就是为rehash操作做准备的，另外一张哈希表，虽然存在，但是没有申请结点内存空间，只有表结构，所以不会占用很大的内存空间
ht[0]为字典正在使用的哈希表，h[1]为字典只有表结构的那个哈希表
rehash的步骤如下：
1）为字典的ht[1]分配空间
分配空间的大小：
*如果执行的是扩展操作，ht[1]的大小 为第一个大于等于 ht[0]的大小*2*（2的n次方）
*如果执行的是收缩操作，ht[1]的大小 为第一个大于等于 ht[0]的大小*（2的n次方）
2）将保存在ht[0]上的所有键值对rehash到ht[1]上面：rehash指的是重新计算key的哈希值和索引值，然后将键值对重新放到ht[1]的指定位置
3）当完成键值对的迁移之后，释放ht[0]，将ht[1]设置为ht[0],并在ht[1]重新设置一次空白的哈希表，为下一次rehash操作做准备
六.rehash的时间
1.扩展操作：
以下任意一个条件被满足时，程序自动开始执行rehash操作
1)服务器目前没有执行BGSAVE命令或BGREWIRITEAOF命令并且哈希表的负载因子大于等于1
2）服务器目前正在执行BGSAVE命令或BGREWRITEAOF命令并且哈希表的负载因子大于等于5
引申出的问题：
1）那为什么满足上面两个条件就会自动rehash呢？
2）两个条件的负载因子差距为什么这么大呢？
BGSAVE命令：数据库会开一个子进程将数据库的所有数据以RDB文件的方式保存到硬盘
BGREWRITEAOF命令：开一个子进程执行AOF文件的重写操作
我们知道无论是执行BGSAVE还是执行BGREWRITEAOF，都会开一个子进程，而大多数的操作系统都采用写时复制技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作需要的负载因子，从而尽可能的避免在子进程存在期间进行哈希表的扩展操作，这样可以避免不必要的内存写入操作，最大限度节约内存
那么现在有个问题，如果哈希表中存在很多很多的数据，rehash动作一次性完成的时间需要很久而且要占用大量的计算资源，如果rehash动作一次性完成的话，数据量大的情况下服务器可能会在一段时间内停止对外服务！这是不可以忍受的！
所以引出了渐进式hash：rehash动作不必一次性完成
七.渐进式rehash
在字典中维护一个索引计数器变量rehashidx，将其设置为0，表示rehash操作正式开始，在rehash期间，每次对字典执行添加，删除，查找或者更新操作时，程序除了完成指定操作外，还会顺带将ht[0]哈希表在rehashidx索引上的键值对rehash到ht[1]，完成顺带操作后，程序将rehashidx属性的值加一，随着程序的不断进行，最终在某个时间点上，rehahs操作会全部完成，这个时候将rehashidx设置为-1
渐进式rehash的优势在于它采用分治的方法，将rehash键值对所需的计算工作平均摊到对字典的每个添加，删除，修改，查找，更新的操作上，从而避免了集中式rehash带来的庞大计算量
核心：在rehash过程中，每个对字典的操作（增删改查）除了完成特定的任务，还需要顺带完成rehahs迭代一部分操作
渐进式rehash执行期间哈希表的操作：
因为在进行渐进式rehash的过程中，字典会同时使用两张哈希表，所以在渐进式rehash过程中，字典的删除，查找，修改，更新等操作会在两张表上进行（不是同时进行），比如查找的话是先去ht[0]查找，没有找到的话再去ht[1]查找，特别是插入操作，只会在ht[1]进行，这样保证了ht[1]上的元素一直在减少，不会增加，随着操作的不断进行，ht[0]将会变成一张空表
八.字典相关的API
宏定义实现的函数：
// 释放给定字典节点的值
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
(d)->type->valDestructor((d)->privdata, (entry)->v.val) // 设置给定字典节点的值
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
entry->v.val = (_val_); \
} while() // 将一个有符号整数设为节点的值
#define dictSetSignedIntegerVal(entry, _val_) \
do { entry->v.s64 = _val_; } while() // 将一个无符号整数设为节点的值
#define dictSetUnsignedIntegerVal(entry, _val_) \
do { entry->v.u64 = _val_; } while() // 释放给定字典节点的键
#define dictFreeKey(d, entry) \
if ((d)->type->keyDestructor) \
(d)->type->keyDestructor((d)->privdata, (entry)->key) // 设置给定字典节点的键
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
entry->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
entry->key = (_key_); \
} while() // 比对两个键
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2)) // 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
// 返回获取给定节点的键
#define dictGetKey(he) ((he)->key)
// 返回获取给定节点的值
#define dictGetVal(he) ((he)->v.val)
// 返回获取给定节点的有符号整数值
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
// 返回给定节点的无符号整数值
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
// 返回给定字典的大小
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
// 返回字典的已有节点数量
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
// 查看字典是否正在 rehash
#define dictIsRehashing(ht) ((ht)->rehashidx != -1)
1)字典迭代器：dictIterator
// dictIterator 字典迭代器
// 如果 safe 属性的值为 1,那么在迭代进行的过程中，程序仍然可以执行 dictAdd, dictFind 和其他函数，对字典进行修改。
// 如果 safe 不为 1 ，那么程序只会调用 dictNext 对字典进行迭代， 而不对字典进行修改。
typedef struct dictIterator
{ // 被迭代的字典
dict *d; //正在被迭代的哈希表的号码
int table; //迭代器当指向的哈希表索引位置
int index; //当前迭代器是否安全
int safe; //当前迭代到的结点的指针
dictEntry *entry; //当前迭代结点的下一个结点(因为迭代器运作时，当前结点可能会被修改，必须保存下一个结点的位置，避免指针丢失
dictEntry *nextEntry; long long fingerprint; //不安全迭代器，正在更新中的表的迭代器，使用指纹来标记
} dictIterator;
为什么Redis的迭代器要分为安全迭代器和不安全迭代器？
首先明确两者的概念：
【安全】：指的是在遍历过程中具有对字典进行查找和修改，不用感到担心，因为查找和修改会触发过期判断，会删除内部元素，安全的另外一层意思就是迭代的过程中不会出现元素重复，为了不保证重复，就会禁止rehash
【不安全】：指的是遍历过程中字典是只读的，你不可以修改，你只能调用dictNext进行持续遍历，不得调用任何可能触发过期判断的函数，不过好处是不影响rehash，代价就是遍历的元素可能会出现重复
安全迭代器在刚刚开始遍历时，会给字典打上一个标记，有了这个标记，rehash就不会执行，遍历元素时就不会出现重复
2）哈希表重置函数：_dictReset
/*
* 重置（或初始化）给定哈希表的各项属性值
*
* T = O(1)
*/
static void _dictReset(dictht *ht) { //属性全部重置为NULL或者0
ht->table = NULL;
ht->size = ;
ht->sizemask = ;
ht->used = ;
}
3）字典初始化函数：_dictInit
/*
* 初始化字典
*
* T = O(1)
*/
int _dictInit(dict *d, dictType *type,void *privDataPtr) { // 初始化两个哈希表的各项属性值，但暂时还不分配内存给哈希表数组 //重置两个哈希表
_dictReset(&d->ht[]);
_dictReset(&d->ht[]); // 设置类型特定函数
d->type = type; // 设置私有数据
d->privdata = privDataPtr; // 设置哈希表 rehash 状态
d->rehashidx = -; // 设置字典的安全迭代器数量
d->iterators = ; return DICT_OK; // 代表初始化成功.
}
初始化字典，字典的结构有了，哈希表的结构也有，但是没有为哈希表数组分配内存
4）dictCreate函数：创建一个新字典
/*
* 创建一个新的字典
*
* T = O(1)
*/
dict *dictCreate(dictType *type,void *privDataPtr) { //申请内存空间
dict *d = zmalloc(sizeof(*d)); //初始化字典
_dictInit(d, type, privDataPtr); // c语言要初始化的话,可能麻烦一点,但是好处在于它不会在背地里干一些你不知道的事情. //返回字典
return d;
}
5）_dictNextPower函数：根据ht[0]的大小，确定rehash操作需要的ht[1]的大小
/*
* 计算第一个大于等于 size 的 2 的 N 次方，用作新哈希表大小的值
*
* 根据ht[0]的大小，确定rehash操作需要的ht[1]的大小
*
* T = O(1)
*/
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE; if (size >= LONG_MAX) return LONG_MAX;
while () {
if (i >= size)
return i;
i *= ;
}
}
6）dictExpand函数：字典哈希表的扩展
/*
* 扩展或者创建一个新的哈希表 * 创建一个新的哈希表，并根据字典的情况，选择以下其中一个动作来进行：
* 1) 如果字典的 0 号哈希表为空，那么将新哈希表设置为 0 号哈希表
* 2) 如果字典的 0 号哈希表非空，那么将新哈希表设置为 1 号哈希表，并打开字典的 rehash 标识，使得程序可以开始对字典进行 rehash
*
* size 参数不够大，或者 rehash 已经在进行时，返回 DICT_ERR 。
*
* 成功创建 0 号哈希表，或者 1 号哈希表时，返回 DICT_OK 。
*
* T = O(N)
*/
int dictExpand(dict *d, unsigned long size) { // 新哈希表
dictht n; // 根据 size 参数，计算新哈希表的大小
unsigned long realsize = _dictNextPower(size); // 不能在字典正在 rehash 时进行扩展表操作，size 的值也不能小于 0 号哈希表的当前已使用节点
if (dictIsRehashing(d) || d->ht[].used > size)
return DICT_ERR;//返回操作失败 //确定新哈希表大小
n.size = realsize;
n.sizemask = realsize - ; //为1号哈希表分配内存空间
n.table = zcalloc(realsize * sizeof(dictEntry*)); // dicEntry是一个数组
n.used = ; //0号哈希表为空，那么这是一次初始化
if (d->ht[].table == NULL) {
// 初始化
d->ht[] = n;//将新表赋给0号表的指针 n也是dictht类型的
}
//0号哈希表不空,那么这是一次rehash
else {
//新表赋值给1号哈希表指针
d->ht[] = n; /* rehashidx设置得非常漂亮,没有rehash时,rehashidx为-1, 一旦
开始rehash时,rehashidx设定为0,表示从ht[0]表的第0个元素开始rehash
然后rehashidx逐步增长,用它作为指示器,可以将ht[0]表中的所有元素都rehash完
*/
d->rehashidx = ;
} return DICT_OK;//范返回操作成功 }
7）dictResize函数：缩小字典的哈希表
/*
* 缩小给定字典
* 让它的已用节点数和字典大小之间的比率接近 1:1
*
* 返回 DICT_ERR 表示字典已经在 rehash ，或者 dict_can_resize 为假。
*
* 成功创建体积更小的 ht[1] ，可以开始 resize 时，返回 DICT_OK。
*
* T = O(N)
*/
int dictResize(dict *d) { //新表所需结点的最小数量
int minimal; // 不能在关闭 rehash 或者正在 rehash 的时候调用
if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR; // 计算让比率接近 1：1 所需要的最少节点数量
minimal = d->ht[].used;
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE; // 调整字典的大小
// T = O(N)
return dictExpand(d, minimal);
}
8）dictRehash函数：rehash
/*
* 执行 N 步渐进式 rehash 。
*
* 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表，
* 返回 0 则表示所有键都已经迁移完毕。
*
* 注意，每步 rehash 都是以一个哈希表索引（桶）作为单位的，
* 一个桶里可能会有多个节点，
* 被 rehash 的桶里的所有节点都会被移动到新哈希表。
*
* T = O(N)
*/
int dictRehash(dict *d, int n)
{
// 这里的n代表一共要迁移多少个dictEntry // 只可以在 rehash 进行中时执行
if (!dictIsRehashing(d)) return ; // 进行 N 步迁移
// T = O(N)
while (n--) // n代表需要迁移的结点数量
{ dictEntry *de, *nextde; // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
if (d->ht[].used == )
{
// 释放 0 号哈希表
zfree(d->ht[].table);
// 将原来的 1 号哈希表设置为新的 0 号哈希表 d->ht[] = d->ht[];
// 重置旧的 1 号哈希表
_dictReset(&d->ht[]);
// 关闭 rehash 标识
d->rehashidx = -;
// 返回 0 ，向调用者表示 rehash 已经完成
return ;
} // 确保 rehashidx 没有越界
assert(d->ht[].size > (unsigned)d->rehashidx); // 找到第一个非空索引的下标
while (d->ht[].table[d->rehashidx] == NULL) d->rehashidx++; // 指向第一个非空索引的链表表头节点
de = d->ht[].table[d->rehashidx]; // 将链表中的所有节点迁移到新哈希表（重新计算位置，在新表上可能就不是在一条链上了）
while (de)
{
unsigned int h; // 保存下个节点的指针
nextde = de->next; //计算结点插入的位置索引=key的哈希值 & sizemask
h = dictHashKey(d, de->key) & d->ht[].sizemask; // 插入节点到新哈希表,而且是插入到表头（每次插入都是差到链表的表头）
de->next = d->ht[].table[h];
d->ht[].table[h] = de; // 更新计数器
d->ht[].used--;//0号哈希表结点数量减少1
d->ht[].used++;//1号哈希表结点数量增加1 // 继续处理下个节点
de = nextde;
}
// 将刚迁移完的哈希表索引的指针设为空
d->ht[].table[d->rehashidx] = NULL; // 更新 rehash 索引
d->rehashidx++;
} //执行完毕
return ;
}
9)timeInMilliseconds函数：返回以毫秒为单位的Unix时间戳
/*
* 返回以毫秒为单位的 UNIX 时间戳
*
* T = O(1)
*/
long long timeInMilliseconds(void)
{
struct timeval tv; //获得当前时间的精准值
gettimeofday(&tv, NULL); //强制类型转换，避免溢出
return (((long long)tv.tv_sec) * ) + (tv.tv_usec / );
}
10）在给定毫秒数内，以 100 步为单位, 对字典进行 rehash（也就是说每次对100个dictEntry进行hash）
/*
* 在给定毫秒数内，以 100 步为单位, 对字典进行 rehash.也就是说每次对100个dictEntry进行hash.
*
* T = O(N)
*/
int dictRehashMilliseconds(dict *d, int ms)
{
// 开始的时间
long long start = timeInMilliseconds(); //这一次迁移完成的dictntry个数
int rehashes = ; while (dictRehash(d, ))
{
rehashes += ; // 如果时间已过，跳出
if (timeInMilliseconds() - start > ms) break;
} //返回本次已经迁移完成的dictEntry个数
return rehashes;
}
11）_dictRehashStep函数：单步rehash，渐进式rehash的关键函数
/*
* 在字典不存在安全迭代器的情况下，对字典进行单步 rehash 。
*
* 字典有安全迭代器的情况下不能进行 rehash ，
* 因为两种不同的迭代和修改操作可能会弄乱字典。
*
* 这个函数被多个通用的查找、更新操作调用，
* 它可以让字典在被使用的同时进行 rehash 。
*
* T = O(1)
*/
static void _dictRehashStep(dict *d)
{
//要求该字典上不存在安全迭代器
if (d->iterators == ) dictRehash(d, );
}
这个函数被多个通用的查找、更新操作调用，它可以让字典在被使用的同时进行 rehash！
12）_dictExpandIfNeeded函数：根据需要，初始化字典或者对字典的现有哈希表进行扩展
/*
* 根据需要，初始化字典（的哈希表），或者对字典（的现有哈希表）进行扩展
*
* T = O(N)
*/
static int _dictExpandIfNeeded(dict *d)
{
// 渐进式 rehash 已经在进行了，不能扩展和初始化 直接返回
if (dictIsRehashing(d))
return DICT_OK;//返回ok // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表
if (d->ht[].size == )
return dictExpand(d, DICT_HT_INITIAL_SIZE); /* 一下两个条件之一为真时，对字典进行扩展
1）字典已使用节点数和字典大小之间的比率接近 1：1，并且 dict_can_resize 为真
2）已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
*/
if (d->ht[].used >= d->ht[].size &&(dict_can_resize ||d->ht[].used / d->ht[].size > dict_force_resize_ratio))
{
// 新哈希表的大小至少是目前已使用节点数的两倍
return dictExpand(d, d->ht[].used * );
}
//返回ok标志
return DICT_OK;
}
ps：调用了dictIsRehashing函数进行当前是否正在进行rehash的判断，因为rehash过程中不能进行初始化字典或者对哈希表进行扩容，满足扩容的条件则会调用dictExpand进行扩容
13）_dictKeyIndex函数
/*
* 返回可以将 key 插入到哈希表的索引位置
* 如果 key 已经存在于哈希表，那么返回 -1
*
* 注意，如果字典正在进行 rehash ，那么总是返回 1 号哈希表的索引。
* 因为在字典进行 rehash 时，新节点总是插入到 1 号哈希表。
*
* T = O(N)
*/
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table; dictEntry *he;//哈希结点 //如果需要的话，扩展哈希表
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -; // 计算 key 的哈希值
h = dictHashKey(d, key); //ht[0]和ht[1]
for (table = ; table <= ; table++)
{ // 计算索引值
idx = h & d->ht[table].sizemask; // 获得哈希表索引上的结点（存在哈希冲突的话，改结点就是链表结点）
he = d->ht[table].table[idx]; //在链表中查找key是否存在
while (he)
{
if (dictCompareKeys(d, key, he->key))//该key存在
return -;//返回-1 he = he->next;//找链表上下一个结点
} // 如果运行到这里时，说明 0 号哈希表中所有节点都不包含 key
if (!dictIsRehashing(d))//如果这个时候没有进行rehash，则跳出去，否则在ht[1]继续计算索引位置
break;
} // 返回索引值
return idx;
}
该函数要完成两个功能：
1）key是否存在于字典中
2）key如果不存在于字典中，返回对应哈希表的索引值，
注意，如果字典正在进行 rehash ，那么总是返回 1 号哈希表的索引，因为在字典进行 rehash 时，新节点总是插入到 1 号哈希表。
14）dictAddRaw函数
/*
* 尝试将键插入到字典中
*
* 如果键已经在字典存在，那么返回 NULL
*
* 如果键不存在，那么程序创建新的哈希节点，
* 将节点和键关联，并插入到字典，然后返回节点本身。
*
* T = O(N)
*/
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;//结点索引
dictEntry *entry;//结点
dictht *ht;//哈希表 // 如果条件允许的话，进行单步 rehash
// 如果需要rehashing,那么我们进行rehash,注意,这里是单步rehash
if (dictIsRehashing(d))
_dictRehashStep(d); // 计算键在哈希表中的索引值
// 如果值为 -1 ，那么表示键已经存在
if ((index = _dictKeyIndex(d, key)) == -)
return NULL; // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表，否则，将新键添加到 0 号哈希表
ht = dictIsRehashing(d) ? &d->ht[] : &d->ht[]; // 为新节点分配空间 entry = zmalloc(sizeof(*entry)); // 将新节点插入到链表表头,因为键不存在，所以index肯定是表头
entry->next = ht->table[index];
ht->table[index] = entry; // 更新哈希表已使用节点数量
ht->used++; // 设置新节点的键
dictSetKey(d, entry, key); //返回结点本身
return entry;
}
插入动作在rehash期间总是伴随着单步rehash，键已存在则也不用插入，根据当前字典是否正在rehash，确定将键添加到哪个哈希表，但是该结点只添加了键，没有添加值！，要添加键值对而不是键的话，还需要依靠下面这个函数
15）dictAdd函数：
/*
* 尝试将给定键值对添加到字典中
*
* 只有给定键 key 不存在于字典时，添加操作才会成功
*
* 添加成功返回 DICT_OK , 失败返回 DICT_ERR
*
* 最坏 T = O(N),平摊 O(1)
*/
int dictAdd(dict *d, void *key, void *val) // 添加一个键值对进入到dict中
{
// 尝试添加键到字典，并返回包含了这个键的新哈希节点
// T = O(N)
dictEntry *entry = dictAddRaw(d, key); // 键已存在，添加失败
if (!entry) return DICT_ERR; // 键不存在，设置节点的值
// T = O(1)
dictSetVal(d, entry, val); // 添加成功
return DICT_OK;
}
先是调用dictAddRaw添加键，然后调用dictSetVal添加键的值，这样才算是添加了键值对
16）dictReplace函数：
/*
* 将给定的键值对添加到字典中，如果键已经存在，那么删除旧有的键值对。
*
* 如果键值对为全新添加，那么返回 1 。
* 如果键值对是通过对原有的键值对更新得来的，那么返回 0 。
*
* T = O(N)
*/
int dictReplace(dict *d, void *key, void *val)
{
dictEntry *entry, auxentry; // 尝试直接将键值对添加到字典 如果键 key 不存在的话，添加会成功
if (dictAdd(d, key, val) == DICT_OK)
return ; // 运行到这里，说明键 key 已经存在，那么找出包含这个 key 的节点
// T = O(1)
entry = dictFind(d, key); // 先保存原有的值的指针
auxentry = *entry; // 然后设置新的值
dictSetVal(d, entry, val); // 然后释放旧值
dictFreeVal(d, &auxentry);//原来的值必须释放，不然会引起内存泄漏 return ;
}
17）dictReplaceRaw函数：查找函数
dictEntry *dictReplaceRaw(dict *d, void *key)
{ // 使用 key 在字典中查找节点
dictEntry *entry = dictFind(d, key); // 如果节点找到了直接返回节点，否则添加并返回一个新节点
return entry ? entry : dictAddRaw(d, key);
}
18）dictGenereicDelete函数：查找并删除给定键的结点
/*
* 查找并删除包含给定键的节点
*
* 参数 nofree 决定是否调用键和值的释放函数
* 0 表示调用，1 表示不调用
*
* 找到并成功删除返回 DICT_OK ，没找到则返回 DICT_ERR
*
* T = O(1)
*/
static int dictGenericDelete(dict *d, const void *key, int nofree)
{
unsigned int h, idx;
dictEntry *he, *prevHe;
int table; // 字典（的哈希表）为空
if (d->ht[].size == )
return DICT_ERR;//返回操作错误标识 //在 rehash期间 可以进行单步 rehash
if (dictIsRehashing(d))
_dictRehashStep(d); // 计算键的哈希值
h = dictHashKey(d, key); //由于可能正在rehash，所以要在两个表中找
for (table = ; table <= ; table++)
{
// 计算索引值
idx = h & d->ht[table].sizemask; // 指向该索引上的链表
he = d->ht[table].table[idx];
prevHe = NULL; // 遍历链表上的所有节点
while (he)
{
//在链上找到了该键
if (dictCompareKeys(d, key, he->key))//比较链表上结点的键和函数给定键的关系，
{ // 从链表中删除
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next; // 如果需要释放，则调用键和值的释放函数
if (!nofree)
{
dictFreeKey(d, he);
dictFreeVal(d, he);
} // 释放节点本身
zfree(he); // 更新已使用节点数量
d->ht[table].used--; // 返回已找到信号
return DICT_OK;
} prevHe = he; he = he->next;//一直遍历到链表尾
} // 如果执行到这里，说明在 0 号哈希表中找不到给定键
//如果当前没有进行rehash，则可以不用在1号哈希表上找了，因为它是空的
if (!dictIsRehashing(d))
break;
} //没有找到，返回操作失败标识
return DICT_ERR;
}
可以根据需求确定删除结点之后要不要释放内存空间，如果当前没有进行rehash，那么只需要在ht[0]上查找和删除，因为ht[1]在没有进行rehash时是空表
19）dictDelete函数：从字典中删除给定键的结点，并调用键释放函数来删除键值，释放空间
/*
* 从字典中删除包含给定键的节点
*
* 并且调用键值的释放函数来删除键值
*
* 找到并成功删除返回 DICT_OK ，没找到则返回 DICT_ERR
* T = O(1)
*/
int dictDelete(dict *ht, const void *key)
{
return dictGenericDelete(ht, key, );
}
20）dictDeleteNoFree函数：从字典中删除给定键的结点，并不调用键释放函数来删除键值和释放空间
/*
* 从字典中删除包含给定键的节点
*
* 但不调用键值的释放函数来删除键值
*
* 找到并成功删除返回 DICT_OK ，没找到则返回 DICT_ERR
* T = O(1)
*/
int dictDeleteNoFree(dict *ht, const void *key)
{
return dictGenericDelete(ht, key, ); // 如果没有保存下没有释放结点的地址的话,容易造成内存泄露
}
21）_dictClear函数：删除哈希表上所有的结点，并重置哈希表的各项属性
/*
* 删除哈希表上的所有节点，并重置哈希表的各项属性
*
* T = O(N)
*/
int _dictClear(dict *d, dictht *ht, void(callback)(void *))
{
unsigned long i; // 遍历整个哈希表
for (i = ; i < ht->size && ht->used > ; i++)
{
//哈希表结点
dictEntry *he, *nextHe; //i==0 privdate为字典私有属性 保存了需要传递给那些类型特定函数的可选参数
if (callback && (i & ) == ) //65535的二进制为16个1
callback(d->privdata); // 跳过空索引
if ((he = ht->table[i]) == NULL) continue; // 遍历整个链表
// T = O(1)
while (he)
{
nextHe = he->next;
// 删除键
dictFreeKey(d, he);
// 删除值
dictFreeVal(d, he);
// 释放节点
zfree(he); // 更新已使用节点计数
ht->used--; // 处理下个节点
he = nextHe;
}
} // 释放哈希表结构
zfree(ht->table); // 重置哈希表属性
_dictReset(ht); return DICT_OK;//返回操作成功标志
}
22)dictRelease函数：删除并释放整个字典
/*
* 删除并释放整个字典
*
* T = O(N)
*/
void dictRelease(dict *d)
{
// 删除并清空两个哈希表
_dictClear(d, &d->ht[], NULL);
_dictClear(d, &d->ht[], NULL);
// 释放节点结构
zfree(d);
}
23）dictFind函数：返回字典中包含key的结点
/*
* 返回字典中包含键 key 的节点
*
* 找到返回节点，找不到返回 NULL
*
* T = O(1)
*/
dictEntry *dictFind(dict *d, const void *key) // 寻找某个key对应的值
{
dictEntry *he;
unsigned int h, idx, table; // 字典的哈希表为空，则没有必要继续找了
if (d->ht[].size == )
return NULL; //在rehash期间 进行单步rehash
if (dictIsRehashing(d)) _dictRehashStep(d); // 计算键的哈希值
h = dictHashKey(d, key); // 在字典的哈希表中查找这个键
for (table = ; table <= ; table++)
{ // 计算索引值
idx = h & d->ht[table].sizemask; // 遍历给定索引上的链表的所有节点，查找 key
he = d->ht[table].table[idx]; //遍历链表
while (he)
{
//找到了
if (dictCompareKeys(d, key, he->key))
return he; //接着往下找
he = he->next;
} // 如果程序遍历完 0 号哈希表，仍然没找到指定的键的节点
// 那么程序会判断此时是否正在rehash，没有rehash的话则不用在ht[1]上找了
//因为没有rehash的话,ht[1]是空表
if (!dictIsRehashing(d)) return NULL;
} // 进行到这里时，说明两个哈希表都没找到
return NULL;
}
24）dictFetchValue函数：获取包含给定键结点的值
/*
* 获取包含给定键的节点的值
*
* 如果节点不为空，返回节点的值
* 否则返回 NULL
*
* T = O(1)
*/
void *dictFetchValue(dict *d, const void *key)
{
dictEntry *he; //根据键在字典中找到该结点
he = dictFind(d, key); //结点不空的话，返回结点的值
return he ? dictGetVal(he) : NULL;
}
25）字典迭代器的创建
/*
* 创建并返回给定字典的不安全迭代器
*
* T = O(1)
*/
dictIterator *dictGetIterator(dict *d)
{
dictIterator *iter = zmalloc(sizeof(*iter)); iter->d = d;
iter->table = ;
iter->index = -;
iter->safe = ;
iter->entry = NULL;
iter->nextEntry = NULL; return iter;
} /*
* 创建并返回给定节点的安全迭代器
*
* T = O(1)
*/
dictIterator *dictGetSafeIterator(dict *d) // 什么叫做安全的迭代器?
{
dictIterator *i = dictGetIterator(d); // 设置安全迭代器标识
i->safe = ; // 安全只是一个标识符而已. return i;
}
为给定的字典创建安全迭代器或者不安全迭代器
迭代器安全和不安全的定义：
为什么Redis的迭代器要分为安全迭代器和不安全迭代器？
首先明确两者的概念：
【安全】：指的是在遍历过程中具有对字典进行查找和修改，不用感到担心，因为查找和修改会触发过期判断，会删除内部元素，安全的另外一层意思就是迭代的过程中不会出现元素重复，为了不保证重复，就会禁止rehash
【不安全】：指的是遍历过程中字典是只读的，你不可以修改，你只能调用dictNext进行持续遍历，不得调用任何可能触发过期判断的函数，不过好处是不影响rehash，代价就是遍历的元素可能会出现重复
安全迭代器在刚刚开始遍历时，会给字典打上一个标记，有了这个标记，rehash就不会执行，遍历元素时就不会出现重复
ps：图片引用自《Redis设计与实现》