Go 面試中，經常會被問到數組和 Map 的擴容策略。本文就來總結說明下數組和 Map 的擴容策略。

數組擴容

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

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

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

哈希表擴容

在 Go 語言中，Map 是一種常用的數據結構，用于存儲鍵值對。其擴容機制對于理解 Map 的性能和內存使用至關重要。

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

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

Map 的底層結構

Go 語言中的 Map 底層是一個哈希表（hashmap），其結構如下：

Go 代碼實現如下：

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

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

 extra *mapextra // optional fields
}

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

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

一些關鍵字段釋義如下：

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

擴容機制：雙倍擴容

(1) 觸發條件：

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

源碼中相關邏輯如下：

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

(2) 擴容過程：

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

擴容機制：等量擴容

(1) 觸發條件：

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

源碼中相關邏輯如下：

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

(2) 擴容過程：

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