渐进式哈希

渐进式哈希

在 redis 扩展或者收缩哈希表需要将 ht[0]中所有键值对 rehash 到 ht[01]中去，不过这个 rehash 动作并非是一次性集中性的完成，而是分多次、渐进式的完成

因为 redis 作为数据库保存的键值对较多，如果需要一次性的全部 rehash 将会对 redis 提供的服务造成影响，甚至导致停止服务。

因而 redis 使用渐进式 rehash，慢慢的将 ht[0]中的键值对 rehash 到 ht[1]中去。

什么情况需要渐进式哈希？
当数据量旁大，一次性的 rehash 将会对服务器造成压力，此时便需要渐进式哈希进行扩容等操作

rehash 过程中，对于所有的插入都直接插入到 ht[1]中，而查找则是在两个 ht 中同时查找

原理

我们可以看 rehash 的详细步骤：

1. 为 ht[1]分配空间，让字典同时拥有 ht[0]和 ht[1]两个哈希表
2. 在字典中维持一个索引计数器变量 rehashidx，并将他的值设置为 0，表示 rehash 开始。
   通过 rehashidx 的偏移进行细粒度渐进式的 rehash
3. 在 rehash 期间，每次对字典进行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
   也就是说每一次操作的同时伴随一次 rehash 操作，rehash 当前 rehashidx 下的键值对，然后 rehashidx+1.而增删改查操作中，添加元素操作的时 ht[1]，查找更新操作从两个 hash 表中查找元素.这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。
4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1， 表示 rehash 操作已完成

渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

下图详细展示了 rehash 的过程

当全部节点搬移完成之后需要做什么呢？

由于只有两个 hash 表容器（也只要两个 hash 表容器就够了），如果 ht[1]需要 rehash 时再搬移到 ht[0]吗？这样是没有问题的，但是显得有点混乱，因为搞不清楚哪个容器是要搬移的。巧妙的做法是搬移完成之后，让 ht[0]指向新的 hash 容器。这样 ht[0]永远是那个要被搬移的对象，dt[1]是搬移过程中的中转。

代码实现

int dictRehash(dict *d, int n) {
	if (!dictIsRehashing(d)) return 0;
	while (n--) {
		dictEntry *de, *nextde;
		if (d->ht[0].used == 0) {   // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
			zfree(d->ht[0].table);
			d->ht[0] = d->ht[1];
			_dictReset(&d->ht[1]);
			d->rehashidx = -1;
			return 0;
		}

		// Note that rehashidx can't overflow as we are sure there are more
		// elements because ht[0].used != 0
		// 确保 rehashidx 没有越界
		assert(d->ht[0].size > (unsigned)d->rehashidx);

		while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;    // 略过数组中为空的索引，找到下一个非空索引

		de = d->ht[0].table[d->rehashidx];
		while (de) {
			unsigned int h;
			nextde = de->next;
			// 计算新哈希表的哈希值，以及节点插入的索引位置
			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;
		d->rehashidx++;
	}
	return 1;
}