假設(shè)有一個(gè) 1G 大的 HashMap，此時(shí)用戶請求過來剛好觸發(fā)它的擴(kuò)容.那么當(dāng)前用戶請求會(huì)被阻塞，因?yàn)?HashMap的底層是基于數(shù)組+鏈表(紅黑樹)來實(shí)現(xiàn)的，一旦它發(fā)生擴(kuò)容，就需要新增一個(gè)比之前大2倍的數(shù)組，然后將元素copy到新的數(shù)組上

那么如何優(yōu)化呢？

簡要回答

此時(shí)可以借鑒 Redis 的 Hash 結(jié)構(gòu)，因?yàn)?Redis 處理命令恰好是單線程的，它的 Hash 表如果很大，觸發(fā)擴(kuò)容的時(shí)候是不是也會(huì)導(dǎo)致阻塞?

我們都知道 HashMap 默認(rèn)的擴(kuò)容過程是一次性重哈希，即每次擴(kuò)容都會(huì)創(chuàng)建一個(gè)更大的數(shù)組，并將所有元素重新哈希并放入新數(shù)組。

此時(shí)我們可以借鑒redis的漸進(jìn)式rehash，就是把擴(kuò)容過程分批完成，通過分批擴(kuò)容來減少單次擴(kuò)容的開銷。

簡單來說不要一次性擴(kuò)容完畢，而是分批搬運(yùn)數(shù)據(jù)。

這種題目其實(shí)是借用HashMap在問redis的漸進(jìn)式hash，是否對redis有深入的理解

擴(kuò)展知識(shí)

Redis的rehash

順道一起來看看Redis的漸進(jìn)式hash是如何實(shí)現(xiàn)的

Redis 定義一個(gè) dict 結(jié)構(gòu)體，這個(gè)結(jié)構(gòu)體里定義了兩個(gè)哈希表（ht_table[2]）。

struct dict {
   //...
    dictEntry **ht_table[2]; //兩個(gè)dictEntry，一個(gè)開始為空，rehash遷移時(shí)使用
    //...
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
};

在正常服務(wù)請求階段，插入的數(shù)據(jù)，都會(huì)寫入到哈希表 1，此時(shí)的哈希表 2  并沒有被分配空間。隨著數(shù)據(jù)逐步增多（根據(jù)負(fù)載因子判斷），觸發(fā)了 rehash 操作，這個(gè)過程分為如下三步：

圖片

如果哈希表 1的數(shù)據(jù)量非常大，那么在遷移至哈希表 2的時(shí)候，因?yàn)闀?huì)涉及大量的數(shù)據(jù)拷貝，此時(shí)可能會(huì)對 Redis 造成阻塞，無法服務(wù)其他請求。因此redis采用了漸進(jìn)式rehash

漸進(jìn)式 rehash 步驟如下：

1. 先給哈希表 2分配空間；
2. 在 rehash 進(jìn)行期間，每次哈希表元素進(jìn)行新增、刪除、查找或者更新操作時(shí)，Redis 除了會(huì)執(zhí)行對應(yīng)的操作之外，還會(huì)順序?qū)?/span>哈希表 1中索引位置上的所有 key-value 遷移到哈希表 2上；
3. 隨著處理客戶端發(fā)起的哈希表操作請求數(shù)量越多，最終在某個(gè)時(shí)間點(diǎn)會(huì)把哈希表 1的所有 key-value 遷移到哈希表 2，從而完成 rehash 操作。

這樣就把一次性大量數(shù)據(jù)遷移工作的開銷，分?jǐn)偟搅硕啻翁幚碚埱蟮倪^程中，避免了一次性 rehash 的耗時(shí)操作。

在進(jìn)行漸進(jìn)式 rehash 的過程中，會(huì)有兩個(gè)哈希表，所以在漸進(jìn)式 rehash 進(jìn)行期間，哈希表元素的刪除、查找、更新等操作都會(huì)在這兩個(gè)哈希表進(jìn)行。比如，在漸進(jìn)式 rehash 進(jìn)行期間，查找一個(gè) key 的值的話，先會(huì)在哈希表 1里面進(jìn)行查找，如果沒找到，就會(huì)繼續(xù)到哈希表 2 里面進(jìn)行找到。新增一個(gè) key-value 時(shí)，會(huì)被保存到哈希表 2里面，而哈希表 1則不再進(jìn)行任何添加操作，這樣保證了哈希表 1的 key-value 數(shù)量只會(huì)減少，隨著 rehash 操作的完成，最終哈希表 1就會(huì)變成空表。

