Golang data structure

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

common structure

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

string

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

slice

特点

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

compare to array

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

原理

实际是一个runtime.slice的struct
包含信息：len,cap和array(指向真正存储数据的数组指针)

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

可能踩坑

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

package main
import "fmt"
func main() {
    s := make([]int, 4)
    s1 := s[0:2]
    s2 := s[2:]
    s1[0] = 1
    s2[0] = 2
    fmt.Println(s, s1, s2) // [1 0 2 0] [1 0] [2 0]
}

run code

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

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

run code

struct

特点

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

empty struct

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

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

package main
import (
    "fmt"
    "unsafe"
)
func main() {
    var s = make([]struct{}, 100)
    fmt.Println(unsafe.Sizeof(s)) // 24
    s = append(s, make([]struct{}, 10)...)
    fmt.Println(unsafe.Sizeof(s)) // 24
}

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

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

package main
import (
    "fmt"
    "sync"
)
func main() {
    var wg sync.WaitGroup
    sig := make(chan struct{})
    wg.Add(1)
    go func() {
        select {
        case <-sig: // wait for a sig comming
        }
        wg.Done()
    }()
    close(sig)
    wg.Wait()
    fmt.Println("done")
}

run code

为啥empty struct不占空间

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

map

原理

指向runtime.hmap的struct指针。

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

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

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

There is no reference type in golang.

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

先拿map来举例

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

package main
import "fmt"
func replace(m map[int]int) {
    m[0]++
}
func main() {
    hm := map[int]int{}
    replace(hm)
    fmt.Println(hm) // map[0:1]
}

run code

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

package main
import "fmt"
func replace(m map[int]int) {
    m = map[int]int{1: 1}
}
func main() {
    hm := map[int]int{}
    replace(hm)
    fmt.Println(hm) // map[]
}

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

再来瞧瞧slice

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

package main
import "fmt"
func inc(s []int) {
    s[0]++
}
func main() {
    sl := []int{0}
    inc(sl)
    fmt.Println(sl) // [1]
}

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

package main
import "fmt"
func inc(s []int) {
    s = append(s, 1)
    s[0]++
}
func main() {
    sl := []int{0}
    inc(sl)
    fmt.Println(sl) // [0]
}

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

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

传递slice pointer

用指针，如：*[]int

package main
import "fmt"
func inc(s *[]int) {
    *s = append(*s, 1)
    (*s)[0]++
}
func main() {
    sl := []int{0}
    inc(&sl)
    fmt.Println(sl) // [1 1]
}

run code

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

比较绕的方法

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

package main
import "fmt"
func inc(s []int) {
    s = append(s, 1)
    s[0]++
}
func main() {
    s := make([]int, 4)
    inc(s[0:0])
    fmt.Println(s) // [2 0 0 0]
}

run code

特别要注意struct传参

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

package main
import "fmt"
type st struct {
    a int
    b int
}
func copyST(st st) {
    st.a++
}
func point2ST(st *st) {
    st.b++
}
func main() {
    st := st{a: 1, b: 2}
    copyST(st)
    fmt.Println(st) // {1 2}
    point2ST(&st)
    fmt.Println(st) // {1 3}
}

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