golang学习笔记（一）

发表于 更新于 分类于 ，

看完pureWhite大哥的golang课程一，简单记录一些笔记挖一些坑，再留一点坑以后有空了填，
顺便推荐一下pureWhite大哥推荐的golang学习博客嘿嘿 https://qcrao.com/

一、slice and array

slice的结构

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

slice是一个结构体，包含array指针
当slice或者array作为函数参数调用时，slice的性能更好（golang函数参数传递都为值传递，slice传指针，需要copy的内容少，array反之）

挖几个坑

for range的问题

https://juejin.cn/post/7120078796845219871
我是这么理解这个坑的，for k,v := range a 的时候，value的内存空间都是同一个，值为a中元素的拷贝，那么如果a中元素为数组，只会把这个数组不停往value里填，但内存空间是不变的，data append的时候，首先会将array转成slice，经过自己的实验，发现slice的array指针地址会直接赋值为array的地址，那么append之后，这些slice中的array指针地址都是同一个
如果a中元素为slice，那么会把slice赋值给value，data append的时候不用进行类型转换，会直接赋值，那么data中的slice中的array指针都是各自的，不会出现指向同一块的情况。

什么时候用array

这是pureWhite大哥在某一个课程中留下来的思考题，出于本能（坏习惯哈哈）想了一会儿没想出答案就去搜了一下，发现并没有直接的答案，不过看到一个提示，array的内存空间是固定的，不会像slice一样，经常扩容，产生内存碎片。那我感觉答案有点呼之欲出了，在明确需要的数组长度时，并且不需要进行数组的值传递，我们是可以使用array来提升内存利用率的
不过感觉还是不够清晰完整，mark一下先吧

slice的扩容机制

pureWhite大哥帮我们找到了明确的源码，长度小于1024的时候是成倍扩容，大于1024的时候是1.25倍扩容，至于为什么是1.25，我想（pureWhite大哥也提到了）是因为这是空间冗余和扩容频率的一个平衡点，经过大量实验得出的。

slice的效率问题

使用slice的时候，如果能定容和定长，直接取下标内存赋值，显然是最快的

slice作为函数参数调用的坑

这里记住一个点就行，就是slice在扩容的时候，会重新分配内存空间，而不是在原来的内存空间后面加内存空间，所以如果你想传一个slice到函数里头，并且在函数里面修改的话，要注意扩容这个特性，避免修改失效

slice初始化

var s []int 这种初始化方式，s是一个null， s := []int{} 这种初始化，s是[]

一个bce(Bounds Checking Elimination)的小技巧

pureWhite大哥教给我们的，利用编译器优化机制做的一个优化

1
2
3
4
5
6
7
func bce(s []int){
    _ = s[3]
    i := 0
    i = i + s[0]
    i = i + s[1]
    i = i + s[2]
}

在上面的代码中，如果有办法让编译器知道下标为3不会越界，它就不会在下面访问0，1，2下标的时候去判断越界

tips: go tool compile -S a.go 获得汇编结果

Map

Map的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// A header for a Go map.
type hmap struct {
    // 元素个数，调用 len(map) 时，直接返回此值
	count     int
	flags     uint8
	// buckets 的对数 log_2
	B         uint8
	// overflow 的 bucket 近似数
	noverflow uint16
	// 计算 key 的哈希的时候会传入哈希函数
	hash0     uint32
    // 指向 buckets 数组，大小为 2^B
    // 如果元素个数为0，就为 nil
	buckets    unsafe.Pointer
	// 扩容的时候，buckets 长度会是 oldbuckets 的两倍
	oldbuckets unsafe.Pointer
	// 指示扩容进度，小于此地址的 buckets 迁移完成
	nevacuate  uintptr
	extra *mapextra // optional fields
}

直接照搬的qcrao大哥的代码

坑点

我觉得需要业务使用重点记的只有flags，标志map的读写问题，如果有并发写或者并发读写，会直接引发panic（搜了一下golang不支持并发读写的原因是，认为去加锁去支持的话，会降低性能，而大部分场景也不需要，所以直接抛出panic，如果实在需要，可以自己用锁实现或者用go1.9版本引入的sync.map）
其他的跟上层使用关系不大？（暂时是这么认为的，如果以后有这方面的优化或者踩坑，再来改改）

bucket的数据结构

1
2
3
4
5
6
7
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

