为什么要研究map的实现
对于这个问题,我的回答有以下几个方面:
- 了解工业级map的另一种实现方案,增加自己的经验,可能对自己日后的工作有借鉴意义
- 只有了解了其实现原理才能清楚其性能瓶颈在哪,开发过程中尽量去避免
map的基本原理
map的底层结构是一个哈希表,map中的键值对被分配到了一个bucket数组上,每个bucket包含8个键值对。hash值的二进制低位部分被用来选择bucket,每个bucket存储了hash值的高位部分以用来在单个bucket上做区分。如果有超过8个key被hash到了同一个bucket上,那么就用链表连接到扩展bucket上。
底层数据结构
map 对应的结构体,一个map实际是hmap指针
type hmap struct {
count int // map中元素个数,即len(map)
flags uint8 // map的标记
B uint8 //bucket数量为2^B个
noverflow uint16 // 溢出bucket的近似数量
hash0 uint32 // hash seed 每次创建map都会生产一个随机的种子,提高hash碰撞攻击门槛
buckets unsafe.Pointer // bucket数组的地址,如果count=0,则有可能是nil
oldbuckets unsafe.Pointer //
nevacuate uintptr // 指示扩容进度,小于此地址的buckets迁移完成
extra *mapextra // optional fields
}
其中flags有以下几种标记:
常量名 | 值 | 对应二进制 | 说明 |
---|---|---|---|
iterator | 1 | 00000001 | 标记有迭代器在迭代buckets |
oldIterator | 2 | 00000010 | 标记有迭代器在迭代oldbuckets |
hashWriting | 4 | 00000100 | 标记当前正在写hashmap |
sameSizeGrow | 8 | 00001000 | 标记此次扩容容量没有变化只是重新分配元素,当扩容是由于溢出桶太多导致时会加此标记 |
bucket对应的结构体如下,源码中是没有keys、values、overflow这三个字段的,但实际运行过程内存中对应位置会有这三个字段
type bmap struct {
tophash [8]uint8 // 如果<5表示存的是状态,>=5存的是hash值高8位
// keys [8]keytype
// values [8]valuetype // 之所以将key和value单独放在一起是因为内存对齐会浪费很多内存
// overflow uintptr // 溢出桶地址
}
tophash时存的是状态,共有以下几种状态:
|常量名|值|说明| |——|——|——|——| |emptyRest|0|当前槽是空的,并且接下来的槽也是空的| |emptyOne|1|当前槽是空的,其他槽不一定| |evacuatedX|2|当前槽有效,但是已经被迁移到了扩容后buckets数组的上半区| |evacuatedY|3|当前槽有效,但是已经被迁移到了扩容后buckets数组的下半区| |evacuatedEmpty|4|当前槽是空的,已经被迁移了|
mapextra对应的结构体如下:
type mapextra struct {
// The indirection allows to store a pointer to the slice in hiter.
// 如果k/v都不包含指针,并且可以被inline,那么我们标记桶不含指针,这样避免gc扫描整个map
// 然而bmap结构体的overflow字段是一个指针,为了保证溢出桶不被回收,我们用overflow存储所有hmap.buckets上的所有溢出桶,oldoverflow存储hmap.oldbuckets上的所有溢出桶
overflow *[]*bmap
oldoverflow *[]*bmap
// 创建bucket数组时会预先分配一些溢出桶出来,nextOverflow为这部分桶的第一个桶
nextOverflow *bmap
}
它们之间的关系可以用下面这张图来表示:
map的创建
在Go中通常使用make来创建一个map,像这样:
make(map[ktype]vtype, hint)
而在Go源码中提供了三个创建map的函数,它们分别是:
func makemap_small() *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap
- 如果不指定hint或者hint(bucketCnt,即bucket上的元素数)时Go会通过runtime.makemap_small()来创建
- 如果hint为int64使用runtime.makemap64()来创建,但里面还是调用的runtime.makemap()
- 否则通过调用runtime.makemap()来创建
makemap_small()的代码非常简单,就是new一个hmap对象,然后生成hash种子:
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}
而makemap()的过程就相对复杂了,步骤为:
- 创建hmap结构体,并生成hash seed
- 通过hint找到bucket数组的长度,其实就是找到B
- 如果B不为0,那么就为hmap预创建bucket数组
- 如果B>=4我们认为大概率会有溢出桶,所以会预先分配2^(b-4)个溢出桶出来,然后将hmap.extra.nextOverflow指向预分配的第一个溢出桶
代码:
// t为map的类型信息, hint即make()的第二个参数
func makemap(t *maptype, hint int, h *hmap) *hmap {
// 计算所需内存
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
// 如果溢出则将初始化大小修改为0
hint = 0
}
// 初始化Hmap
if h == nil {
h = new(hmap)
}
// 生成hash seed, fastrand()这里不做详解,看注释是实现了某篇论文...
h.hash0 = fastrand()
// 找到一个 B,使得 map 的负载因子在正常范围内。
B := uint8(0)
for overLoadFactor(hint, B) { // overLoadFactor(hint, B) 等价于 hint > 2^B*6.5
B++
}
h.B = B
if h.B != 0 {
var nextOverflow *bmap
// 预分配bucket数组
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
// 如果预分配了溢出桶,则用h.extra.nextOverflow存第一个溢出桶的指针
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
makeBucketArray的源码
// dirtyalloc要么是nil要么是之前由makeBucketArray使用相同的t和b创建出来的bucket数组
// 如果dirtyalloc为nil,那么就会创建出一个新数组,如果不为nil则会清空掉之前的dirtyalloc然后重用这部分内存来创建新数组
// 如果b>=4我们认为大概率会有溢出桶,所以会预先分配2^(b-4)个溢出桶出来,nextOverflow即为这部分桶的第一个桶
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b)
nbuckets := base
if b >= 4 {
// 当b>=4时大概率会有溢出桶,所以这里预先分配一些溢出桶出来
nbuckets += bucketShift(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))
} else {
buckets = dirtyalloc
size := t.bucket.size * nbuckets
// 清空dirtyalloc
if t.bucket.ptrdata != 0 {
memclrHasPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
if base != nbuckets {
// 进到这里说明上面申请了一些溢出桶
// nextOverflow为第一个溢出桶的地址
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
// last为最后一个溢出桶的地址
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
// 将最后一个溢出桶的overflow设置为buckets数组的第一个元素
// 之所以这么搞是为了方便判断h.extra.nextOverflow是不是最后一个预分配的溢出桶
// 如果没理解的话看下下面的newoverflow函数😄
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
赋值
Go中编译器会针对不同类型的key调用不同的赋值函数,它们分别是:
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer
func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
它们的实现相差不大,我们只理解mapassign()的实现就行了,mapassign()赋值的步骤如下:
- 求key的hash值,找到其对应的bucket
- 如果正在扩容的话,需要将该bucket迁到新数组中
- 遍历bucket及其链接的溢出桶上的所有槽,如果找到了key,则接下来将新值赋到该槽上
- 如果没有找到key,则写到第一个空槽上
- 如果没有空槽则创建出来一个新的溢出桶出来,将新键值对写到这个新溢出桶上
- 如果要没有找到key或者需要创建新溢出桶的话还需要判断是否需要扩容,如果需要的话就先进行扩容,再重复步骤2
- 将键值对写到查询到的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... // 求key的hash值 hash := t.hasher(key, uintptr(h.hash0)) ... if h.buckets == nil { // 如果map的bucket数组还没有创建则创建出来 h.buckets = newobject(t.bucket) } again: // 获取hash值的低B位 bucket := hash & bucketMask(h.B) if h.growing() { // 如果map正在扩容则调用growWork迁移bucket growWork(t, h, bucket) } // 根据低B位找到对应的bucket b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) // 取hash值的高8位,如果<5则再加上5 top := tophash(hash) var inserti *uint8 var insertk unsafe.Pointer var elem unsafe.Pointer bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { // tophash不匹配 if b.tophash[i] <= emptyOne && 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)) } if b.tophash[i] == emptyRest { // 当前槽是emptyRest,则之后的槽肯定也是空的,就不用往后查了 break bucketloop } continue } // tophash一致的话再判断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没有匹配上则继续查询 continue } // 找到了key,直接更新就行 if t.needkeyupdate() { typedmemmove(t.key, k, key) } elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) // 找到了key直接跳出循环 goto done } // 再遍历溢出桶 ovf := b.overflow(t) if ovf == nil { break } b = ovf } // 走到这里说明,当前map上没有指定的key,所以就需要写入一个新的键值对 // 如果写入新的键值对后负载系数>6.5 或者有太多溢出桶的话,就需要扩容 // 当然了,如果正在扩容中就不用再扩容了 // 溢出桶过多会严重影响查询效率所以需要扩容 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) // 扩容后需要重新找一个新的位置 goto again } if inserti == nil { // 当map上所有槽都满的情况下,上面查到的插入位置就是空了 // 所以加一个溢出桶承载新添加的键值对 newb := h.newoverflow(t, b) inserti = &newb.tophash[0] // 槽上k的位置 insertk = add(unsafe.Pointer(newb), dataOffset) // 槽上v的位置 elem = add(insertk, bucketCnt*uintptr(t.keysize)) } // 在插入位置写入新的键值对 if t.indirectkey() { // t.indirectkey()=true说明bucket存储的是key的指针 // 为key申请一块内存并返回该块内存的地址 kmem := newobject(t.key) // 将插入位置的值转为该块内存的地址 *(*unsafe.Pointer)(insertk) = kmem // insertk也指向到这块内存的地址 insertk = kmem } if t.indirectelem() { vmem := newobject(t.elem) *(*unsafe.Pointer)(elem) = vmem } // 将key写入到insertk指向的内存位置 typedmemmove(t.key, insertk, key) *inserti = top // 元素数量+1 h.count++ done: ... if t.indirectelem() { elem = *((*unsafe.Pointer)(elem)) } return elem }
newoverflow的流程:
源码:
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
var ovf *bmap
if h.extra != nil && h.extra.nextOverflow != nil {
// 如果nextOverflow不为空,说明我们还有空闲的预分配溢出桶
// 我们将优先使用空闲的预分配溢出桶
ovf = h.extra.nextOverflow
if ovf.overflow(t) == nil {
// 如果该桶没有溢出桶,则将当前nextOverflow设置为它的下一个桶
h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
} else {
// 如果该桶有overflow,则说明它是最后一个溢出桶了,我们没有可用的预分配溢出桶了
// 回忆下makeBucketArray函数,我们是不是把最后一个预分配的溢出桶的overflow设置为了buckets数组的第一个元素了😆
// nextOverflow设置为nil
ovf.setoverflow(t, nil)
h.extra.nextOverflow = nil
}
} else {
ovf = (*bmap)(newobject(t.bucket))
}
h.incrnoverflow()
if t.bucket.ptrdata == 0 {
// 这里如果没懂的话看下上面mapextra结构体的说明
h.createOverflow() // 其实是初始化h.extra.overflow
*h.extra.overflow = append(*h.extra.overflow, ovf)
}
b.setoverflow(t, ovf)
return ovf
}
func (h *hmap) createOverflow() {
if h.extra == nil {
h.extra = new(mapextra)
}
if h.extra.overflow == nil {
h.extra.overflow = new([]*bmap)
}
}
扩容
既然上面提到了扩容那就在这里总结下扩容的步骤吧
扩容的条件
- 元素数量 / 桶数量 >= 6.5
- 溢出桶过多,当B<15(即bucket数量<2^15)时,如果溢出桶总数>=bucket数量则判定溢出桶过多;当B>=15时,如果溢出桶总数>=2^15则判定溢出桶过多
当条件1满足时,我们扩容一倍(将B加1),当条件1不足但条件2满足时说明桶利用率比较低,元素都被分配到了溢出桶上,这时容量不变,只移动bucket来降低空槽率
扩容步骤
- 如果负载系数>=6.5说明是由于溢出桶过多进行的扩容,这种扩容会进行等量扩容,不会增加buckets数组大小,这是将给map加上sameSizeGrow标志;否则将B+1,即扩容1倍
- 创建一个新buckets数组,并预分配一些溢出桶,清除map的iterator和oldIterator标志,如果当前map正在被迭代,则需要给map加个oldIterator标志
- 修改hmap结构体,将新buckets数组赋值给hmap.buckets字段,旧buckets数组赋值给hmap.oldbuckets字段,如果hmap.extra上还有溢出桶,还需要将此溢出桶赋值给hmap.extra.oldoverflow,同时hmap.extra.overflow置为nil
- 如果预分配了溢出桶,则将第一个溢出桶赋值给hmap.extra.nextOverflow
func hashGrow(t *maptype, h *hmap) { bigger := uint8(1) if !overLoadFactor(h.count+1, h.B) { // 如果负载系数>=6.5说明是由于溢出桶过多进行的扩容,同时也说明了有许多bucket没有利用上 // 这时不扩容,只rehash bigger = 0 h.flags |= sameSizeGrow } oldbuckets := h.buckets // 创建一个新bucket数组 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) // 将flags中的iterator和oldIterator位清零 flags := h.flags &^ (iterator | oldIterator) if h.flags&iterator != 0 { flags |= oldIterator } // 修改map h.B += bigger h.flags = flags h.oldbuckets = oldbuckets h.buckets = newbuckets h.nevacuate = 0 h.noverflow = 0 if h.extra != nil && h.extra.overflow != nil { if h.extra.oldoverflow != nil { throw("oldoverflow is not nil") } h.extra.oldoverflow = h.extra.overflow h.extra.overflow = nil } if nextOverflow != nil { if h.extra == nil { h.extra = new(mapextra) } h.extra.nextOverflow = nextOverflow } }
可以看到hashGrow中是没有做迁移动作的,桶迁移是调用growWork渐进式进行的。
func growWork(t *maptype, h *hmap, bucket uintptr) {
// bucket是在新数组上的位置,bucket&h.oldbucketmask()是在旧数组上的位置
evacuate(t, h, bucket&h.oldbucketmask())
// 如果还在扩容状态则再多迁移一个oldbucket
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
evacuate源码
// oldbucket是要迁移的bucket在旧数组上的索引
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
// 索引找到要迁移的旧bucket的地址
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
newbit := h.noldbuckets()
if !evacuated(b) {
// x和y是移动的目标
// x表示的是新bucket数组的前半部分
// y表示的是新bucket数组的后半部分
var xy [2]evacDst
x := &xy[0]
// 找到要迁移的bmap的地址
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
// 找到要迁移的k的地址
x.k = add(unsafe.Pointer(x.b), dataOffset)
// 找到要迁移的v的地址
x.e = add(x.k, bucketCnt*uintptr(t.keysize))
if !h.sameSizeGrow() {
y := &xy[1]
y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
y.k = add(unsafe.Pointer(y.b), dataOffset)
y.e = add(y.k, bucketCnt*uintptr(t.keysize))
}
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
e := add(k, bucketCnt*uintptr(t.keysize))
for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
top := b.tophash[i]
if isEmpty(top) {
// 空槽不迁移
b.tophash[i] = evacuatedEmpty
continue
}
if top < minTopHash {
throw("bad map state")
}
k2 := k
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
var useY uint8
if !h.sameSizeGrow() {
// 增量扩容的情况下,计算hash以判断我们的数据是迁移到哪部分bucket
hash := t.hasher(k2, uintptr(h.hash0))
if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
// 为什么要加 reflexivekey 的判断,可以参考这里:
// https://go-review.googlesource.com/c/go/+/1480
// key != key,只有在 float 数的 NaN 时会出现
// 比如:
// n1 := math.NaN()
// n2 := math.NaN()
// fmt.Println(n1, n2)
// fmt.Println(n1 == n2)
// 这种情况下 n1 和 n2 的哈希值也完全不一样
// 这里官方表示这种情况是不可复现的
// 需要在 iterators 参与的情况下才能复现
// 但是对于这种 key 我们也可以随意对其目标进行发配
// 同时 tophash 对于 NaN 也没啥意义
// 还是按正常的情况下算一个随机的 tophash
// 然后公平地把这些 key 平均分布到各 bucket 就好
useY = top & 1
top = tophash(hash)
} else {
// 假设旧桶数为2,那么newbit就为100(二进制形式)
// 新桶数为4,bucketMask为111,
// hash&newbit != 0说明hash形式为xxx1xx,
// hash & bucketMask肯定是>100,所以肯定在Y半区
if hash&newbit != 0 {
useY = 1
}
}
}
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}
// 修改旧桶tophash为状态值
b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
dst := &xy[useY] // evacuation destination
if dst.i == bucketCnt {
dst.b = h.newoverflow(t, dst.b)
dst.i = 0
dst.k = add(unsafe.Pointer(dst.b), dataOffset)
dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
}
dst.b.tophash[dst.i&(bucketCnt-1)] = top
if t.indirectkey() {
*(*unsafe.Pointer)(dst.k) = k2
} else {
typedmemmove(t.key, dst.k, k)
}
if t.indirectelem() {
*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
typedmemmove(t.elem, dst.e, e)
}
dst.i++
dst.k = add(dst.k, uintptr(t.keysize))
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
if h.flags&oldIterator == 0 && t.bucket.ptrdata != 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)
}
}
查找
runtime的map提供了mapaccess1、mapaccess2、mapaccessK三个函数来获取值,取值时编译器会将v, exists = map[k]
转化为mapaccess2,v = map[k]
转化为mapaccess1,mapaccessK只用于map遍历时。下面我们以mapaccess1为例看下是如何查找key的。
mapaccess1查找的流程:
- 计算key的hash值,hash值的低B位即为key所在bucket在map.buckets数组中的下标,通过hash值的低B位就能找到key所在bucket,如果map在扩容中那就找到key所在的旧bucket,如果旧bucket未迁移,那么接下来从旧bucket中找key
- 遍历bucket的每个槽,取hash值的tophash(高8位)与遍历到的槽上的tophash对比,如果不同则先判断下槽上的tophash是否是emptyRest,如果是那说明当前槽即下面的槽都是空槽了,就不用遍历了,如果不是就继续查下一个槽,直到tophash匹配上
- 如果上一步找到了匹配的tophash,就继续判断槽上的key是不是我们要找的key,如果不是还得继续遍历,如果是我们要找的key就取槽上的v返回就结束了
- 如果上一步没有找到对应的槽,说明map上没有我们要找的key
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... if h == nil || h.count == 0 { if t.hashMightPanic() { // 这段代码是因为当从一个非空的map中取值时, // 如果key为nil, 那么会导致一个panic, // 但同样的操作在nil/空 map上就不会发生, 这可能会导致难以发现的bug // 所以这里还是要额外计算下key的hash值 t.hasher(key, 0) // see issue 23734 } return unsafe.Pointer(&zeroVal[0]) } ... // 计算key对应的hash值 // go为不同的type选择不同的hash函数,具体可以看下/cmd/compile/internal/gc/alg.go genhash()函数 hash := t.hasher(key, uintptr(h.hash0)) m := bucketMask(h.B) // 取hash值的低B位,然后找到对应的bucket b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // 如果oldbuckets不为空,说明在扩容中 if c := h.oldbuckets; c != nil { if !h.sameSizeGrow() { m >>= 1 } // 找到旧bucket oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) // 如果还未迁移则下面从旧bucket查询key if !evacuated(oldb) { b = oldb } } // 取hash值的高8位(如果<5则再加上5) top := tophash(hash) bucketloop: // 先查找当前bucket的8个元素,再查找溢出桶上的元素 for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { // 如果tophash为emptyRest则说明当前槽和后面的槽都不会有元素了 if b.tophash[i] == emptyRest { break bucketloop } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } // hash值一致后再判断key是否是我们要查询的key if t.key.equal(key, k) { // 取回元素值 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]) }
删除
删除的步骤:
- 与查找类似先通过key与hash值在bucket数组上找到对应的槽
- 将槽上的k/v清空,并将tophash设置为emptyOne
- 如果该槽是最后一个元素则将它及它之前的空槽tophash都设置为emptyRest,标识其后面都是空槽
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { ... // 计算key的hash值 alg := t.key.alg hash := alg.hash(key, uintptr(h.hash0)) ... // 根据hash值低B位找到bucket索引 bucket := hash & bucketMask(h.B) if h.growing() { // 如果正在扩容则执行迁移操作 growWork(t, h, bucket) } // 找到对应的bmap b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) bOrig := b top := tophash(hash) // 下面与查询类似都是去找到具体所在的槽 search: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break search } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) k2 := k if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } if !alg.equal(key, k2) { continue } // 如果 key 中是指针,就清空 key 的内容 if t.indirectkey() { *(*unsafe.Pointer)(k) = nil } else if t.key.ptrdata != 0 { memclrHasPointers(k, t.key.size) } 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 // 如果该槽不是最后一个元素则跳转到最后 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 } } // 如果该槽是最后一个元素则将它及它之前的空槽tophash都设置为emptyRest,标识其后都是空槽 for { b.tophash[i] = emptyRest if i == 0 { // 如果i=0说明遍历到了该bucket上的第一个槽,这时如果遍历到的b是冲突链表上的第一个bucket说明我们已经遍历完了,break if b == bOrig { break } c := b // 从冲突链表上第一个bucket开始找当前bucket的上一个bucket for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } i = bucketCnt - 1 } else { i-- } if b.tophash[i] != emptyOne { break } } notLast: // 元素数-1 h.count-- break search } } ... }