数组

go的数组与C的数组不同，C的数组名表示第一个元素的地址，go数组是值语义，一个数组名表示整个数组，不是指向第一个元素的指针，一个数组变量被赋值或传递的时候，实际上会复制整个数组，为避免复制可自定义指向数组的指针数组字面值。

  1. b := [2]string{"Penn", "Teller"}         //自己指定长度
  2. b := [...]string{"Penn", "Teller"}         //编译器自动指定长度

数组[]内的长度表达式必须为常数，比如：

  1. var a int
  2. var [a] int // 错误，长度表达式必须为常数

数组的用法：

  1. type Currency int
  3. const (
  4.     USD Currency = iota // 美元
  5.     EUR                 // 欧元
  6.     GBP                 // 英镑
  7.     RMB                 // 人民币
  8. )
  10. symbol := [...]string{USD: "$", EUR: "€", GBP: "￡", RMB: "￥"}
  12. fmt.Println(RMB, symbol[RMB]) // "3 ￥"

数组的元素类型是可以相互比较的，那么数组类型也是可以相互比较的，这时候我们可以直接通过==比较运算符来比较两个数组：

  1. a := [2]int{1, 2}
  2. b := [...]int{1, 2}
  3. c := [2]int{1, 3}
  4. fmt.Println(a == b, a == c, b == c) // "true false false"
  5. d := [3]int{1, 2}
  6. fmt.Println(a == d) // compile error: cannot compare [2]int == [3]int

结构体

  1. // 结构体创建
  2. type Employee struct {
  3.     ID        int
  4.     Name      string
  5.     Address   string
  6.     DoB       time.Time
  7.     Position  string
  8.     Salary    int
  9.     ManagerID int
  10. }
  14. // 结构体访问
  15. var dilbert Employee
  16. dilbert.Salary -= 5000
  17. var employeeOfTheMonth *Employee = &dilbert
  18. employeeOfTheMonth.Position += " (proactive team player)"
  19. // 等价于 (*employeeOfTheMonth).Position += " (proactive team player)"
  21. // 初始化
  22. type Point struct{ X, Y int }
  23. p := Point{1, 2}     // 方式1
  24. p := Point{Y:1}     // 方式2，X自动为0值

匿名成员

只声明一个成员对应的数据类型而不指名成员的名字；这类成员就叫匿名成员。匿名成员的数据类型必须是命名的类型或指向一个命名的类型的指针。下面的代码中，Circle和Wheel各自都有一个匿名成员。我们可以说Point类型被嵌入到了Circle结构体，同时Circle类型被嵌入到了Wheel结构体。

  1. type Point struct {
  2.     X, Y int
  3. }
  5. type Circle struct {
  6.     Point
  7.     Radius int
  8. }
  10. type Wheel struct {
  11.     Circle
  12.     Spokes int
  13. }
  15. // 得益于匿名嵌入的特性，我们可以直接访问叶子属性而不需要给出完整的路径
  16. var w Wheel
  17. w.X = 8            // equivalent to w.Circle.Point.X = 8
  18. w.Y = 8            // equivalent to w.Circle.Point.Y = 8
  19. w.Radius = 5       // equivalent to w.Circle.Radius = 5
  20. w.Spokes = 20

空结构体

什么是空结构体？
就是内容为空的结构体，举例：

  1. type cat struct {}

空结构体大小是多少？如何存储？
举例：

  1. type cat struct{}
  3. func main() {
  4.     c0, c1 := cat{}, cat{}
  5.     fmt.Println(unsafe.Sizeof(c0), unsafe.Sizeof(c1))
  6.     fmt.Printf("%p\n%p\n", &c0, &c1)
  7. }

运行结果：
image.png
说明空结构体大小为 0，且统一使用一个地址。事实上，所有大小为 0 的变量的地址都为同一个，即 runtime/malloc.go中的：

  1. // base address for all 0-byte allocations
  2. var zerobase uintptr

空结构体什么时候使用？
空结构体的主要用途为节约空间，比如用 go map 实现一个类似 set 的结构（go 没有 set）：

  1. m := make(map[int]struct{})
  2. m[1], m[0] = struct{}{}, struct{}{}

slice

slice是一个轻量级的数据结构，由三部分构成：底层数组某个元素的指针、长度和容量。
长度 len 为指针指向的元素到切片指定的尾元素的长度；
长度 cap 为指针指向的元素到数组末尾的长度。

