GO面试题集锦

GO面试题集锦

slice 扩容机制

GO1.17版本及之前
当新切片需要的容量cap大于两倍扩容的容量，则直接按照新切片需要的容量扩容；
当原 slice 容量 < 1024 的时候，新 slice 容量变成原来的 2 倍；
当原 slice 容量 > 1024，进入一个循环，每次容量变成原来的1.25倍,直到大于期望容量。

GO1.18之后
当新切片需要的容量cap大于两倍扩容的容量，则直接按照新切片需要的容量扩容；
当原 slice 容量 < threshold(256) 的时候，新 slice 容量变成原来的 2 倍；
当原 slice 容量 > threshold(256)，进入一个循环，每次容量增加（旧容量+3*threshold）/4。

slice 为什么不是线程安全的

slice底层结构并没有使用加锁的方式,不支持并发读写

map 底层原理

map 是一个指针 占用8个字节(64位计算机),指向hmap结构体,hmap包含多个bmap数组(桶) 
type hmap struct { 
    count int  //元素个数，调用len(map)时直接返回 
    flags uint8  //标志map当前状态,正在删除元素、添加元素..... 
    B uint8  //单元(buckets)的对数 B=5表示能容纳32个元素  B随着map容量增大而变大
    noverflow uint16  //单元(buckets)溢出数量，如果一个单元能存8个key，此时存储了9个，溢出了，就需要再增加一个单元 
    hash0 uint32  //哈希种子 
    buckets unsafe.Pointer //指向单元(buckets)数组,大小为2^B，可以为nil 
    oldbuckets unsafe.Pointer //扩容的时候，buckets长度会是oldbuckets的两倍 
    nevacute uintptr  //指示扩容进度，小于此buckets迁移完成 
    extra *mapextra //与gc相关 可选字段 
}

