Golang中map的深入探究

第Golang中map的深入探究目录简介Map的底层内存模型Map的存与取底层代码Map的扩容第一种情况第二种情况Map的有序性Map的并发总结

简介

本文主要通过探究在golang中map的数据结构及源码实现来学习和了解map的特性，共包含map的模型探究、存取、扩容等内容。欢迎大家共同讨论。

Map的底层内存模型

在golang的源码中表示map的底层struct是hmap，其是hashmap的缩写

typehmapstruct{

//map中存入元素的个数，golang中调用len(map)的时候直接返回该字段

countint

//状态标记位，通过与定义的枚举值进行操作可以判断当前是否处于这种状态

flagsuint8

Buint8//2^B表示bucket的数量，B表示取hash后多少位来做bucket的分组

noverflowuint16//overflowbucket的数量的近似数

hash0uint32//hashseed（hash种子）一般是一个素数

bucketsunsafe.Pointer//共有2^B个bucket，但是如果没有元素存入，这个字段可能为nil

oldbucketsunsafe.Pointer//在扩容期间，将旧的bucket数组放在这里，新buckets会是这个的两倍大

nevacuateuintptr//表示已经完成扩容迁移的bucket的指针，地址小于当前指针的bucket已经迁移完成

extra*mapextra//optionalfields

}

B是buckets数组的长度的对数，即bucket数组的长度是2^B。bucket的本质上是一个指针，指向了一片内存空间，其指向的struct如下所示：

//AbucketforaGomap.

typebmapstruct{

tophash[bucketCnt]uint8

}

但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构：

typebmapstruct{

topbits[8]uint8

keys[8]keytype

values[8]valuetype

paduintptr//内存对齐使用，可能不需要

overflowuintptr//当bucket的8个key存满了之后

}

bmap就是我们常说的桶的底层数据结构，一个桶中可以存放最多8个key/value,map使用hash函数得到hash值决定分配到哪个桶，然后又会根据hash值的高8位来寻找放在桶的哪个位置具体的map的组成结构如下图所示：

Map的存与取

在map中存与取本质上都是在进行一个工作，那就是:

查询当前k/v应该存储的位置。赋值/取值，所以我们理解了map中key的定位我们就理解了存取。

底层代码

