go语言中的数据结构

go 评论

数组

初始化

1
2
arr1 := [3]int{1, 2, 3}    // 显示指定数组大小
arr2 := [...]int{1, 2 ,3}  // 使用[...]T声明数组

[...]T初始化数组的方式是go语言提供的一种语法糖，最终也会转化为具体元素数量

在不考虑逃逸分析的情况下，如果数组中元素个数小于等于4个，则所有的变量会直接在栈上初始化；反之如果数组元素大于4个，变量就会在静态存储去初始化然后拷贝到栈上。

访问和赋值

  • 无论是在栈上还是静态存储区，数组在内存中都是一连串的内存空间。我们通过指向数组开头的指针、元素的数量以及元素类型占的空间大小表示数组。
  • 数组和字符串的一些简单的越界错误都会在编译期间发现。如使用整数或常量访问数组，但是如果使用变量去访问数组或字符串时，编译器就无法提前发现错误，此时会在运行时阻止不合法的访问。

    小结

    对数组的访问和赋值同时需要依赖编译器和运行时支持，其大多数操作在编译期间都会转换成直接读写内存，在中间代码生成期间，编译器还会插入运行时方法runtime.panicIndex防止发生越界错误。

    切片

    数据结构

    切片在运行时由reflect.SliceHeader结构体表示，如下：
    1
    2
    3
    4
    5
    type SliceHeader struct {
        Data uintptr  // 指向数组的指针
        Len  int      // 当前切片的长度
        Cap  int      // 当前切片的容量, 即Data数组的大小
    }

    初始化

    有以下三种初始化切片的方式：
    1
    2
    3
    4
    5
    6
    7
    8
    // 1. 通过下标的方式获得数组或切片的一部分
    arr[0:3] or slice[0:3]

    // 2. 使用字面量初始化新的切片
    slice := []int{1, 2, 3}

    // 3. 使用make关键字
    slice := make([]int, 10)
    • 使用下标：使用下标初始化切片不会拷贝原数组或原切片中的数据，它只会创建一个指向原数组的切片结构体，所以修改新切片的数据也会修改原切片。
    • 使用字面量：根据切片中的元素数量对底层数组的大小进行推断并创建一个数组，将字面量元素存储到初始化的数组中，创建一个同样指向相同类型的数组指针，将初始化的数组赋值给指针所在的地址，通过[:]操作获取一个底层使用该地址的切片。

访问元素

切片的操作基本都是在编译期间完成的，除了访问切片的长度、容量或者其中的元素之外，编译期间也会将包含range关键字的遍历转换成形式更简单的循环。

追加和扩容

当切片容量不足时，会调用runtime.growslice进行切片扩容。扩容是为切片分配新的内存空间并拷贝原切片中元素的过程，那么新切片的容量如何确定呢？

  • 如果期望容量大于当前容量的两倍就会使用当前容量
  • 如果当前切片的长度小于1024就会将容量翻倍
  • 如果当前切片的长度大于1024就会每次增加25%的容量，直到新容量大于期望容量

另外上述调用仅会确定切片的大致容量，还需要根据切片中的元素大小进行内存对齐。

拷贝切片

无论是编译期间拷贝还是运行时拷贝，两种拷贝方式都会通过runtime.memmove将整块内存的内容拷贝到目标的内存区域中，相比于依次拷贝元素，runtime.memmove能提供更好的性能。

小结

切片的很多功能都是由运行时实现的，无论是初始化切片，还是对切片进行追加或扩容都需要运行时的支持，需要注意的是在遇到大切片扩容或者复制时可能会发生大规模的内存拷贝，一定要减少类似的操作避免影响程序的性能。

字典

哈希冲突

开放寻址法
拉链法

数据结构

go语言运行时使用了多个数据结构组合表示哈希表，最核心的结构体runtime.hmap如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type hmap struct {
    count     int  // 表示当前哈希表中的元素数量
    flags     uint8
    B         uint8  // 表示当前哈希表持有的buckets数量(都是2的倍数)
    noverflow uint16
    hash0     uint32  // 哈希种子，为哈希函数的结果引入随机性

    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer  // 扩容时用于保存之前buckets字段
    nevacuate  uintptr

    extra *mapextra
}

type mapextra struct {
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    nextOverflow *bmap
}

如上所示哈希表runtime.hmap的桶是runtime.bmap，每一个runtime.bmap都能存储8个键值对。当哈希表中存储的数据过多，单个桶已经装满时就会使用extra.nextOverflow中桶存储溢出的数据。
这两种不同的桶在内存中都是连续的，分别称之为正常桶和溢出桶

初始化

字面量

1
2
3
4
5
hash := map[string]int{
    "1": 2,
    "2": 4,
    "5": 6,
}

使用字面量初始化的过程都会使用go语言中的关键字make来创建新的哈希并通过最原始的[]语法向哈希追加元素，另外最终都是调用runtime.makemap。

读写操作

扩容
在以下两种情况下会进行扩容：

  1. 装载因子已经超过6.5
  2. 哈希使用了太多溢出桶

小结

  • go语言使用了拉链法来解决哈希碰撞的问题实现了哈希表，它的读写等操作都是在编译期间转换成了运行时的函数或方法。哈希在每一个桶中存储键对应哈希的前8位，当对哈希进行操作时，这些tophash就成为可以帮助哈希快速遍历桶中元素的缓存。
  • 哈希表的每个桶都只能存储8个键值对，一旦当前哈希的某个桶超出8个，新的键值对就会存储到哈希的溢出桶中。随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的数量翻倍，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大抖动。

    字符串

    数据结构

    字符串在运行时会使用如下的reflect.StringHeader表示：
    1
    2
    3
    4
    type StringHeader struct {
        Data uintptr  // 指向字节数组的指针
        Len  int      // 数组的大小
    }

    字符串是只读的类型，我们并不会直接向字符串追加元素改变其本身的内存空间，所有字符串上的写入操作都是
    通过拷贝实现的。

解析过程

1
2
3
4
str1 := "this is a string"
str2 := `this is another
string
`

类型转换

  • 当解析和序列化json等数据格式时，经常需要将数据在string和[]byte之间来回转换，而类型转换的开销并没有想象的那么小。
  • 字符串和[]byte中的内容虽然一样，但是字符串的内容是只读的，我们不能通过下标或者其他形式改变其中的数据，而跑[]byte中的内容是可读写的。不过无论从哪种类型转换到另一种都需要拷贝数据，而内存拷贝的性能损耗会随着字符串和[]byte长度的增长而增长。

    小结

    字符串作为只读的数据类型，我们无法改变其本身的结构，但是在做拼接和类型转换等操作时一定要注意性能的损耗，遇到需要极致性能的场景一定要尽量减少类型转换的次数。

HAHADeveloper & Designer

个人简介