面试题：Go语言切片内存布局与append操作关系

Question

结合Go语言切片的内存布局，详细说明append函数在不同情况下（如容量足够、容量不足）对切片内存布局的影响，并分析其时间和空间复杂度。

Answer 1

1. Go语言切片的内存布局

Go语言的切片（slice）是一种动态数组，它由三个部分组成：

• 指针：指向底层数组的第一个元素。
• 长度：切片当前的元素个数。
• 容量：切片从当前位置到其底层数组末尾的元素个数。

例如：

s := make([]int, 5, 10)

这里创建了一个切片s，长度为5，容量为10。其底层数组可以容纳10个int类型的元素，而当前切片只使用了前5个元素。

2. append函数在容量足够时对切片内存布局的影响

当调用append函数且切片的容量足够时，append函数直接在切片的末尾添加新元素。

• 内存布局变化：
  • 切片的长度增加1，指向底层数组的指针不变，容量不变。
  • 例如：

s := make([]int, 5, 10)
s = append(s, 10)

原本长度为5，容量为10的切片，添加一个元素后，长度变为6，容量仍为10，指针仍指向底层数组的起始位置。

• 时间复杂度：
  • 因为直接在现有内存空间的末尾添加元素，时间复杂度为O(1)。
• 空间复杂度：
  • 由于没有重新分配内存，空间复杂度为O(1)。

3. append函数在容量不足时对切片内存布局的影响

当调用append函数且切片的容量不足时，append函数会进行如下操作：

• 内存布局变化：
  • Go会重新分配一块更大的内存空间，通常是原容量的2倍（如果原容量小于1024），如果原容量大于或等于1024，则新容量会增加原容量的1/4。
  • 将原切片的内容复制到新的内存空间，然后在新空间的末尾添加新元素。
  • 切片的指针指向新的内存空间，长度增加1，容量变为新分配的大小。
  • 例如：

s := make([]int, 10, 10)
s = append(s, 10)

原切片长度和容量都为10，添加元素后，会重新分配内存（容量变为20），指针指向新的内存空间，长度变为11，容量变为20。

• 时间复杂度：
  • 由于需要复制原切片内容，时间复杂度为O(n)，其中n为原切片的长度。
• 空间复杂度：
  • 重新分配内存，空间复杂度在最坏情况下为O(n)，但平均情况下接近O(1)，因为每次扩容通常会预留一些额外空间。