go語言擴(kuò)容方法有：1、Slice擴(kuò)容，在使用append向Slice追加元素時(shí)，如果Slice空間不足，將會觸發(fā)Slice擴(kuò)容；2、Map擴(kuò)容。觸發(fā)Map擴(kuò)容的條件有二個(gè)：1、負(fù)載因子大于6.5時(shí)，也即平均每個(gè)bucket存儲的鍵值對達(dá)到6.5個(gè)；2、overflow數(shù)量大于2^15時(shí)，也即overflow數(shù)量超過32768時(shí)。

本教程操作環(huán)境：windows7系統(tǒng)、GO 1.18版本、Dell G3電腦。

Slice擴(kuò)容

觸發(fā)

使用append向Slice追加元素時(shí)，如果Slice空間不足，將會觸發(fā)Slice擴(kuò)容

原理

擴(kuò)容實(shí)際上是重新分配一塊更大的內(nèi)存，將原Slice數(shù)據(jù)拷貝進(jìn)新Slice，然后返回新Slice，擴(kuò)容后再將數(shù)據(jù)追加進(jìn)去。

機(jī)制

V1.8之前：

擴(kuò)容容量的選擇遵循以下規(guī)則：

• 如果原Slice容量小于1024，則新Slice容量將擴(kuò)大為原來的2倍；
• 如果原Slice容量大于等于1024，則新Slice容量將擴(kuò)大為原來的1.25倍；

// 1.17及以前的版本中 // old指切片的舊容量, cap指期望的新容量 func growslice(old, cap int) int {     newcap := old     doublecap := newcap + newcap     // 如果期望容量大于舊容量的2倍，則直接使用期望容量作為最終容量     if cap > doublecap {         newcap = cap     } else {         // 如果舊容量小于1024，則直接翻倍         if old < 1024 {             newcap = doublecap         } else {             // 每次增長大約1.25倍             for 0 < newcap && newcap < cap {                 newcap += newcap / 4             }             if newcap <= 0 {                 newcap = cap             }         }     }     // 這里忽略了對齊操作     return newcap }

V1.8之后：

新擴(kuò)容容量的選擇遵循以下規(guī)則：(擁有更平滑的擴(kuò)容系數(shù))

• 如果原Slice容量小于256，則新Slice容量將擴(kuò)大為原來的2倍；
• 如果原Slice容量大于等于256，則新Slice容量將擴(kuò)大為原來的 新容量 = (原容量+3*256)/4

// 只關(guān)心擴(kuò)容規(guī)則的簡化版growslice func growslice(old, cap int) int {     newcap := old     doublecap := newcap + newcap     if cap > doublecap {         newcap = cap     } else {         const threshold = 256 // 不同點(diǎn)1         if old < threshold {             newcap = doublecap         } else {             for 0 < newcap && newcap < cap {                 newcap += (newcap + 3*threshold) / 4 // 不同點(diǎn)2             }             if newcap <= 0 {                 newcap = cap             }         }     }     return newcap }

Map擴(kuò)容

觸發(fā)擴(kuò)容的條件有二個(gè)：

• 負(fù)載因子 > 6.5時(shí)，也即平均每個(gè)bucket存儲的鍵值對達(dá)到6.5個(gè)。增量擴(kuò)容

• overflow數(shù)量 > 2^15時(shí)，也即overflow數(shù)量超過32768時(shí)。等量擴(kuò)容/重排

注意：創(chuàng)建溢出桶不屬于擴(kuò)容機(jī)制

增量擴(kuò)容

• 當(dāng)負(fù)載因子過大時(shí)，新開辟buckets空間，bucket數(shù)量為之前的 2 倍
• 新空間被buckets引用，之前的舊空間被oldbuckets引用
• 之后逐漸將 oldbuckets中的數(shù)據(jù) 搬遷到 新開辟的 buckets空間中去

考慮到如果map存儲了數(shù)以億計(jì)的key-value，一次性搬遷將會造成比較大的延時(shí)，Go采用逐步搬遷策略，即每次訪問map時(shí)都會觸發(fā)一次搬遷，每次搬遷2個(gè)鍵值對。當(dāng)oldbuckets中的鍵值對全部搬遷完畢后，刪除oldbuckets。

下圖展示了包含一個(gè)bucket滿載的map(為了描述方便，圖中bucket省略了value區(qū)域):

當(dāng)前map存儲了7個(gè)鍵值對，只有1個(gè)bucket。此時(shí)負(fù)載因子為7 > 6.5。再次插入數(shù)據(jù)時(shí)將會觸發(fā)擴(kuò)容操作，擴(kuò)容之后再將新插入鍵寫入新的bucket。注意，因?yàn)樨?fù)載因子的觸發(fā)，不是創(chuàng)建溢出桶

當(dāng)?shù)?個(gè)鍵值對插入時(shí)，將會觸發(fā)擴(kuò)容，擴(kuò)容后示意圖如下：

后續(xù)對map的訪問操作會觸發(fā)遷移，將oldbuckets中的鍵值對逐步的搬遷過來。

搬遷完成后的示意圖如下：

數(shù)據(jù)搬遷過程中原bucket中的鍵值對將存在于新bucket的前面，新插入的鍵值對將存在于新bucket的后面。

等量擴(kuò)容/重排

所謂等量擴(kuò)容，實(shí)際上并不是擴(kuò)大容量，buckets數(shù)量不變，重新做一遍類似增量擴(kuò)容的搬遷動作，把松散的鍵值對重新排列一次，以使bucket的使用率更高，進(jìn)而保證更快的存取。
在極端場景下，比如不斷地增刪，而鍵值對正好集中在一小部分的bucket，這樣會造成overflow的bucket數(shù)量增多，但負(fù)載因子又不高，從而無法執(zhí)行增量搬遷的情況，如下圖所示：

上圖可見，overflow的bucket中大部分是空的，訪問效率會很差。此時(shí)進(jìn)行一次等量擴(kuò)容，即buckets數(shù)量不變，經(jīng)過重新組織后overflow的bucket數(shù)量會減少，即節(jié)省了空間又會提高訪問效率。

【