举例：

  1. var arr = [5]int{1, 2, 3, 4, 5}
  3. slice := arr[1:3] // 两边的范围值为左闭右开
  4. // 此时slice底层指针指向数组的第二个元素，len(slice) = 2, cap(slice) = 4
  6. slice1 := slice[1:]
  7. // 此时slice1的指针指向数组的第三个元素，len(slice1) = 1, cap(slice1) = 3

切片的底层结构

  1. type slice struct {
  2.     array unsafe.Pointer
  3.     len   int
  4.     cap   int
  5. }

实例：
make([]byte, 5)
image.png

slice 的创建

根据字面量创建

  1. package main
  3. import "fmt"
  5. func main() {
  6.     s := []int{1, 2, 3}
  7.     fmt.Println(s)
  8. }

通过生成 plan9 汇编分析：go build -gcflags -S main.go
image.png
可以看出 slice 的创建过程为：

  1. 创建一个长度为 3 的数组；
  2. 根据数组创建一个 slice；

    其他方式创建

  • 对已知数组的引用
  • 使用 make 方法，实际调用的是 rumtime/malloc.go 中的 makeslice 方法

    append

    由于底层数组容量有限，使用内置的append增加切片元素时，可能需要重新分配一个更大的底层数组。

测试：

  1. func main() {
  2.     var slice []int
  3.     for i := 0; i < 10; i++ {
  4.         slice = append(slice, i)
  5.         fmt.Printf("%d cap = %d \t%v\n", i, cap(slice), slice)
  6.     }
  7. }
  9. // 运行结果：
  10. // 0 cap = 1       [0]
  11. // 1 cap = 2       [0 1]
  12. // 2 cap = 4       [0 1 2]
  13. // 3 cap = 4       [0 1 2 3]
  14. // 4 cap = 8       [0 1 2 3 4]
  15. // 5 cap = 8       [0 1 2 3 4 5]
  16. // 6 cap = 8       [0 1 2 3 4 5 6]
  17. // 7 cap = 8       [0 1 2 3 4 5 6 7]
  18. // 8 cap = 16      [0 1 2 3 4 5 6 7 8]
  19. // 9 cap = 16      [0 1 2 3 4 5 6 7 8 9]

扩容逻辑

  1. func growslice(et *_type, old slice, cap int) slice {
  2.     ...
  3.     ...
  4.     newcap := old.cap
  5.     doublecap := newcap + newcap
  6.     if cap > doublecap { // 
  7.         newcap = cap
  8.     } else {
  9.         if old.cap < 1024 { // 如果小于 1024 则翻倍
  10.             newcap = doublecap 
  11.         } else {
  12.             // 如果大于 1024 每次扩 1/4
  13.             for 0 < newcap && newcap < cap {
  14.                 newcap += newcap / 4
  15.             }
  16.             // 如果越界
  17.             if newcap <= 0 {
  18.                 newcap = cap
  19.             }
  20.         }
  21.     }
  22.     ...
  23.     ...
  24. }

string

string定义

标准库buildin的描述 ：

  1. // string is the set of all strings of 8-bit bytes, conventionally but not
  2. // necessarily representing UTF-8-encoded text. A string may be empty, but
  3. // not nil. Values of string type are immutable.
  4. type string string

可总结特点如下：

  1. string是一系列字节（byte/unit8）的集合；
  2. string可以为空，但是不能为nil；
  3. string对象不可更改；

    string 底层结构

    1. type stringStruct struct {
    2.  str unsafe.Pointer // 指向一个 byte 数组
    3.  len int
    4. }
    所以 string 类型的大小永远为指针大小加上 int 的大小（在64位计算机下为 8 + 8 = 16）。

    如何获取底层数组长度？

    通过 reflect 包提供的结构：
    1. // StringHeader is the runtime representation of a string.
    2. // It cannot be used safely or portably and its representation may
    3. // change in a later release.
    4. // Moreover, the Data field is not sufficient to guarantee the data
    5. // it references will not be garbage collected, so programs must keep
    6. // a separate, correctly typed pointer to the underlying data.
    7. type StringHeader struct {
    8.  Data uintptr
    9.  Len  int
    10. }
    示例：
    1. func main() {
    2.  s := "hello, 富贵猪"
    3.  // 先转为万能指针 usafe.Pointer 再转为 reflec.StringHeader 指针
    4.  strHeader := (*reflect.StringHeader)(unsafe.Pointer(&s))
    5.  fmt.Println(strHeader.Len)
    6. }

其实使用 builtin 包提供的 len() 就可以获取底层数组长度，这里只是理解一下源码。

为什么 string 不可更改？

