假设有一个 1G 大的 HashMap，此时用户请求过来刚好触发它的扩容，会怎样？让你改造下 HashMap 的实现该怎样优化？

回答重点

如果刚好触发扩容，那么当前用户请求会被阻塞，因为 HashMap 的底层是基于数组+链表（红黑树）来实现的，一旦它发生扩容，就需要新增一个比之前大 2 倍的数组，然后将元素搬运到新的数组上。

而 1G 的 HashMap 够大，所以扩容需要一定的时间，而扩容使用的又是当前的线程，所以用户此时会被阻塞，等待扩容完毕。

如何改造现有 HashMap 结构而优化处理这种场景？

此时可以借鉴 Redis 的 Hash 结构，因为 Redis 处理命令恰好是单线程的，它的 Hash 表如果很大，触发扩容的时候是不是也会导致阻塞？

所以它是怎么优化的？答案就是：渐进式rehash

我们都知道 HashMap 默认的扩容过程是一次性重哈希，即每次扩容都会创建一个更大的数组，并将所有元素重新哈希并放入新数组。

而渐进式 rehash 就是把扩容过程分批完成，通过分批扩容来减少单次扩容的开销。

简单来说不要一次性扩容完毕，而是分批搬运数据。

在分段扩容过程中，HashMap 需要维护两个数组：

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

实现方式：

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

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

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

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

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

这类题目就是借助一个场景，看起来问的是 hashmap ，实际上考察对 Redis 的渐进式 Hash 是否有深入的理解，考验面试者是不是仅就死记硬背，无法应用到真实的场景。

Redis Hash 底层实现和渐进式扩容

Redis 的 hash 是什么？

多线程改造

除了往 Redis 的渐进式 Hash 考虑，还可以往 ConcurrentHashMap 多线程方向改造，它的设计也是渐进式扩容，只不过融入了多线程的并发扩容，即可以多个线程同时参与扩容。

ConcurrentHashMap的扩容机制介绍：

1）ConcurrentHashMap 在扩容过程中，会创建一个新数组（nextTable），容量是原数组的两倍。但它不会一次性迁移整个旧表，而是将扩容任务分成多个小段，每次迁移一部分桶（bucket）。通过这种方式，将扩容的负担分散在多个线程、多个操作中。

2）多个线程可以同时参与扩容操作。每个线程负责一段桶的迁移，迁移完成后更新迁移进度，其他线程可以继续处理剩余未迁移的部分。

3）ConcurrentHashMap 通过使用一个 transferIndex 变量来记录当前迁移的进度。transferIndex 从旧表的高位索引开始，逐步向低位递减。每个线程在扩容时会尝试抢占 transferIndex 中的一段桶范围，执行数据迁移并更新 transferIndex。

4）在扩容过程中，如果某个桶中的数据已迁移至新表中，旧表中该桶的引用会被替换为 ForwardingNode。ForwardingNode 节点会指向 nextTable，表示该位置的数据已经迁移到新表中。

5）当所有桶都被迁移至新表时，ConcurrentHashMap 会将 nextTable 替换为 table，并将 nextTable 置为 null，标识扩容完成。