GO语言之分析常用类型的数据结构

前言

本文是记录的是"运行态分析常用类型的数据结构"

此文是个人学习归纳的记录，腾讯云独家发布，未经允许，严禁转载，如有不对, 还望斧正, 感谢!

基本数据类型我就不介绍了，感觉挺简单的，没有那个必要

切片 —— slice

切片是什么

go 语言是强类型的编译性的语言，至于这个强类型有多强？你可以下面的两个数组，由于长度不一样，然后它们的类型是不一样，类型限制很严格。

var arr1 [6]int
var arr2 [7]int

在这个前提的下面，go语言的数组和其他语言的数组就不一样了，虽然说强类型的限制可以避免歧义，但在数组的动态扩容方面，就多少有点不方便了，然后就有了切片，切片基于数组，并且切片更像其他语言中的数组，因此我们开发中一般是使用切片，而不是直接使用go语言中的数组，简而言之，切片可以简单理解为其他语言中的数组。

切片的基本使用

切片在运行态的数据结构

运行态就是go程序的代码被操作系统载入内存，并由CPU进行解释和执行

github上的地址放这里了：https://github.com/golang/go/blob/master/src/runtime

切片的定义 具体在 runtime/slice.go里面，如下

type slice struct {
	array unsafe.Pointer  // 指向底层数组的
	len   int             // 切片的长度
	cap   int             // 切片的容积
}

创建

切片的创建有两种方法，第一种是声明式创建，第二种是基于数组直接创建

var slice1 []int  

slice2  := make([]int,8) 

arr := [...]string{"this ","is","Yzz"} // 通过... 的符号可以自动计数
slice3 := arr[0:1]  // 左开右闭   ，可以省略冒号前后的任意一方或者两方的数字，表示数组的极限值

slice4 := [:] // 切片可以基于切片继续创建切片，然后都是指向同一个底层数组

上面的make函数是用来创建复杂类型常用的函数，在创建切片的时候，这玩意，最多可以传入3个值，第一个值为数据类型，第二个的话，如果这时没有第三个参数传入，第二个参数默认就是容积和长度，如果有第三个值传入，那第二个值就是容积，第三个值为初始长度。

并且make创建切片，实际上先隐式创建了一个底层数组，然后因为这个数组没有名字，所以只能被指向这个数组的切片访问，其他东西都访问不了

通过上图，可以看出，通过切片创建切片，实际上这两个切片仍然指向同一个底层数组，当我们操作slice2的时候，会导致slice1得到的数据也发生改变。

还有一个点，也就是上图的案例，通过切片创建切片，slice2切片可以读写slice21到slice3， 甚至在连续用两个append函数之后，还可以修改切片之外的slice4， 但我们当时切分的时候，只希望能读写slice21，slice22 ， slice23 。

解决这个问题也很简单，就是在切分切片的时候，手动指定第三个数字，这样就不会默认用底层数组剩下的做容积了

slice2 := [1:4:3]

效果如下图

切片的扩容

切片扩容的话，主要是通过append函数向切片添加元素的时候，然后大于了容积，然后进行扩容操作的

slice := make([]int,2,0)  // 创建一个长度为0，容积为3的切片，假设指向的底层数组为arr1
slice = append(slice,1)  // 长度为1 ，小于容积，不扩容,arr1
slice = append(slice,2)  //  长度为2 ，等于容积，不扩容,arr1
slice = append(slice,3)  //  长度为3 ，等于容积，不扩容,arr1

slice = append(slice,4)  //  长度为4 ，容积为6，扩容, 底层数组为arr2

扩容的话，会创建一个新的底层数组，这个数组的容积可以大致认为是老数组的两倍，

然后把老数组的内容复制到新的数组里面，然后添加值，创建一个新的切片，因为添加值是在创建新数组之后，所以老数组是没有加上这个值的。

切片小结

• 通过在运行态的结构体的结构，我们可以知道，我们用len()和cap() 计算切片的长度和容积的时间复杂度均为O(1)， 不需要通过遍历切片来求
• 切片的底层是数组，每个切片都保存了当前切片的长度和容积

映射—— map

映射是什么

映射的话，可以类比于Python中的 dict（字典）数据类型，或者说java里面的HashMap，js里面的对象（有一点类似），通常用来处理键值对数据，go语言中的map的底层是用Hash表实现的。

map的结构

具体在runtime/map.go里面

type hmap struct {
	count     int    //表示当前 map 中活动元素的数量（即大小），必须放在第一位（用于 len() 内置函数）
	flags     uint8  // 标志位
	B         uint8   //以 2 为底的桶数的对数，可以容纳至多 loadFactor * 2^B 个元素
	noverflow uint16 //溢出桶的大致数量，详细信息见 incrnoverflow 函数
	hash0     uint32 // 哈希种子

	buckets    unsafe.Pointer // 桶数组，大小为 2^B，可能为 nil（如果 count == 0）
	oldbuckets unsafe.Pointer // 旧的、大小减半的桶数组，仅在扩容时非空
	nevacuate  uintptr        // 迁移进度计数器，表示已迁移的桶数量（小于这个值的桶已经迁移）

	extra *mapextra // 可选字段的指针
}