为了节约 string 相关操作的成本，因为 string 不可更改，所以 string 对应的底层数据也是不可更改的。所以对应的底层操作就可以简化，比如：

  • 拷贝操作：复制一下底层指针和判断一下长度就行了；

  • 切片操作：复制一下指针和计算一下长度就行了；

    字符串面值

    "hello, world"，将一系列字节序列包含在双引号内就是一个字符串面值。
    image.png
    由于Go源文件默认用UTF-8编码，所以字符串面值可以存放Unicode码点。
    注意：UTF-8中一个中文字符占 3 字节。

    string 遍历

    注意比较两种遍历方式的异同：

    1. func main() {
    2.   s := "hello, 富贵猪"
    3.   for _, v := range s {
    4.       fmt.Printf("%v ", v)
    5.   }
    6.   fmt.Println()
    7.   for i := 0; i < len(s); i++ {
    8.       fmt.Printf("%v ", s[i])
    9.   }
    10. }

    输出：
    image.png
    出现这样结果的原因是：

  • 使用下标遍历时，输出的是 byte 数组每个字节的大小（一个中文 3 字节）。

  • 使用 range 遍历字符串时，在编译时 runtime/uft8.go 中的 utf8 解析器会被调用。

    “” 与 `` 包含的字符串有什么不同？

  • ""包含的字符串面值中，可以用以反斜杠\开头的转义符：

    1. \a      响铃
    2. \b      退格
    3. \f      换页
    4. \n      换行
    5. \r      回车
    6. \t      制表符
    7. \v      垂直制表符
    8. \'      单引号（只用在 '\'' 形式的rune符号面值中）
    9. \"      双引号（只用在 "..." 形式的字符串面值中）
    10. \\      反斜杠
    1. <a name="VqWOv"></a>
    2. ## string 和 []byte
    3. 字符串和字节slice之间可以相互转换：
    4. ```go
    5. s := "abc"
    6. b := []byte(s)
    7. s2 := string(b)

    string 转化为 []byte 是会发生内存拷贝的，理论上任何的强制类型转换都会发生内存拷贝。

bytes 和 strings 包提供的实用函数

  1. func Contains(s, substr string) bool
  2. func Count(s, sep string) int
  3. func Fields(s string) []string
  4. func HasPrefix(s, prefix string) bool
  5. func Index(s, sep string) int
  6. func Join(a []string, sep string) string
  8. func Contains(b, subslice []byte) bool
  9. func Count(s, sep []byte) int
  10. func Fields(s []byte) [][]byte
  11. func HasPrefix(s, prefix []byte) bool
  12. func Index(s, sep []byte) int
  13. func Join(s [][]byte, sep []byte) []byte

string 和 数字

整数转string：

  1. x := 123
  2. y := fmt.Sprintf("%d", x)
  3. fmt.Println(y, strconv.Itoa(x)) // "123 123"
  5. // 转化为不同进制
  6. fmt.Println(strconv.FormatInt(int64(x), 2)) // "1111011"
  7. s := fmt.Sprintf("x=%b", x) // "x=1111011", 还有%d、%o和%x等参数可以用

字符串解析为整数（注意可能发生错误，因为字符串对应的不一定是数字：

  1. x, err := strconv.Atoi("123")             // x is an int
  2. y, err := strconv.ParseInt("123", 10, 64) // base 10, up to 64 bits

string 拼接

当需要拼接少量字符串时，直接使用+号拼接，速度最快。
当需要拼接大量字符串时，使用bytes.buffer，使用缓冲区加快拼接。

  1. var str1 bytes.Buffer
  3. str1.WriteString("hello ")
  4. str1.WriteString("world")
  6. fmt.Println("buffer :", str1.String())

Map

在Go中，map是对一个哈希表的引用：

  • Key：只能是可以比较大小的元素，因为map要判断给定key和已存储key是否相等来确定是否存在哈希表中；
  • Value：可为任意类型；

    map操作

    ```go // 初始化 ages := make(map[string]int)

ages := map[string]int{}

ages := map[string]int{ “alice”: 31, “charlie”: 34, }

// delete delete(ages, “alice”)

