map高8位的问题

Question

老师我有一个问题没有搞明白，
key在hash之后得到一个二进制数字
低B位得到这个key在那个桶中，我能理解，取余就行，
但是高8位怎么确定在桶中的位置呀，没有想到它是怎么做的，
我理解的是在一个桶的都是hash冲突的，这个时候，使用循环找到对应的key，
这个tophash 和高8位没有理解

Answer 1

少林码僧 2023-12-13 18:07:39

对于map的元素查找，源码实现如下：

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 52 53 54

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {   // 如果开启了竞态检测 -race    if raceenabled && h != nil {         callerpc := getcallerpc()         pc := funcPC(mapaccess1)         racereadpc(unsafe.Pointer(h), callerpc, pc)         raceReadObjectPC(t.key, key, callerpc, pc)     }   // 如果开启了memory sanitizer -msan    if msanenabled && h != nil {         msanread(key, t.key.size)     }   // 如果map为空或者元素个数为0，返回零值    if h == nil || h.count == 0 {         if t.hashMightPanic() {             t.hasher(key, 0) // see issue 23734        }         return unsafe.Pointer(&zeroVal[0])     }   // 注意，这里是按位与操作  // 当h.flags对应的值为hashWriting（代表有其他goroutine正在往map中写key）时，那么位计算的结果不为0，因此抛出以下错误。  // 这也表明，go的map是非并发安全的    if h.flags&hashWriting != 0 {         throw("concurrent map read and map write")     }   // 不同类型的key，会使用不同的hash算法，可详见src/runtime/alg.go中typehash函数中的逻辑    hash := t.hasher(key, uintptr(h.hash0))     m := bucketMask(h.B)   // 按位与操作，找到对应的bucket    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))   // 如果oldbuckets不为空，那么证明map发生了扩容  // 如果有扩容发生，老的buckets中的数据可能还未搬迁至新的buckets里  // 所以需要先在老的buckets中找    if c := h.oldbuckets; c != nil {         if !h.sameSizeGrow() {             m >>= 1         }         oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))     // 如果在oldbuckets中tophash[0]的值，为evacuatedX、evacuatedY，evacuatedEmpty其中之一    // 则evacuated()返回为true，代表搬迁完成。    // 因此，只有当搬迁未完成时，才会从此oldbucket中遍历        if !evacuated(oldb) {             b = oldb         }     }   // 取出当前key值的tophash值    top := tophash(hash)   // 以下是查找的核心逻辑  // 双重循环遍历：外层循环是从桶到溢出桶遍历；内层是桶中的cell遍历  // 跳出循环的条件有三种：第一种是已经找到key值；第二种是当前桶再无溢出桶；  // 第三种是当前桶中有cell位的tophash值是emptyRest，这个值在前面解释过，它代表此时的桶后面的cell还未利用，所以无需再继续遍历。bucketloop:     for ; b != nil; b = b.overflow(t) {         for i := uintptr(0); i < bucketCnt; i++ {       // 判断tophash值是否相等            if b.tophash[i] != top {                 if b.tophash[i] == emptyRest {                     break bucketloop                 }                 continue       }       // 因为在bucket中key是用连续的存储空间存储的，因此可以通过bucket地址+数据偏移量（bmap结构体的大小）+ keysize的大小，得到k的地址      // 同理，value的地址也是相似的计算方法，只是再要加上8个keysize的内存地址            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))             if t.indirectkey() {                 k = *((*unsafe.Pointer)(k))             }       // 判断key是否相等            if t.key.equal(key, k) {                 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))                 if t.indirectelem() {                     e = *((*unsafe.Pointer)(e))                 }                 return e             }         }     }   // 所有的bucket都未找到，则返回零值    return unsafe.Pointer(&zeroVal[0])}

如果理解了map的结构，就不难理解这个问题，先看map的存储结构：

首先每个桶中最多只有8个元素，也就是只能存储8个键值对。当某个bucket（比如buckets[0]）的8个空槽（slot）都已填满且map尚未达到扩容条件时，运行时会建立overflow bucket，并将该overflow bucket挂在上面bucket（如buckets[0]）末尾的overflow指针上，这样两个bucket形成了一个链表结构，该结构的存在将持续到下一次map扩容。

这样对于上面的bucket[0]中，实际上是有很多个这种8个元素为一组的这种bucket的，我们可以将这样一组bucket理解成一个cell。那么通过高8位去定位key在bucket[0]里边的位置的时候，就得对整个bucket[0]的cell进行遍历，然后也需要对cell中的元素进行遍历。tophash是用于快速定位key位置的，它存储的是高8位的tophash值。

• 少林码僧 #1

  在遍历过程中，它会先比较哈希的高 8 位和当前cell的 tophash值 是否相等是否相等。为什么不直接去跟key[0],key[1]这些实际存储的key去对比，而要增加一个tophash值去对比呢？
  
  ​当key是size较大的字符串类型时，直接用原始的key值去对比两个字符串是否一样跟对比1个字节的tophash值相比，肯定是直接对比tophash值时更快的，这是一种以空间换时间的思路。
  
  每一个桶都是一整片的内存空间，当发现桶中的 tophash 与传入键的 tophash 匹配之后，会通过指针和偏移量获取哈希中存储的键 keys[0] 并与 key 比较，如果两者相同就会获取目标值的指针 values[0] 并返回。