type bmap struct { 
    tophash [bucketCnt]uint8 
} 
//实际上编译期间会生成一个新的数据结构  
type bmap struct { 
    topbits [8]uint8     //key hash值前8位 用于快速定位keys的位置
    keys [8]keytype     //键
    values [8]valuetype //值
    pad uintptr 
    overflow uintptr     //指向溢出桶 无符号整形 优化GC
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

map 扩容机制

扩容时机：向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容

扩容条件：
1.超过负载 map元素个数 > 6.5（负载因子） * 桶个数
2.溢出桶太多
当桶总数<2^15时，如果溢出桶总数>=桶总数，则认为溢出桶过多
当桶总数>2^15时，如果溢出桶总数>=2^15，则认为溢出桶过多

扩容机制：
双倍扩容：针对条件1，新建一个buckets数组，新的buckets大小是原来的2倍，然后旧buckets数据搬迁到新的buckets。
等量扩容：针对条件2，并不扩大容量，buckets数量维持不变，重新做一遍类似双倍扩容的搬迁动作，把松散的键值对重新排列一次，使得同一个 bucket 中的 key 排列地更紧密，节省空间，提高 bucket 利用率，进而保证更快的存取。

渐进式扩容：
插入修改删除key的时候，都会尝试进行搬迁桶的工作，每次都会检查oldbucket是否nil，如果不是nil则每次搬迁2个桶，蚂蚁搬家一样渐进式扩容
1
2
3
4
5
6
7
8
9
10
11
12
13
14

map 遍历为什么无序

map每次遍历,都会从一个随机值序号的桶,再从其中随机的cell开始遍历,并且扩容后,原来桶中的key会落到其他桶中,本身就会造成失序
如果想顺序遍历map,先把key放到切片排序,再按照key的顺序遍历map

var sl []int
for k := range m {
    sl = append(sl, k)
}
sort.Ints(sl)
for _,k:= range sl {
    fmt.Print(m[k])
}
1
2
3
4
5
6
7
8
9
10
11

map 为什么不是线程安全的

map设计就不是用来多个协程高并发访问的
多个协程同时对map进行并发读写,程序会panic
如果想线程安全,可以使用sync.RWLock 锁

sync.map
这个包里面的map实现了锁,是线程安全的
1
2
3
4
5
6

Map 如何查找

1.写保护机制
先插hmap的标志位flags,如果flags写标志位此时是1,说明其他协程正在写操作,直接panic
2.计算hash值
key经过哈希函数计算后,得到64bit(64位CPU)
10010111 | 101011101010110101010101101010101010 | 10010
3.找到hash对应的桶
上面64位后5(hmap的B值)位定位所存放的桶
如果当前正在扩容中,并且定位到旧桶数据还未完成迁移,则使用旧的桶
4.遍历桶查找
上面64位前8位用来在tophash数组查找快速判断key是否在当前的桶中,如果不在需要去溢出桶查找  
5.返回key对应的指针
1
2
3
4
5
6
7
8
9
10
11

Map 冲突解决方式

GO采用链地址法解决冲突，具体就是插入key到map中时，当key定位的桶填满8个元素后，将会创建一个溢出桶，并且将溢出桶插入当前桶的所在链表尾部
1

Map 负载因子为什么是 6.5

负载因子 = 哈希表存储的元素个数 / 桶个数
Go 官方发现：装载因子越大，填入的元素越多，空间利用率就越高，但发生哈希冲突的几率就变大。
            装载因子越小，填入的元素越少，冲突发生的几率减小，但空间浪费也会变得更多，而且还会提高扩容操作的次数
Go 官方取了一个相对适中的值，把 Go 中的 map 的负载因子硬编码为 6.5，这就是 6.5 的选择缘由。
这意味着在 Go 语言中，当 map存储的元素个数大于或等于 6.5 * 桶个数 时，就会触发扩容行为。
1
2
3
4
5

Map 和 Sync.Map 哪个性能好

type Map struct {
    mu Mutex
    read atomic.Value
    dirty map[interface()]*entry
    misses int
}
对比原始map：
和原始map+RWLock的实现并发的方式相比，减少了加锁对性能的影响。它做了一些优化：可以无锁访问read map，而且会优先操作read map，倘若只操作read map就可以满足要求，那就不用去操作write map(dirty)，所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式
优点：
适合读多写少的场景
缺点：
写多的场景，会导致 read map 缓存失效，需要加锁，冲突变多，性能急剧下降
1
2
3
4
5
6
7
8
9
10
11
12

Channel 底层实现原理

通过var声明或者make函数创建的channel变量是一个存储在函数栈帧上的指针，占用8个字节，指向堆上的hchan结构体
type hchan struct {
    closed   uint32   // channel是否关闭的标志
    elemtype *_type   // channel中的元素类型
    // channel分为无缓冲和有缓冲两种。
    // 对于有缓冲的channel存储数据，使用了 ring buffer（环形缓冲区) 来缓存写入的数据，本质是循环数组
    // 为啥是循环数组？普通数组不行吗，普通数组容量固定更适合指定的空间，弹出元素时，普通数组需要全部都前移
    // 当下标超过数组容量后会回到第一个位置，所以需要有两个字段记录当前读和写的下标位置
    buf      unsafe.Pointer // 指向底层循环数组的指针（环形缓冲区）
    qcount   uint           // 循环数组中的元素数量
    dataqsiz uint           // 循环数组的长度
    elemsize uint16                 // 元素的大小
    sendx    uint           // 下一次写下标的位置
    recvx    uint           // 下一次读下标的位置
    // 尝试读取channel或向channel写入数据而被阻塞的goroutine
    recvq    waitq  // 读等待队列
    sendq    waitq  // 写等待队列
    lock mutex //互斥锁，保证读写channel时不存在并发竞争问题
}
等待队列：
双向链表，包含一个头结点和一个尾结点
每个节点是一个sudog结构体变量，记录哪个协程在等待，等待的是哪个channel，等待发送/接收的数据在哪里
type waitq struct {
    first *sudog
    last  *sudog
}

type sudog struct {
    g *g
    next *sudog
    prev *sudog
    elem unsafe.Pointer 
    c        *hchan 
    ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

创建时:
创建时会做一些检查:
-   元素大小不能超过 64K
-   元素的对齐大小不能超过 maxAlign 也就是 8 字节
-   计算出来的内存是否超过限制

创建时的策略:
-   如果是无缓冲的 channel，会直接给 hchan 分配内存
-   如果是有缓冲的 channel，并且元素不包含指针，那么会为 hchan 和底层数组分配一段连续的地址
-   如果是有缓冲的 channel，并且元素包含指针，那么会为 hchan 和底层数组分别分配地址
1
2
3
4
5
6
7
8
9
10

发送时:
-   如果 channel 的读等待队列存在接收者goroutine
-   将数据**直接发送**给第一个等待的 goroutine， **唤醒接收的 goroutine**
-   如果 channel 的读等待队列不存在接收者goroutine
-   如果循环数组buf未满，那么将会把数据发送到循环数组buf的队尾
-   如果循环数组buf已满，这个时候就会走阻塞发送的流程，将当前 goroutine 加入写等待队列，并**挂起等待唤醒**
1
2
3
4
5
6

接收时:
-   如果 channel 的写等待队列存在发送者goroutine
-   如果是无缓冲 channel，**直接**从第一个发送者goroutine那里把数据拷贝给接收变量，**唤醒发送的 goroutine**
-   如果是有缓冲 channel（已满），将循环数组buf的队首元素拷贝给接收变量，将第一个发送者goroutine的数据拷贝到 buf循环数组队尾，**唤醒发送的 goroutine**
-   如果 channel 的写等待队列不存在发送者goroutine
-   如果循环数组buf非空，将循环数组buf的队首元素拷贝给接收变量
-   如果循环数组buf为空，这个时候就会走阻塞接收的流程，将当前 goroutine 加入读等待队列，并**挂起等待唤醒**
1
2
3
4
5
6
7

Channel 有什么特点

channel有2种类型：无缓冲、有缓冲
channel有3种模式：写操作模式（单向通道）、读操作模式（单向通道）、读写操作模式（双向通道）
写操作模式    make(chan<- int)
读操作模式    make(<-chan int)
读写操作模式    make(chan int)
1
2
3
4
5

channel 有 3 种状态：未初始化、正常、关闭

注意点：

一个 channel不能多次关闭，会导致painc
如果多个 goroutine 都监听同一个 channel，那么 channel 上的数据都可能随机被某一个 goroutine 取走进行消费
如果多个 goroutine 监听同一个 channel，如果这个 channel 被关闭，则所有 goroutine 都能收到退出信号

Channel 为什么是线程安全的

不同协程通过channel进行通信，本身的使用场景就是多线程，为了保证数据的一致性，必须实现线程安全
channel的底层实现中，hchan结构体中采用Mutex锁来保证数据读写安全。在对循环数组buf中的数据进行入队和出队操作时，必须先获取互斥锁，才能操作channel数据

Channel 发送和接收什么情况下会死锁？

func deadlock1() {    //无缓冲channel只写不读
    ch := make(chan int) 
    ch <- 3 //  这里会发生一直阻塞的情况，执行不到下面一句
}
func deadlock2() { //无缓冲channel读在写后面
    ch := make(chan int)
    ch <- 3  //  这里会发生一直阻塞的情况，执行不到下面一句
    num := <-ch
    fmt.Println("num=", num)
}
func deadlock3() { //无缓冲channel读在写后面
    ch := make(chan int)
    ch <- 100 //  这里会发生一直阻塞的情况，执行不到下面一句
    go func() {
        num := <-ch
        fmt.Println("num=", num)
    }()
    time.Sleep(time.Second)
}
func deadlock3() {    //有缓冲channel写入超过缓冲区数量
    ch := make(chan int, 3)
    ch <- 3
    ch <- 4
    ch <- 5
    ch <- 6  //  这里会发生一直阻塞的情况
}
func deadlock4() {    //空读
    ch := make(chan int)
    // ch := make(chan int, 1)
    fmt.Println(<-ch)  //  这里会发生一直阻塞的情况
}
func deadlock5() {    //互相等对方造成死锁
    ch1 := make(chan int)
    ch2 := make(chan int)
    go func() {
        for {
        select {
        case num := <-ch1:
            fmt.Println("num=", num)
            ch2 <- 100
        }
    }
    }()
    for {
        select {
        case num := <-ch2:
            fmt.Println("num=", num)
            ch1 <- 300
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51