// 判断key是否存在 if age, ok := ages[“bob”]; !ok { / … / }

  1. <a name="qATwD"></a>
  2. ## map 的底层结构
  3. go 的 map 底层是对一个使用拉链法的 hashmap 的引用。
  4. ```go
  5. // A header for a Go map.
  6. type hmap struct {
  7.     count     int // 总键值对的数量，即 len()
  8.     flags     uint8
  9.     B         uint8  // buckets 的数量为 2^B
  10.     noverflow uint16 // 溢出的 buckets 数目的近似值; see incrnoverflow for details
  11.     hash0     uint32 // hash seed
  13.     buckets    unsafe.Pointer // 长度为 2^B 的 Buckets 数组，count == 0 则为 nil
  14.     oldbuckets unsafe.Pointer // 扩容时 oldbuckets 数组的指针
  15.     nevacuate  uintptr        // buckets 地址小于该值表示迁移完成
  17.     extra *mapextra // optional fields
  18. }
  20. ...
  21. ...
  23. // A bucket for a Go map.
  24. type bmap struct {
  25.     // tophash 存储哈希值的第一个字节（前八位），每个 bucket 存储 bucketCnt（8）个键值对。
  26.     // 如果 tophash[0] < minTopHash, tophash[0] 表示该桶以搬迁完毕。
  27.     tophash [bucketCnt]uint8
  29.     // tophash 后面的是 key 数组和 elem 数组
  30.     // NOTE: 使用 key/key/key.../elem/elem/elem...的格式存储
  31.     // 而不是 key/elem/key/elem/... 
  32.     // 这样可以节约字节对齐的开销，比如 map[int64]int8
  34.     // 最后有一个溢出指针
  35. }

结构示意图
image.png

注意事项

为什么不能对map的元素进行取址？

原因是map可能随着元素数量的增长而重新分配更大的内存空间，从而可能导致之前的地址无效。

为什么map每次遍历的顺序都不一致？

这是故意的，每次都使用随机的遍历顺序可以强制要求程序不会依赖具体的哈希函数实现。因为每次扩容、缩容的时候可能发生rehash，导致原有的次序改变，所以这种次序是不可靠的，go干脆就故意随机每次的遍历顺序来避免程序员利用这个不可靠的点。

想要有序的遍历，参考如下实现：

  1. import "sort"
  3. names := make([]string, 0, len(ages))
  4. for name := range ages {
  5.     names = append(names, name)
  6. }
  8. sort.Strings(names)
  10. for _, name := range names {
  11.     fmt.Printf("%s\t%d\n", name, ages[name])
  12. }

map类型的零值？
map类型的零值是nil，也就是没有引用任何哈希表。
注意：在使用map读和存的时候，必须保证其不为空（保证底层引用了哈希表）

map 初始化

使用 make 初始化

  1. // makemap implements Go map creation for make(map[k]v, hint).
  2. // If the compiler has determined that the map or the first bucket
  3. // can be created on the stack, h and/or bucket may be non-nil.
  4. // If h != nil, the map can be created directly in h.
  5. // If h.buckets != nil, bucket pointed to can be used as the first bucket.
  6. func makemap(t *maptype, hint int, h *hmap) *hmap {
  7.     mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
  8.     if overflow || mem > maxAlloc {
  9.         hint = 0
  10.     }
  12.     // initialize Hmap
  13.     if h == nil {
  14.         h = new(hmap)
  15.     }
  16.     h.hash0 = fastrand()
  18.     // Find the size parameter B which will hold the requested # of elements.
  19.     // For hint < 0 overLoadFactor returns false since hint < bucketCnt.
  20.     B := uint8(0)
  21.     for overLoadFactor(hint, B) {
  22.         B++
  23.     }
  24.     h.B = B
  26.     // allocate initial hash table
  27.     // if B == 0, the buckets field is allocated lazily later (in mapassign)
  28.     // If hint is large zeroing this memory could take a while.
  29.     if h.B != 0 {
  30.         var nextOverflow *bmap
  31.         h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
  32.         if nextOverflow != nil {
  33.             h.extra = new(mapextra)
  34.             h.extra.nextOverflow = nextOverflow
  35.         }
  36.     }
  38.     return h
  39. }

make(map[k]v, hint) 示意图
image.png

使用字面量初始化

使用字面量初始化的步骤为：

  1. 创建一个对应大小的 map；
  2. 将字面量值依次赋值给 map；
  • 元素少于25时转化为简单赋值

image.png

  • 元素大于25时转化为循环赋值

image.png

map 的访问步骤

  1. 使用 key 和 hash0 通过哈希函数得到哈希值；
  2. 计算在哪个 bucket：例如 m.B == 3，那么说明有 2^3 个 buckets（编号为0~7），使用哈希值的后 3 位即可确定在哪个桶，例如后三位为 010，就说明桶号为 2；
  3. 计算在桶中的位置：取哈希值的前八位得到 tophash ；
    1. 如果该桶或对应的溢出桶存在匹配了 tophash 且对应的 key 为访问的 key 的值，则返回 key 对应的 value；
    2. 如果不存在该 tophash 或者不存在对应的 key，则表示 map 中没有这个元素；

      map 的写入步骤

      和 map 的访问步骤类似，区别是如果不存在该 key，则直接添加一个键值对。

      map 的扩容问题

      为什么 map 需要扩容？

      溢出桶过多，使得 kv 操作效率大幅降低，此时需要进行扩容操作。

      map 何时扩容？

      ```go func mapassign(t maptype, h hmap, key unsafe.Pointer) unsafe.Pointer { … // If we hit the max load factor or we have too many overflow buckets, // and we’re not already in the middle of growing, start growing. if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again } … }

… func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) } … func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { // 当桶总数 < 2 ^ 15 时，如果溢出桶总数 >= 桶总数，则认为溢出桶过多。 // 当桶总数 >= 2 ^ 15 时，直接与 2 ^ 15 比较，当溢出桶总数 >= 2 ^ 15 时， // 即认为溢出桶太多了。 if B > 15 { B = 15 }
return noverflow >= uint16(1)<<(B&15) }

  1. 分析源码可知，两种情况下 map 需要扩容：
  3. 1. 每个哈希值对应的 key 大于某个固定值（装载因子超过6.5）；
  4. 1. 溢出桶过多，溢出桶数量大于普通桶；
  5. <a name="p2esf"></a>
  6. ### map 怎样扩容？
  7. ```go
  8. func hashGrow(t *maptype, h *hmap) {
  9.     bigger := uint8(1) // h.B 如果 +1，则 buckets 数量翻倍
  11.     // 装载因子不超过 6.5 进行等量扩容
  12.     if !overLoadFactor(h.count+1, h.B) {
  13.         bigger = 0
  14.         h.flags |= sameSizeGrow
  15.     }
  16.     oldbuckets := h.buckets // oldbuckets 指向原来的桶数组
  17.     newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
  19.     flags := h.flags &^ (iterator | oldIterator)
  20.     if h.flags&iterator != 0 {
  21.         flags |= oldIterator
  22.     }
  23.     // commit the grow (atomic wrt gc)
  24.     h.B += bigger
  25.     h.flags = flags
  26.     h.oldbuckets = oldbuckets
  27.     h.buckets = newbuckets
  28.     h.nevacuate = 0 // 搬迁进度为0
  29.     h.noverflow = 0 // 溢出桶为0
  31.     // 更新溢出桶
  32.     if h.extra != nil && h.extra.overflow != nil {
  33.         // 老的溢出桶不为空说明之前的扩容还未搬迁完成
  34.         if h.extra.oldoverflow != nil {
  35.             throw("oldoverflow is not nil")
  36.         }
  37.         h.extra.oldoverflow = h.extra.overflow
  38.         h.extra.overflow = nil
  39.     }
  40.     if nextOverflow != nil {
  41.         if h.extra == nil {
  42.             h.extra = new(mapextra)
  43.         }
  44.         h.extra.nextOverflow = nextOverflow
  45.     }
  47.     // 真正的元素搬迁发生在 growWork() 和 evacuate().
  48. }

map 扩容的方式有两种：

  1. 等量扩容：count 不多但是溢出桶太多（情况可能是原来 count 多但是 delete 了大量元素），该情况使用等量的桶来作为存储的新桶；
  2. 翻倍扩容：装载因子超过 6.5；

注意：hashGrow中只分配了新桶，并没有操作迁移旧桶的数据，go map 采用的是渐进式扩容方式，如果旧桶中的数据被操作时，才将旧桶的数据迁移到新桶。

渐进式扩容

比如在 map 的 assign （修改/添加）操作时

  1. func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  2.     ...
  3. again:
  4.     bucket := hash & bucketMask(h.B) // 获取当前桶的编号
  5.     if h.growing() { // 如果 map 正在扩容搬迁
  6.         growWork(t, h, bucket) // 
  7.     }
  8.     ...
  9. }
  11. ...
  12. func growWork(t *maptype, h *hmap, bucket uintptr) {
  13.     // 保证当前使用的桶的旧桶迁移完毕
  14.     evacuate(t, h, bucket&h.oldbucketmask())
  16.     // 保证每次操作至少搬运一个桶
  17.     if h.growing() {
  18.         evacuate(t, h, h.nevacuate)
  19.     }
  20. }

参考资料

  1. https://zhuanlan.zhihu.com/p/144923309 -string 和 []byte 转换
  2. https://coding.imooc.com/learn/list/576.html - 慕课网 Moody
  3. https://www.golangroadmap.com/question_bank/golang.html