map

数据结构

对应的源码位置runtime/map.go。注：以下涉及的go源码版本1.16

简化后的数据结构

// A header for a Go map.
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    // 内置函数len()用到
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    // 桶的数量2^B个
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    // 溢出桶的近似值。如果B太大，计数随机增加
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    // hash种子
    hash0     uint32 // hash seed
    // 新桶
    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    // 扩容时会存在旧桶。大小等于新桶大小或一半
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    // 移桶次数
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

access

有3种方式：

key := 1
m := map[int]int{}
// 方式1
value := m[key]
// 方式2
value,ok := m[key]
// 方式3
for key, value := range m {
}

方式1对应的源码 mapaccess1

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0])
    }
    // 不允许并发访问
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    // hash值低位索引桶
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // 迁移未完成会存在旧桶。每次迁移不是都会扩容1倍，有可能是更换hash种子
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // There used to be half as many buckets; mask down one more power of two.
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    top := tophash(hash)
bucketloop:
    // 遍历溢出桶
    for ; b != nil; b = b.overflow(t) {
        // 每个桶存储了8个键值对
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            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
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}