Go 面試中，經(jīng)常會被問到數(shù)組和 Map 的擴容策略。本文就來總結(jié)說明下數(shù)組和 Map 的擴容策略。

數(shù)組擴容

Go 語言中，動態(tài)數(shù)組被稱為切片（slice），它提供了一種靈活、動態(tài)大小的數(shù)組解決方案。使用append函數(shù)向切片添加元素時，Go 語言會根據(jù)切片的當(dāng)前容量（capacity）來決定是否需要擴容。

Go 中切片擴容的策略是這樣的：

• 首先判斷，如果新申請容量大于 2 倍的舊容量，最終容量就是新申請的容量；
• 否則判斷，如果舊切片的長度小于 1024，則最終容量就是舊容量的兩倍；
• 否則判斷，如果舊切片長度大于等于 1024，則最終容量從舊容量開始循環(huán)增加原來的 1/4，直到最終容量大于等于新申請的容量；
• 如果最終容量計算值溢出，則最終容量就是新申請容量。

哈希表擴容

在 Go 語言中，Map 是一種常用的數(shù)據(jù)結(jié)構(gòu)，用于存儲鍵值對。其擴容機制對于理解 Map 的性能和內(nèi)存使用至關(guān)重要。

Go 語言中 Map 的兩種擴容方式：

• 雙倍擴容： 當(dāng)鍵值對數(shù)量超過當(dāng)前桶數(shù)組容量的6.5倍時，說明桶即將被填滿，此時會觸發(fā)擴容，桶數(shù)量翻倍。目的是減少哈希沖突，提升查詢效率；
• 等量擴容： 當(dāng)溢出桶過多（如頻繁插入刪除導(dǎo)致數(shù)據(jù)分散）但鍵值對總數(shù)較少時，桶數(shù)量不變，但會重新排列數(shù)據(jù)，合并冗余的溢出桶，使數(shù)據(jù)分布更緊湊，從而提高查詢性能。

Map 的底層結(jié)構(gòu)

Go 語言中的 Map 底層是一個哈希表（hashmap），其結(jié)構(gòu)如下：

Go 代碼實現(xiàn)如下：

// runtime/map.go
// A header for a Go map.
type hmap struct {
 count     int // 當(dāng)前哈希表中鍵值對的數(shù)量
 flags     uint8
 B         uint8  // 當(dāng)前哈希表持有的 buckets 數(shù)量, 因為哈希表中桶的數(shù)量都按2倍擴容,改字段存儲對數(shù)，也就是 len(buckets) == 2^B
 noverflow uint16 // 溢出桶的大致數(shù)量
 hash0     uint32 // hash seed

 buckets    unsafe.Pointer // 存儲 2^B 個桶的數(shù)組
 oldbuckets unsafe.Pointer // 擴容時用于保存之前 buckets 的字段 , 大小事buckets的一般
 nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

 extra *mapextra // optional fields
}

// mapextra 主要維護，當(dāng)hmap中的buckets中有一些桶發(fā)生溢出，但有達不到擴容閾值時，存儲溢出的桶
type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap

 // nextOverflow holds a pointer to a free overflow bucket.
 nextOverflow *bmap
}

一些關(guān)鍵字段釋義如下：

• count：表示哈希表中鍵值對的數(shù)量；
• B：這是以 2 為底的對數(shù)，用于確定桶（bucket）的數(shù)量。例如，當(dāng) B = 1 時，桶的數(shù)量為 2^1 = 2 個；當(dāng) B = 2 時，桶的數(shù)量為 2^2 = 4 個，以此類推；
• hash0：是計算鍵的哈希值時用到的一個因子；
• buckets：是一個指向桶數(shù)組的指針，每個桶用于存儲鍵值對；
• overflow：當(dāng)桶中裝不下更多元素，且 key 又被 hash 到這個桶時，就會放到溢出桶，原桶的 overflow 字段指向溢出桶（鏈地址法）。

擴容機制：雙倍擴容

(1) 觸發(fā)條件：

當(dāng) Map 的負載超過一定閾值時會觸發(fā)雙倍擴容。負載的計算方式是元素個數(shù)（count）除以桶的數(shù)量（2^B），如果這個比值大于等于 6.5，則認為負載超了。例如，當(dāng) B = 2，桶有 2^2 = 4 個，如果元素個數(shù) count 為 26（26/4 = 6.5），就會觸發(fā)雙倍擴容。

源碼中相關(guān)邏輯如下：

// 假設(shè)h為map結(jié)構(gòu)體指針
if!h.flags&hashWriting && h.count > int(float64(1<<h.B)*loadFactor) {
    // 觸發(fā)雙倍擴容邏輯
}

(2) 擴容過程：

• 雙倍擴容時，B 的值會加 1，從而使桶的數(shù)量翻倍。例如，原來 B = 2，桶有 4 個，擴容后 B = 3，桶的數(shù)量變?yōu)?2^3 = 8個；
• 數(shù)據(jù)遷移時，會將原來桶中的數(shù)據(jù)重新分配到新的桶中。具體是根據(jù)鍵的哈希值重新計算在新桶中的位置。假設(shè)鍵的哈希值為 hash，原來桶的數(shù)量為 2^B1，擴容后桶的數(shù)量為 2^B2，則數(shù)據(jù)會從原來的桶（hash % 2^B1）遷移到新的桶（hash % 2^B2）。例如，原來哈希值為 10，B = 2（桶數(shù)量為 4）時，10 % 4 = 2，數(shù)據(jù)在索引為 2 的桶中；擴容后 B = 3（桶數(shù)量為 8），10 % 8 = 2，數(shù)據(jù)仍在索引為 2 的桶中，但此時桶的分布更稀疏，減少了哈希沖突的概率。

擴容機制：等量擴容

(1) 觸發(fā)條件：

當(dāng)有大量的鍵被刪除，導(dǎo)致溢出桶過多時，可能會觸發(fā)等量擴容。這里的溢出桶是指當(dāng)一個桶存滿 8 個元素后，新的元素會存儲到溢出桶中，溢出桶不占用桶的數(shù)量計數(shù)。當(dāng)溢出桶的數(shù)量大于等于 2^B 時，可能觸發(fā)等量擴容。但如果是由于哈希沖突導(dǎo)致溢出桶過多且負載超了，會優(yōu)先觸發(fā)雙倍擴容。

源碼中相關(guān)邏輯如下：

// 假設(shè)h為map結(jié)構(gòu)體指針，noverflow為溢出桶數(shù)量
if noverflow >= uint16(1)<<(h.B) {
    if h.B < 15 {
        // 可能觸發(fā)等量擴容或雙倍擴容邏輯
    }
}

(2) 擴容過程：

等量擴容主要是對桶進行整理，去除空的位置。它會創(chuàng)建一個新的桶數(shù)組，然后遍歷老的桶數(shù)組，將不為空的鍵值對重新放置到新的桶數(shù)組中，同時釋放原來的溢出桶。由于哈希因子、B 值和哈希算法都沒有變化，鍵值對在新桶中的位置計算方式與原來相同，只是去除了空的存儲位置，使鍵值對更加緊湊，提高后續(xù)操作的效率。