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

數(shù)組擴(kuò)容

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

Go 中切片擴(kuò)容的策略是這樣的：

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

哈希表擴(kuò)容

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

Go 語言中 Map 的兩種擴(kuò)容方式：

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

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

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

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

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

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

 extra *mapextra // optional fields
}

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

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

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

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

擴(kuò)容機(jī)制：雙倍擴(kuò)容

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

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

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

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

(2) 擴(kuò)容過程：

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

擴(kuò)容機(jī)制：等量擴(kuò)容

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

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

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

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

(2) 擴(kuò)容過程：

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