Go源码解析——Map篇
站长
· 阅读数 50
前言
上一篇文章《Go源码解析——Channel篇》中，我们对Channel的源码进行了详细解析，相信看过的同学已经对Channel的底层原理有了较为深入的了解。
和Channel一样，Map在我们的日常开发工作中也有着广泛的应用，了解Map的底层原理可以让我们在业务中写出更高效的代码，同样也可以避免在开发中踩坑。
本篇文章从源码角度学习golang map的底层操作，和上一篇文章一样，基于Go1.17源码进行分析。
相信大家对Hash表并不陌生，Go语言中的Map基于Hash表实现，通过链表来解决Hash的碰撞问题，主要结构如下图所示：
本文会从map的底层数据结构 、初始化 、Map数据的查找、写入、更新、删除以及遍历等常见操作展开，在文章末尾提出map的并发操作并与Java****中哈希表进行对比，篇幅较长，请大家耐心阅读😂。
本专栏目前已更新两篇源码文章，后续会持续更新Golang源码和编译相关的文章，对Golang源码感兴趣的同学可以持续关注。
专栏地址：[Golang源码解析]
如果对大家有帮助的话，麻烦三连哦😊😊😊！！！
hmap数据结构
首先我们对map的底层数据结构hmap进行介绍，结构如下：
代码位置：src/runtime/map.go
type hmap struct {
count int // map中k-v对数
flags uint8 // map状态字段
B uint8 // 桶的个数为2^B
noverflow uint16 // 溢出桶的个数
hash0 uint32 // 计算key的hash值时作为hash种子使用
buckets unsafe.Pointer // 指向bucket首地址的指针
oldbuckets unsafe.Pointer // map扩容后, 该字段指向扩容前buckets内存首地址
nevacuate uintptr // 迁移进度
extra *mapextra // 可选数据
}
type mapextra struct {
overflow *[]*bmap // overflow地址数组的指针
oldoverflow *[]*bmap // 扩容时原overflow地址数组的指针
nextOverflow *bmap // 下一个空闲overflow的地址
}
bucket的结构为bmap ，但这只是(src/runtime/map.go)的结构，编译期间会动态创建一个新的结构：
// 表面是以下的情况
type bmap struct {
tophash [8]uint8
}
// 以下才是bucket实际的结构
type bmap struct {
topbits [8]uint8 // 存储hash值的高8位，除了存储hash值的高8位，也可以存储一些状态码
keys [8]keytype // key数组，隐藏字段
values [8]valuetype // value数组，隐藏字段
overflow uintptr // 溢出buceket指针，隐藏字段
}
通过上面的讲解，大家可能只是对字段的含义有所了解，但是对map每个字段和结构在流程中起到的作用还是很迷惑，没关系，我们会在对map常见操作的原理解析中补充细节。
创建Map
由于map的创建方式不同，其对应的底层编译方式不同，按照初始化方式不同可以分为字面量初始化和make初始化两种，按照编译方式的不同可以分为栈分配 、堆分配 、常规分配三种。
同一种初始化方式，可能会对应不同的内存分配方式，这里主要介绍map的常见创建方式以及对应的内存分配方式，并会对不同情况下的内存分配进行总结。
创建方式
字面量创建方式
// 栈分配
m1 := map[int]int{1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1}
m1[1] = 1024
// 堆分配
m2 := map[int]int{1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1}
fmt.Println(m2)// 此处由于使用fmt.Println发生了内存逃逸
// 常规分配
m3 := map[int]int{1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1}
m3[1] = 1024
以上三种创建方式中，分别对应着栈上分配内存 、堆上分配内存和常规分配 （makemap函数）三种内存分配方式，对应的汇编结果如下：go.godbolt.org/z/MaKfdTjoo
查看与初始化相关的带有CALL 指令的如下：
CALL runtime.fastrand(SB)
CALL runtime.makemap_small(SB)
CALL runtime.makemap(SB)
关键字创建方式
// 栈分配
m1 := make(map[int]int)
m1[0] = 1024
// 栈分配
m2 := make(map[int]int,8)
m2[0] = 1024
// 堆分配
m3 := make(map[int]int,8)
fmt.Println(m3)// 此处由于使用fmt.Println发生了内存逃逸
// 常规分配
m4 := make(map[int]int,9)
m4[0] = 1024
以上四种字面量创建方式中，前两种初始化方式为栈上分配内存，后面两种分别为堆上分配内存和常规分配 （makemap函数），对应的汇编结果如下：go.godbolt.org/z/Ez1bzh3fT
CALL runtime.fastrand(SB)
CALL runtime.makemap_small(SB)
CALL runtime.makemap(SB)
总结 ：
- 无论是字面量初始化还是make初始化，当所需Map分配到堆上且所需长度<=8时，使用runtime.makemap_small初始化；
- 无论是字面量初始化还是make初始化，当所需Map分配到不需要分配到堆上且所需长度<=8时，通过快速哈希方式创建；
- 其余情况均调用runtime.makemap函数进行内存分配
由于大部分场景中都是调用makemap。下面我们对makemap函数进行详细介绍：
makemap
makemap函数主要完成以下工作：
- 内存校验，校验map初始化所需内存是否超过内存限制
- 创建结构体
- 获取hash种子
- 计算合适的B值
- 调用makeBucketArray函数，得到桶的首地址以及溢出bmap
- 返回hmap指针
源码如下：
代码位置：src/runtime/map.go
func makemap(t *maptype, hint int, h *hmap) *hmap {
// 校验所需内存是否超过内存限制，即hint*size
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
// 创建结构体
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()// 获取hash种子
B := uint8(0)
// 计算B值
for overLoadFactor(hint, B) {
// hint > 8 && uintptr(hint) > 13*(2^B/2)
B++
}
h.B = B
if h.B != 0 {
var nextOverflow *bmap
// 调用makeBucketArray函数，得到桶的首地址以及溢出bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
// 溢出bmap不为nil
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
此处的重点内容是，makemap函数调用overLoadFactor函数完成B值的计算，之后调用makeBucketArray获取bmap的首地址和溢出桶的地址，代码如下：
func overLoadFactor(count int, B uint8) bool {
// count > 8 && uintptr(count) > 13*(2^B/2)
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// 返回2^B
func bucketShift(b uint8) uintptr {
return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}
makeBucketArray函数代码如下：
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b) // 2^B
nbuckets := base // buckets数量
if b >= 4 { // 如果 b>=4，额外申请一定数量bucket
nbuckets += bucketShift(b - 4))// 新增bucket的数量为2^(b-4)
sz := t.bucket.size * nbuckets // 整体大小
up := roundupsize(sz) // 返回分配的空间
if up != sz {
nbuckets = up / t.bucket.size // 重新计算桶数量
}
}
if dirtyalloc == nil {
buckets = newarray(t.bucket, int(nbuckets)) // 创建底层bucket数据
} else {
// 对dirtyalloc的空间进行一次清空
buckets = dirtyalloc
size := t.bucket.size * nbuckets
if t.bucket.ptrdata != 0 {
memclrHasPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
if base != nbuckets {
// 处理额外添加bucket的情况
// step1: 额外添加的初始位置
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
// step2: buckets的最后一个bucket
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
// step3: 将最后一个bucket的overflow指向buckets的头部
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
处理额外bucket的情况看起来有点复杂，这里借助一个例子讲解，当B为5时，此时base =2 ^ 5= 32，nbuckets = 2 ^ B + 2 ^ (B-4) = 32+2 = 34，具体如图所示：
Map中数据的读取
Go语言中常见的读取数据的方式如下：
value := m["name"]
value, ok := m["name"]
对应的汇编结果如下：go.godbolt.org/z/cjrE99YvK
与读取相关的CALL指令如下所示：
CALL runtime.mapaccess1_faststr(SB)
CALL runtime.mapaccess2_faststr(SB)
两种语法对应到以下两个不同的函数，稍后我们对函数进行源码分析。
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
key的定位
我们首先对key的定位原理进行介绍，这将对之后学习Map中数据的读取、写入和删除打下基础，这部分内容也可以说是Map的核心内容。
对于key的定位问题主要有两个步骤需要确定：
- 数据落在哪个bucket中
- 确定bucket中的具体位置
我们通过一个例子来说明，通过上面的示意图以及代码，这里我们假设B为5，key的定位流程如下图所示：
假定B = 5，所以bucket总数就是 2^5 = 32。
-
首先计算出待查找key的哈希，使用低5位00100，对应4号bucket
-
之后使用高8位10010110，对应十进制150，在6号 bucket中寻找tophash值（HOB hash）为150的 key，找到了2号槽位，那么对应的key和value也是在2号槽位，这样整个查找过程就结束了
如果在 bucket 中没找到，并且overflow不为空，则继续去overflow bucket中寻找，直到找到key或所有的key槽位都找遍了，包括所有的overflow bucket。
定位的核定逻辑：
- key的哈希值的低B位确定数据落在哪个桶里，key的哈希值的高8位确定数据的具体位置
需要注意的点包括：
- 每个bucket只能存8对key-value，一旦超过就通过overflow指向下一个bmap
- HOBHash 指的就是tophash，每个bucket中topHash唯一
- key 和 value 是各自放在一起的，并不是key/value/...这样的形式，可以节省内存空间
上面我们完成了key定位的讲解，接下来我们对数据读取的两个函数mapaccsess1和mapaccsess2进行介绍，由于mapaccsess1与mapaccsess2函数的区别在于runtime.mapaccess2多返回了一个bool值标记是否查询到数据，接下来以mapaccsess1为例对map中数据的读取原理进行解析。
mapaccsess1
mapaccsess1函数整体流程如下：
- 判断是否并发读写，如果是，则抛出panic（map不支持并发读写）；
- 计算hash值，根据hash的低B位找到对应的bucket，根据高8位，找到对应tophash槽位进而找到key-value；
- map迁移场景下，优先从oldbuckets中查找kv；
- 比较key，相等则返回value，不等则返回0值；
源码如下所示：
代码位置：src/runtime/map.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if h == nil || h.count == 0 {// 如果h为nil或无key-value，返回零值
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
// 并发读写会产生panic
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
hash := t.hasher(key, uintptr(h.hash0))// 计算hash值
m := bucketMask(h.B)// m表示map中bucket的数量
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 利用`hash mod m`可以计算bucket索引，b表示bucket首地址
// 如果map正在迁移，优先从oldbuckets中查找kv
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// 如果是等量扩容迁移，则oldbuckets实际的bucket数量是m的一半
m >>= 1
}
// 根据hash值，查找oldbuckets中对应的bucket地址
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 如果oldb的标志位不是撤离状态，则我们从oldb中查找kv
if !evacuated(oldb) {
b = oldb
}
}
// top表示hash的高8位，如果hash高8位小于5，则top需要加上5；因为5表示`minTopHash`
// top如果是小于等于5，都是表示特殊状态；正常的key的top值都是大于5的
top := tophash(hash)
bucketloop:
// 逐个查找对应bucket和其溢出bucket
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
// 如果b.tophash[i] == emptyRest，表示剩下的kv对都是空的，所以直接跳出循环
break bucketloop
}
continue
}
// 查找对应key的地址
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if t.key.equal(key, k) {
// 如果key相等，则找到对应的value
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
return unsafe.Pointer(&zeroVal[0]) // 返回对应的0值
}
Map中数据的新增和更新
Go语言中map的新增和更新操作如下所示：
m1 := make(map[int8]int)
m1[1] = 1 // 新增
m1[1] = 1024 // 更新
对应的汇编结果如下：go.godbolt.org/z/rPz6fjd4W
map 有很多种类的赋值语句：
func mapassign(mapType *byte, hmap map[any]any, key *any) (val *any)
func mapassign_fast32(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_fast32ptr(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_fast64(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_fast64ptr(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_faststr(mapType *byte, hmap map[any]any, key any) (val *any)
由于其原理是类似的，我们以mapassign为例进行分析：
mapassign
函数整体流程：
- map优先检查是否有相同的key，如果有，则表示是更新操作；
-
如果没有相同的key，则表示是插入操作
- 如果有空位，则在第一个空位处插入；
- 如果没有空位，则增加一个溢出bucket，在溢出bucket中插入；
- 插入操作可能会触发扩容操作；
- map不是一次性完成扩容的，而是逐步完成扩容的；
-
map库容分为等量迁移和加倍扩容：
- 等量迁移是为了让稀疏数据分布紧凑（由于删除操作，map可能会很稀疏）；
- 加倍扩容是由于数据过多，申请一个加倍空间来存储kv，加倍扩容同样会删除空槽位，让数据分布紧凑。
函数源码如下所示：
代码位置：src/runtime/map.go
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
if h.flags&hashWriting != 0 {// 并发读写检测
throw("concurrent map writes")
}
// 计算hash值
hash := t.hasher(key, uintptr(h.hash0))
// map状态设置为hashWriting
h.flags ^= hashWriting
if h.buckets == nil {
// 如果map没有初始化bucket，申请bucket空间
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// 根据hash的低B位确定在哪个桶
bucket := hash & bucketMask(h.B)
// 判断是否在扩容
if h.growing() {
// 将对应的bucket从hmap.oldbuckets迁移到新的buckets中
growWork(t, h, bucket)
}
// 目标bucket首地址
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
// hash高八位
top := tophash(hash)
var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer
bucketloop:
for {
// 遍历tophash查找key是否已经存在，或者是否有空位插入kv
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
// tophash中可能有多个空位，我们记录第一个空位的索引
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
}
// b.tophash[i] == emptyRest 表示剩余都是空位，则直接结束循环
break bucketloop
}
continue
}
// 获取对应位置key
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
// 判断key是否相等
if !t.key.equal(key, k) {
continue
}
// 更新
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
goto done
}
// 如果bucket是满的，而且没找到对应的key，溢出查找
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
// 若无此key，此次操作是插入，此时需要判断map是否需要扩容；
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
// hashGrow函数主要是设置hmap.flags为扩容状态，申请新的内存空间用来扩容，同时设置hmap.oldbuckets为原来的hmap.buckets
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
// inserti == nil表示没有插入的槽位，需要申请溢出bucket
if inserti == nil {
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// store new key/elem at insert position
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectelem() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.key, insertk, key)
*inserti = top
h.count++
done:
// 设置flag并写入value
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {
elem = *((*unsafe.Pointer)(elem))
}
return elem
}
触发扩容的情况主要包括两种情况：
-
overLoadFactor函数用来判断map是否由于数据太多，需要增量1倍扩容
-
tooManyOverflowBuckets函数用来判断map是否需要等量迁移，map由于删除操作，溢出bucket很多，但是数据分布很稀疏，我们可以通过等量迁移，将数据更加紧凑的存储在一起，节约空间
// 装载因子超过6.5
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// overflow buckets太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
return noverflow >= uint16(1)<<(B&15)
}
再来看看真正执行搬迁工作的 growWork函数：
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 这里将当前 bucketIndex 对应的oldBuckets进行迁移
evacuate(t, h, bucket&h.oldbucketmask())
// evacuate one more oldbucket to make progress on growing
if h.growing() {
// 如果还没结束迁移，则将在oldBuckets中h.nevacuate的对应bucket位置进行迁移
evacuate(t, h, h.nevacuate)
}
}
evacuate函数源码如下：
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
// 定位旧bucket地址
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// 计算容量结果是 2^B
newbit := h.noldbuckets()
// 如果b没有被搬迁过
if !evacuated(b) {
// 默认是等size扩容，前后bucket序号不变
var xy [2]evacDst
// 通过x来进行搬迁
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))
// 如果不是等size扩容，前后bucket序号有变
if !h.sameSizeGrow() {
// 通过y来进行搬迁
y := &xy[1]
// y 代表的bucket序号增加了2^B
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，包括overflow buckets,b是旧bucket地址
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
v := add(k, bucketCnt*uintptr(t.keysize))
// 遍历bucket中的所有cell
for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
// 当前cell的top hash值
top := b.tophash[i]
// 如果cell为空，即没有key
if top == empty {
// 那就标志它被"搬迁"过
b.tophash[i] = evacuatedEmpty
continue
}
// 未被搬迁的cell只可能是empty 或是正常的top hash（大于 minTopHash）
if top < minTopHash {
throw("bad map state")
}
// 如果key是指针，则解引用
k2 := k
if t.indirectkey {
k2 = *((*unsafe.Pointer)(k2))
}
var useY uint8
// 如果不是等量扩容
if !h.sameSizeGrow() {
// 计算hash值，和key第一次写入时一样
hash := t.key.alg.hash(k2, uintptr(h.hash0))
// 如果有协程正在遍历map如果出现相同的key值，算出来的hash值不同
if h.flags&iterator != 0 && !t.reflexivekey && !t.key.alg.equal(k2, k2) {
// useY =1 使用位置Y
useY = top & 1
top = tophash(hash)
} else {
// 第B位不是0
if hash&newbit != 0 {
// 使用位置Y
useY = 1
}
}
}
if evacuatedX+1 != evacuatedY {
throw("bad evacuatedN")
}
// 决定key迁移到X还是Y
b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
dst := &xy[useY] // evacuation destination
// 如果xi等于8，说明要溢出了
if dst.i == bucketCnt {
// 新建一个bucket
dst.b = h.newoverflow(t, dst.b)
// xi从0开始计数
dst.i = 0
// key移动的位置
dst.k = add(unsafe.Pointer(dst.b), dataOffset)
// value移动的位置
dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
}
// 设置 top hash 值
dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
// key是指针
if t.indirectkey {
// 将原key（是指针）复制到新位置
*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
} else {
// 将原key（是值）复制到新位置
typedmemmove(t.key, dst.k, k) // copy value
}
// value同上
if t.indirectvalue {
*(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v)
} else {
typedmemmove(t.elem, dst.v, v)
}
// 定位到下一个cell
dst.i++
dst.k = add(dst.k, uintptr(t.keysize))
dst.v = add(dst.v, uintptr(t.valuesize))
}
}
// bucket搬迁完毕如果没有协程在使用老的buckets，就把老buckets清除
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)
}
}
// 更新搬迁进度
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
Map中数据的删除
Go语言中删除map中数据操作如下：
delete(m, "name")
对应编译结果如下：go.godbolt.org/z/3KPzEhvMG
由编译结果，底层调用的函数为mapdelete，接下来对其进行详细介绍：
mapdelete
mapdelete函数的流程如下：
- 首先会检查 h.flags 标志，如果发现写标位是 1，直接 panic；
- 计算 key 的哈希，找到对应的bucket，如果正在扩容中，触发一次搬迁操作；
- 查找key操作同样是两层循环，核心还是找到key的具体位置。寻找过程都是类似的，首先查找bucket，之后查找具体的位置。
- 找到对应位置后，对key或者value进行“清除”操作。
详细代码如下：
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
...
if h == nil || h.count == 0 { // 如果hmap为nil或者为空
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return
}
if h.flags&hashWriting != 0 { // 如果正在进行写入，则throw
throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0)) // 算出当前key的hash值
h.flags ^= hashWriting // 将“写入位”置1
bucket := hash & bucketMask(h.B) // 算出对应的 bucketIndex
if h.growing() {
growWork(t, h, bucket)// 参考上文growwork函数的解析
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
// 寻找对应的bucket
bOrig := b
top := tophash(hash)
search:
for ; b != nil; b = b.overflow(t) { // 遍历当前的bucket以及overflow
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
// 如果emptyReset，说明之后无数据，break
break search
}
continue
}
// 找到了对应的位置
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
k2 := k
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
if !t.key.equal(key, k2) { // hash冲突
continue
}
// 这里清理空间key的空间
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.ptrdata != 0 {
memclrHasPointers(k, t.key.size)
}
// elem与上面key同理
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
*(*unsafe.Pointer)(e) = nil
} else if t.elem.ptrdata != 0 {
memclrHasPointers(e, t.elem.size)
} else {
memclrNoHeapPointers(e, t.elem.size)
}
b.tophash[i] = emptyOne // emptyOne表示曾经有过，然后被清空了
// 判断当前位置之后是否还有数据存储过
if i == bucketCnt-1 {
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
goto notLast
}
} else {
if b.tophash[i+1] != emptyRest {
goto notLast
}
}
// 到这里说明当前的bucket的topIndex 以及之后索引包括overflow都没有过数据，准备从后向前进行整理
for {
b.tophash[i] = emptyRest // 则将当前的top设置为emptyRest
if i == 0 {// 由于是i==0 ，则要寻找到上一个bucket
if b == bOrig {
break // beginning of initial bucket, we're done.
}
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {//找到当前 bucket 的上一个 bucket
}
i = bucketCnt - 1
} else {// 寻找上一个top
i--
}
if b.tophash[i] != emptyOne {
break
}
}
notLast:
h.count--
break search
}
}
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting // 将“写入位”置0
}
func mapclear(t *maptype, h *hmap) {
...
if h == nil || h.count == 0 {
return
}
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
h.flags ^= hashWriting // "写入位"置1
h.flags &^= sameSizeGrow // 将 sameSizeGrow 清0
h.oldbuckets = nil
h.nevacuate = 0
h.noverflow = 0
h.count = 0// Keep the mapextra allocation but clear any extra information.if h.extra != nil { // 这里直接数据清空
*h.extra = mapextra{}
}
_, nextOverflow := makeBucketArray(t, h.B, h.buckets)// 将其中buckets数据清空，并拿到nextOverFlow
if nextOverflow != nil {
h.extra.nextOverflow = nextOverflow // 重新更新h.extra.nextOverflow
}
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting // 将“写入位”置0
}
Map的遍历操作
Go语言中map的遍历操作如下所示：
for k, v := range m {
……
}
对应的汇编结果如下：go.godbolt.org/z/3dM69W1cG
由编译结果，底层调用的函数为mapiterinit，接下来对其进行详细介绍：
mapiterinit
首先，我们知道golang中的map是无序的，但是有没有想过为什么golang中的map是无序的？
map无序主要是有两个原因：
- 首先是map的迁移；在遍历中，首先遍历bucket，之后遍历key，但是由于map的迁移，key的位置有很大改变；
- 如果不发生迁移，是不是遍历就是有序的呢？ golang为了保证遍历的无序性，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历；
mapiterinit核心部分代码如下：
func mapiterinit(t *maptype, h *hmap, it *hiter) {
...
it.t = t
it.h = h
it.B = h.B
it.buckets = h.buckets
if t.bucket.kind&kindNoPointers != 0 {
h.createOverflow()
it.overflow = h.extra.overflow
it.oldoverflow = h.extra.oldoverflow
}
r := uintptr(fastrand())// 生成随机数
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)// 找到随机开始的bucketIndex
it.offset = uint8(r >> h.B & (bucketCnt - 1))// 找到随机开始的bucket的topHash索引
it.bucket = it.startBucket
...
mapiternext(it)
}
Map的并发操作
上面我们说了map是不支持并发读写的，如果想要进行并发操作可以参考以下方法：
- 解决方法1：读写锁sync.RWMutex
type TestMap struct {
M map[int]string
Lock sync.RWMutex
}
func main() {
testMap := TestMap{}
testMap.M = map[int]string{1: "lili"}
go func() {
i := 0
for i < 10000 {
testMap.Lock.RLock()
fmt.Println(i, testMap.M[1])
testMap.Lock.RUnlock()
i++
}
}()
go func() {
i := 0
for i < 10000 {
testMap.Lock.Lock()
testMap.M[1] = "lily"
testMap.Lock.Unlock()
i++
}
}()
for {
runtime.GC()
}
}
- 解决方法2：使用golang提供的sync.Map
func main() {
m := sync.Map{}
m.Store(1, 1)
i := 0
go func() {
for i < 1000 {
m.Store(1, 1)
i++
}
}()
go func() {
for i < 1000 {
m.Store(2, 2)
i++
}
}()
go func() {
for i < 1000 {
fmt.Println(m.Load(1))
i++
}
}()
for {
runtime.GC()
}
}
以上，我们完成了对于golang中map的介绍，接下来，我们将介绍Java****中map的设计，看看有哪些不同
Java中map的设计
HashMap内部结构
Java中Map同样是采用数组+链表的结构，但细节上有明显不同。数组（Entry[] table）的长度为capacity，Entry<key,Value>的数目被称为HashMap的大小(size)，结构如下图所示：
基本工作流程
基本的工作流程同样分为两步:
- key的定位 ：根据key的hashCode，可以直接定位到存储这个Entry<key,Value>的桶所在的位置，这个时间的复杂度为O(1) ；
- 具体key-value的定位 ：在桶中查找对应的Entry<key,Value>对象节点，需要遍历这个桶的Entry<key,Value>链表，时间复杂度为O(n) ;
数组是内存中连续的存储单元，空间代价是很大的，但是随机存取的速度是Java集合中最快的。我们可以增加桶的数量，减少Entry<key,Value>链表长度，来提高读取数据的速度（空间换时间）。
但不能刚开始就给HashMap分配过多的桶，因为数组的创建代价很大，况且不能确定HashMap的实际使用空间，为解决这一个问题，HashMap采用动态分配桶数量的方法。
HashMap的扩容策略：
如果HashMap 的大小（size）> HashMap的capacity*加载因子（经验值0.75）时容量扩充一倍；然后重新将原桶中的Entry<key,Value>进行分配。
源码解析
这里，我们同样对常见操作的源码进行讲解，主要原理是上文中提到的定位方式以及扩容策略，对Java源码不感兴趣的同学可以跳过。
Put
Put方法整体流程：
- 获取hashcode：获取key的hashcode，根据此值确定要存放桶的索引；
-
遍历：遍历桶中的Entry<key,Value>链表，查找对应key的对象是否已存在；
- 若已存在，对数据进行更新
- 若不存在，则创建一个新的Entry<key,Value>对象，然后添加到链表的头部
- 阈值判断：当前的HashMap的大小(size)是否超过了阀值，若超过了阀值(threshold)，则增大HashMap的容量(capacity)，并且重新组织各个Entry<key,Value>排列。
public V put(K key, V value) {
// 1.如果key为null，那么将此value放置到table[0]
if (key == null){
return putForNullkey(value);
}
// 2.重新计算hashcode
int hash = hash(key.hashCode());
// 3.获取桶的索引
int i = indexFor(hash, table.length);
// 4.循环遍历Entry列表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 5.若已存在,则将Value值更新
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 6.若不存在，创建新的Entry<key,Value>对象，添加到链表头部。
addEntry(hash, key, value, i);
return null;
}
当HashMap的大小大于阈值时，HashMap的扩充算法:
HashMap的大小大于阀值时，HashMap会对此HashMap的容量进行扩充:
- 容量的大小应当是 2的N次幂；
- 当容量大小超过阀值时，容量扩充为当前的一倍；
- 这里容量扩充的操作可以分为以下几个步骤:
-
- 申请一个大小为当前容量两倍的数组；
- 将旧数组的Entry[] table中的链表重新计算hash值，然后均匀地分配到新的扩充数组；
- 释放旧数组；
由于容量扩充的代价非常大，所以每次扩充的比例为当前的一倍，这样可以减少扩充次数。
为了提高HashMap的性能：
- 使用HashMap时，若容量已知，则应该在创建HashMap的时候指定它的容量；
- 如果你确定HashMap使用的过程中，size会非常大，那么你应该控制好加载因子的大小，尽量将它设置得大些，避免Entry[] table过大。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
Get
Get方法整体流程：
- 获取这个key的hashcode值，根据此hashcode值确定桶的索引；
-
遍历链表，查找Entry<key,Value>对；
- 若已存在，定位到对应的Entry<key,Value>,返回value；
- 若不存在，返回null；
public V get(Object key) {
if (key == null)
return getForNullkey();
int hash = hash(key.hashCode());
// 遍历列表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
HashMap允许key以null的形式存取，Hashmap会将key为null组成的Entry<null,Value>放置到table[0],即第一个桶中，在put()和get()操作时，会先对key 为null的值特殊处理：
private V getForNullkey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
private V putForNullkey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
Remove
移除键值对的操作的流程分为两步：
- 定位对象；
-
完成链表中节点的删除;移除键值对的操作的流程分为两步：
-
定位对象；
- 完成链表中节点的删除;
public V remove(Object key) {
Entry<K,V> e = removeEntryForkey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForkey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
总结
- HashMap是线程不安全的，如果想使用线程安全的,可以使用ConcurrentHashMap；
- HashMap的查找效率很高，可直接定位到key值所在的桶；
-
使用HashMap时，要注意HashMap容量和加载因子的关系，这将直接影响到HashMap的性能问题；
- 加载因子过小，会提高HashMap的查找效率，但消耗大量的内存空间；
- 加载因子过大，节省了空间，但是会降低查找效率；
总结
以上，我们完成了对map数据结构，map中key的定位、数据的读取、新增、更新、删除以及遍历操作，并在最后介绍了golang中map的并发操作以及与java****中map设计的对比，篇幅较长，能看到这里真的很不容易。
map的结构上围绕着数组和链表展开，流程上围绕着key的定位、扩容、迁移等操作展开，个人认为核心部分主要在于key的定位以及扩容思想。
转载自:https://juejin.cn/post/7130082747715944461