golang基础数据结构的底层原理（slice，channel，map）

矫情吗；* 2022-10-16 00:43 133阅读 0赞

golang其他数据类型如Int，float等，跟大多数编程语言类似，

主要介绍slice，channel，map的底层实现逻辑：

**目录**

一：slice

底层数据结构：

slice的创建

slice的追加

slice的拷贝

二：channel

底层数据结构

channel创建

向channel写数据的过程

从一个channel读数据简单过程

关闭channel

channel导致panic的场景

常见用法

三：map

底层结构

map的创建

map解决冲突的方法

map的扩容

map查找过程

map插入过程

map拓展知识（重要）

--------------------

## 一：slice ##

Slice又称动态数组， 依托数组实现， 可以方便的进行扩容、 传递等， 实际使用中比数组更灵活。

### 底层数据结构： ###

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

### slice的创建 ###

创建切片的过程就是初始化该结构的过程。创建切片的方式有3种：

（1）sliceOne := make(\[\]int, 0, 10)

通过Make创建，可指定创建的切片的长度和容量。如果不指定容量，那么容量就等于长度。

（2）sliceTwo := sliceOne\[2:4\]

这种方式是基于其他切片或数据创建容量，长度为创建切片是指定的结束-起始位置, = 4-2=2；容量就等于切片的容量-起始位置=10-2=8.且两个切片共享同一个数据区；

（3）sliceThree := \[\]int\{1,2\}

这种方式直接字面量创建，长度和容量都等于其元素个数。

### slice的追加 ###

使用append向Slice追加元素时， 如果Slice空间不足， 将会触发Slice扩容， 扩容实际上重新一配一块更大的内存， 将原Slice数据拷贝进新Slice， 然后返回新Slice， 扩容后再将数据追加进去。  
扩容容量的选择遵循以下规则：  
如果原Slice容量小于1024， 则新Slice容量将扩大为原来的2倍；  
如果原Slice容量大于等于1024， 则新Slice容量将扩大为原来的1.25倍；

### slice的拷贝 ###

使用copy()内置函数拷贝两个切片，但是需要注意的是，copy 会将源切片的数据逐个拷贝到目的切片指向的数组中， 拷贝数量取两个切片长度的最小值。copy不会扩容，只有append才会扩容。  
基于以上切片特性。编程过程需要注意：  
1.创建切片时可跟据实际需要预分配容量， 尽量避免追加过程中扩容操作， 有利于提升性能；  
2.切片拷贝时需要判断实际拷贝的元素个数  
3.谨慎使用多个切片操作同一个数组， 以防读写冲突

## 二：channel ##

channel是go语言协程间通信的管道。channel可用于协程同步，也可以协程间可以传递各种消息数据。

### 底层数据结构 ###

type hchan struct {
    	qcount uint
    	dataqsiz uint
    	buf unsafe.Pointer
    	elemsize uint16
    	closed uint32
    	elemtype *_type
    	sendx uint
    	recvx uint
    	recvq waitq
    	sendq waitq
    
    	lock mutex
    }

channel底层数据结构有一个环形队列指针   buf   
以及环形队列存储的数据类型和数据结构大小。  elemsize,elemtype  
，还有标识环形队列指针读写位置的标记。sendx,recvx  
等待读写的两个goroutine队列。 recvq,sendq  
还有互斥锁。 lock

其中环形队列是用来存储传递的消息  
两个gotoutine队列是用来存储和唤醒被该channel阻塞的队列。  
数据类型和数据大小是用来读写消息时用于计算便宜量。

### channel创建 ###

channel初始化的过程时用make初始化，初始化的过程也就是初始化channel底层数据结构的过程；

ch := make(chan int, 1)

### 向channel写数据的过程 ###

1. 如果等待接收队列recvq不为空， 说明缓冲区中没有数据或者没有缓冲区， 此时直接从recvq取出G,并把数据写入， 最后把该G唤醒， 结束发送过程；  
2. 如果接受队列recvq为空，且缓冲区中有空余位置， 将数据写入缓冲区， 结束发送过程；  
3. 如果接受队列recvq为空，缓冲区中没有空余位置， 将待发送数据写入G， 将当前G加入sendq， 进入睡眠， 等待被读goroutine唤醒；

### 从一个channel读数据简单过程 ###

1. 如果等待发送队列sendq不为空， 且没有缓冲区， 直接从sendq中取出G， 把G中数据读出， 最后把G唤醒， 结束读取过程；  
2. 如果等待发送队列sendq不为空， 此时说明缓冲区已满， 从缓冲区中首部读出数据， 把G中数据写入缓冲区尾部， 把G唤醒， 结束读取过程；  
3. 如果缓冲区中有数据， 则从缓冲区取出数据， 结束读取过程；  
4. 将当前goroutine加入recvq， 进入睡眠， 等待被写goroutine唤醒；

### 关闭channel ###

关闭channel时会把recvq中的G全部唤醒， 返回Nil。 把sendq中的G全部唤醒， 让这些G panic。

### channel导致panic的场景 ###

1. 关闭值为nil的channel  
2. 关闭已经被关闭的channel  
3. 向已经关闭的channel写数据

### 常见用法 ###

