Golang Map实现赋值和扩容的示例代码
golangmap操作，是map实现中较复杂的逻辑。因为当赋值时，为了减少hash冲突链的长度过长问题，会做map的扩容以及数据的迁移。而map的扩容以及数据的迁移也是关注的重点。
数据结构
首先，我们需要重新学习下map实现的数据结构：
typehmapstruct{
countint
flagsuint8
Buint8
noverflowuint16
hash0uint32
bucketsunsafe.Pointer
oldbucketsunsafe.Pointer
nevacuateuintptr
extra*mapextra
}
typemapextrastruct{
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的赋值操作写法如下：
data:=mapExample["hello"]
赋值的实现，golang为了对不同类型k做了优化，下面时一些实现方法：
funcmapassign(t*maptype,h*hmap,keyunsafe.Pointer)unsafe.Pointer{}
funcmapassign_fast32(t*maptype,h*hmap,keyuint32)unsafe.Pointer{}
funcmapassign_fast32ptr(t*maptype,h*hmap,keyunsafe.Pointer)unsafe.Pointer{}
funcmapassign_fast64(t*maptype,h*hmap,keyuint64)unsafe.Pointer{}
funcmapassign_fast64ptr(t*maptype,h*hmap,keyunsafe.Pointer)unsafe.Pointer{}
funcmapassign_faststr(t*maptype,h*hmap,sstring)unsafe.Pointer{}
内容大同小异，我们主要学习mapassign的实现。
mapassign方法的实现是查找一个空的bucket，把key赋值到bucket上，然后把val的地址返回,然后直接通过汇编做内存拷贝。
那我们一步步看是如何找空闲bucket的：
①在查找key之前，会做异常检测，校验map是否未初始化，或正在并发写操作，如果存在，则抛出异常：（这就是为什么map并发写回panic的原因）
ifh==nil{
panic(plainError("assignmenttoentryinnilmap"))
}
//竟态检查和内存扫描
ifh.flags&hashWriting!=0{
throw("concurrentmapwrites")
}
②需要计算key对应的hash值，如果buckets为空（初始化的时候小于一定长度的map不会初始化数据）还需要初始化一个bucket
alg:=t.key.alg
hash:=alg.hash(key,uintptr(h.hash0))
//为什么需要在hash后设置flags，因为alg.hash可能会panic
h.flags^=hashWriting
ifh.buckets==nil{
h.buckets=newobject(t.bucket)//newarray(t.bucket,1)
}
③通过hash值，获取对应的bucket。如果map还在迁移数据，还需要在oldbuckets中找对应的bucket，并搬迁到新的bucket。
//通过hash计算bucket的位置偏移
bucket:=hash&bucketMask(h.B)
//此处是搬迁逻辑，我们后续详解
ifh.growing(){
growWork(t,h,bucket)
}
//计算对应的bucket位置，和tophash值
b:=(*bmap)(unsafe.Pointer(uintptr(h.buckets)+bucket*uintptr(t.bucketsize)))
top:=tophash(hash)
④拿到bucket之后，还需要按照链表方式一个一个查，找到对应的key，可能是已经存在的key，也可能需要新增。
for{
fori:=uintptr(0);i
总结下这段程序，主要有几个部分：
a.maphash不匹配的情况，会看是否是空kv。如果调用了delete，会出现空kv的情况，那先把地址留下，如果后面也没找到对应的k（也就是说之前map里面没有对应的Key），那就直接用空kv的位置即可。
b.如果maphash是匹配的，需要判定key的字面值是否匹配。如果不匹配，还需要查找。如果匹配了，那直接把key更新（因为可能有引用），v的地址返回即可。
c.如果上面都没有，那就看下一个bucket
⑤插入数据前，会先检查数据太多了，需要扩容，如果需要扩容，那就从第③开始拿到新的bucket，并查找对应的位置。
if!h.growing()&&(overLoadFactor(h.count+1,h.B)||tooManyOverflowBuckets(h.noverflow,h.B)){
hashGrow(t,h)
gotoagain//Growingthetableinvalidateseverything,sotryagain
}
⑥如果刚才看没有有空的位置，那就需要在链表后追加一个bucket，拿到kv。
ifinserti==nil{
//allcurrentbucketsarefull,allocateanewone.
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约束
//如果非指针数据（也就是直接赋值的数据），还需要申请内存和拷贝
ift.indirectkey(){
kmem:=newobject(t.key)
*(*unsafe.Pointer)(insertk)=kmem
insertk=kmem
}
ift.indirectvalue(){
vmem:=newobject(t.elem)
*(*unsafe.Pointer)(val)=vmem
}
//更新tophash,k
typedmemmove(t.key,insertk,key)
*inserti=top
done:
ifh.flags&hashWriting==0{
throw("concurrentmapwrites")
}
h.flags&^=hashWriting
ift.indirectvalue(){
val=*((*unsafe.Pointer)(val))
}
returnval
到这里，map的赋值基本就介绍完了。下面学习下步骤⑤中的map的扩容。
Map的扩容
有两种情况下，需要做扩容。一种是存的kv数据太多了，已经超过了当前map的负载。还有一种是overflow的bucket过多了。这个阈值是一个定值，经验得出的结论，所以我们这里不考究。
当满足条件后，将开始扩容。如果满足条件二，扩容后的buckets的数量和原来是一样的，说明可能是空kv占据的坑太多了，通过map扩容做内存整理。如果是因为kv量多导致map负载过高，那就扩一倍的量。
funchashGrow(t*maptype,h*hmap){
bigger:=uint8(1)
//如果是第二种情况，扩容大小为0
if!overLoadFactor(h.count+1,h.B){
bigger=0
h.flags|=sameSizeGrow
}
oldbuckets:=h.buckets
//申请一个大数组，作为新的buckets
newbuckets,nextOverflow:=makeBucketArray(t,h.B+bigger,nil)
flags:=h.flags&^(iterator|oldIterator)
ifh.flags&iterator!=0{
flags|=oldIterator
}
//然后重新赋值map的结构体，oldbuckets被填充。之后将做搬迁操作
h.B+=bigger
h.flags=flags
h.oldbuckets=oldbuckets
h.buckets=newbuckets
h.nevacuate=0
h.noverflow=0
//extra结构体做赋值
ifh.extra!=nil&&h.extra.overflow!=nil{
//Promotecurrentoverflowbucketstotheoldgeneration.
ifh.extra.oldoverflow!=nil{
throw("oldoverflowisnotnil")
}
h.extra.oldoverflow=h.extra.overflow
h.extra.overflow=nil
}
ifnextOverflow!=nil{
ifh.extra==nil{
h.extra=new(mapextra)
}
h.extra.nextOverflow=nextOverflow
}
}
总结下map的扩容操作。首先拿到扩容的大小，然后申请大数组，然后做些初始化的操作，把老的buckets，以及overflow做切换即可。
map数据的迁移
扩容完成后，需要做数据的迁移。数据的迁移不是一次完成的，是使用时才会做对应bucket的迁移。也就是逐步做到的数据迁移。下面我们来学习。
在数据赋值的第③步，会看需要操作的bucket是不是在旧的buckets里面，如果在就搬迁。下面是搬迁的具体操作：
funcgrowWork(t*maptype,h*hmap,bucketuintptr){
//首先把需要操作的bucket搬迁
evacuate(t,h,bucket&h.oldbucketmask())
//再顺带搬迁一个bucket
ifh.growing(){
evacuate(t,h,h.nevacuate)
}
}
nevacuate标识的是当前的进度，如果都搬迁完，应该和2^B的长度是一样的（这里说的B是oldbuckets里面的B，毕竟新的buckets长度可能是2^(B+1))。
在evacuate方法实现是把这个位置对应的bucket，以及其冲突链上的数据都转移到新的buckets上。
①先要判断当前bucket是不是已经转移。(oldbucket标识需要搬迁的bucket对应的位置)
b:=(*bmap)(add(h.oldbuckets,oldbucket*uintptr(t.bucketsize)))
//判断
if!evacuated(b){
//做转移操作
}
转移的判断直接通过tophash就可以，判断tophash中第一个hash值即可（tophash的作用可以参考第三讲）
funcevacuated(b*bmap)bool{
h:=b.tophash[0]
//这个区间的flag均是已被转移
returnh>emptyOne&&h
②如果没有被转移，那就要迁移数据了。数据迁移时，可能是迁移到大小相同的buckets上，也可能迁移到2倍大的buckets上。这里xy都是标记目标迁移位置的标记：x标识的是迁移到相同的位置，y标识的是迁移到2倍大的位置上。我们先看下目标位置的确定：
varxy[2]evacDst
x:=&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(){
//如果是2倍的大小，就得算一次y的值
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）
//遍历每个bucket
for;b!=nil;b=b.overflow(t){
k:=add(unsafe.Pointer(b),dataOffset)
v:=add(k,bucketCnt*uintptr(t.keysize))
//遍历bucket里面的每个kv
fori:=0;i
对于key非间接使用的数据（即非指针数据），做内存回收
ifh.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
//ptr是kv的位置，前面的topmap保留，做迁移前的校验使用
memclrHasPointers(ptr,n)
}
④如果当前搬迁的bucket和总体搬迁的bucket的位置是一样的，我们需要更新总体进度的标记nevacuate
//newbit是oldbuckets的长度，也是nevacuate的重点
funcadvanceEvacuationMark(h*hmap,t*maptype,newbituintptr){
//首先更新标记
h.nevacuate++
//最多查看2^10个bucket
stop:=h.nevacuate+1024
ifstop>newbit{
stop=newbit
}
//如果没有搬迁就停止了，等下次搬迁
forh.nevacuate!=stop&&bucketEvacuated(t,h,h.nevacuate){
h.nevacuate++
}
//如果都已经搬迁完了，oldbukets完全搬迁成功，清空oldbuckets
ifh.nevacuate==newbit{
h.oldbuckets=nil
ifh.extra!=nil{
h.extra.oldoverflow=nil
}
h.flags&^=sameSizeGrow
}
}
总结
- Map的赋值难点在于数据的扩容和数据的搬迁操作。
- bucket搬迁是逐步进行的，每进行一次赋值，会做至少一次搬迁工作。
- 扩容不是一定会新增空间，也有可能是只是做了内存整理。
- tophash的标志即可以判断是否为空，还会判断是否搬迁，以及搬迁的位置为XorY。
- deletemap中的key，有可能出现很多空的kv，会导致搬迁操作。如果可以避免，尽量避免。
到此这篇关于GolangMap实现赋值和扩容的示例代码的文章就介绍到这了,更多相关GolangMap赋值和扩容内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！