【Golang 面试题】每日 3 题（十七）
✍个人博客：Pandaconda-CSDN博客
📣专栏地址：http://t.csdnimg.cn/UWz06
📚专栏简介：在这个专栏中，我将会分享 Golang 面试中常见的面试题给大家~
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪
49. Go Map 查找流程
- 写保护监测
函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行“写”操作，进而导致程序 panic，这也说明了 map 不是线程安全的。
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
- 计算 hash 值
hash := t.hasher(key, uintptr(h.hash0))
key 经过哈希函数计算后，得到的哈希值如下（主流 64 位机下共 64 个 bit 位），不同类型的 key 会有不同的 hash 函数。
10010111 | 000011110110110010001111001010100010010110010101010 │ 01010
- 找到 hash 对应的 bucket
bucket 定位：哈希值的低 B 个 bit 位，用来定位 key 所存放的 bucket。
如果当前正在扩容中，并且定位到的旧 bucket 数据还未完成迁移，则使用旧的 bucket（扩容前的 bucket）。
hash := t.hasher(key, uintptr(h.hash0))
// 桶的个数m-1，即 1<<B-1,B=5时，则有0~31号桶
m := bucketMask(h.B)
// 计算哈希值对应的bucket
// t.bucketsize为一个bmap的大小，通过对哈希值和桶个数取模得到桶编号，通过对桶编号和buckets起始地址进行运算，获取哈希值对应的bucket
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 是否在扩容
if c := h.oldbuckets; c != nil {
// 桶个数已经发生增长一倍，则旧bucket的桶个数为当前桶个数的一半
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
// 计算哈希值对应的旧bucket
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 如果旧bucket的数据没有完成迁移，则使用旧bucket查找
if !evacuated(oldb) {
b = oldb
}
}
- 遍历 bucket 查找
tophash 值定位：哈希值的高 8 个 bit 位，用来快速判断 key 是否已在当前 bucket 中（如果不在的话，需要去 bucket 的 overflow 中查找）。
用步骤 2 中的 hash 值，得到高 8 个 bit 位，也就是 10010111，转化为十进制，也就是 151。
top := tophash(hash)
func tophash(hash uintptr) uint8 {
top := uint8(hash >> (goarch.PtrSize*8 - 8))
if top < minTopHash {
top += minTopHash
}
return top
}
上面函数中 hash 是 64 位的，sys.PtrSize 值是 8，所以 top := uint8(hash >> (sys.PtrSize*8 - 8)) 等效 top = uint8(hash >> 56)，最后 top 取出来的值就是 hash 的高 8 位值。
在 bucket 及 bucket 的 overflow 中寻找 tophash 值（HOB hash）为 151* 的 槽位，即为 key 所在位置，找到了空槽位或者 2 号槽位，这样整个查找过程就结束了，其中找到空槽位代表没找到。
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
// 未被使用的槽位，插入
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 找到tophash值对应的的key
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
return e
}
}
}
5. 返回 key 对应的指针
如果通过上面的步骤找到了 key 对应的槽位下标 i，我们再详细分析下 key/value 值是如何获取的：
// keys的偏移量
dataOffset = unsafe.Offsetof(struct{
b bmap
v int64
}{}.v)
// 一个bucket的元素个数
bucketCnt = 8
// key 定位公式
k :=add(unsafe.Pointer(b),dataOffset+i*uintptr(t.keysize))
// value 定位公式
v:= add(unsafe.Pointer(b),dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
bucket 里 keys 的起始地址就是 unsafe.Pointer(b)+dataOffset。
第 i 个下标 key 的地址就要在此基础上跨过 i 个 key 的大小；
而我们又知道，value 的地址是在所有 key 之后，因此第 i 个下标 value 的地址还需要加上所有 key 的偏移。
50. Go Map 冲突的解决方式？
比较常用的 Hash 冲突解决方案有链地址法和开放寻址法：
- 链地址法
当哈希冲突发生时，创建新单元，并将新单元添加到冲突单元所在链表的尾部。 - 开放寻址法
当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序，从哈希表中寻找一个空闲的单元，然后把发生冲突的元素存入到该单元。开放寻址法需要的表长度要大于等于所需要存放的元素数量。
开放寻址法有多种方式：线性探测法、平方探测法、随机探测法和双重哈希法。这里以线性探测法来帮助读者理解开放寻址法思想。
51. Go Map 冲突解决方式比较
线性探测法
设 Hash(key) 表示关键字 key 的哈希值， 表示哈希表的槽位数（哈希表的大小）。
线性探测法则可以表示为：
如果 Hash(x) % M 已经有数据，则尝试 (Hash(x) + 1) % M ;
如果 (Hash(x) + 1) % M 也有数据了，则尝试 (Hash(x) + 2) % M ;
如果 (Hash(x) + 2) % M 也有数据了，则尝试 (Hash(x) + 3) % M ;
两种解决方案比较
对于链地址法，基于数组 + 链表进行存储，链表节点可以在需要时再创建，不必像开放寻址法那样事先申请好足够内存，因此链地址法对于内存的利用率会比开方寻址法高。链地址法对装载因子的容忍度会更高，并且适合存储大对象、大数据量的哈希表。而且相较于开放寻址法，它更加灵活，支持更多的优化策略，比如可采用
红黑树代替链表。但是链地址法需要额外的空间来存储指针。
对于开放寻址法，它只有数组一种数据结构就可完成存储，继承了数组的优点，对 CPU 缓存友好，易于序列化操作。但是它对内存的利用率不如链地址法，且发生冲突时代价更高。当数据量明确、装载因子小，适合采用开放寻址法。
总结
在发生哈希冲突时，Python 中 dict 采用的开放寻址法，Java 的 HashMap 采用的是链地址法，而 Go map 也采用链地址法解决冲突，具体就是插入 key 到 map 中时，当 key 定位的桶填满 8 个元素后（这里的单元就是桶，不是元素），将会创建一个溢出桶，并且将溢出桶插入当前桶所在链表尾部。
if inserti == nil {
// all current buckets are full, allocate a new one.
newb := h.newoverflow(t, b)
// 创建一个新的溢出桶
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}