1.函数传参限制为单向channel

2.select

3.range

## 三：map ##

map底层使用哈希表来实现的，哈希过程产生冲突使用的冲突解决办法是链地址法。  
除此之外常见的冲突解决办法还有：开放寻址法，链地址法，再次哈希法，创建一个公共溢出区等几种方法。  
python中的字典底层依靠哈希表(hash table)实现, 使用开放寻址法解决冲突,  
java和go都采用链地址法来解决哈希冲突。

### 底层结构 ###

type hmap struct {
    	count int // 当前保存的元素个数
    	...
    	B uint8 // 指示bucket数组的大小
    	...
    	buckets unsafe.Pointer // bucket数组指针， 数组的大小为2^B
    	...
    }

go的哈希表实现底层数据结构中有一个count标识当前元素个数，一个B成员标识桶的个数，还有一个buckes是一个指针指向桶数组。

而桶的底层数据结构：

type bmap struct {
    	tophash [8]uint8 //存储哈希值的高8位
    	data byte[1] //key value数据:key/key/key/.../value/value/value...
    	overflow *bmap //溢出bucket的地址
    }

tophash是个数组用来存放键的哈希值的高8位，，一个data成员用来存放value，还有一个Overflow成员用来指向溢出的桶的地址。

### map的创建 ###

1.make方式创建

hash := make(map[string]int, 10)

10指定按10个count创建hash，此时的B成员标识桶的个数，会根据10个count来划分桶的个数。

如果不预先指定count，那么按照0个来划分桶的个数，后续往map写数据会自动进行扩容。

2.字面量方式创建

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

count个数就是字面量的个数。

### map解决冲突的方法 ###

使用链地址法：当多个键被哈希到了同一个bucket时，也就是产生了哈希冲突。由于每个bucket可以存放8个键值对， 所以同一个bucket存放超过8个键值对时就会创建一个桶， 用链表的方式将bucket关联起来。

### map的扩容 ###

因为不能放任它无休止的冲突下去，无休止冲突的话会影响读写性能，于是引入了负载因子的概念，计算方式为：

负载因子=键数量/桶数量，当负载因子达到指定的值就会进行扩容操作。

go语言中的哈希表触发扩容的条件有两个：

1. 负载因子 > 6.5时， 也即平均每个bucket存储的键值对达到6.5个

2. overflow数量 > 2^15时， 也即overflow数量超过32768时

第一种情况负载因子过大，使用增量扩容。  
当负载因子过大时， 就新建一个bucket， 新的bucket长度是原来的2倍， 然后旧bucket数据搬迁到新的bucket。  
考虑到如果map存储了数以亿计的key-value， 一次性搬迁将会造成比较大的延时， Go采用逐步搬迁策略， 即每次访问map时都会触发一次搬迁， 每次搬迁2个键值对。

第二种overflow数量过多，使用等量扩容。  
所谓等量扩容， 实际上并不是扩大容量， buckets数量不变， 重新做一遍类似增量扩容的搬迁动作， 把松散的键值对重新排列一次， 以使bucket的使用率更高， 进而保证更快的存取。 在极端场景下， 比如不断的增删， 而键值对正好集中在一小部分的bucket， 这样会造成overflow的bucket数量增多， 但负载因子又不高， 从而无法执行增量搬迁的情况。

### map查找过程 ###

1. 跟据key值算出哈希值  
2. 取哈希值低位与hmpa.B取模确定bucket位置  
3. 取哈希值高位在tophash数组中查询  
4. 如果tophash\[i\]中存储值也哈希值相等， 则去找到该bucket中的key值进行比较  
5. 当前bucket没有找到， 则继续从下个overflow的bucket中查找。  
6. 如果当前处于搬迁过程， 则优先从oldbuckets查找

### map插入过程 ###

1. 跟据key值算出哈希值  
2. 取哈希值低位与hmap.B取模确定bucket位置  
3. 查找该key是否已经存在， 如果存在则直接更新值  
4. 如果没找到将key， 将key插入

### map拓展知识（重要） ###

go语言的map数据结构并不是并发安全的。想要并发安全的使用map结构。  
通常由几种方式：  
1.为map加读写锁，  
2.使用concurrent-map（开源库）  
3.使用sync.map

三者的区别在于第一种是为整个map加锁，加锁粒度较大。影响性能。  
第二个使用开源库concurrent-map，原理是对map分段加锁。加锁粒度相对减少，性能相对第一个有所提高。  
第三种是go1.9引入的官方库，  
使用了空间换时间策略，通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。 通过引入两个map将读写分离到不同的map，其中read map提供并发读和已存元素原子写，而dirty map则负责读写。 这样read map就可以在不加锁的情况下进行并发读取,当read map中没有读取到值时,再加锁进行后续读取,并累加未命中数,当未命中数大于等于dirty map长度,将dirty map上升为read map。  
所以具体使用哪种并发安全的map，根据实际情况而定。  
如并发不是很高，为了避免并发冲突可简单使用map+rwmature.  
如读操作原因大于写操作，且写操作大都是插入Map，那用sync.map更好。  
如果是需要维护一段内存映射表，那么使用分段map性能更高。

**sync.map原理在其他文章中介绍**