funcmapaccess2(t*maptype,h*hmap,keyunsafe.Pointer)(unsafe.Pointer,bool){

//map为空，或者元素数为0，直接返回未找到

ifh==nil||h.count==0{

returnunsafe.Pointer(zeroVal[0]),false

//不支持并发读写

ifh.flagshashWriting!=0{

throw("concurrentmapreadandmapwrite")

//根据hash函数算出hash值，注意key的类型不同可能使用的hash函数也不同

hash:=t.hasher(key,uintptr(h.hash0))

//如果B=5，那么结果用二进制表示就是11111，返回的是B位全1的值

m:=bucketMask(h.B)

//根据hash的后B位，定位在bucket数组中的位置

b:=(*bmap)(unsafe.Pointer(uintptr(h.buckets)+(hashm)*uintptr(t.bucketsize)))

//当h.oldbuckets非空时，说明map发生了扩容

//这时候，新的buckets里可能还没有老的内容

//所以一定要在老的里面找，否则有可能发生“消失”的诡异现象

ifc:=h.oldbuckets;c!=nil{

if!h.sameSizeGrow(){

//说明之前只有一半的bucket，需要除2

m=1

oldb:=(*bmap)(unsafe.Pointer(uintptr(c)+(hashm)*uintptr(t.bucketsize)))

if!evacuated(oldb){

b=oldb

//tophash取其高8bit的值

top:=tophash(hash)

//一个bucket在存储满8个元素后，就再也放不下了，这时候会创建新的bucket，挂在原来的bucket的overflow指针成员上

//遍历当前bucket的所有链式bucket

for;b!=nil;b=b.overflow(t){

//在bucket的8个位置上查询

fori:=uintptr(0);ibucketCnt;i++{

//如果找到了相等的tophash，那说明就是这个bucket了

ifb.tophash[i]!=top{

continue

//根据内存结构定位key的位置

k:=add(unsafe.Pointer(b),dataOffset+i*uintptr(t.keysize))

ift.indirectkey{

k=*((*unsafe.Pointer)(k))

//校验找到的key是否匹配

ift.key.equal(key,k){

//定位v的位置

v:=add(unsafe.Pointer(b),dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))

ift.indirectvalue{

v=*((*unsafe.Pointer)(v))

returnv,true

//所有bucket都没有找到，返回零值和false

returnunsafe.Pointer(zeroVal[0]),false

}

寻址过程

Map的扩容

在golang中map和slice一样都是在初始化时首先申请较小的内存空间，在map的不断存入的过程中，动态的进行扩容。扩容共有两种，增量扩容与等量扩容（重新排列并分配内存）。下面我们来了解一下扩容的触发方式：

负载因子超过阈值，源码里定义的阈值是6.5。(触发增量扩容)overflow的bucket数量过多：当B小于15，也就是bucket总数2^B小于2^15时，如果overflow的bucket数量超过2^B；当B=15，也就是bucket总数2^B大于等于2^15，如果overflow的bucket数量超过2^15。（触发等量扩容）

第一种情况

第二种情况

Map的有序性

先说结论，在golang中map是无序的，准确的说是无法严格保证顺序的，从上面的源码中我们可以知道，golang中map在扩容后，可能会将部分key移至新内存，由于在扩容搬移数据过程中，并未记录原数据位置，并且在golang的数据结构中也并未保存数据的顺序，所以那么这一部分在扩容后实际上就已经是无序的了。

遍历的过程，其实就是按顺序遍历内存地址，同时按顺序遍历内存地址中的key。但这时已经是无序的了。但是如果我就一个map，我保证不会对map进行修改删除等操作，那么按理说没有扩容就不会发生改变。但也是因为这样，GO才在源码中但是有一个有趣的现象，就算不对map进行插入删除等操作致使其扩容，其在遍历过程中仍是无序的。

objMap:=make(map[string]int)

fori:=0;ii++{

objMap[strconv.Itoa(i)]=i

fori:=0;ii++{

varvalStr1,valStr2string

fork,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")

以上的运行结果是

不难看出，即使不对map进行扩容，在多次遍历时也是无序的，这是因为golang官方在设计时故意加上随机的元素，将遍历map的顺序随机化，用来防止使用者用来顺序遍历。

依赖map的顺序进行遍历，这是有风险的代码，在GO的严格语法规则下，是坚决不提倡的。所以我们在使用map时一定要记得其是无序的，不要依赖其顺序。

Map的并发

首先我们大家都知道，在golang中map并不是一个并发安全的数据结构，当几个goruotine同时对一个map进行读写操作时，就会出现并发写问题：fatalerror:concurrentmapwrites。但是为什么map是不支持并发安全的呢，主要是因为成本与效益。

官方答复原因如下：

典型使用场景：map的典型使用场景是不需要从多个goroutine中进行安全访问。非典型场景（需要原子操作）：map可能是一些更大的数据结构或已经同步的计算的一部分。

性能场景考虑：若是只是为少数程序增加安全性，导致map所有的操作都要处理mutex，将会降低大多数程序的性能。同时golang提供了并发安全的syncmap。

，//不支持并发读写

ifh.flagshashWriting!=0{

throw("concurrentmapreadandmapwrite")

}

但是我们又有疑问了，为什么golangmap并发冲突了不抛一个error出来，或者panic掉，而是要让程序panic，选择让程序crash崩溃掉。这里是golang官方出于权衡风险和map使用复杂度场景考虑的，首先map在官方中就明确表示不支持并发读写，所以并发对map进行读写操作本身就是不正确的。

场景假设一：如果map选择在写入或者读取时增加error返回值，会导致程序在使用map时就无法像现在一样，需要额外的捕获并判断err。

场景假设二