好的，直接开始！
各位观众，欢迎来到“Redis Hash Table的秘密花园”讲座！今天咱们就来扒一扒Redis hashtable的内裤…啊不，是内部实现，重点聊聊哈希冲突和渐进式Rehash这两个有趣的话题。
一、字典的本质：Key-Value存储的基石
Redis字典，也就是dict类型，是Redis最核心的数据结构之一。它干的事情很简单：存储键值对（key-value pairs）。但它背后的实现可不简单，因为它需要足够快、足够稳，才能撑起Redis高性能的半边天。
Redis字典的底层实现，核心就是一个hashtable（哈希表）。 想象一下，你有一个巨大的数组，每个数组元素可以存放一个键值对。 但问题来了：你如何快速地找到某个key对应的value呢？ 难道要一个一个遍历数组？ 那效率也太低了！
这时候，哈希函数就登场了！ 它的作用就是：将key转换成一个整数（哈希值），这个哈希值就对应着数组的下标。这样，我们就可以直接通过哈希值找到对应的数组元素，也就是找到了对应的键值对。
用代码来表示一下，大概是这个样子：
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 用于解决哈希冲突
} dictEntry;
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);
uint64_t (*seedFunction)(void);
} dictType;
/* 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; // 哈希表大小掩码，用于计算索引：index = hash & sizemask
unsigned long used; // 已使用的节点数量
} dictht;
typedef struct dict {
dictType *type; // 字典类型，用于处理不同类型的key和value
void *privdata; // 私有数据，传递给类型特定函数
dictht ht[2]; // 两个哈希表，用于渐进式rehash
long rehashidx; /* rehashing not in progress if rehashidx == -1 */ // rehash 索引，-1表示rehash未进行
int iterators; /* number of iterators currently running */ // 迭代器数量
} dict;解释一下：
dictEntry：这是哈希表中的一个节点，存储一个键值对。注意next指针，它是解决哈希冲突的关键。dictType：这是一个函数指针结构，定义了如何操作不同类型的key和value。 Redis是一个泛型数据结构，它可以存储各种类型的key和value。dictht：这就是真正的哈希表结构。它包含一个table数组，数组的每个元素都是一个dictEntry指针，指向一个键值对节点。size是哈希表的大小，used是已使用的节点数量。dict：这是字典结构，包含两个哈希表ht[0]和ht[1]。通常情况下，我们只使用ht[0]。ht[1]只在rehash的时候使用。rehashidx记录了rehash的进度。
二、哈希冲突：甜蜜的烦恼
理想情况下，每个key经过哈希函数计算后，都应该得到一个唯一的哈希值，对应数组中唯一的位置。但现实往往是残酷的，不同的key可能得到相同的哈希值，这就是所谓的哈希冲突。
哈希冲突就像：你和你的邻居都想住进同一个房间，怎么办？
Redis采用的是链地址法来解决哈希冲突。 简单来说，就是把哈希到同一个位置的所有键值对，用链表串起来。
也就是 dictEntry 结构体中的 next 指针起作用了。 当发生哈希冲突时，新的键值对会插入到链表的头部。
用代码来演示一下插入过程：
/* Add an element to the table creating a new hash entry.
*
* It is up to the caller to take care of increasing the table size
* if needed. */
int dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or return -1 if
* the element already exists. */
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return DICT_ERR;
/* Allocate the memory and store the new entry.
* Insert the element in top, with the assumption that in a database
* a given element is more likely to be accessed more often. */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index]; // 新节点插入到链表头部
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. */
dictSetKey(d, entry, key);
*existing = entry;
return DICT_OK;
}这段代码的关键在于 entry->next = ht->table[index]; 和 ht->table[index] = entry; 这两行，它们实现了将新节点插入到链表头部的操作。
链地址法简单粗暴，但也有缺点：如果哈希冲突太严重，导致某个链表过长，那么查找效率就会下降，从 O(1) 退化到 O(n)。
三、渐进式Rehash：优雅的扩容与缩容
为了避免哈希冲突过多，影响性能，Redis会定期对哈希表进行rehash操作。 Rehash的过程就是：
- 扩容/缩容： 创建一个新的哈希表
ht[1]，大小是当前哈希表ht[0]的两倍（扩容）或一半（缩容）。 - 数据迁移： 将
ht[0]中的所有键值对，重新计算哈希值，迁移到ht[1]中。 - 替换： 将
ht[1]设置为ht[0]，并释放原来的ht[0]。
但是，如果哈希表中存储了大量的键值对，一次性地将所有数据迁移到新的哈希表中，可能会导致Redis服务器阻塞，影响性能。
为了解决这个问题，Redis采用了渐进式rehash。 渐进式rehash的核心思想是：化整为零，分批迁移。
具体来说，渐进式rehash的过程如下：
- 设置rehashidx： 设置
dict结构的rehashidx为0，表示rehash开始。 - 逐步迁移： 在每次对字典进行增删改查操作时，除了执行正常的操作外，还会顺带地将
ht[0]中rehashidx位置上的所有键值对迁移到ht[1]。 - rehashidx递增： 每迁移完一个位置上的所有键值对，就将
rehashidx加1。 - 完成rehash： 当
ht[0]中的所有键值对都迁移到ht[1]后，将rehashidx设置为-1，表示rehash完成。
在rehash期间，Redis会同时使用ht[0]和ht[1]两个哈希表。 新增的键值对，会直接添加到ht[1]中，保证ht[0]的大小只减不增。
查找、修改、删除操作，会先在ht[0]中进行，如果找不到，再去ht[1]中查找。
用代码来演示一下渐进式rehash的过程：
/* 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 the main hash table can not be modified otherwise
* some iterator could be invalidated. */
int _dictRehashStep(dict *d) {
if (d->iterators > 0) return 0; // 如果有迭代器正在运行，则不进行rehash
if (!dictIsRehashing(d)) return 0; // 如果rehash未进行，则不进行rehash
/* 10 steps at a time... that is fast enough while still
* buying us still some time to return to the caller. */
for (int j = 0; j < 100; j++) { // 每次最多迁移100个元素
dictEntry *de, *nextde;
/* Check if we already rehashed the entire table... */
if (d->ht[0].used == 0) { // ht[0]为空，表示rehash完成
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* Make sure we are within the range of a valid bucket. */
assert(d->rehashidx < (long)d->ht[0].size);
while (d->ht[0].table[d->rehashidx] == NULL) { // 找到下一个非空bucket
d->rehashidx++;
if (d->rehashidx >= (long)d->ht[0].size) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
}
de = d->ht[0].table[d->rehashidx]; // 获取当前bucket的链表头节点
/* 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) & d->ht[1].sizemask; // 计算在新哈希表中的索引
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; // 清空旧哈希表中的bucket
d->rehashidx++;
}
return 1;
}这段代码的关键在于：
dictIsRehashing(d)：判断是否正在进行rehash。_dictRehashStep(d)：执行一次rehash的步骤，每次最多迁移100个元素。d->rehashidx：记录rehash的进度。
通过渐进式rehash，Redis可以将rehash的代价分摊到每一次操作中，避免了长时间的阻塞，保证了服务器的性能。
四、Rehash的触发条件
那么，Redis在什么情况下会触发rehash呢？
Redis的rehash触发条件有两个：
-
负载因子： 负载因子 = 哈希表中已使用的节点数量 / 哈希表的大小。
- 当哈希表的负载因子大于等于1，并且服务器没有执行BGSAVE或BGREWRITEAOF命令时，会进行扩容。
- 当哈希表的负载因子大于等于5时，无论服务器是否执行BGSAVE或BGREWRITEAOF命令，都会强制进行扩容。
- 当哈希表的负载因子小于0.1时，会进行缩容。
-
BGSAVE或BGREWRITEAOF： 在执行BGSAVE或BGREWRITEAOF命令时，为了避免写入时复制（copy-on-write）导致内存浪费，Redis会尽量避免进行rehash。 如果需要rehash，会将负载因子调高到5。
用表格来总结一下：
| 条件 | 操作 |
|---|---|
| 负载因子 >= 1 且 没有执行BGSAVE/BGREWRITEAOF | 扩容 |
| 负载因子 >= 5 | 强制扩容 |
| 负载因子 < 0.1 | 缩容 |
五、总结
Redis hashtable的实现，巧妙地利用了哈希函数、链地址法和渐进式rehash等技术，实现了高效的键值对存储。
- 哈希函数： 将key转换成数组下标，实现快速查找。
- 链地址法： 解决哈希冲突，保证所有键值对都能存储。
- 渐进式rehash： 避免长时间阻塞，保证服务器性能。
掌握了这些知识，你就可以更好地理解Redis的内部实现，更好地使用Redis，甚至可以自己动手实现一个简单的哈希表！
好了，今天的讲座就到这里。 感谢各位的观看，希望大家有所收获！下次再见！