面试题

面试题
面试官心理分析
面试题剖析
- 1. 为字典的备用哈希表分配空间。
- 2. 渐进式 rehash

有了解过 Redis rehash 的过程吗？

面试官心理分析

这个知识点算 redis 中比较低频的面试点，但是当你在介绍 HashMap 的 rehash 或者 ConcurrentHashMap 的 rehash 过程中，可以主动和面试官提及你不仅了解这些，同时还了解 Redis 中的 rehash 过程。

Redis 是以速度快，性能好著称的，我们知道 Redis 一开始的容量是有限的，当容量不足时，需要扩容，那扩容的方式是什么？一次性全部将数据转移吗？那当数据量上千万上亿，这必定会阻塞 Redis 对命令的执行。因此就非常有必要了解一下 Redis 中的 rehash 过程。

面试题剖析

众所周知，Redis 主要用于存储键值对(Key-Value Pair)，而键值对的存储方式是由字典实现，而 Redis 中字典的底层又是通过哈希表来实现的。通过哈希表中的节点保存字典中的键值对。类似 Java 中的 HashMap，将 Key 通过哈希函数映射到哈希表节点位置。

Redis 中字典的数据结构如下：

// 字典对应的数据结构，有关hash表的结构可以参考redis源码，再次就不进行描述
typedef struct dict {
    dictType *type;  // 字典类型
    void *privdata;  // 私有数据
    dictht ht[2];    // 2个哈希表，这也是进行rehash的重要数据结构，从这也看出字典的底层通过哈希表进行实现。
    long rehashidx;   // rehash过程的重要标志，值为-1表示rehash未进行
    int iterators;   //  当前正在迭代的迭代器数
} dict;

在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面，具体过程如下：

1. 为字典的备用哈希表分配空间。

如果执行的是扩展操作，那么备用哈希表的大小为第一个大于等于需要扩容的哈希表的键值对数量2 的 2”(2 的 n 次方幂);【`52=10,`所以备用哈希表的容量为第一个大于 10 的 2”，即 16】

如果执行的是收缩操作,那么备用哈希表的大小为第一个大于等于需要扩容的哈希表的键值对数量（ht[0] .used）的 2”。

2. 渐进式 rehash

rehash 过程在数据量非常大（几千万、亿）的情况下并不是一次性地完成的，而是渐进式地完成的。渐进式 rehash的好处在于避免对服务器造成影响。

渐进式 rehash 的本质：

借助 rehashidx，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。
在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将原哈希表在 rehashidx 索引上的所有键值对 rehash 到备用哈希表，当 rehash 工作完成之后，程序将 rehashidx 属性的值加 1。