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

主要介绍slice，channel，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原理在其他文章中介绍