出于内存和性能的考虑（猜的，mark一下），开发者们将存储kv的结构设计成了一个bucket，每个bucket可以放8个kv，放不下了会像链表一样往后再加个overflow的bucket
细节不讲太多了，有需要的可以直接看这篇 https://qcrao.com/post/dive-into-go-map/

map的创建

分配内存（设置B的大小） + 设置哈希函数（根据定义的类型来获取）

坑点

map创建完之后是一个指针，任何传递都是指针地址传递（函数调用时修改会直接影响实参），如果需要拷贝一份，那么得自己实现浅拷贝和深拷贝

map的赋值

这里只做概括，细节可以看qcrao大哥的文章

Q: key是如何对应到某个bucket的呢
A: key值通过哈希函数哈希之后获得一个64位二进制数，取后B位（B在上面map的结构体里），找到对应的bucket，比如 B为3，哈希值后3位为010，则放到2号bucket，101放到5号bucket

Q: 那之前说bucket可以存至少8个key，那key和bucket内部的内存是如何对应的呢
A: 哈希值的前8位和bucket中的topbits一一比较，如果发现有对得上的，再用key值和bucket中已经存在的key2比较，如果相等，说明key的位置就找到了，如果不相等，则一直往下找（包括overflow bucket），如果都不存在，那么直接找第一个空位往里填就行了

map的读取和遍历

key值对应的部分在赋值部分讲过了，遍历稍微特殊一点，因为map内部的kv完全是无序的，即使在扩容之前保持了一定的结构，在扩容之后结构也会完全打乱，而设计Go的大叔们不想我这样的新手程序猿进入这种误区，所以就在遍历的时候，完全按照随机顺序遍历了

map的删除

这个和写入类似，不细讲了

map的扩容

扩容时机

有两种扩容方式

等量扩容

如果map里经常有写和删的操作，那么容易造成overflow buckets过多的情况，比如加进来9个key正好都在一个bucket里，那么就会多一个overflow，这时候再把原bucket里的8个数删光，那就白白多一个bucket的检索时间，浪费效率，简单来说就是bucket里的内容太稀疏了，所以需要等量的bucket重新刷一遍，让key密集一点

两倍扩容

buckets内容太挤了，存储的key值数量太多，接近上限，会影响查找和插入效率，所以需要扩容，这个时候是真的容量不够，需要再加一倍的量，所以采取的是两倍扩容

扩容方式

概括一下流程，map对象里的oldBuckets指针指向原buckets指针，重新申请buckets的内存空间，再把oldBuckets里的内容逐渐往buckets里迁，每次迁移一个bucket
迁移有几个细节

  1. 新bucket和老bucket的对应，等量扩容是一一对应的，这个非常好理解，只要把overflow bucket的内容缩一遍就达到目的了，但是两倍扩容的话，则是一对二，我们可以回到key值和bucket对应的那个部分，我们取了key值的哈希值的后B位，不难得知，两倍扩容之后，我们应该取B+1位，所以原来的bucket也会多对应一个，比如010这个bucket会对应1010和0010这两个桶，这样每个桶都有自己对应的两个桶且不重复
  2. 迁移的时候读取，会优先读新bucket，按照map的结构体里的nevacuate这个参数，我们是可以知道现在的迁移进度的，也就是可以知道现在读的这个bucket有没有迁移完成，如果没有迁移完成，那么就会回到老bucket里面去读
  3. 迁移的时候写入，这个比读要特殊一点，毕竟写老bucket是没有任何意义的，而直接写新bucket，可能会和迁移过程冲突，所以要先等要写入的bucket先迁移完成，再往里写
  4. 迁移的时候遍历，这个和读取类似
  5. 迁移的时候删除，和写入类似

额外的小坑

  1. delete map中的元素之后，map不会自动缩容，这导致map会一直占用一台机器的内存，直到它不再使用，被垃圾回收，至于为什么，mark一下qaq
  2. NaN作为key插入map的时候，无法获取其value，因为NaN != NaN，而它在遍历的时候会被找出来，并且可能会被找出来多个

结语

哎这部分先到这吧，光是学这两个还算简单的类型，背后都挖出这么多东西，想要完整的掌握，是需要长时间的积累的，但我现在优先要准备面试，所以没办法这么细地看这些东西，等有了offer之后，一定潜心研究研究，现在先过一遍别人总结的坑点吧～