在Golang中探索Map_0

作者｜赵彦辉简介本文主要通过探索Map在golang中的数据结构和源码实现，包括map的模型探索、访问、扩展等，来学习和理解map的特性.欢迎大家一起讨论。Map的底层内存模型在goland的源码中说明了map的底层struct是hmap，是hashmap的缩写typehmapstruct{//map中存储的元素个数，len()时直接返回map)在golang中调用字段countint//状态标志位，可以通过&运算定义的枚举值flags来判断当前是否处于该状态uint8Buint8//2^B表示桶的个数，和B表示哈希桶分组后有多少位nooverflowuint16//溢出桶的大概个数hash0uint32//哈希种子（hashseed）一般为质数bucketsunsafe.Pointer//一共有2^B个桶，但是如果没有存储任何元素，这个字段可能是niloldbucketsunsafe.Pointer//扩容的时候，把旧的bucket数组放在这里，新的buckets会比这个大一倍。存储桶已迁移。extra*mapextra//可选字段}B是buckets数组长度的对数，即bucket数组的长度为2^B。bucket的本质是一个指针，指向一块内存空间，它指向的struct如下：surface(src/runtime/hashmap.go)结构，在编译时会加入，动态创建新结构：typebmapstruct{topbits[8]uint8keys[8]keytypevalues[8]valuetypepaduintptr//内存对齐，可能不需要溢出uintptr//当桶的8个key都满了}bmap就是我们常说的“桶”的底层数据结构。一个bucket最多可以存储8个key/value，map通过hash函数得到hash值决定分配到哪个bucket，然后根据hash的高8位寻找放在bucket的什么位置价值。有一个工作在进行，就是：查询当前k/v应该存放的位置。赋值/取值，这样我们就明白了key在map中的位置，也就明白了访问。底层代码funcmapaccess2(t*maptype,h*hmap,keyunsafe.Pointer)(unsafe.Pointer,bool){//map为空，或者元素个数为0，直接返回notfoundifh==nil||h.count==0{returnunsafe.Pointer(&zeroVal[0]),false}//不支持并发读写ifh.flags&hashWriting!=0{throw("concurrentmapreadandmapwrite")}//根据hash函数计算哈希值。注意不同类型的key可能使用不同的hash函数hash:=t.hasher(key,uintptr(h.hash0))//如果B=5，那么结果用二进制表示就是11111，返回的是所有的值1sintheBbitsm:=bucketMask(h.B)//根据hash的最后B位，定位桶数组中的位置b:=(*bmap)(unsafe.Pointer(uintptr(h.buckets)+(hash&m)*uintptr(t.bucketsize)))//当h.oldbuckets不为空时，表示map已经展开。//此时，新桶中可能没有旧内容。//所以它必须在旧的Ifc:=h.oldbuckets;c!=nil{if!h.sameSizeGrow(){//表示之前的桶只有一半，所以需要除以2m>>=1}oldb:=(*bmap)(unsafe.指针(uintptr(c)+(hash&m)*uintptr(t.bucketsize)))if!evacuated(oldb){b=oldb}}//tophash取其高8位值top:=tophash(hash)//一个桶存储了8个元素后，不能再放入，此时会创建一个新的桶并挂在原桶的溢出指针成员上//遍历当前桶的所有链式桶for;b!=零；b=b.overflow(t){//查询桶的8个位置i:=uintptr(0);我=15时，即buckets总数2^B大于等于2^15，如果溢出的buckets个数超过2^15。（触发等于展开）第一种情况，第二种情况，Map的顺序就是结论。在golang中，地图是乱序的。准确地说，不能严格保证顺序。从上面的源码我们可以知道，golang中的map在扩容后，可能会将一些key移动到新的内存中。由于在扩容和移动数据的过程中并没有记录原始数据的位置，在golang的数据结构中也没有保存数据的顺序，所以这部分实际上是扩容后乱序的。遍历的过程其实就是依次遍历内存地址，同时依次遍历内存地址中的key。但到现在已经不正常了。但是如果我有地图的话，我保证我不会修改或者删除地图，所以按理说没有扩容就没有变化。但也正因如此，GO才会出现在源码中。但是有一个有趣的现象，即使没有通过插入、删除等操作对map进行扩容，在遍历过程中它仍然是乱序的。objMap:=make(map[string]int)fori:=0;我<5;i++{objMap[strconv.Itoa(i)]=i}fori:=0;我<5;i++{varvalStr1,valStr2stringfork,v:=rangeobjMap{fmt.Println(k)fmt.Println(v)valStr1+=k}fork,v:=rangeobjMap{fmt.Println(k)fmt.Println(v)valStr2+=k}fmt.Println(valStr1==valStr2)ifvalStr1!=valStr2{fmt.Println("notequal")}}fmt.Println("end")以上操作结果不难看出，即使不展开地图，遍历多次也会乱序。这是因为golang官方在设计时故意加入随机元素，将遍历map的顺序随机化，防止用户使用它进行顺序遍历。而且这是有风险的代码，在GO严格的语法规则下，坚决不提倡。所以我们在使用map的时候一定要记住它是无序的，不要依赖它的顺序。Map的并发性首先，我们都知道golang中的map并不是一个并发安全的数据结构。当多个goruotines同时读写一个map时，会出现并发写问题：fatalerror:concurrentmapwrites。但是map为什么不支持并发安全，主要是成本和收益的问题。官方回答如下：典型使用场景：map的典型使用场景是不需要多个goroutine的安全访问。非典型场景（需要原子操作）：地图可能是一些更大的数据结构的一部分或已经同步的计算。性能场景考虑：如果只对少数几个程序增加安全性，导致所有map操作都要处理互斥体，会降低大部分程序的性能。同时，golang提供了并发安全的同步映射。,//不支持并发读写ifh.flags&hashWriting!=0{throw("concurrentmapreadandmapwrite")}但是我们又有一个问题，为什么golangmap在有的时候不抛出错误或者panic是并发冲突，但是为了让程序死机，选择让程序崩溃。这是golang官方对map使用的风险和复杂度权衡的考虑。首先，map在官方文档中明确表示不支持并发读写，所以对map本身的并发读写操作是不正确的。场景假设1：如果map在写入或读取时选择增加error返回值，程序将无法像现在这样使用map，需要额外捕获和判断err。场景假设2：如果map选择panic（可以恢复），如果有数据并发写入的场景，会导致恢复。这种场景如果不特别处理，map中就会出现脏数据。data，这时候程序在使用map的时候会出现不可预知的错误，此时很难找到问题的根源。因此，在考虑了这些场景后，golang选择显式抛出crash异常，让风险提前暴露。可以清楚地定位问题点。综上所述，我们在使用map的时候，一定要严格保证在单线程中使用。如果有多个线程，建议使用syncmap