哈希表是一种十分要害的数据结构，在计算机系统中施展着重要作用。
它的底层是数组+链表，通过哈希计算，能以 O(1) 的复杂度疾速依据key查问到数据。
(1) 数据结构-哈希表
假如让咱们本人实现一个哈希表，咱们要思考哪些方面？
- 哈希表提供的性能
- 哈希表操作的工夫复杂度为O(1)
- 哈希表的容量与扩容
(1.1) 提供的性能
新建哈希表、新增数据、批改数据、删除数据、查问数据
(1.2) 工夫复杂度O(1)
要想使工夫复杂度为O(1)，要通过高效的定位办法，比方hash函数
然而hash函数有个问题，可能会哈希抵触，抵触后有多种办法 链地址法、 凋谢定位法、 再哈希法，这里咱们应用链地址法实现。
/** 哈希函数 */ int hash(Object key) { int h; // h = key.hashCode() 为第一步 取hashCode值 // h ^ (h >>> 16) 为第二步 高位参加运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }链式哈希的链不能太长，否则会升高 哈希表性能。
链表哈希的链表太长时能够转换为红黑树进步查问性能。
(1.3) 哈希表容量与扩容
这里咱们在创立哈希表的时候反对指定容量
扩容时容量是原来的2倍
public void resize(){ //todo }如果容量特地大，内存不够怎么办？
(2) Redis里的哈希表
对于 Redis 键值数据库来说，哈希表既是键值对中的一种值类型，同时，Redis 也应用一个全局 哈希表来保留所有的键值对，从而既满足利用存取 Hash 构造数据需要，又能提供疾速查问性能。
在理论利用 哈希表时，当数据量一直减少，它的性能就常常会受到哈希抵触和 rehash 开销的影响。
针对哈希抵触，Redis 采纳了链式哈希，在不扩容哈希表的前提下，将具备雷同哈希值的数据链接起来，以便这些数据在表中依然能够被查问到；
对于 rehash 开销，Redis 实现了渐进式 rehash 设计，进而缓解了 rehash 操作带来的额定开销对系统的性能影响。
dict.h 文件定义了 哈希表的构造、哈希项，以及 哈希表的各种操作函数，dict.c 文件蕴含了 哈希表各种操作的具体实现代码。
源码 https://github.com/redis/redi...
https://github.com/redis/redis/blob/6.0/src/dict.c(2.1) 哈希表构造定义
/** * 这是哈希表构造。 * 每个字典都有两个这样的字典，因为咱们实现了增量从新哈希，从旧表到新表。 */typedef struct dictht { dictEntry **table; // 一维数组的指针 unsigned long size; // 哈希表大小 unsigned long sizemask; // size-1 = (2^n - 1)，比2^n少1，用于计算key对应桶的下标 unsigned long used; // } dictht;/** * 哈希表节点 */typedef struct dictEntry { void *key; // 存储的key union { void *val; uint64_t u64; int64_t s64; double d; } v; // 存储的值 struct dictEntry *next; // 链表的下一个节点} dictEntry;能够看到 哈希表dictht里定义了 二维数组()、哈希表大小、
哈希节点里定义了 键(key)、值(v)、链表的下一个节点(next)，其中值(v)是一个联合体，联合体中蕴含了指向理论值的指针 *val，还蕴含了无符号的 64 位整数、有符号的 64 位整数，以及 double 类的值。
为什么要应用联合体呢？
这种实现办法是一种节俭内存的小技巧，因为当值为整数或双精度浮点数时，因为其自身就是64位，就能够不必指针指向了，而是能够间接存在键值对的构造体中，这样就防止了再用一个指针，从而节俭了内存空间。
(2.2) 哈希表提供的性能
| 操作 | 函数 | 算法复杂度 |
|---|---|---|
| 创立一个新字典 | dictCreate | O(1) |
| 增加新键值对到字典 | dictAdd | O(1) |
| 增加或更新给定键的值 | dictReplace | O(1) |
| 在字典中查找给定键所在的节点 | dictFind | O(1) |
| 在字典中查找给定键的值 | dictFetchValue | O(1) |
| 从字典中随机返回一个节点 | dictGetRandomKey | O(1) |
| 依据给定键，删除字典中的键值对 | dictDelete | O(1) |
| 清空并开释字典 | dictRelease | O(N) |
| 清空并重置（但不开释）字典 | dictEmpty | O(N) |
| 放大字典 | dictResize | O(N) |
| 扩充字典 | dictExpand | O(N) |
| 对字典进行给定步数的 rehash | dictRehash | O(N) |
| 在给定毫秒内，对字典进行rehash | dictRehashMilliseconds | O(N) |
(2.2.1) 创立一个哈希表
/** 创立一个新的哈希表 */dict *dictCreate(dictType *type, void *privDataPtr){ // 分配内存 dict *d = zmalloc(sizeof(*d)); // 初始化 _dictInit(d,type,privDataPtr); return d;}/** 初始化哈希表 */int _dictInit(dict *d, dictType *type, void *privDataPtr){ _dictReset(&d->ht[0]); // 重置ht[0] _dictReset(&d->ht[1]); // 重置ht[1] d->type = type; // 设置哈希表类型 d->privdata = privDataPtr; // d->rehashidx = -1; // 设置成-1 代表没有进行rehash d->iterators = 0; // return DICT_OK;}/* 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; // 哈希表的数组置为null ht->size = 0; // 哈希表长度设置为0 ht->sizemask = 0; // 掩码设置为0 ht->used = 0; // 已应用空间设置为0}(2.2.2) 哈希表增加元素
// file: dict.c/** * 往哈希表增加一个元素 * * @param *d * @param *key * @param *val */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;}/* * 低级增加或查找： * 此函数增加条目但不是设置值，而是将 dictEntry 构造返回给用户，这将确保依照他的志愿填充值字段。 * * 这个函数也是间接裸露给用户API调用的，次要是为了在hash值外面存储非指针，例如： * * entry = dictAddRaw(dict,mykey,NULL); * if (entry != NULL) dictSetSignedIntegerVal(entry,1000); * * 返回值： * 如果键曾经存在，则返回 NULL，如果 existing 不为 NULL，则“*existing”将填充现有条目。 * 如果增加了键，则返回哈希条目以供调用者操作。 */dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){ long index; dictEntry *entry; dictht *ht; // 如果正在rehash，进行rehash 这里只迁徙一个桶，简直对性能无影响 if (dictIsRehashing(d)) _dictRehashStep(d); // 获取元素下标 如果元素曾经存在返回-1 if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) return NULL; /* 分配内存并存储新条目。 * 在顶部插入元素，假如在数据库系统中，最近增加的条目更有可能被更频繁地拜访。*/ // 如果在进行rehash，往ht[1]里增加元素 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 为新节点分配内存 entry = zmalloc(sizeof(*entry)); // 把新节点插入到链表的头部 entry->next = ht->table[index]; // 更新链表头结点 ht->table[index] = entry; // 哈希表已应用节点数+1 ht->used++; /* Set the hash entry fields. */ dictSetKey(d, entry, key); return entry;}// file: dict.h/** 设置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)// file: dict.h/** 设置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)(2.2.3) 哈希表更新元素
/** * 增加或笼罩： * 增加一个元素，如果键曾经存在则抛弃旧值。 * 如果该键是从头开始增加的，则返回 1， * 如果曾经存在具备该键的元素，则返回 0，并且 dictReplace() 刚刚执行了值更新操作。 */int dictReplace(dict *d, void *key, void *val){ dictEntry *entry, *existing, auxentry; // 增加条目 entry = dictAddRaw(d,key,&existing); if (entry) { // 设置值 dictSetVal(d, entry, val); return 1; } /* 设置新值并开释旧值。 * 请留神，按此程序执行此操作很重要，因为值可能与前一个值完全相同。 * 在这种状况下，想想援用计数，你想要递增（设置），而后递加（自在），而不是相同。 */ auxentry = *existing; // 笼罩值 dictSetVal(d, existing, val); // 开释原来的 dictFreeVal(d, &auxentry); return 0;}(2.2.4) 哈希表查找元素
/** * * @param *d * @param *key */dictEntry *dictFind(dict *d, const void *key){ dictEntry *he; uint64_t h, idx, table; // 哈希表为空 if (dictSize(d) == 0) return NULL; /* dict is empty */ // 哈希表正在rehash，执行rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 依据key查找桶 h = dictHashKey(d, key); // ht[0] ht[1] 都会查，所以 table=0 table<=1 for (table = 0; table <= 1; table++) { // 获取下标 idx = h & d->ht[table].sizemask; // 链表头结点 he = d->ht[table].table[idx]; // 遍历链表 while(he) { // key雷同 或 key比照相等 if (key==he->key || dictCompareKeys(d, key, he->key)) return he; he = he->next; } if (!dictIsRehashing(d)) return NULL; } return NULL;}(2.2.5) 哈希表删除元素
/** * 删除一个元素 * 胜利时返回 DICT_OK，如果找不到该元素则返回 DICT_ERR。 * * @param *ht * @param *key */int dictDelete(dict *ht, const void *key) { return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;}/** * 搜寻并删除元素。 * 这是 dictDelete() 和 dictUnlink()的辅助函数，请查看这些函数的顶部正文。 * * @param *d * @param *key * @param nofree */static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) { uint64_t h, idx; dictEntry *he, *prevHe; int table; // ht[0] ht[1] 已应用大小为0，返回null if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL; // 如果正在rehash，执行rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 获取hash值 h = dictHashKey(d, key); // ht[0] ht[1] 都会查，所以 table=0 table<=1 for (table = 0; table <= 1; table++) { // 获取下标 idx = h & d->ht[table].sizemask; // 获取桶 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; // 设置next节点为头结点，next有可能是null if (!nofree) { // 开释key dictFreeKey(d, he); // 开释val dictFreeVal(d, he); // 开释entry zfree(he); } // 更新应用元素个数 d->ht[table].used--; return he; } // 更新前驱节点 prevHe = he; // 解决下一个节点 he = he->next; } if (!dictIsRehashing(d)) break; } // 没有找到key return NULL;}(2.3) 哈希表扩容
哈希表扩容是指 rehash 操作，其实就是指扩充 哈希表空间。
Redis rehash流程
- Redis里保留了两个 Hash表
ht[0]和ht[1]，用于 rehash 时交替保留数据； - 在失常服务申请阶段，所有的键值对写入哈希表 ht[0]；
- 当进行 rehash 时，键值对被迁徙到哈希表 ht[1]中；
- 当迁徙实现后，ht[0]的空间会被开释，并把 ht[1]的地址赋值给 ht[0]，ht[1]的表大小设置为 0
这样一来，又回到了失常服务申请的阶段，ht[0]接管和服务申请，ht[1]作为下一次 rehash 时的迁徙表。
typedef struct dict { dictType *type; // 类型 void *privdata; // dictht ht[2]; // 2个哈希表 long rehashidx; // rehashidx == -1 则rehashing没有进行 unsigned long iterators; // 以后正在运行的迭代器数} dict;在rehashing时，rehashidx对应要操作的 ht[0].table[rehashidx] 的桶
(3) rehash
rehash的整体流程
在
(3.1) rehash的触发条件-什么时候产生rehash
- 在哈希表为空时，调用
_dictExpandIfNeeded会触发哈希表初始化，默认大小为4。 在哈希表不为空时，触发rehash须要同时满足2个条件:
- 已应用桶数量:哈希表桶容量 达到了 1:1 的比例 (
ht[0].used > ht[0].size) - 容许调整哈希表的大小(
dict_can_resize=1) 或者 元素/桶 > 5 (dict_force_resize_ratio>5)
- 已应用桶数量:哈希表桶容量 达到了 1:1 的比例 (
具体代码如下:
// file: dict.c /** * 如果须要扩大哈希表 * * @param *d */static int _dictExpandIfNeeded(dict *d){ // 增量rehash正在进行中，返回 通过 rehashidx != -1 判断 if (dictIsRehashing(d)) return DICT_OK; // 如果哈希表为空，则将其扩大到初始大小。 初始大小默认为4 if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); /* * 如果 已应用桶数量:哈希表桶容量 达到了 1:1 的比例， * 并且咱们被容许调整哈希表的大小(全局设置) 或者 应该防止它然而元素/桶之间的比例超过了“平安”阈值 5 ， * 咱们调整大小使桶的数量为原来2倍。 * * 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)) // dict_force_resize_ratio 默认为5 { // 扩容 return dictExpand(d, d->ht[0].used*2); } return DICT_OK;}dict_can_resize 变量值默认是1，能够在 dictEnableResize、 dictDisableResize 函数中设置
// file: dict.c /* * 应用 dictEnableResize() / dictDisableResize() 咱们能够依据须要启用/禁用哈希表的大小调整。 * 这对 Redis 来说十分重要，因为咱们应用写时复制，并且不想在有子过程正在执行保留操作时挪动太多内存。 * * 请留神，即便将 dict_can_resize 设置为 0，也不会阻止所有调整大小： * 如果元素数量与桶数之间的比率 > dict_force_resize_ratio，则哈希表依然容许增长。 */static int dict_can_resize = 1;void dictEnableResize(void) { dict_can_resize = 1;}void dictDisableResize(void) { dict_can_resize = 0;}dict_force_resize_ratio 值在 dict.c 文件中定义，默认是5
在哪些函数里调用了_dictExpandIfNeeded
_dictExpandIfNeeded 是被 _dictKeyIndex 函数调用的_dictKeyIndex 函数又会被 dictAddRaw 函数调用dictAddRaw 会被 dictAdd dictRelace dictAddorFind sentinelLeaderIncr setTypeAdd zunionInterGenericCommand 函数调用
当咱们往 Redis 中写入新的键值对或是批改键值对时，Redis 都会判断下是否须要进行 rehash。
这里你能够参考上面给出的示意图，其中就展现了 _dictExpandIfNeeded 被调用的关系。
(3.2) rehash如何执行？
为什么要实现渐进式rehash？
因为哈希表在执行rehash时，因为哈希表扩容，key对应的地位会扭转，很多key就须要从原来的地位复制到新的地位。
而在键复制时，因为Redis主线程无奈执行其余申请，会阻塞主线程，如果要复制的键特地多，Redis在执行哈希表扩容时，此时Redis Server对外是不可用的，这个是咱们不能承受的。
为了防止Redis Server在哈希表扩容时不可用，提出了渐进式 rehash 的办法。
相当于把一次要干的很多事件分成屡次要做的小事件。 把一次要复制的100万个key 转换为 10万次每次复制10个key，这样既不影响其余申请，也把哈希表扩容了。
渐进式rehash在代码层面是如何实现的呢？
有两个要害函数：dictRehash 和 _dictRehashStep。
/* * 执行N步增量rehashing。 * 如果仍有键从旧哈希表挪动到新哈希表，则返回 1，否则返回 0。 * * 请留神，从新散列步骤包含将一个桶(在应用链表时可能有不止一个键)从旧哈希表挪动到新哈希表， * 然而因为哈希表的一部分可能由空白组成，因而不能保障 这个函数甚至会从新散列一个桶， * 因为它总共最多拜访 N*10 个空桶，防止它所做的工作量将不受限制，并且该函数可能会阻塞很长时间。 * * @param *d * @param n */int dictRehash(dict *d, int n) { int empty_visits = n*10; // 最多拜访10倍的空桶 一个桶对应一个数组下标 // 如果哈希表没有进行rehashing 返回0 if (!dictIsRehashing(d)) return 0; // 循环 // n>0 并且 哈希表里已应用元素 > 0 时，进行 while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; // 防止ht[0]数组下标越界 assert(d->ht[0].size > (unsigned long)d->rehashidx); // 哈希表ht[0]对应数组下标的元素为null 也就是 桶对应的元素为null while(d->ht[0].table[d->rehashidx] == NULL) { // 全局rehashidx+1 这里的rehashidx 就是要操作的 ht[0].table的下标对应的桶 d->rehashidx++; if (--empty_visits == 0) return 1; } // 获取ht[0].table[rehashidx] 对应的桶 de = d->ht[0].table[d->rehashidx]; // 反转链表-尾插法 // 遍历链表 将这个桶中的所有键从旧的ht[0] 移到新的ht[1] while(de) { uint64_t h; nextde = de->next; // 下一个链表节点 // 获取key在新ht[1]的下标 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--; // 更新ht[0]已应用个数 d->ht[1].used++; // 更新ht[1]已应用个数 de = nextde; // 指向下一个链表节点 } // 把ht[0].table[d->rehashidx] 对应桶的链表置空 d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; // 更新rehashidx } // 判断ht[0]的数据是否全副迁徙实现 if (d->ht[0].used == 0) { // 开释ht[0]内存空间 zfree(d->ht[0].table); // 把ht[0]指向ht[1]，以便承受失常的申请 d->ht[0] = d->ht[1]; // 重置ht[1]的大小为0 _dictReset(&d->ht[1]); // 设置全局哈希表的rehashidx标识为-1，示意rehash完结 d->rehashidx = -1; //返回0，示意ht[0]中所有元素都迁徙完 return 0; } //返回1，示意ht[0]中依然有元素没有迁徙完 return 1;}/** * 此函数仅执行一个从新散列步骤，并且仅当没有平安迭代器绑定到咱们的散列表时。 * 当在从新散列两头有迭代器时，不能弄乱两个散列表，否则某些元素可能会失落或反复。 * * 此函数由字典中的常见查找或更新操作调用，以便哈希表在被动应用时主动从 H1 迁徙到 H2。 * * @param *d */static void _dictRehashStep(dict *d) { // rehash一个桶的数据 if (d->iterators == 0) dictRehash(d,1);}/* * 以 ms+"delta" 毫秒rehash。 * "delta" 的值大于0，少数状况下小于1。 * 确切的下限取决于 dictRehash(d,100) 的运行工夫。 * * @param *d * @param ms */int dictRehashMilliseconds(dict *d, int ms) { long long start = timeInMilliseconds(); // ms工夫戳 int rehashes = 0; while(dictRehash(d,100)) { // 一次rehash 100个桶 rehashes += 100; // 超过指定工夫，break if (timeInMilliseconds()-start > ms) break; } return rehashes;}dictAddRaw -> _dictRehashStep
dictGenericDelete -> _dictRehashStep
dictFind -> _dictRehashStep
dictGetRandomKey -> _dictRehashStep
dictGetSomeKeys -> _dictRehashStep
_dictRehashStep -> dictRehash
incrementallyRehash -> dictRehashMilliseconds -> dictRehash
(3.3) 渐进式hash时，增删改查操作哪个ht?
当局部bucket 执行 rehash，局部bucket还没有执行rehash，这时增删查申请操作是对ht[1]操作，还是ht[0] ?
在新增操作时，调用dictAdd，会调用dictAddRaw，有一行代码专门对rehash做了解决，会保留到ht[1]，ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
在更新操作时，调用dictReplace，也会调用dictAddRaw，原理同上
在删除操作时，调用dictDelete办法，会对ht[0]和ht[1]都做删除， for (table = 0; table <= 1; table++) 这行代码就是要对2个哈希表分表处理
查问操作，调用dictFind办法，也是会对两个ht都查问，for (table = 0; table <= 1; table++)，先查ht[0]，查到了返回，没有查到再查ht[1]
(3.4) rehash扩容后有多大-rehash的后果
在 Redis 中，rehash 对 哈希表空间的扩容是通过调用 dictExpand 函数来实现的。
dictExpand 函数的参数有两个，一个是要扩容的 哈希表，另一个是要扩到的容量
/** * 扩大或创立哈希表 * * @param *d 要扩容的哈希表 * @param size 扩容后的容量 */int dictExpand(dict *d, unsigned long size){ // 校验 // 如果曾经在扩容 或者 扩容后的大小<哈希表中已有的元素数 返回谬误 if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; dictht n; // 新哈希表 unsigned long realsize = _dictNextPower(size); // 获取扩容后的大小 (realsize >= size 并且 realsize是2的幂次方) // 扩容后的大小 = 以后大小，返回谬误 if (realsize == d->ht[0].size) return DICT_ERR; // 为新的哈希表分配内存 并 将所有指针初始化为NULL n.size = realsize; // 大小 n.sizemask = realsize-1; // n.table = zcalloc(realsize*sizeof(dictEntry*)); // 分配内存 n.used = 0; // 未应用 // 这是第一次初始化吗？ 如果是这样，那不是真正的从新哈希，咱们只是设置第一个哈希表，以便它能够承受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; // 设置 rehash index return DICT_OK;}/* 哈希表的容量是2的幂次方 */static unsigned long _dictNextPower(unsigned long size){ unsigned long i = DICT_HT_INITIAL_SIZE; // 哈希表初始大小默认是4 // 如果要扩容的大小曾经超过最大值，则返回最大值加1 if (size >= LONG_MAX) return LONG_MAX + 1LU; // 这里是计算2的幂次方 获取一个>=size 的最小2的幂次方 while(1) { // 如果扩容大小大于等于要扩容的值，就返回以后值 if (i >= size) return i; i *= 2; }}为什么哈希表的容量要是2的幂次方？
因为容量是2的幂次方，进行计算能够转换为位运算，位运算计算比拟快。
(4) Redis里的Hash函数
Hash 函数会影响 哈希表的查问效率及哈希抵触状况，那么，你能从 Redis 的源码中，找到 哈希表应用的是哪一种 Hash 函数吗？
在rehash时，dictRehash函数里 从老的ht[0]把数据迁徙到ht[1]的时候，须要计算key的hash，与sizemask计算获取数组下标，对应代码是 h = dictHashKey(d, de->key) & d->ht[1].sizemask;
dictHashKey(d, de->key) 调用了哈希函数，点进这个办法
调用 #define dictHashKey(d, key) (d)->type->hashFunction(key)，也就是应用的 hashFunction(key) 这个函数
想了想，Hash有多种实现，而且struct dict也定义了dictType *type
typedef struct dictType { uint64_t (*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;看到这儿时，找了一下援用dictType的中央，发现有很多，排除掉redis-cli.c sentinel.c 感觉 dict.c 和 server.c里的概率更大
看了一下server.c里的援用，有setDictType zsetDictType dbDictType 而且正文里写着 /* hash function */
看了dictSdsHash，对应 dictGenHashFunction
uint64_t dictGenHashFunction(const void *key, int len) { return siphash(key,len,dict_hash_function_seed);}发现应用的siphash.c文件里的siphash
这个办法不太容易看懂
uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k) {#ifndef UNALIGNED_LE_CPU uint64_t hash; uint8_t *out = (uint8_t*) &hash;#endif uint64_t v0 = 0x736f6d6570736575ULL; uint64_t v1 = 0x646f72616e646f6dULL; uint64_t v2 = 0x6c7967656e657261ULL; uint64_t v3 = 0x7465646279746573ULL; uint64_t k0 = U8TO64_LE(k); uint64_t k1 = U8TO64_LE(k + 8); uint64_t m; const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t)); const int left = inlen & 7; uint64_t b = ((uint64_t)inlen) << 56; v3 ^= k1; v2 ^= k0; v1 ^= k1; v0 ^= k0; for (; in != end; in += 8) { m = U8TO64_LE(in); v3 ^= m; SIPROUND; v0 ^= m; } switch (left) { case 7: b |= ((uint64_t)in[6]) << 48; /* fall-thru */ case 6: b |= ((uint64_t)in[5]) << 40; /* fall-thru */ case 5: b |= ((uint64_t)in[4]) << 32; /* fall-thru */ case 4: b |= ((uint64_t)in[3]) << 24; /* fall-thru */ case 3: b |= ((uint64_t)in[2]) << 16; /* fall-thru */ case 2: b |= ((uint64_t)in[1]) << 8; /* fall-thru */ case 1: b |= ((uint64_t)in[0]); break; case 0: break; } v3 ^= b; SIPROUND; v0 ^= b; v2 ^= 0xff; SIPROUND; SIPROUND; b = v0 ^ v1 ^ v2 ^ v3;#ifndef UNALIGNED_LE_CPU U64TO8_LE(out, b); return hash;#else return b;#endif}总结
1、Redis 中的 dict 数据结构，采纳「链式哈希」的形式存储，当哈希抵触重大时，会开拓一个新的哈希表，翻倍扩容，并采纳「渐进式 rehash」的形式迁徙数据
2、所谓「渐进式 rehash」是指，把很大块迁徙数据的开销，平摊到屡次小的操作中，目标是升高主线程的性能影响
3、Redis 中但凡须要 O(1) 工夫获取 k-v 数据的场景，都应用了 dict 这个数据结构，也就是说 dict 是 Redis 中重中之重的「底层数据结构」
4、dict 封装好了敌对的「增删改查」API，并在适当机会「主动扩容、缩容」，这给下层数据类型（Hash/Set/Sorted Set）、全局哈希表的实现提供了十分大的便当
5、例如，Redis 中每个 DB 存放数据的「全局哈希表、过期key」都用到了 dict：
6、「全局哈希表」在触发渐进式 rehash 的状况有 2 个：
- 增删改查哈希表时：每次迁徙 1 个哈希桶（文章提到的 dict.c 中的 _dictRehashStep 函数）
- 定时 rehash：如果 dict 始终没有操作，无奈渐进式迁徙数据，那主线程会默认每距离 100ms 执行一次迁徙操作。这里一次会以 100 个桶为根本单位迁徙数据，并限度如果一次操作耗时超时 1ms 就完结本次工作，待下次再次触发迁徙（文章没提到这个，详见 dict.c 的 dictRehashMilliseconds 函数）
（留神：定时 rehash 只会迁徙全局哈希表中的数据，不会定时迁徙 Hash/Set/Sorted Set 下的哈希表的数据，这些哈希表只会在操作数据时做实时的渐进式 rehash）
7、dict 在负载因子超过 1 时（used: bucket size >= 1），会触发 rehash。但如果 Redis 正在 RDB 或 AOF rewrite，为防止父过程大量写时复制，会临时敞开触发 rehash。但这里有个例外，如果负载因子超过了 5（哈希抵触已十分重大），依旧会强制做 rehash（重点）
8、dict 在 rehash 期间，查问旧哈希表找不到后果，还须要在新哈希表查问一次
参考资料
https://weikeqin.com/tags/redis/
[1] Redis源码分析与实战 - 03 如何实现一个性能优异的Hash表？
[2] Redis设计与实现 - 字典
Redis源码分析与实战 - 03 如何实现一个性能优异的Hash表？ https://time.geekbang.org/col...