站長資訊網
go語言擴容方法有：1、Slice擴容，在使用append向Slice追加元素時，如果Slice空間不足，將會觸發Slice擴容；2、Map擴容。觸發Map擴容的條件有二個：1、負載因子大于6.5時，也即平均每個bucket存儲的鍵值對達到6.5個；2、overflow數量大于2^15時，也即overflow數量超過32768時。
本教程操作環境：windows7系統、GO 1.18版本、Dell G3電腦。
Slice擴容
觸發
使用append向Slice追加元素時，如果Slice空間不足，將會觸發Slice擴容
原理
擴容實際上是重新分配一塊更大的內存，將原Slice數據拷貝進新Slice，然后返回新Slice，擴容后再將數據追加進去。
機制
V1.8之前：
擴容容量的選擇遵循以下規則：
- 如果原Slice容量小于1024，則新Slice容量將擴大為原來的2倍；
- 如果原Slice容量大于等于1024，則新Slice容量將擴大為原來的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之后：
新擴容容量的選擇遵循以下規則：(擁有更平滑的擴容系數)
- 如果原Slice容量小于256，則新Slice容量將擴大為原來的2倍；
- 如果原Slice容量大于等于256，則新Slice容量將擴大為原來的 新容量 = (原容量+3*256)/4
// 只關心擴容規則的簡化版growslice func growslice(old, cap int) int { newcap := old doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 // 不同點1 if old < threshold { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += (newcap + 3*threshold) / 4 // 不同點2 } if newcap <= 0 { newcap = cap } } } return newcap }
Map擴容
觸發擴容的條件有二個：
-
負載因子 > 6.5時，也即平均每個bucket存儲的鍵值對達到6.5個。增量擴容
-
overflow數量 > 2^15時，也即overflow數量超過32768時。等量擴容/重排
注意：創建溢出桶不屬于擴容機制
增量擴容
- 當負載因子過大時，新開辟buckets空間，bucket數量為之前的 2 倍
- 新空間被buckets引用，之前的舊空間被oldbuckets引用
- 之后逐漸將 oldbuckets中的數據 搬遷到 新開辟的 buckets空間中去
考慮到如果map存儲了數以億計的key-value，一次性搬遷將會造成比較大的延時，Go采用逐步搬遷策略，即每次訪問map時都會觸發一次搬遷，每次搬遷2個鍵值對。當oldbuckets中的鍵值對全部搬遷完畢后，刪除oldbuckets。
下圖展示了包含一個bucket滿載的map(為了描述方便，圖中bucket省略了value區域):
當前map存儲了7個鍵值對，只有1個bucket。此時負載因子為7 > 6.5。再次插入數據時將會觸發擴容操作，擴容之后再將新插入鍵寫入新的bucket。注意，因為負載因子的觸發，不是創建溢出桶
當第8個鍵值對插入時，將會觸發擴容，擴容后示意圖如下：
后續對map的訪問操作會觸發遷移，將oldbuckets中的鍵值對逐步的搬遷過來。
搬遷完成后的示意圖如下：
數據搬遷過程中原bucket中的鍵值對將存在于新bucket的前面，新插入的鍵值對將存在于新bucket的后面。
等量擴容/重排
所謂等量擴容，實際上并不是擴大容量，buckets數量不變，重新做一遍類似增量擴容的搬遷動作，把松散的鍵值對重新排列一次，以使bucket的使用率更高，進而保證更快的存取。
在極端場景下，比如不斷地增刪，而鍵值對正好集中在一小部分的bucket，這樣會造成overflow的bucket數量增多，但負載因子又不高，從而無法執行增量搬遷的情況，如下圖所示：
上圖可見，overflow的bucket中大部分是空的，訪問效率會很差。此時進行一次等量擴容，即buckets數量不變，經過重新組織后overflow的bucket數量會減少，即節省了空間又會提高訪問效率。
【
