golang map 操作,是map 实现中较复杂的逻辑。因为当赋值时,为了减少hash 冲突链的长度过长问题,会做map 的扩容以及数据的迁移。而map 的扩容以及数据的迁移也是关注的重点。
数据结构 首先,我们需要重新学习下map实现的数据结构:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 type hmap struct { count int flags uint8 B uint8 noverflow uint16 hash0 uint32 buckets unsafe.Pointer oldbuckets unsafe.Pointer nevacuate uintptr extra *mapextra } type mapextra struct { overflow *[]*bmap oldoverflow *[]*bmap nextOverflow *bmap }
hmap 是 map 实现的结构体。大部分字段在 第一节中已经学习过了。剩余的就是nevacuate 和extra 了。
首先需要了解搬迁的概念:当hash 中数据链太长,或者空的bucket 太多时,会操作数据搬迁,将数据挪到一个新的bucket 上,就的bucket数组成为了oldbuckets。bucket的搬迁不是一次就搬完的,是访问到对应的bucket时才可能会触发搬迁操作。(这一点是不是和redis 的扩容比较类似,将扩容放在多个访问上,减少了单次访问的延迟压力)
nevactuate 标识的是搬迁的位置(也可以考虑为搬迁的进度)。标识目前 oldbuckets 中 (一个 array)bucket 搬迁到哪里了。
extra 是一个map 的结构体,nextOverflow 标识的是申请的空的bucket,用于之后解决冲突时使用;overflow 和 oldoverflow 标识溢出的链表中正在使用的bucket 数据。old 和非old 的区别是,old 是为搬迁的数据。
理解了大概的数据结构,我们可以学习map的 赋值操作了。
map 赋值操作 map 的赋值操作写法如下:
1 2 data := mapExample["hello" ]
赋值的实现,golang 为了对不同类型k做了优化,下面时一些实现方法:
1 2 3 4 5 6 func mapassign (t *maptype, h *hmap, key unsafe.Pointer) unsafe .Pointer {}func mapassign_fast32 (t *maptype, h *hmap, key uint32 ) unsafe .Pointer {}func mapassign_fast32ptr (t *maptype, h *hmap, key unsafe.Pointer) unsafe .Pointer {}func mapassign_fast64 (t *maptype, h *hmap, key uint64 ) unsafe .Pointer {}func mapassign_fast64ptr (t *maptype, h *hmap, key unsafe.Pointer) unsafe .Pointer {}func mapassign_faststr (t *maptype, h *hmap, s string ) unsafe .Pointer {}
内容大同小异,我们主要学习mapassign 的实现。
mapassign
方法的实现是查找一个空的bucket,把key赋值到bucket上,然后把val的地址返回,然后直接通过汇编做内存拷贝。 那我们一步步看是如何找空闲bucket的:
① 在查找key之前,会做异常检测,校验map是否未初始化,或正在并发写操作,如果存在,则抛出异常:(这就是为什么map 并发写回panic的原因)
1 2 3 4 5 6 7 8 if h == nil { panic (plainError("assignment to entry in nil map" )) } if h.flags&hashWriting != 0 { throw("concurrent map writes" ) }
② 需要计算key 对应的hash 值,如果buckets 为空(初始化的时候小于一定长度的map 不会初始化数据)还需要初始化一个bucket
1 2 3 4 5 6 7 8 9 alg := t.key.alg hash := alg.hash(key, uintptr (h.hash0)) h.flags ^= hashWriting if h.buckets == nil { h.buckets = newobject(t.bucket) }
③ 通过hash 值,获取对应的bucket。如果map 还在迁移数据,还需要在oldbuckets中找对应的bucket,并搬迁到新的bucket。
1 2 3 4 5 6 7 8 9 10 11 12 bucket := hash & bucketMask(h.B) if h.growing() { growWork(t, h, bucket) } b := (*bmap)(unsafe.Pointer(uintptr (h.buckets) + bucket*uintptr (t.bucketsize))) top := tophash(hash)
④ 拿到bucket之后,还需要按照链表方式一个一个查,找到对应的key, 可能是已经存在的key,也可能需要新增。
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 for { for i := uintptr (0 ); i < bucketCnt; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr (t.keysize)) val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr (t.keysize)+i*uintptr (t.valuesize)) } 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 !alg.equal(key, k) { continue } if t.needkeyupdate() { typedmemmove(t.key, k, key) } val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr (t.keysize)+i*uintptr (t.valuesize)) goto done } ovf := b.overflow(t) if ovf == nil { break } b = ovf }
总结下这段程序,主要有几个部分:
a. map hash 不匹配的情况,会看是否是空kv 。如果调用了delete,会出现空kv的情况,那先把地址留下,如果后面也没找到对应的k(也就是说之前map 里面没有对应的Key),那就直接用空kv的位置即可。 b. 如果 map hash 是匹配的,需要判定key 的字面值是否匹配。如果不匹配,还需要查找。如果匹配了,那直接把key 更新(因为可能有引用),v的地址返回即可。 c. 如果上面都没有,那就看下一个bucket
⑤ 插入数据前,会先检查数据太多了,需要扩容,如果需要扩容,那就从第③开始拿到新的bucket,并查找对应的位置。
1 2 3 4 if !h.growing() && (overLoadFactor(h.count+1 , h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again }
⑥ 如果刚才看没有有空的位置,那就需要在链表后追加一个bucket,拿到kv。
1 2 3 4 5 6 7 if inserti == nil { newb := h.newoverflow(t, b) inserti = &newb.tophash[0 ] insertk = add(unsafe.Pointer(newb), dataOffset) val = add(insertk, bucketCnt*uintptr (t.keysize)) }
⑦ 最后更新tophash 和 key 的字面值, 并解除hashWriting 约束
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 if t.indirectkey() { kmem := newobject(t.key) *(*unsafe.Pointer)(insertk) = kmem insertk = kmem } if t.indirectvalue() { vmem := newobject(t.elem) *(*unsafe.Pointer)(val) = vmem } typedmemmove(t.key, insertk, key) *inserti = top done: if h.flags&hashWriting == 0 { throw("concurrent map writes" ) } h.flags &^= hashWriting if t.indirectvalue() { val = *((*unsafe.Pointer)(val)) } return val
到这里,map的赋值基本就介绍完了。下面学习下步骤⑤中的map的扩容。
Map 的扩容 有两种情况下,需要做扩容。一种是存的kv数据太多了,已经超过了当前map的负载。还有一种是overflow的bucket过多了。这个阈值是一个定值,经验得出的结论,所以我们这里不考究。
当满足条件后,将开始扩容。如果满足条件二,扩容后的buckets 的数量和原来是一样的,说明可能是空kv占据的坑太多了,通过map扩容做内存整理。如果是因为kv 量多导致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 func hashGrow (t *maptype, h *hmap) { bigger := uint8 (1 ) if !overLoadFactor(h.count+1 , h.B) { bigger = 0 h.flags |= sameSizeGrow } oldbuckets := h.buckets newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil ) flags := h.flags &^ (iterator | oldIterator) if h.flags&iterator != 0 { flags |= oldIterator } h.B += bigger h.flags = flags h.oldbuckets = oldbuckets h.buckets = newbuckets h.nevacuate = 0 h.noverflow = 0 if h.extra != nil && h.extra.overflow != nil { if h.extra.oldoverflow != nil { throw("oldoverflow is not nil" ) } h.extra.oldoverflow = h.extra.overflow h.extra.overflow = nil } if nextOverflow != nil { if h.extra == nil { h.extra = new (mapextra) } h.extra.nextOverflow = nextOverflow } }
总结下map的扩容操作。首先拿到扩容的大小,然后申请大数组,然后做些初始化的操作,把老的buckets,以及overflow做切换即可。
map 数据的迁移 扩容完成后,需要做数据的迁移。数据的迁移不是一次完成的,是使用时才会做对应bucket的迁移。也就是逐步做到的数据迁移。下面我们来学习。
在数据赋值的第③步,会看需要操作的bucket是不是在旧的buckets里面,如果在就搬迁。下面是搬迁的具体操作:
1 2 3 4 5 6 7 8 9 func growWork (t *maptype, h *hmap, bucket uintptr ) { evacuate(t, h, bucket&h.oldbucketmask()) if h.growing() { evacuate(t, h, h.nevacuate) } }
nevacuate 标识的是当前的进度,如果都搬迁完,应该和2^B的长度是一样的(这里说的B是oldbuckets 里面的B,毕竟新的buckets长度可能是2^(B+1))。
在evacuate 方法实现是把这个位置对应的bucket,以及其冲突链上的数据都转移到新的buckets上。
① 先要判断当前bucket是不是已经转移。 (oldbucket 标识需要搬迁的bucket 对应的位置)
1 2 3 4 5 b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr (t.bucketsize))) if !evacuated(b) { }
转移的判断直接通过tophash 就可以,判断tophash中第一个hash值即可 (tophash的作用可以参考第三讲)
1 2 3 4 5 func evacuated (b *bmap) bool { h := b.tophash[0 ] return h > emptyOne && h < minTopHash }
② 如果没有被转移,那就要迁移数据了。数据迁移时,可能是迁移到大小相同的buckets上,也可能迁移到2倍大的buckets上。这里xy 都是标记目标迁移位置的标记:x 标识的是迁移到相同的位置,y 标识的是迁移到2倍大的位置上。我们先看下目标位置的确定:
1 2 3 4 5 6 7 8 9 10 11 12 var xy [2 ]evacDstx := &xy[0 ] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr (t.bucketsize))) x.k = add(unsafe.Pointer(x.b), dataOffset) x.v = add(x.k, bucketCnt*uintptr (t.keysize)) if !h.sameSizeGrow() { y := &xy[1 ] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr (t.bucketsize))) y.k = add(unsafe.Pointer(y.b), dataOffset) y.v = add(y.k, bucketCnt*uintptr (t.keysize)) }
③ 确定bucket位置后,需要按照kv 一条一条做迁移。(目的就是清除空闲的kv)
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 for ; b != nil ; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) v := add(k, bucketCnt*uintptr (t.keysize)) for i := 0 ; i < bucketCnt; i, k, v = i+1 , add(k, uintptr (t.keysize)), add(v, uintptr (t.valuesize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty continue } if top < minTopHash { throw("bad map state" ) } k2 := k if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } var useY uint8 if !h.sameSizeGrow() { hash := t.key.alg.hash(k2, uintptr (h.hash0)) if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.alg.equal(k2, k2) { useY = top & 1 top = tophash(hash) } else { if hash&newbit != 0 { useY = 1 } } } if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY { throw("bad evacuatedN" ) } b.tophash[i] = evacuatedX + useY dst := &xy[useY] if dst.i == bucketCnt { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) dst.v = add(dst.k, bucketCnt*uintptr (t.keysize)) } dst.b.tophash[dst.i&(bucketCnt-1 )] = top if t.indirectkey() { *(*unsafe.Pointer)(dst.k) = k2 } else { typedmemmove(t.key, dst.k, k) } if t.indirectvalue() { *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v) } else { typedmemmove(t.elem, dst.v, v) } dst.i++ dst.k = add(dst.k, uintptr (t.keysize)) dst.v = add(dst.v, uintptr (t.valuesize)) } }
对于key 非间接使用的数据(即非指针数据),做内存回收
1 2 3 4 5 6 7 8 if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { b := add(h.oldbuckets, oldbucket*uintptr (t.bucketsize)) ptr := add(b, dataOffset) n := uintptr (t.bucketsize) - dataOffset memclrHasPointers(ptr, n) }
④ 如果当前搬迁的bucket 和 总体搬迁的bucket的位置是一样的,我们需要更新总体进度的标记 nevacuate
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 func advanceEvacuationMark (h *hmap, t *maptype, newbit uintptr ) { h.nevacuate++ stop := h.nevacuate + 1024 if stop > newbit { stop = newbit } for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { h.nevacuate++ } if h.nevacuate == newbit { h.oldbuckets = nil if h.extra != nil { h.extra.oldoverflow = nil } h.flags &^= sameSizeGrow } }
总结
Map 的赋值难点在于数据的扩容和数据的搬迁操作。
bucket 搬迁是逐步进行的,每进行一次赋值,会做至少一次搬迁工作。
扩容不是一定会新增空间,也有可能是只是做了内存整理。
tophash 的标志即可以判断是否为空,还会判断是否搬迁,以及搬迁的位置为X or Y。
delete map 中的key,有可能出现很多空的kv,会导致搬迁操作。如果可以避免,尽量避免。