Golang data structure

作者:杨润炜
日期:2022/3/15 20:30

强烈推荐先看看这个godata,里面描述了大多数go数据类型的内存结构。

common structure

基本上开发语言都具备的基础数据结构: int(32|64), float, bytes

string

在内存里的结构是一个指针和一个整形数,前者指向一块类型为byte的内存空间,表示字符串内容,后者表示字符串的长度。

slice

特点

  • 初始化长度可选
  • 可在运行时动态扩展长度
  • 可以配置长度和容量

compare to array

数组是固定长度的,slice长度可动态扩展,所以应用更广泛

原理

  • 实际是一个runtime.slice的struct
  • 包含信息:len,cap和array(指向真正存储数据的数组指针)
  1. type slice struct {
  2. array unsafe.Pointer
  3. len int
  4. cap int
  5. }

可能踩坑

slicing的时候会共享底层的数组空间,请看示例:

  1. package main
  2. import "fmt"
  3. func main() {
  4. s := make([]int, 4)
  5. s1 := s[0:2]
  6. s2 := s[2:]
  7. s1[0] = 1
  8. s2[0] = 2
  9. fmt.Println(s, s1, s2) // [1 0 2 0] [1 0] [2 0]
  10. }

run code

另外,append在扩展数组的时候会复用当前的地址进行顺延,可能会覆盖原有的数据,请看示例:

  1. package main
  2. import "fmt"
  3. func main() {
  4. s := make([]int, 4)
  5. s1 := s[0:2]
  6. s2 := s[2:]
  7. s1[0] = 1
  8. s2[0] = 2
  9. fmt.Println(s, s1, s2) // [1 0 2 0] [1 0] [2 0]
  10. s1 = append(s1, 3)
  11. fmt.Println(s, s1, s2) // [1 0 3 0] [1 0 3] [3 0]
  12. }

run code

struct

特点

能够组合多种数据结构,以kv形式区分,在内存中是连续存储的,编译器对其进行内存对齐。

empty struct

空结构体(struct{})的位宽是0,有利于降低空间复杂度。

如果你想要个装东西的容器,又想在不装东西的时候容器不占空间,这种白镖的事就可以交给empty struct。

  1. package main
  2. import (
  3. "fmt"
  4. "unsafe"
  5. )
  6. func main() {
  7. var s = make([]struct{}, 100)
  8. fmt.Println(unsafe.Sizeof(s)) // 24
  9. s = append(s, make([]struct{}, 10)...)
  10. fmt.Println(unsafe.Sizeof(s)) // 24
  11. }

run code
注:24长度是slice底层struct 3个字段的长度,还有可能是12长度,具体根据所在机器是32bit or 64bit。

empty struct跟chan也很配,如果你只是想通过chan在goroutine间传达某个信号,最节省空间的方式就是chan struct{}

  1. package main
  2. import (
  3. "fmt"
  4. "sync"
  5. )
  6. func main() {
  7. var wg sync.WaitGroup
  8. sig := make(chan struct{})
  9. wg.Add(1)
  10. go func() {
  11. select {
  12. case <-sig: // wait for a sig comming
  13. }
  14. wg.Done()
  15. }()
  16. close(sig)
  17. wg.Wait()
  18. fmt.Println("done")
  19. }

run code

为啥empty struct不占空间

因为golang将这种zero-size的变量都指向同一个内存地址空间,而且才不用每次申请新的内存空间。
参考官方的说明

map

原理

指向runtime.hmap的struct指针。

  1. // A header for a Go map.
  2. type hmap struct {
  3. // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
  4. // Make sure this stays in sync with the compiler's definition.
  5. count int // # live cells == size of map. Must be first (used by len() builtin)
  6. flags uint8
  7. B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
  8. noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
  9. hash0 uint32 // hash seed
  10. buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
  11. oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
  12. nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
  13. extra *mapextra // optional fields
  14. }

详情可查阅map source code,函数makemap就是负责make map的调用和返回。

因为是指针,所以它作为函数参数时,修改字段值会影响函数外的变量。

There is no reference type in golang.

