字典(dict)又称为映射(map)，是一种用于保存键值对(key-value pairs)的数据结构。在字典中，一个键(key)可以和一个值(value)进行关联，字典中的每个键都是唯一的，可以通过键查找(或者更新)与之关联的值，当然也可以根据键删除整个键值对。
redis 使用的 c 语言没有内置字典这种数据结构，因此 redis 只能自己实现 dict 的数据结构。字典在 redis 中应用广泛，本身就是一个大的字典，键为各种 key，值为存储五种数据类型的数值。举例说明，当执行 set msg "hello" 命令时，redis 数据库会创建一个键为 "msg"，值为 "hello" 的键值对，而这个键值对就是保存在字典里。字典除了用来表示数据库之外，还是哈希键的底层实现之一：当哈希键包含的键值对较多，或者键值对中的元素都是比较长的字符串时，redis 就会使用字典作为哈希键的底层实现。
创建一个哈希键对象：
127.0.0.1:6379> hset website python python.org(integer) 1127.0.0.1:6379> hset website golang golang.org(integer) 1127.0.0.1:6379> hgetall website1) "python"2) "python.org"3) "golang"4) "golang.org"website 键的底层实现就是字典。包含 2 个键值对：其中一个键为 "python"，值为 "python.org"；另一个键为 "golang"，值为 "golang.org"。
1 字典的实现
dict 的本质是为了解决查找问题，一般查找问题的方法分为两类：基于各种平衡树和基于哈希表。各语言的 map 大都是基于哈希表实现的，哈希表的特点：存储无序，查找时间复杂度接近O(1)。在不发生键冲突的条件下查找时间复杂度就是 O(1)，如果发生哈希冲突，假设最坏情况下，所有键都映射到同一个索引位置，此时形成一个单向链表，因此查找时间复杂度就是 O(n)。
redis 的 dict(字典)使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点，每个哈希表节点就保存字典中的一个键值对。和传统的哈希算法类似，使用某个哈希函数，根据 key 计算得到哈希表中的位置，采用拉链法解决哈希冲突，并在装载因子(load factor)超过预定值时自动扩容，引发重哈希(rehashsing)。redis 采用增量式 rehashsing 的方法，避免一次性对所有 key 进行 rehashsing，而是将 rehashsing 操作分散到对于 dict 的增删改查操作中，每次只对一小部分 key 进行 rehashsing，而每次 rehashsing 之间不影响 dict 的操作，从而避免 rehash 期间某些请求的响应时间骤增。
1.1 哈希表节点
哈希表节点使用 dictEntry 结构体表示，每个 dictEntry 结构都保存一个键值对，其定义如下：
// redis-6.0.5/src/dict.htypedef struct dictEntry { void *key; // 键 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 值 struct dictEntry *next; // 指向下一个哈希表节点，形成链表} dictEntry;key：保存键值对中的键，由于 key 是 void 指针，所以它可以指向任何类型
v：保存键值对中的值，它可以是一个 void 指针，uint64_t 的整数，int64_t 的整数，或者是 double 类型的浮点数，所以 v 也能存储任何类型的数据
next：指向下一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，用于解决哈希冲突(collision)的问题
1.2 哈希表
redis 的哈希表结构体定义如下所示：
// redis-6.0.5/src/dict.h/* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */typedef struct dictht { dictEntry **table; // 哈希表数组 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，总是等于 size-1 unsigned long used; // 该哈希表已有节点数量} dictht;table：是个数组，数组的每个元素都是一个指向 dictEntry 结构的指针，每个 dictEntry 结构都保存一个键值对。key 的哈希值最终映射到这个数组的某个位置上，如果多个 key 映射到同一个位置，即发生哈希冲突，此时通过拉链法构建出一个 dictEntry 链表
size：记录哈希表的大小，即 table 数组的总大小，取值大小为 2^n(n为正整数)，也就是说，redis 哈希表的大小取值只能是：4，8，16，32，64 等。(#define DICT_HT_INITIAL_SIZE 4 // redis 将字典的初始大小设置为 4)
sizemark：总是等于 size - 1，该值与哈希值一起决定一个键应该被放到数组的哪个索引上。实现过程大致如下：sizemask 二进制数的每个 bit 的值全为 1，每个 key 经过 hashFunction 计算得到一个哈希值，然后将该哈希值与 sizemask 执行按位与操作(哈希值 & sizemask)，相当于取余操作(哈希值 % size)
used：记录哈希表已有节点的数量，即已有键值对数量，used 与 size 的比值就是装载因子(load factor)，装载因子越大，发生哈希冲突的概率就越高
大小为 4 的空哈希表示例如下：
通过 next 指针，将两个索引值相同的键 k0 和 k1 连接在一起的示例如下：
1.3 dict
redis 中的 dict(字典)的结构体定义如下：
// redis-6.0.5/src/dict.htypedef struct dictType { uint64_t (*hashFunction)(const void *key); // 根据 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); // 比较 key1 和 key2 是否相等 void (*keyDestructor)(void *privdata, void *key); // 销毁键的函数 void (*valDestructor)(void *privdata, void *obj); // 销毁值的函数} dictType;typedef struct dict { dictType *type; // 类型特定函数 void *privdata; // 私有数据 dictht ht[2]; // 哈希表，ht 是 hash table 的首字母缩写 long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */} dict;对 dict 的成员分析如下：
type：类型特定函数，是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，redis 会为不同的字典设置不同的类型特定函数
privdata：私有数据，保存了需要传给类型特定函数的可选参数，type 与 privdata 成员是为创建多态字典而设置的
ht：hash table 的首字母缩写，是个包含 2 个元素的哈希表数组，数组中的每个元素是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehashing 时使用，在重哈希过程中，数据从 ht[0] 逐渐向 ht[1] 迁移
rehashidx：记录 rehashing 目前的进度，如果目前没有 rehash，那么它的值为 -1；当 rehashidx 大于等于 0 时，表示小于 rehashidx 对应的索引已完成 rehash，等于 rehashidx 值对应的索引表示下一次将要 rehash 的对象。
iterators：当前正在运行的迭代器数量，也就是正在遍历的迭代器数量
在没有 rehash 状态下的字典示例如下(此时 rehashidx=-1)：
2 哈希
2.1 哈希算法
// redis-6.0.5/src/hyperloglog.c// HyperLogLog algorithm 翻译为：基数统计算法/* ========================= HyperLogLog algorithm ========================= *//* Our hash function is MurmurHash2, 64 bit version. * It was modified for Redis in order to provide the same result in * big and little endian archs (endian neutral). */uint64_t MurmurHash64A (const void * key, int len, unsigned int seed) { const uint64_t m = 0xc6a4a7935bd1e995; const int r = 47; uint64_t h = seed ^ (len * m); const uint8_t *data = (const uint8_t *)key; const uint8_t *end = data + (len-(len&7)); // ... h ^= h >> r; h *= m; h ^= h >> r; return h;}根据 redis 源码可知，redis 使用 MurmurHash2 算法来计算键的哈希值。该算法已被 redis 适配过，以便在大端和小端机器上计算得到相同的哈希值。
MurmurHash 算法是目前比较流行的哈希算法之一，优点在于即使输入的键是有规律的，该算法能给给出较好随机分布的值，且冲突概率低。Murmur 名称来自乘法(multiplication)和旋转(rotation)，是一种非机密的哈希函数(散列函数)。目前有 3 个版本，MurmurHash1, MurmurHash2 和 MurmurHash3，其中 1 已过时，2 产生一个 32 位 或者 64 位的值，3 产生一个 32 位或者 128 位的值，使用 128 位时，x86 和 x64 版本会产生不同的值，因为算法针对各自的平台做了优化。
往字典添加一个新的键值对时，程序需要先根据键计算出哈希值和索引值，再根据索引值将包含新键值对的哈希表节点放在哈希表数组的对应索引位置上。
hash = dict->type->hashFunction(key); // 根据哈希函数计算 key 的哈希值index = hash & dict->ht[0].sizemask; // 计算索引值，如果发生 rehash，ht[0] 也可以是 ht[1]2.2 解决键冲突
当两个或两个以上的键映射到同一个索引位置时，称这些键发生哈希冲突(collision)，redis 的哈希表使用链地址法(也叫拉链法)来解决键的冲突：每个哈希表节点都有一个 next 指针，被分配到同一个索引位置的多个节点可以用 next 指针构成一个单向链表，从而解决哈希冲突。由于 dictEntry 节点没有指向链表表尾的指针，所以 redis 使用头插法实现插入过程。由于没有尾指针，尾插法的插入时间复杂度为O(n)，n 为链表的长度，而头插法的时间复杂度为O(1)，所以 redis 选用头插法。
假设哈希表的 size = 4，且包含 3 个键，k0, k1 和 k2，假设 k0 对应的索引值为 0，k1 和 k2 对应的索引值为 2，依次往哈希表存储 k0, k1 和 k2，则未发生 rehash 的哈希表(rehashidx=-1)示例如下：
从发生冲突的哈希表获取值的过程大致如下：从该哈希表取值时，假设取 k0 的值，根据索引值 0，取出 ht[0].table[0] 的元素，比较其中的 key 字段，发现就是要获取的 k0，因此直接返回 v0；假设取 k1 的值，根据索引值 2，取出 ht[0].table[2] 的元素，比较其中的 key 字段，发现 k2 不是要找的 key，于是通过 next 访问下一个元素，再通过比较 key，发现 k1 就是要找的 key，于是返回 v1。
2.3 rehash
rehash 指的是重新计算键的哈希值和索引值，然后将 ht[0] 的键值对放到 ht[1] 哈希表的指定位置上。随着操作的不断进行，哈希表保存的键值对可能会增多或者减少，为了使冗余因子(load factor)保持在一个合理范围内，当哈希表保存的键值对数量太多或者太少时，redis 会对哈希表进行扩容或者收缩。
redis 对字典的哈希表进行 rehash 的步骤如下：
为字典的 ht[1] 哈希表分配空间，ht[1] 哈希表的大小取决于要执行的操作(扩容或者收缩)，以及 ht[0] 哈希表包含的键值对数量(即 ht[0].used 的值)：
如果是扩容操作，ht[1] 的大小为第一个大于等于 2*ht[0].used 的2^n(n 为正整数)
如果是收缩操作，ht[1] 的大小为第一个大于等于 ht[0].used 的2^n(n 为正整数)
将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 哈希表上
当 ht[0] 包含的所有键值对都迁移到 ht[1] 之后，释放 ht[0]，将 ht[1] 设置为 ht[0]，并为 ht[1] 创建一张空的哈希表，为下一次 rehash 做准备
举例说明：假设 ht[0].size = 4，ht[0].used = 4，假设进行扩容操作，2 * ht[0].used = 2*4=8，而第一个大于等于 8 的 2^n 的值为 8(2^3=8)，所以 ht[1].size 设置为 8。
2.3.1 扩容或收缩时机
redis 根据哈希表的冗余因子决定是否进行扩容：redis 服务器未执行 bgsave 或 bgrewriteaof 命令，当负载因子大于等于 1 时，redis 将对哈希表进行扩容；当负载因子大于等于 5 时，即使正在运行 bgsave 或 bgrewriteaof 命令，redis 也将对哈希表进行扩容。当哈希表的负载因子小于 0.1 时，redis 将对哈希表进行收缩操作。
哈希表的负载因子计算公式为：load_factor = ht0].used / ht[0].size，即负载因子等于哈希表已保存的键值对数量除以哈希表的总大小。
根据是否正在运行 bgsave 或者 bgrewriteaof 命令，redis 执行扩展所需的负载因子大小不同的原因：在执行 bgsave 或者 bgrewriteaof 命令的过程中，redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展所需的负载因子，尽可能避免在子进程存在期间进行哈希表的扩展操作，从而避免不必要的内存写入操作，最大限度地节约内存。
2.3.2 渐进式 rehash
rehash 就是将 ht[0] 里的所有键值对复制到 ht[1] 中，但是 rehash 是分多次，渐进式完成的。这么做的原因在于：redis 要保证对外提供可靠稳定的服务，如果 rehash 是一次性完成的，再假设 ht[0] 保存几百万的键值对，可能会导致 redis 在一段时间内无法对外提供服务。
redis 哈希表渐进式 rehash 的步骤大致如下：
为 ht[1] 分配空间，此时 redis 字典拥有 ht[0] 和 ht[1] 两个哈希表
将 redis 字典中 rehashidx 的值修改为 0，表示开始 rehash
在 rehash 期间，每次对字典执行增删改查操作时，除了执行指定的操作外，还会将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 中，并对 rehashidx 执行加 1 操作
不断对字典执行操作后，最终在某个时间 ht[0] 的所有键值对会被 rehash 到 ht[1] 中，此时将 rehashidx 的值设置为 -1，表示 rehash 操作已完成(从代码角度来说什么时候将 rehashidx 的值设为 -1 呢？==》当 rehashidx == ht[0].size 时)
渐进式 rehash 期间的哈希表删除、查找，更新操作，会在 ht[0] 和 ht[1] 这两个哈希表上进行，举例说明：假设要在字典查找一个键，程序先在 ht[0] 查找，如果没找到，再去 ht[1] 查找。如果是执行增加操作，所有的键值对都会被保存到 ht[1] 中，保证 ht[0] 只减不增。
2.3.3 图解 rehash 过程
假设 ht[0].size = 4，且 ht[0].used = 4，此时负载因子为 1，再假设服务器未在执行 bgsave 或 bgrewriteaof 命令，此时触发 rehash 动作。
找到满足 2^n >= 2*ht[0].size 条件的最小 n 值，即 2^n >= 8，计算得到最小的 n 值为 3，此时 2^n=2^3=8 即为 ht[1].size 的大小。
如果 rehashidx 对应索引位置未存储键值对，则 rehashidx 会继续执行加 1 操作，但最多尝试 10 次，防止长时间都在查找一个可以 rehash 的键值对，而对客户端的响应时间骤增。
因为装载因子等于 1，所以准备开始 rehash，为 ht[1] 分配空间，此时 rehashidx = 0 表示下次将把 ht[0] 哈希表中索引为 0 的键值对 rehash 到 ht[1] 哈希表中，几个重要的值：ht[0].used=4，ht[1].used=0，rehashidx=0，示例如下：
假设对该字典进行读操作，此时触发一次 rehash，将 ht[0] 哈希表 0 索引上的值 rehash 到 ht[1] 哈希表中，并将 rehashidx 的值自增为 1，表示下次将 rehash 的索引值为 1，几个重要的值：ht[0].used=3，ht[1].used=1，rehashidx = 1，示例如下：
触发 rehash，根据 rehashidx = 1，将 ht[0] 哈希表 1 索引上的值 rehash 到 ht[1] 哈希表中，并自增 rehashidx 的值为 2，几个重要的值：ht[0].used=2，ht[1].used=2，rehashidx = 2，示例如下：
触发 rehash，根据 rehashidx = 2，将 ht[0] 哈希表 2 索引上的值 rehash 到 ht[1] 哈希表中，由于 ht[0] 哈希表中索引为 2 的位置没有值，再次自增 rehashidx 的值为 3(最多尝试 10 次)，并将索引位置为 3 上的所有元素都 rehash 到 ht[1] 哈希表中，并自增 hashidx 的值 为 4，几个重要的值：ht[0].used=0，ht[1].used=4，rehashidx = 4，示例如下：
ht[0] 哈希表中的所有值已全部 rehash 到 ht[1] 哈希表中，此时 ht[0] 变为空表，表示 rehash 结束，最后将 ht[0] 释放，并将 ht[1] 设置为 ht[0]，并为 ht[1] 创建一张空表，修改 rehashidx 为 -1，为下一次 rehash 做准备，最终完成 rehash 后的字典示例如下：
3 字典 api
为了使篇幅在较短范围内，部分 api 没有贴源码，将会在 “源码分析 redis api(2)——dict” 中分析。
3.1 创建字典
函数：dictCreate，作用：创建一个新的字典，时间复杂度：O(1)。
// redis-6.0.5/src/dict.h#define DICT_OK 0#define DICT_ERR 1// redis-6.0.5/src/dict.c/* -------------------------- private prototypes ---------------------------- */static int _dictInit(dict *ht, dictType *type, void *privDataPtr);/* Reset a hash table already initialized with ht_init(). * NOTE: This function should only be called by ht_destroy(). */static void _dictReset(dictht *ht){ ht->table = NULL; ht->size = 0; ht->sizemask = 0; ht->used = 0;}/* Create a new hash table */dict *dictCreate(dictType *type, void *privDataPtr){ dict *d = zmalloc(sizeof(*d)); _dictInit(d,type,privDataPtr); return d;}/* Initialize the hash table */int _dictInit(dict *d, dictType *type, void *privDataPtr){ _dictReset(&d->ht[0]); _dictReset(&d->ht[1]); d->type = type; d->privdata = privDataPtr; d->rehashidx = -1; d->iterators = 0; return DICT_OK;}源码分析：
dictCreate 为 dict 的数据结构分配空间，并完成各成员的初始化
此时两个哈希表 ht[0] 和 ht[1] 指向 NULL，表示都未分配空间，当插入第一条数据时才会为 ht[0] 分配空间
3.2 增加
函数：dictAdd ，作用：往字典添加一个键值对，如果 key 已存在，则插入失败，时间复杂度：O(1)。
// redis-6.0.5/src/dict.h/* This is the initial size of every hash table */#define DICT_HT_INITIAL_SIZE 4#define dictCompareKeys(d, key1, key2) \ (((d)->type->keyCompare) ? \ (d)->type->keyCompare((d)->privdata, key1, key2) : \ (key1) == (key2))#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 dictHashKey(d, key) (d)->type->hashFunction(key)// ...#define dictIsRehashing(d) ((d)->rehashidx != -1)// redis-6.0.5/src/dict.c/* Add an element to the target hash table */int dictAdd(dict *d, void *key, void *val){ dictEntry *entry = dictAddRaw(d,key,NULL); if (!entry) return DICT_ERR; dictSetVal(d, entry, val); return DICT_OK;}/* Low level add or find: * ... * Return values: * * If key already exists NULL is returned, and "*existing" is populated * with the existing entry if existing is not NULL. * * If key was added, the hash entry is returned to be manipulated by the caller. */dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){ long index; dictEntry *entry; dictht *ht; if (dictIsRehashing(d)) _dictRehashStep(d); // 如果当前字典正在 rehash，则尝试将 ht[0] rehashidx 上的值 rehash 到 ht[1] /* Get the index of the new element, or -1 if * the element already exists. */ // 如果 key 已存在，则返回错误 if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) return NULL; /* Allocate the memory and store the new entry. * Insert the element in top, with the assumption that in a database * system it is more likely that recently added entries are accessed * more frequently. */ // 如果发生 rehash 则往 ht[1] 插入新值，反之往 ht[0] 插入 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; // 头插法插入数据 ht->table[index] = entry; ht->used++; // 插入一个键值对，哈希表的使用量需要加 1 /* Set the hash entry fields. */ dictSetKey(d, entry, key); return entry;}/* This function performs just a step of rehashing, and only if there are * no safe iterators bound to our hash table. When we have iterators in the * middle of a rehashing we can't mess with the two hash tables otherwise * some element can be missed or duplicated. * * This function is called by common lookup or update operations in the * dictionary so that the hash table automatically migrates from H1 to H2 * while it is actively used. */static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1); // 没有正在运行的迭代器时才能调用 dictRehash 函数}/* 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. * * 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, however * since part of the hash table may be composed of empty spaces, it is not * guaranteed that this function will rehash even a single bucket, since it * will visit at max N*10 empty buckets in total, otherwise the amount of * work it does would be unbound and the function may block for a long time. */ int dictRehash(dict *d, int n) { // 调用时，n 赋值为 1，所以 empty_visits 的值为 10 int empty_visits = n*10; /* Max number of empty buckets to visit. */ if (!dictIsRehashing(d)) return 0; // 未发生 rehash，直接返回 // 进入循环的条件: ht[0] 哈希表仍有键值对，即 used ！= 0，n 的值为 1，所以该循环最多发生一次 while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */ assert(d->ht[0].size > (unsigned long)d->rehashidx); // 异常断言，条件成立则继续运行，防止出现数组越界访问 while(d->ht[0].table[d->rehashidx] == NULL) { // 查找第一个需要 rehash 到 ht[1] 中的键值对 d->rehashidx++; if (--empty_visits == 0) return 1; // 最多尝试按顺序找 10 个索引位置，如果还没找到，则直接返回 } de = d->ht[0].table[d->rehashidx]; // 找到需要进行 rehash 的索引 /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { // 可能已发生哈希冲突，需要将该索引位置上的所有值都 rehash 到 ht[1] 中 uint64_t h; nextde = de->next; /* Get the index in the new hash table */ h = dictHashKey(d, de->key) & d->ht[1].sizemask; // 计算在 ht[1] 中的哈希值，即在 ht[1] 中的索引位置 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; // 将 ht[0] 哈希表中 rehashidx 位置的值置空 d->rehashidx++; // rehashidx 自增，指示下一次 rehash 的索引位置 } /* Check if we already rehashed the whole table... */ if (d->ht[0].used == 0) { // 如果 ht[0] 是空表 zfree(d->ht[0].table); // 释放 ht[0] d->ht[0] = d->ht[1]; // 另 ht[0] 指向 ht[1] _dictReset(&d->ht[1]); // 为 ht[1] 创建空表 d->rehashidx = -1; // 标记未发生 rehash return 0; // 返回 0 表示无需再进行 rehash } /* More to rehash... */ return 1; // 返回 1 表示当前字典需要继续 rehash}/* Returns the index of a free slot that can be populated with * a hash entry for the given 'key'. * If the key already exists, -1 is returned * and the optional output parameter may be filled. * * Note that if we are in the process of rehashing the hash table, the * index is always returned in the context of the second (new) hash table. */static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing){ unsigned long idx, table; dictEntry *he; if (existing) *existing = NULL; /* Expand the hash table if needed */ if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; for (table = 0; table <= 1; table++) { idx = hash & d->ht[table].sizemask; /* Search if this slot does not already contain the given key */ he = d->ht[table].table[idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) { if (existing) *existing = he; return -1; } he = he->next; } if (!dictIsRehashing(d)) break; } return idx;}/* Expand the hash table if needed */static int _dictExpandIfNeeded(dict *d){ /* Incremental rehashing already in progress. Return. */ if (dictIsRehashing(d)) return DICT_OK; /* If the hash table is empty expand it to the initial size. */ if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); /* If we reached the 1:1 ratio, and we are allowed to resize the hash * table (global setting) or we should avoid it but the ratio between * elements/buckets is over the "safe" threshold, we resize doubling * the number of buckets. */ 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); } return DICT_OK;}/* Expand or create the hash table */int dictExpand(dict *d, unsigned long size){ /* the size is invalid if it is smaller than the number of * elements already inside the hash table */ if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; dictht n; /* the new hash table */ unsigned long realsize = _dictNextPower(size); /* Rehashing to the same table size is not useful. */ if (realsize == d->ht[0].size) return DICT_ERR; /* Allocate the new hash table and initialize all pointers to NULL */ n.size = realsize; n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; /* Is this the first initialization? If so it's not really a rehashing * we just set the first hash table so that it can accept keys. */ if (d->ht[0].table == NULL) { d->ht[0] = n; return DICT_OK; } /* Prepare a second hash table for incremental rehashing */ d->ht[1] = n; d->rehashidx = 0; return DICT_OK;}/* Our hash table capability is a power of two */// 一般情况下，哈希表的大小为 2^n，当大于 LONG_MAX 时，不再遵循 2^nstatic unsigned long _dictNextPower(unsigned long size){ unsigned long i = DICT_HT_INITIAL_SIZE; // 如果大于 LONG_MAX(在 limits.h 中的宏定义)，则哈希表的大小为 size + 1 if (size >= LONG_MAX) return LONG_MAX + 1LU; while(1) { // 找到第一个 i，使得 2^n 大于等于 size if (i >= size) return i; i *= 2; }}源码分析：
if (dictIsRehashing(d)) _dictRehashStep(d); =>如果当前字典正在发生 rehash 过程，则会触发一次渐进式 rehash，将 ht[0] 一个索引位置上的所有键值对都 rehash 到 ht[1] 中
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; => 如果发生 rehash 则，新的键值对都将插入到 ht[1] 中
采用头插法的方式插入新值
插入动作可能会触发哈希扩容，即触发 rehash 过程
如果是空哈希表，则将哈希表的初始大小设置为 4
3.3 删除
函数：dictDelete，作用：从字典中删除给定 key 的键值对，时间复杂度：O(1)。
主要功能：
与增加动作类似，如果当前字典正在发生 rehash 过程，则会触发一次渐进式 rehash
如果未发生 rehash 过程，只在 ht[0] 中查找并删除指定的 key，如果发生 rehash 过程，先在 ht[0] 中查找，再去 ht[1] 查找
成功删除指定的 key 之后，会调用 keyDestructor 和 valueDestructor 函数(析构函数)来释放 key 和 value 所占用的内存空间
3.4 修改
函数：dictReplace，作用：将给定键值对添加到字典中，如果 key 已存在则更新 value 值，时间复杂度：O(1)。
源码：
/* Add or Overwrite: * Add an element, discarding the old value if the key already exists. * Return 1 if the key was added from scratch, 0 if there was already an * element with such key and dictReplace() just performed a value update * operation. */int dictReplace(dict *d, void *key, void *val){ dictEntry *entry, *existing, auxentry; /* Try to add the element. If the key * does not exists dictAdd will succeed. */ entry = dictAddRaw(d,key,&existing); // 调用 dictAddRaw 函数 if (entry) { // 如果 key 不存在，则成功插入 key，返回值为插入链表节点的地址 dictSetVal(d, entry, val); // 设置 key 对应的 calue 值 return 1; } /* Set the new value and free the old one. Note that it is important * to do that in this order, as the value may just be exactly the same * as the previous one. In this context, think to reference counting, * you want to increment (set), and then decrement (free), and not the * reverse. */ auxentry = *existing; // key 已存在，existing 为已存在 key 所在链表节点的地址 dictSetVal(d, existing, val); // 更新已有 key 对应的 value 值，不是更新原有内存所存的值，而是在新的内存地址上操作 dictFreeVal(d, &auxentry); // 释放原有 value 值的所占用的内存 return 0;}源码分析：
与增加动作类似，如果当前字典正在发生 rehash 过程，则会触发一次渐进式 rehash
功能与 dictAdd 类似，只是如果 key 存在，则更新 key 所对应的 value 值
3.5 查找
函数：dictFind，作用：从字典中查找指定 key 所对应的 value 的值，时间复杂度：O(1)。
主要功能：
与增加动作类似，如果当前字典正在发生 rehash 过程，则会触发一次渐进式 rehash
使用 hashFunction 函数计算 key 的哈希值，将哈希值与 sizemask 执行按位与操作，计算出该 key 所在的索引位置
如果未发生 rehash 过程，只需根据 ht[0] 的 sizemask 计算一个哈希值，并只在 ht[0] 上查找；如果发生 rehash 过程，先在 ht[0] 查找，如果没找到继续在 ht[1] 查找，此时可能需要计算两次哈希值
遍历索引位置指向的 dictEntry 链表，依次比较 key 是否相等，若相等则返回该项，如果遍历完链表(rehash 时需要在 ht[1] 也执行相同的查找比较)，还未找到，说明 key 不存在
3.6 其他重要 api
dictRelease：释放字典以及字典中包含的所有键值对，时间复杂度：O(n);
dictGetRandomKey：从字典中随机返回一个键值对，时间复杂度：O(1);
dictFetchValue：返回给定 key 的值，时间复杂度：O(1)。
4 参考资料
redis-6.0.5 源码(http://download.redis.io/releases/redis-6.0.5.tar.gz
Redis 设计与实现(http://redisbook.com/preview/dict/content.html)
http://zhangtielei.com/posts/blog-redis-dict.html
https://github.com/aappleby/smhasher