[面试题～]Golang

3. 数组和切片

3.1 数组和切片的区别

Go语言中数组是固定长度的，不能动态扩容，在编译期就会确定大小。
切片是一种数据结构，包含一个底层数组的指针，当前切片个数 len 以及切片的最大容量 cap， 描述的是一块数组。

3.2 切片的扩容策略

切片的扩容都是调用growslice方法，不同版本，扩容机制也有细微差距。
Go1.17 版本，切片在扩容时会进行内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于老 slice 容量的 2倍或者1.25倍。
当新切片需要的容量大于两倍扩容的容量，则直接按照新切片需要的容量扩容，当原 slice 容量小于 1024 的时候，新 slice 容量变成原来的 2 倍；原 slice 容量超过 1024，新 slice 容量变成原来的1.25倍。
在1.18时，又改成不和1024比较了，而是和256比较。
简单地说，就是小切片按照2倍扩容，大切片按照1.25倍扩容。
Go官方注释说这么做的目的是能更平滑的过渡。

3.3 Go 中对 nil 的 Slice 和空 Slice 的处理是一致的吗?

首先 Go 的 JSON 标准库对 nil slice 和 空 slice 的处理是不一致。

• slice := make([]int,0）：slice 不为 nil，但是 slice 没有值，slice 的底层的空间是空的。
• slice := []int{} ：slice 的值是 nil，可用于需要返回 slice 的函数，当函数出现异常的时候，保证函数依然会有 nil 的返回值。

4. map

4.1 map 的底层实现

Golang 中 map 的底层实现是一个散列表，因此实现 map 的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫 hmap(a header for a go map)，一个叫 bmap(a bucket for a Go map，通常叫其 bucket)。

4.2 map 如何扩容

扩容其实就是一个预分配内容的过程，在 map 中的表现是 预分配 bucket。

1. 双倍扩容：扩容采取了一种称为“渐进式”的方式，原有的 key 并不会一 次性搬迁完毕，每次最多只会搬迁 2 个 bucket。
2. 等量扩容：重新排列，极端情况下，重新排列也解决不了，map 存储就会蜕变成链表，性能大大降低，此时哈希因子 hash0 的设置，可以降低此类极端场景的发生。

4.3 什么时候会发生扩容

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

1. 装载因子超过阈值
2. overflow 的 bucket 数量过多

---

• 对于条件 1，元素太多，而 bucket 数量太少，很简单：将 B 加 1，bucket 最大数量(2^B)直接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。注意，这时候元素都在老 bucket 里，还没迁移到新的 bucket 来。新 bucket 只是最大数量变为原来最大数量的 2 倍(2^B * 2) 。
• 对于条件 2，其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升。

4.4 map 什么时候会发生迁移

map 扩容完毕后，不会马上就进行迁移。而是采取增量扩容的方式，当有访问到具体 bukcet 时，才会逐渐的进行迁移（将 oldbucket 迁移到 bucket）。

4.5 map 查找

Go 语言中 map 采用的是哈希查找表，由一个 key 通过哈希函数得到哈希值，64 位系统中就生成一个 64bit 的哈希值，由这个哈希值将 key 对应存到不同的桶 （bucket）中，当有多个哈希映射到相同的的桶中时，使用链表解决哈希冲突。
细节：key 经过 hash 后共 64 位，根据 hmap 中 B 的值，计算它到底要落在哪个桶时，桶的数量为 2B ，如 B=5，那么用 64 位最后 5 位表示第几号桶，在用hash 值的高 8 位确定在 bucket 中的存储位置，当前 bmap 中的 bucket 未找到，则查询对应的 overflow bucket，对应位置有数据则对比完整的哈希值， 确定是否是要查找的数据。如果当前 map 处于数据搬移状态，则优先从 oldbuckets 查找。

4.6 map 删除

删除的逻辑相对比较简单，核心是找到 key 的具体位置。在 bucket 中挨个 cell 寻找。找到对应位置后，对 key 或者 value 进行“清零”操作，将 count 值减 1，将对应位置的 tophash 值置成 Empty

4.7 为什么遍历map是无序的？

遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key，而每个 key 进入 bucket 之前都先进行了哈希散列，所以没办法保证遍历的有序性。

4.8 如何实现有序遍历map？

可以把 map 的 key 全部拿出来进行排序，然后根据 key 去获取 value 。

4.9 为什么Go map是非线程安全的？

因为hash map 的内存是按照2的倍数开辟的，当前面开辟的内存不够的时候，会新开辟一段内存，将原来内存的数据转移到新的内存块中，这个过程是没有加锁的，如果这个时候同时有个读的线程过来获取这块内存数据，就会出现安全问题。

4.10 线程安全的map如何实现?

避免map并发读写panic的方式之一就是加锁，考虑到读写性能，可以使用读写锁提供性能。

4.11 Go sync.map 和原生 map 谁的性能好，为什么？

在基准测试中，在并发安全的情况下sync.Map会比我们常用的map+读写锁更加的快，快了五倍，这是得以于只读read设计，减低锁的粒度。但是利用读写锁的话，我们存储的不是一个简单数据类型，而是一个指针对象，那么用普通map+读写锁能很好地控制锁的粒度，达到更好的操作。

4.12 为什么 Go map 的负载因子是 6.5？

源码里定义的阈值的 6.5 (loadFactorNum/loadFactorDen)，是经过测试后取出的一个比较合理的因子
因为每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。