首先要理清这里说的reference type和pointer的区别,前者是变量的别名,与原变量的地址是一样的,后者是新建一块内存存储原变量的地址。

先拿map来举例

map作为函数参数时,函数内修改其字段是会影响到外部的:

  1. package main
  2. import "fmt"
  3. func replace(m map[int]int) {
  4. m[0]++
  5. }
  6. func main() {
  7. hm := map[int]int{}
  8. replace(hm)
  9. fmt.Println(hm) // map[0:1]
  10. }

run code

但如果是修改整个map,则不会影响到外部

  1. package main
  2. import "fmt"
  3. func replace(m map[int]int) {
  4. m = map[int]int{1: 1}
  5. }
  6. func main() {
  7. hm := map[int]int{}
  8. replace(hm)
  9. fmt.Println(hm) // map[]
  10. }

run code
这也就说明了map不是引用类型(如果还不直观,可以试试用c++的引用类型),只是个指向原变量的指针,函数内替换掉的只是指针的地址值,并不会影响原变量,但修改指针值(原变量的地址)关联的数据(修改map的字段值),是会影响原变量的。

再来瞧瞧slice

我们平时也试过把slice作为函数参数,在函数内修改slice是会影响外部的,如:

  1. package main
  2. import "fmt"
  3. func inc(s []int) {
  4. s[0]++
  5. }
  6. func main() {
  7. sl := []int{0}
  8. inc(sl)
  9. fmt.Println(sl) // [1]
  10. }

run code
上文不是说slice是个struct么,struct是值传递呀,按理说不会影响外部,但别忘了,slice的元素数据是struct的array指针指向的数组,而且go设计者应该是为了提升slice创建的性能,在传递slice参数时复用原slice的数组,这就导致了函数参数虽然创建了新的slice,但数据却是共享的。我们可以通过点小手段避免复用原slice数组,实现如下:

  1. package main
  2. import "fmt"
  3. func inc(s []int) {
  4. s = append(s, 1)
  5. s[0]++
  6. }
  7. func main() {
  8. sl := []int{0}
  9. inc(sl)
  10. fmt.Println(sl) // [0]
  11. }

run code
函数内的slice被append扩展,底下的数组也会重新申请内存并扩容。

如果确实想要传输引用,在函数内共享外部变量呢?

传递slice pointer

用指针,如:*[]int

  1. package main
  2. import "fmt"
  3. func inc(s *[]int) {
  4. *s = append(*s, 1)
  5. (*s)[0]++
  6. }
  7. func main() {
  8. sl := []int{0}
  9. inc(&sl)
  10. fmt.Println(sl) // [1 1]
  11. }

run code

其它的诸如string和struct也是一样的方法。

比较绕的方法

如果你知道slice的上限,也可以先申请固定长度后再传入,如:

  1. package main
  2. import "fmt"
  3. func inc(s []int) {
  4. s = append(s, 1)
  5. s[0]++
  6. }
  7. func main() {
  8. s := make([]int, 4)
  9. inc(s[0:0])
  10. fmt.Println(s) // [2 0 0 0]
  11. }

run code

特别要注意struct传参

把struct当函数参数,会复制一份副本,如果struct的值很多将导致一定的性能问题。这也算是go的gotcha。

  1. package main
  2. import "fmt"
  3. type st struct {
  4. a int
  5. b int
  6. }
  7. func copyST(st st) {
  8. st.a++
  9. }
  10. func point2ST(st *st) {
  11. st.b++
  12. }
  13. func main() {
  14. st := st{a: 1, b: 2}
  15. copyST(st)
  16. fmt.Println(st) // {1 2}
  17. point2ST(&st)
  18. fmt.Println(st) // {1 3}
  19. }

run code
如上述代码所示,如果直接传struct作为参数,将会产生st变量副本,如果用pointer就能够复用原变量的内存空间。
注意这里函数参数struct pointer地址并不是原变量的,它是另一块内存地址,只是pointer值是原变量的地址。这也是本文要重点说明的,go无引用类型。

参考

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/127.html
邮箱:glowrypauky@gmail.com
QQ: 892413924