侧边栏壁纸
博主头像
汪洋

即使慢,驰而不息,纵会落后,纵会失败,但一定可以达到他所向的目标。 - 鲁迅

  • 累计撰写 191 篇文章
  • 累计创建 74 个标签
  • 累计收到 112 条评论

Golang - 通过源码认识数组与切片(面试题)

汪洋
2022-04-20 / 0 评论 / 0 点赞 / 239 阅读 / 2,332 字

大家好,今天我们通过两道面试题初步学习一下 Go 语言中数组和切片的底层实现

第一题

a := [3]int{1,2,3}
b := []int{1,2,3}
c := a
d := b
c[0] = 4
d[0] = 4
fmt.Println(a)
fmt.Println(b)
运行结果
    [1 2 3]
    [4 2 3]

第二题

arr := make([]int, 0, 10)
arr = append(arr, 1, 2, 3)
newSlice := append(arr, 4)
arr = append(arr,5)
arr = append(arr,6)
fmt.Println(newSlice)
运行结果

[1 2 3 5]

如果你对Go语言的切片不是很了解,那么可能弄不明白上述两题为什么会有这样的结果,我们先一起了解下数组和切片

原理

数组是相同类型元素组成的集合,计算机会为数组分配一块连续的内存来保存其中的元素,

func NewArray(elem *Type, bound int64) *Type {
	if bound < 0 {
		Fatalf("NewArray: invalid bound %v", bound)
	}
	t := New(TARRAY)
	t.Extra = &Array{Elem: elem, Bound: bound}
	t.SetNotInHeap(elem.NotInHeap())
	return t
}

Go语言中,数组类型是由上述cmd/compile/internal/types.NewArray函数生成的,
该类型包括两个字段,分别是元素类型Elem和数组大小Bound,由此我们也可以看出,只有元素类型和大小均相同的数组才是同一类型。

切片是可变长的数组,在其容量不足时会自动扩容。

func NewSlice(elem *Type) *Type {
	if t := elem.Cache.slice; t != nil {
		if t.Elem() != elem {
			Fatalf("elem mismatch")
		}
		return t
	}

	t := New(TSLICE)
	t.Extra = Slice{Elem: elem}
	elem.Cache.slice = t
	return t
}

通过上述cmd/compile/internal/types.NewSlice函数,我们可以了解到切片在编译期间生成的类型只包括元素类型。 运行时切片可以由如下reflect.SliceHeader结构体表示

type SliceHeader struct {
	Data uintptr
	Len  int
	Cap  int
}
  • Data是指向数组的指针;
  • Len是当前切片的长度;
  • Cap是当前切片的容量,即Data数组的大小。
  • Data是一块连续的内存空间,可用于存储切片中的全部元素。

解题

第一题中,将变量b赋值给变量d,Data、Len、Cap均会赋值,所以变量d与变量b共用同一个底层数组Data,修改变量b时,变量d也自然受到影响 如果想要复制出新的切片时,可以用如下代码来代替 d := b

d := make([]int, 3)
copy(d,b)

原理

使用append关键字向切片中追加元素是常见的切片操作,如果append返回的新切片不需要赋值回原变量,就会进入如下流程:

// If inplace is false, process as expression "append(s, e1, e2, e3)":

ptr, len, cap := s
newlen := len + 3
if newlen > cap {
    ptr, len, cap = growslice(s, newlen)
    newlen = len + 3 // recalculate to avoid a spill
}
// with write barriers, if needed:
*(ptr+len) = e1
*(ptr+len+1) = e2
*(ptr+len+2) = e3
return makeslice(ptr, newlen, cap)

从切片中获取它的数组指针、大小、容量,如果在追加元素后切片大小大于容量,就会调用runtime.growslice对切片进行扩容,并将新元素依次加入切片
覆盖原变量的逻辑如下:

//If inplace is true, process as statement "s = append(s, e1, e2, e3)":

a := &s
ptr, len, cap := s
newlen := len + 3
if uint(newlen) > uint(cap) {
   newptr, len, newcap = growslice(ptr, len, cap, newlen)
   vardef(a)       // if necessary, advise liveness we are writing a new a
   *a.cap = newcap // write before ptr to avoid a spill
   *a.ptr = newptr // with write barrier
}
newlen = len + 3 // recalculate to avoid a spill
*a.len = newlen
// with write barriers, if needed:
*(ptr+len) = e1
*(ptr+len+1) = e2
*(ptr+len+2) = e3

解题

我们可以看到,无论覆盖原变量与否,数据都是在*(ptr+len)的位置开始写入,区别在于覆盖原变量会造成len和cap的修改。
回过头来再看第二题,newSlice := append(arr, 4) 操作后,arr的len仍为3,
arr = append(arr,5)操作则在底层数组的第四个位置写入了5,覆盖了4
arr = append(arr,6)在底层数组的第五个位置写入6,打印newSlice时,newSlice的len为4,
于是打印底层数组的前四个元素,便是1235

0

评论区