type hmap struct { count int// # live cells == size of map. flags uint8 B uint8// log_2 of # of buckets (can hold up to loadFactor * 2^B items) noverflow uint16// approximate number of overflow buckets 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 nevacuate uintptr
// https://github.com/golang/go/blob/release-branch.go1.11/src/runtime/map.go#L470 // ..., xxx, yyy 为省略部分，接下来的代码类似 for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { continue } k := xxx if alg.equal(key, k) { v := yyy return v, true } } } return unsafe.Pointer(&zeroVal[0]), false
again: bucket := hash & bucketMask(h.B) // 根据 hash 值计算在哪个桶 if h.growing() { growWork(t, h, bucket) } top := tophash(hash) var inserti *uint8 var insertk unsafe.Pointer var val unsafe.Pointer
for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if b.tophash[i] == empty && inserti == nil { // 找到空位准备插入 inserti = &b.tophash[i] insertk = xxx val = yyy } continue } k := xxx if !alg.equal(key, k) { continue } // already have a mapping for key. Update it. if t.needkeyupdate { typedmemmove(t.key, k, key) } val = yyy goto done } ovf := b.overflow(t) if ovf == nil { break } b = ovf }
// Did not find mapping for key. Allocate new cell & add entry.
// If we hit the max load factor or we have too many overflow buckets, // and we're not already in the middle of growing, start growing. if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again }
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) val = add(insertk, bucketCnt*uintptr(t.keysize)) }
// store new key/value at insert position // ... typedmemmove(t.key, insertk, key) *inserti = top h.count++
done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } h.flags &^= hashWriting if t.indirectvalue { val = *((*unsafe.Pointer)(val)) } return val
delete(m, key)
// in mapdelete: L660 for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { continue } // ... // clear key and value ... // ... b.tophash[i] = empty h.count-- break search } }
const (empty = 0// cell is empty evacuatedEmpty = 1// cell is empty, bucket is evacuated. evacuatedX = 2// key/value is valid. // Entry has been evacuated to first half of larger table. evacuatedY = 3// same as above, but evacuated to second half of larger table. minTopHash = 4// minimum tophash for a normal filled cell. )
functophash(hash uintptr)uint8 { top := uint8(hash>> (sys.PtrSize*8 - 8)) if top < minTopHash { top += minTopHash } return top }
接下来看迭代器的结构体和迭代器的 next。
// 删除了部分过长的注释 type hiter struct { key unsafe.Pointer value unsafe.Pointer t *maptype h *hmap buckets unsafe.Pointer // bucket ptr at hash_iter initialization time bptr *bmap // current bucket overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive startBucket uintptr// bucket iteration started at offset uint8 wrapped bool B uint8 i uint8 bucket uintptr checkBucket uintptr }
// https://github.com/golang/go/blob/release-branch.go1.11/src/runtime/map.go#L783 // 省略大量涉及 evacuate 的代码 next: if b == nil { if bucket == it.startBucket && it.wrapped { // end of iteration it.key = nil it.value = nil return } bucket++ if bucket == bucketShift(it.B) { bucket = 0 it.wrapped = true } i = 0 } for ; i < bucketCnt; i++ { offi := (i + it.offset) & (bucketCnt - 1) if b.tophash[offi] == empty || b.tophash[offi] == evacuatedEmpty { continue } // ... it.key = xxx it.value = yyy
it.bucket = bucket if it.bptr != b { // avoid unnecessary write barrier; see issue 14921 it.bptr = b } it.i = i + 1 it.checkBucket = checkBucket return } b = b.overflow(t) i = 0 goto next