Redis源码学习：高性能Hash表的设计与实现
哈希表（Hash）是Redis数据库的数据类型之一，理解哈希表的实现对于掌握Redis非常重要。这篇文章，从哈希冲突和哈希扩展这两个角度，来一步步讲解Redis哈希表的工作原理。
什么是哈希表？
哈希表是一种通过哈希函数将键映射到值的数据结构。简单来说，就是通过一个计算公式（哈希函数）把一个键（比如一个名字）转换成一个数组的索引，数组中的每一个元素就是一个哈希桶（也叫bucket），然后在这个索引位置存储对应的值（比如电话号码）。这样我们就能以O(1)的时间复杂度通过键快速找到对应的值。
哈希冲突
哈希冲突是什么？
当键的数量超过数组的大小，必然会出现两个不同的键通过哈希函数映射到数组的同一个位置时，就发生了哈希冲突。举个例子，如果我们把“Tom”和“Jerry”这两个名字通过同一个公式转换成同一个数组位置，这时候就会有冲突。
如何解决哈希冲突？
Redis使用链式哈希来解决这个问题。链式哈希的意思是，每个bucket不再只存一个值，而是变成一个链表的头指针。如果有冲突，新来的键值对就插到链表头中。这样，同一个位置上可以存多个键值对。
Redis中的链式哈希
在Redis使用链式哈希解决哈希冲突，每个bucket指向一个链表，源码（位于dict.h文件）如下：
// 哈希表的定义
typedef struct dictht {
// 哈希项数组，保存指向哈希项的指针
dictEntry **table;
// 哈希表的大小
unsigned long size;
// 哈希表小的掩码，总是等于 size -1
unsigned long sizemask;
// 哈希项的数量，因为有哈希冲突的存在，used可能会比size大
unsigned long used;
} dictht;
// 哈希项的定义
typedef struct dictEntry {
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值
struct dictEntry *next; // 指向下一个条目的指针（用于链式哈希）
} dictEntry;
每个dictEntry结构包含一个键key，一个值v，以及一个指向下一个条目的指针next。
联合体
v是一个四选一的类型，包含了指向实际值的指针val，还包含了无符号的 64 位整数、有符号的 64 位整数，以及 double 类的值。这是一种节省内存的设计。当值为整数或双精度浮点数时，由于其本身就是 64 位，就可以不用指针指向了，而是可以直接存在键值对的结构体中，这样就避免了再用一个指针，从而节省了内存空间。
插入键值对时，如果发生冲突，新条目将插入到链表的头部。采用头插法的好处就是性能高，不需要遍历链表了。
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) {
// 进行rehash检查
if (dictIsRehashing(d)) _dictRehashStep(d);
unsigned long idx = dictHashKey(d, key) & ht->sizemask;
dictEntry *entry = ht->table[idx];
while (entry) {
if (dictCompareKeys(d, key, entry->key)) {
if (existing) *existing = entry;
return NULL;
}
entry = entry->next;
}
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[idx];
ht->table[idx] = entry;
ht->used++;
dictSetKey(d, entry, key);
return entry;
}
哈希扩展
为什么需要哈希扩展？
随着哈希表中存储的键值对越来越多，哈希冲突变得越来越频繁，哈希表的效率会降低。为了保持高效的性能，需要在恰当的扩展哈希表，也就是增加哈希表的大小。这个过程称为哈希扩展或rehash。
渐进式rehash
Redis采用渐进式rehash策略，以避免扩展过程中阻塞数据库的正常操作。也就是说，Redis不会一次性把所有数据搬到新的哈希表中，而是分多次慢慢进行，每次只处理一个bucket数据。
rehash的实现
Redis在dict结构中，定义了两个哈希表，用于 rehash 时交替保存数据。
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2]; //两个Hash表，交替使用，用于rehash操作
long rehashidx; //Hash表是否在进行rehash的标识，-1表示没有进行rehash
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
每次rehash只处理一个bucket的链表，这样就不会长时间阻塞数据库的其他操作。调用dictRehash函数，传入的参数n始终为1，这样一来，每次迁移完一个bucket，哈希表就会执行正常的增删查请求操作，这就是在代码层面实现渐进式 rehash 的方法。
以下是相关的源码片段：
void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d, 1);
}
int dictRehash(dict *d, int n) {
if (!dictIsRehashing(d)) return 0;
while (n--) {
dictEntry *de, *nextde;
/* 如果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]);
/* 值改完1，表示rehash结束 */
d->rehashidx = -1;
/* 返回0，表示ht[0]中所有元素都迁移完成 */
return 0;
}
/* 当前正在迁移的桶*/
while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
/* 哈希表中的哈希项 */
de = d->ht[0].table[d->rehashidx];
while (de) {
unsigned long h;
/* 获得下一个哈希项 */
nextde = de->next;
/* 当前哈希项在ht[1]的位置 */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
/* 添加到ht[1]中 */
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
/* 减少ht[0]中的哈希项 */
d->ht[0].used--;
/* 增加ht[1]中的哈希项*/
d->ht[1].used++;
/* 指向下一个哈希项 */
de = nextde;
}
/* 如果当前bucket中已经没有哈希项了，将该bucket置为NULL */
d->ht[0].table[d->rehashidx] = NULL;
/* 将rehash加1，下一次将迁移下一个bucket中的元素 */
d->rehashidx++;
}
/* 返回1，表示ht[0]中仍然有元素没有迁移 */
return 1;
}
什么时候触发rehash
Redis中在每次的增删查中都会判断是否需要扩容，在函数_dictExpandIfNeeded中检查负载因子（LoadFactor=used/size），只要满足以下任意一个条件就会触发哈希表扩容：
- 哈希表的LoadFactor>=1，并且服务器没有执行SAVE或REWRITEAOF等子进程
- 哈希表的LoadFactor>5
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
if (dictIsRehashing(d)) return DICT_OK;
/* 如果哈希表为空，则进行初始化为4. */
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
if (!dictTypeExpandAllowed(d))
return DICT_OK;
if ((dict_can_resize == DICT_RESIZE_ENABLE &&
d->ht[0].used >= d->ht[0].size) ||
(dict_can_resize != DICT_RESIZE_FORBID &&
d->ht[0].used / d->ht[0].size > dict_force_resize_ratio))
{
/* 扩容大小为used + 1, 底层会对扩容的大小做判断，实际上找的是第一个大于等于used+1的2倍 */
return dictExpand(d, d->ht[0].used + 1);
}
return DICT_OK;
}
rehash扩容大小
通过函数_dictExpand对哈希表进行扩容，每次扩容大小总是2的幂，看下内部的 _dictNextPower函数源码：
static unsigned long _dictNextPower(unsigned long size)
{
/* 哈希表的初始大小 */
unsigned long i = DICT_HT_INITIAL_SIZE;
/* 如果要扩容的大小已经超过了最大值，则返回最大值加1*/
if (size >= LONG_MAX) return LONG_MAX + 1LU;
/* 要扩容的大小没有超过最大值 */
while(1) {
/* 从DICT_HT_INITIAL_SIZE（通常是4）开始，不断将i乘以2，直到 i 大于等于size */
if (i >= size)
return i;
i *= 2;
}
}
总结
通过链式哈希，Redis有效地解决了哈希冲突的问题；通过渐进式rehash，Redis确保了哈希表扩展时的高效性和稳定性。这些机制让Redis哈希表在处理大量数据时仍然保持高效。
参考资料
转载自:https://juejin.cn/post/7382394009199460371