字典，又叫映射，是一种用于保存键值对的抽象数据结构
划重点：抽象数据结构
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[2];//便于渐进式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(0) // 将一个有符号整数设为节点的值 #define dictSetSignedIntegerVal(entry, _val_) do { entry->v.s64 = _val_; } while(0) // 将一个无符号整数设为节点的值 #define dictSetUnsignedIntegerVal(entry, _val_) do { entry->v.u64 = _val_; } while(0) // 释放给定字典节点的键 #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(0) // 比对两个键 #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 = 0; ht->sizemask = 0; ht->used = 0; }
3）字典初始化函数：_dictInit
/* * 初始化字典 * * T = O(1) */ int _dictInit(dict *d, dictType *type,void *privDataPtr) { // 初始化两个哈希表的各项属性值，但暂时还不分配内存给哈希表数组 //重置两个哈希表 _dictReset(&d->ht[0]); _dictReset(&d->ht[1]); // 设置类型特定函数 d->type = type; // 设置私有数据 d->privdata = privDataPtr; // 设置哈希表 rehash 状态 d->rehashidx = -1; // 设置字典的安全迭代器数量 d->iterators = 0; 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 (1) { if (i >= size) return i; i *= 2; } }
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[0].used > size) return DICT_ERR;//返回操作失败 //确定新哈希表大小 n.size = realsize; n.sizemask = realsize - 1; //为1号哈希表分配内存空间 n.table = zcalloc(realsize * sizeof(dictEntry*)); // dicEntry是一个数组 n.used = 0; //0号哈希表为空，那么这是一次初始化 if (d->ht[0].table == NULL) { // 初始化 d->ht[0] = n;//将新表赋给0号表的指针 n也是dictht类型的 } //0号哈希表不空,那么这是一次rehash else { //新表赋值给1号哈希表指针 d->ht[1] = n; /* rehashidx设置得非常漂亮,没有rehash时,rehashidx为-1, 一旦 开始rehash时,rehashidx设定为0,表示从ht[0]表的第0个元素开始rehash 然后rehashidx逐步增长,用它作为指示器,可以将ht[0]表中的所有元素都rehash完 */ d->rehashidx = 0; } 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[0].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 0; // 进行 N 步迁移 // T = O(N) while (n--) // n代表需要迁移的结点数量 { dictEntry *de, *nextde; // 如果 0 号哈希表为空，那么表示 rehash 执行完毕 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; } // 确保 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]; // 将链表中的所有节点迁移到新哈希表（重新计算位置，在新表上可能就不是在一条链上了） while (de) { unsigned int h; // 保存下个节点的指针 nextde = de->next; //计算结点插入的位置索引=key的哈希值 & sizemask 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--;//0号哈希表结点数量减少1 d->ht[1].used++;//1号哈希表结点数量增加1 // 继续处理下个节点 de = nextde; } // 将刚迁移完的哈希表索引的指针设为空 d->ht[0].table[d->rehashidx] = NULL; // 更新 rehash 索引 d->rehashidx++; } //执行完毕 return 1; }
9)timeInMilliseconds函数：返回以毫秒为单位的Unix时间戳
/*
* 返回以毫秒为单位的 UNIX 时间戳
*
* T = O(1)
*/
long long timeInMilliseconds(void)
{
struct timeval tv;
//获得当前时间的精准值
gettimeofday(&tv, NULL);
//强制类型转换，避免溢出
return (((long long)tv.tv_sec) * 1000) + (tv.tv_usec / 1000);
}
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 = 0; while (dictRehash(d, 100)) { rehashes += 100; // 如果时间已过，跳出 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 == 0) dictRehash(d, 1); }
这个函数被多个通用的查找、更新操作调用，它可以让字典在被使用的同时进行 rehash！
12）_dictExpandIfNeeded函数：根据需要，初始化字典或者对字典的现有哈希表进行扩展
/* * 根据需要，初始化字典（的哈希表），或者对字典（的现有哈希表）进行扩展 * * T = O(N) */ static int _dictExpandIfNeeded(dict *d) { // 渐进式 rehash 已经在进行了，不能扩展和初始化 直接返回 if (dictIsRehashing(d)) return DICT_OK;//返回ok // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表 if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); /* 一下两个条件之一为真时，对字典进行扩展 1）字典已使用节点数和字典大小之间的比率接近 1：1，并且 dict_can_resize 为真 2）已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio */ if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||d->ht[0].used / d->ht[0].size > dict_force_resize_ratio)) { // 新哈希表的大小至少是目前已使用节点数的两倍 return dictExpand(d, d->ht[0].used * 2); } //返回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 -1; // 计算 key 的哈希值 h = dictHashKey(d, key); //ht[0]和ht[1] for (table = 0; table <= 1; 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;//返回-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)) == -1) return NULL; // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表，否则，将新键添加到 0 号哈希表 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 为新节点分配空间 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 1; // 运行到这里，说明键 key 已经存在，那么找出包含这个 key 的节点 // T = O(1) entry = dictFind(d, key); // 先保存原有的值的指针 auxentry = *entry; // 然后设置新的值 dictSetVal(d, entry, val); // 然后释放旧值 dictFreeVal(d, &auxentry);//原来的值必须释放，不然会引起内存泄漏 return 0; }
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[0].size == 0) return DICT_ERR;//返回操作错误标识 //在 rehash期间 可以进行单步 rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 计算键的哈希值 h = dictHashKey(d, key); //由于可能正在rehash，所以要在两个表中找 for (table = 0; table <= 1; 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, 0); }
20）dictDeleteNoFree函数：从字典中删除给定键的结点，并不调用键释放函数来删除键值和释放空间
/* * 从字典中删除包含给定键的节点 * * 但不调用键值的释放函数来删除键值 * * 找到并成功删除返回 DICT_OK ，没找到则返回 DICT_ERR * T = O(1) */ int dictDeleteNoFree(dict *ht, const void *key) { return dictGenericDelete(ht, key, 1); // 如果没有保存下没有释放结点的地址的话,容易造成内存泄露 }
21）_dictClear函数：删除哈希表上所有的结点，并重置哈希表的各项属性
/* * 删除哈希表上的所有节点，并重置哈希表的各项属性 * * T = O(N) */ int _dictClear(dict *d, dictht *ht, void(callback)(void *)) { unsigned long i; // 遍历整个哈希表 for (i = 0; i < ht->size && ht->used > 0; i++) { //哈希表结点 dictEntry *he, *nextHe; //i==0 privdate为字典私有属性 保存了需要传递给那些类型特定函数的可选参数 if (callback && (i & 65535) == 0) //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[0], NULL); _dictClear(d, &d->ht[1], 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[0].size == 0) return NULL; //在rehash期间 进行单步rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 计算键的哈希值 h = dictHashKey(d, key); // 在字典的哈希表中查找这个键 for (table = 0; table <= 1; 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 = 0; iter->index = -1; iter->safe = 0; iter->entry = NULL; iter->nextEntry = NULL; return iter; } /* * 创建并返回给定节点的安全迭代器 * * T = O(1) */ dictIterator *dictGetSafeIterator(dict *d) // 什么叫做安全的迭代器? { dictIterator *i = dictGetIterator(d); // 设置安全迭代器标识 i->safe = 1; // 安全只是一个标识符而已. return i; }
为给定的字典创建安全迭代器或者不安全迭代器
迭代器安全和不安全的定义：
为什么Redis的迭代器要分为安全迭代器和不安全迭代器？
首先明确两者的概念：
【安全】：指的是在遍历过程中具有对字典进行查找和修改，不用感到担心，因为查找和修改会触发过期判断，会删除内部元素，安全的另外一层意思就是迭代的过程中不会出现元素重复，为了不保证重复，就会禁止rehash
【不安全】：指的是遍历过程中字典是只读的，你不可以修改，你只能调用dictNext进行持续遍历，不得调用任何可能触发过期判断的函数，不过好处是不影响rehash，代价就是遍历的元素可能会出现重复
安全迭代器在刚刚开始遍历时，会给字典打上一个标记，有了这个标记，rehash就不会执行，遍历元素时就不会出现重复
ps：图片引用自《Redis设计与实现》