哈希表的查找過程：

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);//檢查是否正在漸進(jìn)式 rehash，如果是，那就rehash一步
    h = dictHashKey(d, key);//計(jì)算key的hash值
 //哈希表元素的刪除、查找、更新等操作都會(huì)在兩個(gè)哈希表進(jìn)行
    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;
}

關(guān)鍵在于哈希表插入時(shí)會(huì)去檢查是都正在Rehash，如果不是，那就往0號hash表中插入；如果是，那就直接往1號hash表中插入，因?yàn)槿绻赗ehash還往0號hash表中插入，那么最終還是要rehash到1號hash表的

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

rehash的觸發(fā)條件是什么？

負(fù)載因子 = 哈希表已保存節(jié)點(diǎn)數(shù)量/哈希表大小

觸發(fā) rehash 操作的條件，主要有兩個(gè)：

• 當(dāng)負(fù)載因子大于等于 1 ，并且 Redis 沒有在執(zhí)行 bgsave 命令或者 bgrewiteaof 命令，也就是沒有執(zhí)行 RDB 快照或沒有進(jìn)行 AOF 重寫的時(shí)候，就會(huì)進(jìn)行 rehash 操作。
• 當(dāng)負(fù)載因子大于等于 5 時(shí)，此時(shí)說明哈希沖突非常嚴(yán)重了，不管有沒有有在執(zhí)行 RDB 快照或 AOF 重寫，都會(huì)強(qiáng)制進(jìn)行 rehash 操作

那如何優(yōu)化HashMap

借用Redis漸進(jìn)式hash的思想，在分批擴(kuò)容過程中，我們可以給 HashMap 維護(hù)兩個(gè)數(shù)組:

• 舊數(shù)組：擴(kuò)容之前的數(shù)組，包含了部分尚未遷移的數(shù)據(jù)。
• 新數(shù)組：擴(kuò)容過程中創(chuàng)建的新數(shù)組，用于存儲(chǔ)遷移后的數(shù)據(jù)。

實(shí)現(xiàn)方式:

• 擴(kuò)容分批化：將重新哈希的過程分成多個(gè)步驟，而不是一次性完成。在擴(kuò)容時(shí)，先創(chuàng)建新的數(shù)組，但只重新哈希一部分舊數(shù)據(jù)。
• 增量式遷移：每次插入、修改或查詢時(shí)，檢查當(dāng)前是否有未完成的擴(kuò)容任務(wù)。如果有，則遷移少量舊數(shù)據(jù)到新數(shù)組中，直到完成所有數(shù)據(jù)的遷移。
• 遷移狀態(tài)管理：通過狀態(tài)字段記錄擴(kuò)容的進(jìn)度，確保每次操作時(shí)擴(kuò)容任務(wù)逐步推進(jìn)。

有兩個(gè)數(shù)組，那么 get操作時(shí)候如何查詢呢?

• 優(yōu)先查找新數(shù)組：當(dāng)用戶發(fā)起 get 請求時(shí)，優(yōu)先從新數(shù)組中查找。因?yàn)橐呀?jīng)遷移的數(shù)據(jù)會(huì)直接放入新數(shù)組。
• 回退查找舊數(shù)組：如果在新數(shù)組中沒有找到對應(yīng)的鍵，說明該鍵還未遷移至新數(shù)組，需要回退到舊數(shù)組查找

其實(shí)這就是空間換時(shí)間的概念，也是一種權(quán)衡。

• 優(yōu)點(diǎn)：節(jié)省的用戶擴(kuò)容阻塞時(shí)間，把擴(kuò)容時(shí)間的消耗平均分散都后面的處理中，基本上做到了無感知
• 缺點(diǎn)：空間開銷比較大，因?yàn)樵跀U(kuò)容的時(shí)候，同時(shí)存在兩個(gè)大數(shù)組。