如果让你改造下 HashMap 的扩容实现，你会怎样优化？
<p>假设有一个 1G 大的 HashMap，此时用户请求过来刚好触发它的扩容.那么当前用户请求会被阻塞，因为 HashMap的底层是基于数组+链表(红黑树)来实现的，一旦它发生扩容，就需要新增一个比之前大2倍的数组，然后将元素copy到新的数组上</p><p>那么如何优化呢？</p>
<h2 id="简要回答">简要回答</h2>
<p>此时可以借鉴 Redis 的 Hash 结构，因为 Redis 处理命令恰好是单线程的，它的 Hash 表如果很大，触发扩容的时候是不是也会导致阻塞?</p>
<p>我们都知道 HashMap 默认的扩容过程是一次性重哈希，即每次扩容都会创建一个更大的数组，并将所有元素重新哈希并放入新数组。</p>
<p>此时我们可以借鉴redis的渐进式rehash，就是把扩容过程分批完成，通过分批扩容来减少单次扩容的开销。</p>
<p>简单来说不要一次性扩容完毕，而是分批搬运数据。</p>
<p>这种题目其实是借用HashMap在问redis的渐进式hash，是否对redis有深入的理解</p>
<h2 id="扩展知识">扩展知识</h2>
<h3 id="redis的rehash">Redis的rehash</h3>
<p>顺道一起来看看Redis的渐进式hash是如何实现的</p>
<p>Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht_table）。</p>
<pre><code class="language-c">struct dict {
//...
dictEntry **ht_table; //两个dictEntry，一个开始为空，rehash迁移时使用
//...
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
};
</code></pre>
<p>在正常服务请求阶段，插入的数据，都会写入到<code>哈希表 1</code>，此时的<code>哈希表 2</code>并没有被分配空间。随着数据逐步增多（根据负载因子判断），触发了 rehash 操作，这个过程分为如下三步：<br>
<img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404270803033.png" alt="" loading="lazy"></p>
<p>如果<code>哈希表 1</code>的数据量非常大，那么在迁移至<code>哈希表 2</code>的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。因此redis采用了渐进式rehash</p>
<p>渐进式 rehash 步骤如下：</p>
<ol>
<li>先给<code>哈希表 2</code>分配空间；</li>
<li>在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将<code>哈希表 1</code>中索引位置上的所有 key-value 迁移到<code>哈希表 2</code>上；</li>
<li>随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把<code>哈希表 1</code>的所有 key-value 迁移到<code>哈希表 2</code>，从而完成 rehash 操作。</li>
</ol>
<p>这样就把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。</p>
<p>在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。比如，在渐进式 rehash 进行期间，查找一个 key 的值的话，先会在<code>哈希表 1</code>里面进行查找，如果没找到，就会继续到<code>哈希表 2</code> 里面进行找到。新增一个 key-value 时，会被保存到<code>哈希表 2</code>里面，而<code>哈希表 1</code>则不再进行任何添加操作，这样保证了<code>哈希表 1</code>的 key-value 数量只会减少，随着 rehash 操作的完成，最终<code>哈希表 1</code>就会变成空表。</p>
<p>哈希表的查找过程：</p>
<pre><code class="language-c">dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
if (dictSize(d) == 0) return NULL; /* dict is empty */
if (dictIsRehashing(d)) _dictRehashStep(d);//检查是否正在渐进式 rehash，如果是，那就rehash一步
h = dictHashKey(d, key);//计算key的hash值
//哈希表元素的删除、查找、更新等操作都会在两个哈希表进行
for (table = 0; table <= 1; table++) {
idx = h & DICTHT_SIZE_MASK(d->ht_size_exp);
he = d->ht_table;
while(he) {
void *he_key = dictGetKey(he);
if (key == he_key || dictCompareKeys(d, key, he_key))
return he;
he = dictGetNext(he);
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
</code></pre>
<p>关键在于哈希表插入时会去检查是都正在Rehash，如果不是，那就往0号hash表中插入；如果是，那就直接往1号hash表中插入，因为如果正在Rehash还往0号hash表中插入，那么最终还是要rehash到1号hash表的</p>
<pre><code class="language-c">int htidx = dictIsRehashing(d) ? 1 : 0;
</code></pre>
<p>rehash的触发条件是什么？</p>
<p>负载因子 = 哈希表已保存节点数量/哈希表大小</p>
<p>触发 rehash 操作的条件，主要有两个：</p>
<ul>
<li>当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。</li>
<li>当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作</li>
</ul>
<h3 id="那如何优化hashmap">那如何优化HashMap</h3>
<p>借用Redis渐进式hash的思想，在分批扩容过程中，我们可以给 HashMap 维护两个数组:</p>
<ul>
<li>旧数组：扩容之前的数组，包含了部分尚未迁移的数据。</li>
<li>新数组：扩容过程中创建的新数组，用于存储迁移后的数据。</li>
</ul>
<p>实现方式:</p>
<ul>
<li>扩容分批化：将重新哈希的过程分成多个步骤，而不是一次性完成。在扩容时，先创建新的数组，但只重新哈希一部分旧数据。</li>
<li>增量式迁移：每次插入、修改或查询时，检查当前是否有未完成的扩容任务。如果有，则迁移少量旧数据到新数组中，直到完成所有数据的迁移。</li>
<li>迁移状态管理：通过状态字段记录扩容的进度，确保每次操作时扩容任务逐步推进。</li>
</ul>
<p>有两个数组，那么 get操作时候如何查询呢?</p>
<ul>
<li>优先查找新数组：当用户发起 get 请求时，优先从新数组中查找。因为已经迁移的数据会直接放入新数组。</li>
<li>回退查找旧数组：如果在新数组中没有找到对应的键，说明该键还未迁移至新数组，需要回退到旧数组查找</li>
</ul>
<p>其实这就是空间换时间的概念，也是一种权衡。</p>
<ul>
<li>优点：节省的用户扩容阻塞时间，把扩容时间的消耗平均分散都后面的处理中，基本上做到了无感知</li>
<li>缺点：空间开销比较大，因为在扩容的时候，同时存在两个大数组。</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18881021
頁:
[1]