GO语言面试问题

Go的chan关闭原则

• 不要在数据接收方或者在有多个发送者的情况下关闭通道
• 不要关闭已关闭的通道

常见的形式：
（1）多消费者，单生产者
生产者结束后可关闭chan
（2）单消费者，多生产者
消费者消费完之后发信号告知生产者结束。
（3）多消费者，多生产者
通过信号通道告知生产者和消费者结束

func consumer(wg ) {
    for i:=0; i<n; i++ {

    }
}

如何防止协程泄露

如何产生的泄露？

协程终止的三个条件：

1. 当一个协程完成他的工作
2. 由于发生了没有处理的错误
3. 有其他的协程告诉他终止

如果上述三个条件都没有满足，则会产生协程泄露。

协程泄露的危害

如果协程发生泄露，会导致GC无法回收协程。直至内存占满后发生系统崩溃。是个很严重的事情。

协程泄露的一般场景：

1. 无缓冲chan只写不读
2. 无缓冲chan只读不写
3. 协程内死循环
4. 协程内发生阻塞，如select未命中也无default。

如何检测呢？通过pprof。

怎么防止产生泄露？

1. 创建协程时就要想好协程如何结束
2. 使用channel时要考虑到如果channel阻塞时的行为
3. 实现循环语句时主要退出条件，避免死循环。

   如果协程内用到了chan，那么最好能在退出前关闭这个chan或者用select的default。

数组和切片

数组是分配的连续内存空间，大小和类型一致。
切片是Go内设计的一个结构体:

• 数组是可以比较的，切片不可比较。
• 数组长度初始化时已确定，切片的长度会变化。
• 切片可以通过append追加元素，如果超过len则会创建新的Slice并且把旧值拷贝给新的切片。会有一定的开销。这也是为什么用append会有返回值。
• Slice的扩容是按2的指数扩容的，申请的cap会按照最小的2^n分配。

map

map结构体是Go内部的一个实现，结构如下：

对结构体的理解，可以从使用case去分析。

初始化map

m := make(map[int]int, 0)

• 初始化指定len=0，只会初始化hmap结构，不会初始化buckets。buckets的初始化会延迟到赋值时。
• 初始化指定len=3，也只会初始化hmap结构，并不会初始化buckets。因为在makemap函数内会通过overLoadFactor获取h.B,值为0则延迟初始化buckets.
• 初始化指定len=14，h.B值为1，会初始化2个Bucket。此时不会有溢出指针。当h.B>=4时，会初始化溢出指针。

func overLoadFactor(count int, B uint8) bool {
    return count > 8 && uintptr(count) > 13*(1<<B/2)
}

Q：为什么h.B>=4时才会有溢出指针呢？溢出指针的作用是什么？
A：
（1）为什么h.B>=4时才会有溢出指针呢？（如果理解的没错的话）是为了防止浪费内存空间。
在map的注释当中，有这么个表格：

如果loadFactor太大，会有太多的溢出指针。太小，会浪费很多内存空间。
（2）溢出指针的作用是什么呢？
一个Bucket只能存放8个k/v，如果命中了同一个Bucket但是此时k/v已满，那么就可以通过溢出指针的方式链接。

map的插入

m := make(map[int]int, 0)
m[1] = 1

map的插入操作很简单，在底层又是做了些什么呢？

1. 计算key的hash, 设置h.flags ^= hashWriting
2. 如果bucket为nil，则初始化。再通过hash找到对应的Bucket：bucket := hash & 1<<b.B-1
3. 找到Bucket后，计算hash的的高8位：top = tophash(hash). 这个top对应的就是map结构图的key hash.
4. 遍历tophash的key hash，和新插入的top比较。这里的操作会复杂一点，因为还可能涉及到更新等，具体详细步骤如下：
   （1）如果找到空的待插入位置，先标记。后续如果没有相同的key则做插入。
   （2）如果key已存在，则比较val。val不同则更新，否则不处理。
   （3）如果在这个bucket没找到相同的key，还会继续遍历溢出指针，做相同的操作。直到确认key不存在并且找到可插入位置则插入。
   （4）如果把所有的Bucket都已经遍历完，依然没有找到可插入位置，则从extra.nextoverflow新分配一个Of Bucket链接到溢出指针，并且插入key。
   （5）重置h.flags &^= hashWriting, 这个标志的作用是为了防止并发操作map.

func tophash(hash uintptr) uint8 {
    top := uint8(hash >> 24)
    if top < minTopHash { //minTopHash=5
        top += minTopHash
    }
    return top
}

