面试题：Redis字典的渐进式rehash对内存管理的意义

基本概念：
- Redis的字典（dict）使用哈希表作为底层数据结构。当哈希表的负载因子过高（如超过1.0）或过低（如小于0.1）时，需要对哈希表进行扩展或收缩，这个过程涉及重新计算键的哈希值并将键值对重新分布到新的哈希表中，即rehash。
- 渐进式rehash是指，在扩展或收缩哈希表时，不是一次性完成所有键值对的迁移，而是分多次逐步完成。
实现方式：
- Redis的字典结构中维护两个哈希表，ht[0]和ht[1]。
- 在进行rehash时，先分配好ht[1]，大小通常是ht[0]的两倍（扩展时）或一半（收缩时）。
- 然后，在每次对字典进行增、删、改、查操作时，除了执行相应的操作外，还会顺带将ht[0]中的少量键值对迁移到ht[1]中。具体迁移数量由dict.c中的dictRehashMilliseconds控制，一般每次迁移10个键值对。
- 当ht[0]中的所有键值对都迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并为ht[1]重新分配一个空的哈希表，以备下一次rehash使用。

避免一次性内存分配：
- 如果采用传统的一次性rehash，在扩展哈希表时，需要一次性分配出比当前哈希表大得多的内存空间（通常是两倍），这可能会导致内存使用峰值过高。在内存紧张的系统中，这种一次性的大内存分配可能会导致内存不足的错误。
- 渐进式rehash每次只迁移少量键值对，逐步完成哈希表的扩展或收缩，避免了一次性分配大量内存，从而有效降低了内存使用峰值。
减少内存碎片：
- 一次性分配大内存可能会在堆内存中形成较大的空洞，产生内存碎片。渐进式rehash每次分配相对较小的内存，且随着迁移的逐步完成，内存使用更加紧凑，减少了内存碎片的产生。

内存分配：
- 在开始rehash时，为ht[1]分配内存。如果是扩展操作，ht[1]的大小是ht[0]的两倍；如果是收缩操作，ht[1]的大小是ht[0]的一半。
- 例如，假设当前ht[0]有1000个键值对，负载因子超过1.0需要扩展。此时为ht[1]分配能容纳2000个键值对的内存空间。
内存回收：
- 当ht[0]中的所有键值对都迁移到ht[1]后，释放ht[0]占用的内存空间。
- 例如，完成上述1000个键值对从ht[0]到ht[1]的迁移后，释放ht[0]的内存，此时ht[1]成为新的ht[0]，而ht[1]重新被分配为空表，等待下一次rehash。

假设一个Redis字典当前存储了1000个键值对，且负载因子达到1.5，触发了扩展操作。

开始rehash：
- 为ht[1]分配能容纳2000个键值对的内存空间。
操作过程：
- 当有客户端对该字典进行操作（如SET key1 value1）时，在执行SET操作的同时，顺带将ht[0]中的10个键值对迁移到ht[1]。
- 经过多次操作后，ht[0]中的1000个键值对逐步迁移到ht[1]。
完成rehash：
- 释放ht[0]的内存空间，将ht[1]设置为ht[0]，并重新为ht[1]分配一个空的哈希表。这样，既完成了哈希表的扩展，又避免了内存使用峰值过高的问题。

知识考点