map的基本用法

map的用法相对简单

map的创建，一种是直接拿值来进行，还有一种是用mack函数，光只是声明是不行的，需要开辟内存。

map1 := map[string]int{
    "言志志":666,
    "腾讯云":666,
}

// 还有一种
map2 := mack(map[string]int,5)
map2["言志志"] = 666   // 有则改之，无则加之
map2["腾讯云"] = 666

用mack的话，指定一个足够大的容量，可以后面内存分配的次数，当然效果微乎其微，不指定也是可以的。

map的基本操作的话，就是有则改之，无则加之，如果是赋值的操作的话，先去找对应的，找不到，就创建一个，找到了就改为新的那个。

删除的话，要用内置关键字delete（），括号里面传要删除的值的键，没有返回值。

查询时，最多可以返回两个值，第一个是值，第二个是布尔类型的变量，如果没找到，就返回这个map类型的零值。

map存值的实际流程

前面介绍了map在运行态的基本结构，其中有一个桶数组指针buckets，这个数组是下面的结构体的数组，下面这玩意其实也是bucket

type bmap struct {
	tophash [8] int8  // 存储hash值的高8位
    data []byte // key value数据，先写全部key，再按顺序记录所有value
    overflow *bmap // 溢出的bucket地址，其实就是相当于链表，指向下一个bmap的
}

然后，如果你看过源码的话，你会发现和上面那玩意不一样，发现实际上是下面的结构。或许你会感到奇怪，这玩意怎么存键和值？

// 这玩意就是存键和值的
type bmap struct {
	tophash [bucketCnt]uint8
}

这是因为我把注释删了，你看不到注释。我来解释一下， 在 bmap 结构体中，按照作用域分的话keys 和 elems 字段并没有明确地定义为独立的字段，而是通过内存布局进行组织。

实际上，在 tophash 数组之后，紧跟着的是键和值的数据，它们是按照键/值对的方式连续存储的。这种方式允许 Go 语言消除由于不同类型的键和值导致的内存对齐问题。例如，对于 mapint64int8 类型的 map，我们可以避免因为 int64 类型的键需要额外的内存对齐而导致的空间浪费。

关于溢出指针 overflow，它也没有被明确地定义为一个字段，而是作为桶数据结构的一部分进行管理。当一个桶中的元素数量超过 bucketCnt（默认为 8）时，会创建一个新的桶，并将超出部分的键值对存放在新的桶中。此时，原桶中的溢出指针就会指向新创建的桶，这种设计方式使得 Go 语言可以更灵活地处理不同类型的键和值，同时还能优化内存使用。

每个bucket可以储存8个键值对，当同一个bucket通过hash运算分配到大于8个键值对的时候，为了消除hash冲突，就会再创建一个bucket，通过overflow用类似链表的方式，将bucket连起来。

扩容过程大概是这样的，先让老指针oldbuckets 指向原来的，然后创建一个两倍大的新的，让buckets 指向，在把老指针oldbuckets指向的搬过去

查

查找的过程在具体的这个结构里面是这样的，先计算传入的键的hash值， 取hash值低位与hmap.B取模来确定bucket的位置，然后再取Hash，在tophash数据中查询，找到了，然后就把值返回去，没找到就继续沿着这个链表找，如果最终都没有找到，那么就返回一个对应类型的零值，注意不会返回nil

字符串

字符串的话，基础操作就不记录了，主要记录一下觉得重要的一些点。

字符串的运行态在runtime/string.go里面

具体结构如下

type stringStruct struct {
	str unsafe.Pointer  // 指向存储地址
	len int                    // 记录字节长度
}

看到上面的结构，应该有些眼熟吧，没错，这玩意比切片的结构就少了个容积，而且这样做还有好处，整个字符串就很轻量，因为只存了一个指针和一个数字。

type slice struct {
	array unsafe.Pointer  // 指向底层数组的
	len   int             // 切片的长度
	cap   int             // 切片的容积
}

因此，字符串转byte切片就比较好处理。

特点

在go语言里面，string使用8比特的集合来存储字符，utf-8编码，存储汉字的话，就将占用多个字节，并且go语言的字符串是不可以修改的。

但这时就有朋友要问了，字符串不是可以拼接吗？

是的，实际上，那是一个新的字符串，在运行态的concatstrings函数里面有讲，通过先计算要拼接的所有字符串的大小，然后创建一个合适的内存，同时创建一个切片，切片和字符串共享内存，然后进行修改。

其实到这里，我感觉还是没搞明白为什么字符串不能修改的原理，它和切片结构类似，但却不能修改，看了一下别的大佬的解释

因为底层是一个[]byte类型的切片，当我们使用下标的方式去修改值，这时候将一个字符内容赋值给byte类型，肯定是不允许的。但是我们可以通过下标的方式去访问对应的byte值。

感觉好像也是这么回事，我们通过下标直接访问的是指针指向的那个切片，赋值的话，赋值不了。

我正在参与2023腾讯技术创作特训营第四期有奖征文，快来和我瓜分大奖！