[toc]
四个数据结构
dictEntry
dictEntry 的构造如下(Redis 7.0)：
typedef struct dictEntry { void *key; // 键 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 值 struct dictEntry *next; /* Next entry in the same hash bucket.即下一个节点 */ void *metadata[]; /* An arbitrary number of bytes (starting at a * pointer-aligned address) of size as returned * by dictType's dictEntryMetadataBytes(). */} dictEntry;能够比照 《Redis 设计与实现》中的 dictEntry 构造，发现联合结构 v 中多了一个 double 的浮点数示意，metadata 是一块任意长度的数据，具体的长度由 dictType 中的 dictEntryMetadataBytes() 返回，作用相当于 privdata
dictType
dictType 是一系列操作字典的键和值的操作：
typedef struct dictType { uint64_t (*hashFunction)(const void *key); // 哈希函数 void *(*keyDup)(dict *d, const void *key); // 复制键的函数 void *(*valDup)(dict *d, const void *obj); // 复制值的函数 int (*keyCompare)(dict *d, const void *key1, const void *key2); // 键的比拟 void (*keyDestructor)(dict *d, void *key); // 键的销毁 void (*valDestructor)(dict *d, void *obj); // 值的销毁 int (*expandAllowed)(size_t moreMem, double usedRatio); // 字典里的哈希表是否容许扩容 /* Allow a dictEntry to carry extra caller-defined metadata. The * extra memory is initialized to 0 when a dictEntry is allocated. */ /* 容许调用者向条目 (dictEntry) 中增加额定的元信息. * 这段额定信息的内存会在条目调配时被零初始化. */ size_t (*dictEntryMetadataBytes)(dict *d);} dictType;该构造是为了实现字典的多态。
dict
7.0 版本的字典构造如下：
struct dict { dictType *type; dictEntry **ht_table[2]; unsigned long ht_used[2]; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ /* Keep small vars at end for optimal (minimal) struct padding */ int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */ signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */};相比于 《Redis 设计与实现》中的字典实现，改变较大，7.0中去掉了 dictht 构造，即去掉了哈希构造。接下来介绍每个成员：
/* type 下面曾经解释过了;* ht_table 即哈希表数组* ht_used 别离示意哈希表数组中各自曾经寄存键值对的个数* rehashidx 是 rehash 时用的，没有 rehash 时值为1* pauserehash 则是示意 rehash 的状态，大于0时示意 rehash 暂停了，小于0示意出错了* ht_size_exp 则是示意两个哈希表数组的大小，通过 1 << ht_size_exp[0/1] 来计算*/咱们能够看到一行正文：/* Keep small vars at end for optimal (minimal) struct padding */ ，将小变量放在构造体的前面，为了最佳或最小的填充，即节俭空间。
dictIterator
dictIterator 是字典的迭代器
/* If safe is set to 1 this is a safe iterator, that means, you can call * dictAdd, dictFind, and other functions against the dictionary even while * iterating. Otherwise it is a non safe iterator, and only dictNext() * should be called while iterating. */typedef struct dictIterator { dict *d; long index; int table, safe; dictEntry *entry, *nextEntry; /* unsafe iterator fingerprint for misuse detection. */ unsigned long long fingerprint;} dictIterator;解释其成员：
/* d 指向以后迭代的字典* index 示意指向的键值对索引* table 是哈希表的号码，ht[0]/ht[1]* safe 示意该迭代器是否平安。平安时能够掉用 dictAdd,dictFind等等其余函数，不平安时只能调用 dictNext* entry 指向迭代器所指的键值对，nextEntry 指向下一个键值对* fingerprint 指纹, 用于查看不平安迭代器的误用*/常量与一系列宏
首先是对于哈希表初始化的两个常量：
/* This is the initial size of every hash table */#define DICT_HT_INITIAL_EXP 2#define DICT_HT_INITIAL_SIZE (1<<(DICT_HT_INITIAL_EXP))很显著，哈希表的初始大小为 4
dictFreeVal
开释 val
#define dictFreeVal(d, entry) \ if ((d)->type->valDestructor) \ (d)->type->valDestructor((d), (entry)->v.val)调用 dictType 中提供的 valDestructor 函数开释 val
dictSetVal
设置 val 的值
#define dictSetVal(d, entry, _val_) do { \ if ((d)->type->valDup) \ (entry)->v.val = (d)->type->valDup((d), _val_); \ else \ (entry)->v.val = (_val_); \} while(0)如果 dictType 提供了设置 val 值的办法则调用，没有则间接赋值
dictSetSignedIntegerVal
设置有符号的整型 val 值
#define dictSetSignedIntegerVal(entry, _val_) \ do { (entry)->v.s64 = _val_; } while(0)当然还有设置 无符号的整型值、double 值
dictFreeKey
开释 key
#define dictFreeKey(d, entry) \ if ((d)->type->keyDestructor) \ (d)->type->keyDestructor((d), (entry)->key)dictSetKey
设置 key 的值
#define dictSetKey(d, entry, _key_) do { \ if ((d)->type->keyDup) \ (entry)->key = (d)->type->keyDup((d), _key_); \ else \ (entry)->key = (_key_); \} while(0)dictCompareKeys
key 的比拟
#define dictCompareKeys(d, key1, key2) \ (((d)->type->keyCompare) ? \ (d)->type->keyCompare((d), key1, key2) : \ (key1) == (key2))如果 dictType 中的 keyCompare 指针不为空，则调用它进行比拟，否则间接用 == 比拟
dictMetadata
获取用户提供的元数据
#define dictMetadata(entry) (&(entry)->metadata)dictMetadataSize
获取用户提供的元数据的长度
#define dictMetadataSize(d) ((d)->type->dictEntryMetadataBytes \ ? (d)->type->dictEntryMetadataBytes(d) : 0)获取 key 和 val 的宏
#define dictHashKey(d, key) (d)->type->hashFunction(key) // 获取 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 dictGetDoubleVal(he) ((he)->v.d)对于哈希表大小的宏
// 获取哈希表的大小#define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))// 哈希表的掩码(size - 1)#define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)dictSlots
// 获取字典的总大小#define dictSlots(d) (DICTHT_SIZE((d)->ht_size_exp[0])+DICTHT_SIZE((d)->ht_size_exp[1]))dictSize
// 获取字典保留键值对的总数#define dictSize(d) ((d)->ht_used[0]+(d)->ht_used[1])对于 rehash 的宏
// 判断以后是否在 rehash#define dictIsRehashing(d) ((d)->rehashidx != -1)// 暂停 rehash#define dictPauseRehashing(d) (d)->pauserehash++// 复原 rehash#define dictResumeRehashing(d) (d)->pauserehash--创立/销毁/批改字典
创立字典
创立字典的接口是 dictCreate
dictCreate 为字典构造调配空间，并调用 _dictInit 进行初始化
在 _dictinit 中，又调用了 _dicrReset 进行成员设置
/* Create a new hash table */dict *dictCreate(dictType *type){ dict *d = zmalloc(sizeof(*d)); _dictInit(d,type); return d;}/* Initialize the hash table */int _dictInit(dict *d, dictType *type){ _dictReset(d, 0); _dictReset(d, 1); d->type = type; d->rehashidx = -1; d->pauserehash = 0; return DICT_OK;}/* Reset hash table parameters already initialized with _dictInit()*/static void _dictReset(dict *d, int htidx){ d->ht_table[htidx] = NULL; d->ht_size_exp[htidx] = -1; d->ht_used[htidx] = 0;}在 _dictInit 中有一个宏 DICT_OK，它的定义为：
#define DICT_OK 0#define DICT_ERR 1用来标识操作是否胜利实现
批改字典
个别批改字典都是为 rehash 做筹备，或者扩充容量或者放大容量。
dictResize
放大字典大小，前提是以后没有在进行 rehash 以及 dict_can_resize 变量不为 0
dict_can_resize 是 dict.c 中定义的一个全局变量，用来批示 resize 是否进行
static int dict_can_resize = 1;什么时候 dict_can_resize 会为0呢？
当 redis 在后盾进行长久化时， 为了最大化地利用零碎的 copy on write 机制，会临时地将 dict_can_resize 设置为0，防止执行天然 rehash，从而缩小程序对内存的碰撞。长久化工作实现后，dict_can_resize 又会设置为1
/* Resize the table to the minimal size that contains all the elements, * but with the invariant of a USED/BUCKETS ratio near to <= 1 */int dictResize(dict *d){ unsigned long minimal; if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR; minimal = d->ht_used[0]; if (minimal < DICT_HT_INITIAL_SIZE) minimal = DICT_HT_INITIAL_SIZE; return dictExpand(d, minimal);}放大哈希表的大小，新的容量刚好能包容已有元素。minimal 等于已有元素的数量，而后在 _dictExpand 中，会将新容量的大小设置为刚好大于等于 minimal 的 2 的幂。
dictExpand
再来看 dictExpand，调用 _dictExpand 进行理论的扩容。
/* return DICT_ERR if expand was not performed */int dictExpand(dict *d, unsigned long size) { return _dictExpand(d, size, NULL);}/* Expand or create the hash table, * when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1). * Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */int _dictExpand(dict *d, unsigned long size, int* malloc_failed){ if (malloc_failed) *malloc_failed = 0; /* the size is invalid if it is smaller than the number of * elements already inside the hash table */ if (dictIsRehashing(d) || d->ht_used[0] > size) return DICT_ERR; /* the new hash table */ dictEntry **new_ht_table; unsigned long new_ht_used; signed char new_ht_size_exp = _dictNextExp(size); /* Detect overflows */ size_t newsize = 1ul<<new_ht_size_exp; if (newsize < size || newsize * sizeof(dictEntry*) < newsize) return DICT_ERR; /* Rehashing to the same table size is not useful. */ if (new_ht_size_exp == d->ht_size_exp[0]) return DICT_ERR; /* Allocate the new hash table and initialize all pointers to NULL */ if (malloc_failed) { new_ht_table = ztrycalloc(newsize*sizeof(dictEntry*)); *malloc_failed = new_ht_table == NULL; if (*malloc_failed) return DICT_ERR; } else new_ht_table = zcalloc(newsize*sizeof(dictEntry*)); new_ht_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_table[0] == NULL) { d->ht_size_exp[0] = new_ht_size_exp; d->ht_used[0] = new_ht_used; d->ht_table[0] = new_ht_table; return DICT_OK; } /* Prepare a second hash table for incremental rehashing */ d->ht_size_exp[1] = new_ht_size_exp; d->ht_used[1] = new_ht_used; d->ht_table[1] = new_ht_table; d->rehashidx = 0; return DICT_OK;}_dictExpand 函数不是只为了 rehash，还能够初始化字典。 _dictExpand 函数判断是否是 rehash 是通过判断 ht_table[0] 是否为空来判断的。也就是说如果调用 _dictExpand 的字典是非空的，则增容后的哈希表是放在 ht_table[1] 中的，所以须要调用者手动开释 ht_table[0]，将 ht_table[1] 放到 ht_table[0] 地位上。
Rehash
rehash 扩容分为两种：
- 天然 rehash：used / size >= 1 时且
dict_can_resize为1 - 强制 rehash：used / size >
dict_force_resize_ratio该版本中dict_force_resize_ratio的值为5
另外，当哈希表的负载因子小于 0.1 时，程序主动开始对哈希表执行膨胀操作。
Rehash 过程：创立一个新的哈希表 ht[1]，rehashidx 变成0，依据 rehashidx 指向的桶进行数据的迁徙。当所有数据迁徙结束时，开释 ht[0]，将 ht[1] 迁徙到 ht[0]，ht[1] 置为空。
上面是 Rehash 的一个简略示例：
Rehash 之前：
Rehash 开始：
所有元素从新映射到 ht_table[1] ：
表的转移，实现 Rehash：
Rehash 不是一步就实现的，否则数据量特地大时，迁徙数据会是一个很大的工程，可能会导致服务器暂停服务来迁徙数据，Rehash 是渐进式的，数据的迁徙产生在对数据的增删改查时，这样就将迁徙平摊在每个增删改查的操作上。
如果在 rehash 期间要执行增加键的操作，都是在 ht[1] 中进行的，而进行删改查等操作，会同时在两张表中进行。
每次 rehash 都是以 n 个桶为单位的，将每个桶上的链都移到新的哈希表上。一次 rehash 实现当前，如果之后还有桶要 rehash，则返回1，如果 rehash 实现，则返回0。然而实际上，rehashidx 指向的桶可能是空桶，所以为了效率，一次 rehash 最多要遍历 10n 个空桶，遍历完了 10 n 个空桶就会返回。
int dictRehash(dict *d, int n) { int empty_visits = n*10; /* Max number of empty buckets to visit. */ if (!dictIsRehashing(d)) return 0; while(n-- && d->ht_used[0] != 0) { dictEntry *de, *nextde; /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */ assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx); while(d->ht_table[0][d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } de = d->ht_table[0][d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { uint64_t h; nextde = de->next; /* Get the index in the new hash table */ h = dictHashKey(d, de->key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]); de->next = d->ht_table[1][h]; d->ht_table[1][h] = de; d->ht_used[0]--; d->ht_used[1]++; de = nextde; } d->ht_table[0][d->rehashidx] = NULL; d->rehashidx++; } /* Check if we already rehashed the whole table... */ if (d->ht_used[0] == 0) { zfree(d->ht_table[0]); /* Copy the new ht onto the old one */ d->ht_table[0] = d->ht_table[1]; d->ht_used[0] = d->ht_used[1]; d->ht_size_exp[0] = d->ht_size_exp[1]; _dictReset(d, 1); d->rehashidx = -1; return 0; } /* More to rehash... */ return 1;}销毁字典
销毁字典的接口是dictRelease
dictRelease 调用_dictClear 来开释两个哈希表，并最初开释字典空间
/* Destroy an entire dictionary */int _dictClear(dict *d, int htidx, void(callback)(dict*)) { unsigned long i; /* Free all the elements */ for (i = 0; i < DICTHT_SIZE(d->ht_size_exp[htidx]) && d->ht_used[htidx] > 0; i++) { dictEntry *he, *nextHe; if (callback && (i & 65535) == 0) callback(d); if ((he = d->ht_table[htidx][i]) == NULL) continue; while(he) { nextHe = he->next; dictFreeKey(d, he); dictFreeVal(d, he); zfree(he); d->ht_used[htidx]--; he = nextHe; } } /* Free the table and the allocated cache structure */ zfree(d->ht_table[htidx]); /* Re-initialize the table */ _dictReset(d, htidx); return DICT_OK; /* never fails */}/* Clear & Release the hash table */void dictRelease(dict *d){ _dictClear(d,0,NULL); _dictClear(d,1,NULL); zfree(d);}_dictClear 的第三个参数是一个函数指针，但 dictRelease 在这里都传了空指针，所以暂且不论。 _dictClear 遍历所有的索引，当该索引上有键值对时，则开释该索引上的整条链表。开释完所有键值对之后，再开释该哈希表并重置其成员。
键的操作
dictAdd
增加一个键值对到指定哈希表中
/* 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;}该函数调用了 dictAddRaw 函数，上面是 dictAddRaw 函数的定义：
/* Low level add or find: * This function adds the entry but instead of setting a value returns the * dictEntry structure to the user, that will make sure to fill the value * field as they wish. * * This function is also directly exposed to the user API to be called * mainly in order to store non-pointers inside the hash value, example: * * entry = dictAddRaw(dict,mykey,NULL); * if (entry != NULL) dictSetSignedIntegerVal(entry,1000); * * 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; int htidx; if (dictIsRehashing(d)) _dictRehashStep(d); /* Get the index of the new element, or -1 if * the element already exists. */ 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. */ htidx = dictIsRehashing(d) ? 1 : 0; size_t metasize = dictMetadataSize(d); entry = zmalloc(sizeof(*entry) + metasize); if (metasize > 0) { memset(dictMetadata(entry), 0, metasize); } entry->next = d->ht_table[htidx][index]; d->ht_table[htidx][index] = entry; d->ht_used[htidx]++; /* Set the hash entry fields. */ dictSetKey(d, entry, key); return entry;}该函数下面有一串正文，意思是：该函数增加一个 dictEntry 到哈希表中，但并不会设置值，将该构造返回给用户，将值的设置交给用户。 这个函数也间接裸露给要调用的用户API，次要是为了在哈希值外部存储非指针。
返回值：如果键曾经存在，则返回 NULL，并填充“*existing” 如果 existing 不为 NULL，则应用现有条目。如果胜利增加了键，则返回哈希条目(dictEntry)以供调用者操作
咱们剖析函数的一个实现细节：能够看到函数首先会判断以后的哈希表是否在 rehash，如果在 rehash，则进行一次只迁徙一个桶的 rehash。_dictRehashStep 是实现一次只迁徙一个桶的 rehash。
所以当初咱们就晓得。dictAdd 调用 dictAddRaw，获取一个已插入的 dictEntry，而后实现值的设置。
在该函数中还调用了 _dictKeyIndex 函数，该函数实现如下：
函数返回 key 在哈希表中的索引，如果哈希表中存在该 key，则返回 -1，可选的输入参数 existing 会被填充成对应的 dictEntry。
须要留神的是，如果以后哈希表正在 rehash，则返回的索引始终是第二张哈希表的索引。
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 & DICTHT_SIZE_MASK(d->ht_size_exp[table]); /* 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;}dictReplace
如果 key 不存在，则增加 key，并设置 value，函数返回1。如果 key 曾经存在，则更新 value 值，函数返回0
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); if (entry) { dictSetVal(d, entry, val); 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; dictSetVal(d, existing, val); dictFreeVal(d, &auxentry); return 0;}首先调用 dictAddRaw 函数，依据返回值判断 key 是否曾经在哈希表中，如果不存在，则 entry 不为空，设置 val 值并返回1。如果 entry 为空，则进行值的更新。但要遵循先设置新值再开释旧值的程序。因为新值和旧值可能雷同，这种状况就须要思考援用计数，咱们应该先减少计数，再缩小计数。
dictAddOrFind
该函数总是返回一个 指定key 的 dictEntry。如果 key 曾经存在，则将其 dictEntry 返回；如果不存在，则将其增加并返回。
dictEntry *dictAddOrFind(dict *d, void *key) { dictEntry *entry, *existing; entry = dictAddRaw(d,key,&existing); return entry ? entry : existing;}dictDelete
删除元素
/* Remove an element, returning DICT_OK on success or DICT_ERR if the * element was not found. */int dictDelete(dict *ht, const void *key) { return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;}dictDelete 通过 dictGenericDelete 来删除哈希表中的元素。
如果没找到要删除的元素则返回 NULL，找到了则返回曾经开释的 dictEntry。
/* Search and remove an element. This is a helper function for * dictDelete() and dictUnlink(), please check the top comment * of those functions. */static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) { uint64_t h, idx; dictEntry *he, *prevHe; int table; /* dict is empty */ if (dictSize(d) == 0) return NULL; if (dictIsRehashing(d)) _dictRehashStep(d); h = dictHashKey(d, key); for (table = 0; table <= 1; table++) { idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]); he = d->ht_table[table][idx]; prevHe = NULL; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) { /* Unlink the element from the list */ if (prevHe) prevHe->next = he->next; else d->ht_table[table][idx] = he->next; if (!nofree) { dictFreeUnlinkedEntry(d, he); } d->ht_used[table]--; return he; } prevHe = he; he = he->next; } if (!dictIsRehashing(d)) break; } return NULL; /* not found */}dictUnlink 与 dictFreeUnlinkedEntry
dictUnlink 函数是从哈希表中删除 key，但 key，value 和 dictEntry 并没有被开释，须要调用 dictFreeUnlinkedEntry 函数来开释这些资源。如果 key 在哈希表中找到了，则返回对应的 dictEntry，如果没找到则返回 NULL
dictEntry *dictUnlink(dict *d, const void *key) { return dictGenericDelete(d,key,1);}/* You need to call this function to really free the entry after a call * to dictUnlink(). It's safe to call this function with 'he' = NULL. */void dictFreeUnlinkedEntry(dict *d, dictEntry *he) { if (he == NULL) return; dictFreeKey(d, he); dictFreeVal(d, he); zfree(he);}dictFind
查找 key，找到了返回其 dictEntry；否则返回 NULL
dictEntry *dictFind(dict *d, const void *key){ dictEntry *he; uint64_t h, idx, table; if (dictSize(d) == 0) return NULL; /* dict is empty */ if (dictIsRehashing(d)) _dictRehashStep(d); h = dictHashKey(d, key); for (table = 0; table <= 1; table++) { idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]); he = d->ht_table[table][idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) return he; he = he->next; } if (!dictIsRehashing(d)) return NULL; } return NULL;}