这里有3个情况未说明：（1）如果发现tophash对应的key已经被删除了怎么处理？（2）如果nextoverflow已经为空了怎么办？（3）如果map需要扩容怎么办？
（1）如果发现tophash对应的key已经被删除了怎么处理？

func isEmpty(x uint8) bool {
    return x <= emptyOne //emptyOne=1
}

在map中如果key被删除，并不会立即去置空该位置的k/v。而是标记为emptyOne。
（2）如果nextoverflow为空了怎么办？则会new一个bmap，并且append到extra.overflow。如下图：

（3）如果map需要扩容怎么办？
扩容的三个条件：未扩容 && (overLoadFactor || tooManyOverflowBuckets)

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    if B > 15 {
        B = 15
    }
    // noverflow是extra.overflow的长度
    return noverflow >= uint16(1)<<(B&15)
}

如果是overLoadFactor则扩容h.B+1,如果是tooManyOverflowBuckets则无需扩容。
这里有个疑问，就是命中tooManyOverflowBuckets无需扩容的情况下，原来的溢出指针存储的数据怎么办？这个问题map是考虑了的，所以才会有判断overLoadFactor,因为count太大了则会扩容，否则count不大却溢出指针太多，则认为可能是已经删除了的元素还在里面。

go的chan

chan的数据结构如下：

读写消息的G只可能有一种存在。

• 缓冲满了，再写则G链接在sendq，等待读G唤醒。
• 缓冲空了，再读则G链接在recvq，等待写G唤醒。

buf指向的内存是环形的，循环使用！

chan的写过程

    wg := sync.WaitGroup{}
    ch := make(chan int, 6)
    //(1) put
    for i:=0;i<6;i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            fmt.Println("put: ", i)
            ch<-i
        }(i)
    }
    //(2) sleep
    //time.Sleep(1*time.Second)
    //(3) get
    for i:=0;i<6;i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            fmt.Println("get: ", <-ch)
        }(i)
    }
    wg.Wait()

观察三种现象（代表代码顺序）：

• (1)(3) 和 (3)(1)： 写读 or 读写
• (1)(2)(3)：写sleep读
• (3)(2)(1)：读sleep写
  每种情况的结果都不同，如何去解释这种现象呢？

无缓冲chan

ch := make(chan int)
//这里报错：fatal error: all goroutines are asleep - deadlock!
ch<-0

上面代码创建了一个无缓冲的chan，直接存储数据会报错，因为*buf没有分配存储空间。无缓冲通道必须发送和接收协程都准备好，才能正常工作。那么它的作用是什么呢？

ch := make(chan int)
    wg := sync.WaitGroup{}
    wg.Add(2)
    go func() {
        defer wg.Done()
        ch<-0
    }()
    go func() {
        defer wg.Done()
        fmt.Println(<-ch)
    }()
    wg.Wait()

这里举两个现实中的例子：

• 打乒乓球、羽毛球、排球等
• 接力赛

有缓冲chan

可以实现什么呢？

• 令牌桶，但是Go本身内部实现了令牌桶算法。
• 协程之间的通信

测试：

• 实现往chan放入1和2，然后求和。

    sum := 0
    buf := make(chan int, 1)
    wg := sync.WaitGroup{}
    for i:=1; i<=2; i++ {
        wg.Add(1)
        go func(i int) { //不同的协程往chan放入数据
            defer wg.Done()
            fmt.Println("putin ", i)
            buf<-i
        }(i)
    }
    for i:=1; i<=2; i++ {
        wg.Add(1)
        go func(i int) { //不同的协程往chan放入数据
            defer wg.Done()
            sum += <-buf
        }(i)
    }
    wg.Wait() //放在这里，执行完了一次就结束了
    fmt.Printf("sum: %d", sum)

  上述代码有个缺陷，假设生产者数量不固定，那么是无法知道用多少个消费者来消费的。那么代码的实现难度就会很大。

（1）代码如何改进呢？

sum := 0
buf := make(chan int, 2)
wg := sync.WaitGroup{}
for i:=1; i<=2; i++ {
   wg.Add(1)
   go func(i int) { //不同的协程往chan放入数据
  defer wg.Done()
      fmt.Println("putin ", i)
      buf<-i
   }(i)
}
wg.Wait()
close(buf) //关闭chan

// 无需指定接收者的数量
for {
   if a,ok := <-buf; ok {
      fmt.Println("get", a)
      sum += a
   } else {
      break
  }
}
fmt.Printf("sum: %d", sum)

单向chan

关闭chan