【Go语言】切片的扩容

不论是在Java中，或者其他语言中，集合的一个底层原理都是面试考察的一个重点，这篇文章就简单的讲一下切片的扩容机制，如果需要深入研究，可以自行看源码。

在不同的版本中，扩容的机制也是不同的，如果你能够同时大致的说出这两种的不同，很有可能获得面试官的一个好感。

首先看1.13版本的一个代码：

newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
   newcap = cap
} else {
   if old.len < 1024 {
      newcap = doublecap
   } else {
      // Check 0 < newcap to detect overflow
      // and prevent an infinite loop.
      for 0 < newcap && newcap < cap {
         newcap += newcap / 4
      }
      // Set newcap to the requested cap when
      // the newcap calculation overflowed.
      if newcap <= 0 {
         newcap = cap
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

如果所需的容量大于两倍就扩容至所需的容量
否则如果小于1024就扩容两倍
否则每次增加四分之一，知道大于所需容量

如果超出最大值 则等于所需容量

在看一下1.18版本的

newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
   newcap = cap
} else {
   const threshold = 256
   if old.cap < threshold {
      newcap = doublecap
   } else {
      // Check 0 < newcap to detect overflow
      // and prevent an infinite loop.
      for 0 < newcap && newcap < cap {
         // Transition from growing 2x for small slices
         // to growing 1.25x for large slices. This formula
         // gives a smooth-ish transition between the two.
         newcap += (newcap + 3*threshold) / 4
      }
      // Set newcap to the requested cap when
      // the newcap calculation overflowed.
      if newcap <= 0 {
         newcap = cap
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

如果所需的容量大于两倍就扩容至所需的容量
否则如果小于256就扩容两倍
否则每次增加四分之一容量在加上四分之三的阈值容量知道大于所需容量（newcap += (newcap + 3*threshold) / 4）

如果超出最大容量 则等于所需容量