如果让你改造下 HashMap 的扩容实现，你会怎样优化？

假设有一个 1G 大的 HashMap，此时用户请求过来刚好触发它的扩容.那么当前用户请求会被阻塞，因为 HashMap的底层是基于数组+链表(红黑树)来实现的，一旦它发生扩容，就需要新增一个比之前大2倍的数组，然后将元素copy到新的数组上
那么如何优化呢？
简要回答

此时可以借鉴 Redis 的 Hash 结构，因为 Redis 处理命令恰好是单线程的，它的 Hash 表如果很大，触发扩容的时候是不是也会导致阻塞?
我们都知道 HashMap 默认的扩容过程是一次性重哈希，即每次扩容都会创建一个更大的数组，并将所有元素重新哈希并放入新数组。
此时我们可以借鉴redis的渐进式rehash，就是把扩容过程分批完成，通过分批扩容来减少单次扩容的开销。
简单来说不要一次性扩容完毕，而是分批搬运数据。
这种题目其实是借用HashMap在问redis的渐进式hash，是否对redis有深入的理解
扩展知识

Redis的rehash

顺道一起来看看Redis的渐进式hash是如何实现的
Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht_table[2]）。

1. struct dict {
2.    //...
3.     dictEntry **ht_table[2]; //两个dictEntry，一个开始为空，rehash迁移时使用
4.     //...
5.     long rehashidx; /* rehashing not in progress if rehashidx == -1 */
6. };

复制代码

在正常服务请求阶段，插入的数据，都会写入到哈希表 1，此时的哈希表 2  并没有被分配空间。随着数据逐步增多（根据负载因子判断），触发了 rehash 操作，这个过程分为如下三步：

如果哈希表 1的数据量非常大，那么在迁移至哈希表 2的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。因此redis采用了渐进式rehash
渐进式 rehash 步骤如下：

• 先给哈希表 2分配空间；
  
• 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将哈希表 1中索引位置上的所有 key-value 迁移到哈希表 2上；
  
• 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把哈希表 1的所有 key-value 迁移到哈希表 2，从而完成 rehash 操作。
  

这样就把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。
在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。比如，在渐进式 rehash 进行期间，查找一个 key 的值的话，先会在哈希表 1里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。新增一个 key-value 时，会被保存到哈希表 2里面，而哈希表 1则不再进行任何添加操作，这样保证了哈希表 1的 key-value 数量只会减少，随着 rehash 操作的完成，最终哈希表 1就会变成空表。
哈希表的查找过程：

1. dictEntry *dictFind(dict *d, const void *key)
2. {
3.     dictEntry *he;
4.     uint64_t h, idx, table;
6.     if (dictSize(d) == 0) return NULL; /* dict is empty */
7.     if (dictIsRehashing(d)) _dictRehashStep(d);//检查是否正在渐进式 rehash，如果是，那就rehash一步
8.     h = dictHashKey(d, key);//计算key的hash值
9.         //哈希表元素的删除、查找、更新等操作都会在两个哈希表进行
10.     for (table = 0; table <= 1; table++) {
11.         idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
12.         he = d->ht_table[table][idx];
13.         while(he) {
14.             void *he_key = dictGetKey(he);
15.             if (key == he_key || dictCompareKeys(d, key, he_key))
16.                 return he;
17.             he = dictGetNext(he);
18.         }
19.         if (!dictIsRehashing(d)) return NULL;
20.     }
21.     return NULL;
22. }

复制代码

关键在于哈希表插入时会去检查是都正在Rehash，如果不是，那就往0号hash表中插入；如果是，那就直接往1号hash表中插入，因为如果正在Rehash还往0号hash表中插入，那么最终还是要rehash到1号hash表的

1. int htidx = dictIsRehashing(d) ? 1 : 0;

复制代码

rehash的触发条件是什么？
负载因子 = 哈希表已保存节点数量/哈希表大小
触发 rehash 操作的条件，主要有两个：

• 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
  
• 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作
  

那如何优化HashMap

借用Redis渐进式hash的思想，在分批扩容过程中，我们可以给 HashMap 维护两个数组:

• 旧数组：扩容之前的数组，包含了部分尚未迁移的数据。
  
• 新数组：扩容过程中创建的新数组，用于存储迁移后的数据。
  

实现方式:

• 扩容分批化：将重新哈希的过程分成多个步骤，而不是一次性完成。在扩容时，先创建新的数组，但只重新哈希一部分旧数据。
  
• 增量式迁移：每次插入、修改或查询时，检查当前是否有未完成的扩容任务。如果有，则迁移少量旧数据到新数组中，直到完成所有数据的迁移。
  
• 迁移状态管理：通过状态字段记录扩容的进度，确保每次操作时扩容任务逐步推进。
  

有两个数组，那么 get操作时候如何查询呢?

• 优先查找新数组：当用户发起 get 请求时，优先从新数组中查找。因为已经迁移的数据会直接放入新数组。
  
• 回退查找旧数组：如果在新数组中没有找到对应的键，说明该键还未迁移至新数组，需要回退到旧数组查找
  

其实这就是空间换时间的概念，也是一种权衡。

• 优点：节省的用户扩容阻塞时间，把扩容时间的消耗平均分散都后面的处理中，基本上做到了无感知
  
• 缺点：空间开销比较大，因为在扩容的时候，同时存在两个大数组。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！