HashMap和Redis的rehash过程

有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步,认准https://blog.zysicyj.top

全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。 https://store.amazingmemo.com/chapterDetail/1685324709017001`

HashMap 和 Redis 的 Rehash 过程

HashMap 和 Redis 都是常用的键值存储结构，它们在处理哈希冲突和动态扩容时会使用到 rehash（重新哈希）的过程。下面分别介绍它们的 rehash 过程。

HashMap 的 Rehash 过程

HashMap 是 Java 中的一个基于哈希表的 Map 接口实现，它存储键值对，并允许使用 null 键和 null 值。HashMap 在内部使用一个数组来存储数据，当数据量增加导致负载因子超过设定的阈值时，HashMap 会进行扩容，这个过程就涉及到 rehash。

步骤

1. 扩容：创建一个新的数组，大小通常是原数组的两倍。

2. 遍历旧数组：遍历原数组中的每一个元素（键值对）。

3. 计算新的索引：对每个元素重新计算哈希值，并根据新数组的大小确定它们在新数组中的位置。

4. 数据迁移：将旧数组中的元素放到新数组的对应位置上。

特点

• 逐个迁移：HashMap 的 rehash 是一次性完成的，即在扩容时会一次性将所有元素迁移到新的数组中。

• 影响性能：由于一次性迁移，如果 HashMap 中存储了大量的数据，rehash 过程可能会导致短暂的性能下降。

Redis 的 Rehash 过程

Redis 是一个开源的使用 ANSI C 编写的高性能键值对存储系统。它的数据结构是一个字典，内部使用哈希表实现。与 HashMap 类似，当哈希表中的元素太多时，Redis 也需要进行 rehash 来扩容。

步骤

1. 分配新哈希表：创建一个新的哈希表，大小是原哈希表的两倍。

2. 渐进式迁移：在执行常规操作（如添加、删除、查找键值对）的同时，逐步将旧哈希表中的键值对迁移到新哈希表中。

3. 完成迁移：当所有键值对都迁移到新的哈希表后，释放旧哈希表的空间。

特点

• 渐进式：Redis 的 rehash 是渐进式的，它不会一次性迁移所有数据，而是分多次迁移，这样可以避免长时间的阻塞。

• 双哈希表：在 rehash 过程中，Redis 同时维护旧的和新的哈希表，直到迁移完成。

总结

HashMap 和 Redis 的 rehash 都是为了解决哈希表的扩容问题，但它们的实现方式有所不同。HashMap 采用一次性迁移的方式，可能会导致性能短暂下降，而 Redis 使用渐进式迁移，可以避免长时间的服务中断。这两种方式各有优劣，选择哪种方式取决于具体的应用场景和性能要求。