Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

Go map实现原理

啊汉 2019-02-20 20:16:00 阅读数:219 评论数:0 点赞数:0 收藏数:0

map结构

整体为一个数组,数组每个元素可以理解成一个槽,槽是一个链表结构,槽的每个节点可存8个元素,搞清楚了map的结构,想想对应的增删改查操作也不是那么难**![]()**

1:槽大小计算&hash算法我们可以简单的理解成:槽大小为1<

关于hash冲突,那是必须的,当你指定预计元素个数时,预计平均一个槽6.5个元素,据我观察好多语言的hash都是采用hashCode&1<

 2:容量计算和扩容

m := make(map[string]int, hint) func overLoadFactor(count int64, B uint8)bool{return count >= 8 && float32(count) >= 6.5/*float32((uint64(1)<= 4{ nbuckets+= 1 << (b - 4) //多分配了1/16的空间,当某个槽满了之后可以可以从这里多取出一个节点 sz := t.bucket.size /*nbuckets up :=roundupsize(sz)if up !=sz { nbuckets= up /t.bucket.size } } buckets= newarray(t.bucket, int(nbuckets))if base !=nbuckets { nextOverflow= (/*bmap)(add(buckets, base/*uintptr(t.bucketsize))) last := (/*bmap)(add(buckets, (nbuckets-1)/*uintptr(t.bucketsize))) last.setoverflow(t, (/*bmap)(buckets)) }returnbuckets, nextOverflow }初始化容量和扩容都是调上面的方法makeBucketArray

举个例子:m := make(map[int][string], 10),通过上面计算b的方法得出b=2,即4=1<<2个槽,每个槽一个节点,每个节点可容纳8个元素,总共可容纳32个元素,可容纳期望的10个元素扩容基本采取2/*N + N/16的方式(2倍扩容),多出来的N/16用于槽满的情况,新增的节点就从这多出来的地方取,如果多出来的槽也用完了就直接new新的内存

槽大小(t.bucketsize)应该是提前就计算好了的,每个槽能容纳8个元素,当槽满之后,如果还有新增到这个槽的元素,会新增一个槽,以链表的方式连在这个槽的后面 

扩容后数据怎么复制过来go并没有采用一下子就将数据全部复制过来的方式,如果数据很多还是非常耗时的,而是在写数据的时候如果命中一个老槽,就将这个槽中的所有数据重新hash到新的数据结果中,在扩容过程中,新老数据结构同时提供数据的查询,写数据的时候只会写入新的数据结构中,同时将命中老数据结构对应槽中的数据重新hash到新的数据结构中。

 扩容条件

1:已经处于扩容状态就不能再扩容了,就新老两个数据结构,没有第三了2:元素个数>6.5/*槽数量(槽的每个节点能容纳8个元素,但是分布不可能这么均匀的),可以扩容

3:槽节点写满的个数到达一定数量也可以扩容也就是说,在没有扩容的情况下:元素个数太多 || 槽节点满的数量多,都会触发扩容 

 一个槽就是多个节点组成的链表,节点数据结构如下:

//A bucket for a Go map. const bucketCnt = 8type bmapstruct{//tophash generally contains the top byte of the hash value//for each key in this bucket. If tophash[0] < minTopHash,//tophash[0] is a bucket evacuation state instead. tophash [bucketCnt]uint8//Followed by bucketCnt keys and then bucketCnt values.//NOTE: packing all the keys together and then all the values together makes the//code a bit more complicated than alternating key/value/key/value/... but it allows//us to eliminate padding which would be needed for, e.g., map[int64]int8.//Followed by an overflow pointer. }节点数据结构:

1:8个标记位的数组,用于标记每个元素的情况,如这个位置是否有元素,8个字节2:连续的8个key,根据key的类型能计算出8个key的大小

3:连续的8个value,根据value的类型能计算出8个value的大小4:指向下一个节点的指针,8个字节

但从节点的数据结构中只看到了8个标记位的数组,其他的都没有写出来,但是一个节点的大小是能计算出来的,可以分配一个能容纳以上4个元素的空间,在强制转换成/*bmap就行,然后按照地址+偏移量就能计算出每个元素的地址 

value = map[key] 源码分析 //go:linkname reflectmapaccess reflect.mapaccess map[key] func reflectmapaccess(t /maptype, h /hmap, key unsafe.Pointer) unsafe.Pointer { val, ok :=mapaccess2(t, h, key)if !ok { val=nil }returnval } func mapaccess2(t/maptype, h /hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { alg :=t.key.alg//计算hashCode hash :=alg.hash(key, uintptr(h.hash0)) m := 1<bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)/uintptr(t.bucketsize)))//老的数据结构对应的槽如果有数据,就从老的取 if c := h.oldbuckets; c !=nil {if !h.sameSizeGrow() { m>>= 1 //如果正在扩容,老的容量为新的容量的一半 } oldb := (/bmap)(unsafe.Pointer(uintptr(c) + (hash&m)/uintptr(t.bucketsize)))if !evacuated(oldb) { b=oldb } } top := uint8(hash >> (sys.PtrSize/8 - 8))if top uintptr(t.keysize)) k= /((/unsafe.Pointer)(k))//如果第i个key等于我们要查找的key,就返回第i个value ifalg.equal(key, k) {//通过槽首地址+偏移量计算第i个value的位置 v := add(unsafe.Pointer(b), dataOffset+bucketCnt/uintptr(t.keysize)+i/uintptr(t.valuesize)) v= /((/unsafe.Pointer)(v))return v, true} }//b指向下一个节点,如果不为空就继续遍历 b =b.overflow(t)if b ==nil {return unsafe.Pointer(&zeroVal[0]), false} } }

  

map[key] = value 源码分析//go:linkname reflectmapassign reflect.mapassign map[key] = value func reflectmapassign(t /maptype, h /hmap, key unsafe.Pointer, val unsafe.Pointer) { p := mapassign(t, h, key) //这里会把key写进去 typedmemmove(t.elem, p, val) //这里写value }//Like mapaccess, but allocates a slot for the key if it is not present in the map. func mapassign(t /maptype, h /hmap, key unsafe.Pointer) unsafe.Pointer { alg :=t.key.alg hash :=alg.hash(key, uintptr(h.hash0)) h.flags|=hashWriting//没元素就分配1个元素的空间 if h.buckets ==nil { h.buckets= newarray(t.bucket, 1) } again://hash到第bucket个槽 bucket := hash & (uintptr(1)<bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket/uintptr(t.bucketsize))) top := uint8(hash >> (sys.PtrSize/8 - 8))if top uint8 //标记位 var insertk unsafe.Pointer//key写在这里 var val unsafe.Pointer //value写在这里 for{for i := uintptr(0); i < bucketCnt; i++{if b.tophash[i] !=top {//第i个元素为空,如果是新增的,新增就往这里写数据啊 if b.tophash[i] == empty && 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)) }continue} k := add(unsafe.Pointer(b), dataOffset+i/*uintptr(t.keysize))ift.indirectkey { k= /*((/*unsafe.Pointer)(k)) }//如果key相等就是更新数据 if !alg.equal(key, k) {continue}//already have a mapping for key. Update it. ift.needkeyupdate { typedmemmove(t.key, k, key) }//更新数据,找到对应的位置返回就行 val = add(unsafe.Pointer(b), dataOffset+bucketCnt/*uintptr(t.keysize)+i/*uintptr(t.valuesize))gotodone }//b指向下一个节点,如果不为空就继续遍历 ovf :=b.overflow(t)if ovf ==nil {break} b=ovf }//已经处于扩容状态就不能再扩容了,就新老两个数据结构,没有第三了//元素个数>6.5/*槽数量(槽的每个节点能容纳8个元素,但是分布不可能这么均匀的),可以扩容//槽节点写满的个数较多也可以扩容 if !h.growing() && (overLoadFactor(int64(h.count), h.B) ||tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h)goto again //Growing the table invalidates everything, so try again }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)) }//引用类型分配key所需空间,同时把key在槽中对应的位置指向这个空间 ift.indirectkey { kmem :=newobject(t.key)/*(/*unsafe.Pointer)(insertk) =kmem insertk=kmem }//引用类型分配value所需空间,同时把value在槽中对应的位置指向这个空间 ift.indirectvalue { vmem :=newobject(t.elem)/*(/*unsafe.Pointer)(val) =vmem }//将key写入刚分配的空间 typedmemmove(t.key, insertk, key)//更新标记位 /*inserti =top//元素个数+1 h.count++done:if h.flags&hashWriting == 0{throw("concurrent map writes") } h.flags&^=hashWritingift.indirectvalue { val= /*((/*unsafe.Pointer)(val)) }//直接将val返回了,value为一个结构体(非指针)map[key].fieldXXX = 1,这样做是不行的//因为val作为返回值会被拷贝,如果val类型结构体(非指针),map[key]返回的就是一个拷贝,并没有更新真正的val,而指针类型却没有这个问题,如果结构体较大最好以指针的方式存入map returnval }

 

版权声明
本文为[啊汉]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/hlxs/p/10408961.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领