如果讓你改造下 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]）。
struct dict {
//...
dictEntry **ht_table[2]; //兩個dictEntry，一個開始為空，rehash遷移時使用
//...
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
};在正常服務請求階段，插入的數據，都會寫入到哈希表 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就會變成空表。
哈希表的查找過程：
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[table]);
he = d->ht_table[table][idx];
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;
}關鍵在于哈希表插入時會去檢查是都正在Rehash，如果不是，那就往0號hash表中插入；如果是，那就直接往1號hash表中插入，因為如果正在Rehash還往0號hash表中插入，那么最終還是要rehash到1號hash表的
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 請求時，優先從新數組中查找。因為已經遷移的數據會直接放入新數組。
- 回退查找舊數組：如果在新數組中沒有找到對應的鍵，說明該鍵還未遷移至新數組，需要回退到舊數組查找
其實這就是空間換時間的概念，也是一種權衡。
- 優點：節省的用戶擴容阻塞時間，把擴容時間的消耗平均分散都后面的處理中，基本上做到了無感知
- 缺點：空間開銷比較大，因為在擴容的時候，同時存在兩個大數組。
