当前我们基于golang 1.15.6 版本源码进行解析。关于map 的图形化记录大家可以查看惜暮大神的Golang map实践以及实现原理。我在这里就不在赘述了。接下来的部分我会重点关注map 源码细节性的内容。
Map struct:
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8 //设置的标志位，当写的时候会设置写标志位
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}创建map：
//在开发中我们创建一个map的语法如下
//不设置map 长度
m := make(map[string]string)
// 指定 map 长度
m := make(map[string]string, 10)其实在编译器编译时它会定位到调用 runtime.makemap()，主要做的工作就是初始化 hmap 结构体的各种字段，例如计算 B 的大小，设置哈希种子 hash0 等等。、
// makemap implements Go map creation for make(map[k]v, hint).
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If h.buckets != nil, bucket pointed to can be used as the first bucket.
// hint 就是我们初始化的长度
func makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size) //判断存储的数据长度是否越界
if overflow || mem > maxAlloc {
hint = 0
}
// initialize Hmap
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand() //设置hash 种子
// Find the size parameter B which will hold the requested # of elements.
// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
B := uint8(0)
// 判断hint是否大于当前的桶内长度*负载因子（6.5）。
for overLoadFactor(hint, B) {
B++
}
h.B = B
// allocate initial hash table
// if B == 0, the buckets field is allocated lazily later (in mapassign)
// If hint is large zeroing this memory could take a while.
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}// makeBucketArray 初始化桶数组为map buckets
// 1<<b 是最小分配桶数量，
// dirtyalloc应该是nil或者先前由makeBucketArray分配的具有相同t和b参数的桶数组。
// 如果dirtyalloc为nil，一个新的后备数组将被分配，否则dirtyalloc将被清除并作为后备数组重新使用。
//
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b) //计算桶的数量，在范围内（根据机器系统位数计算）是1<<b
nbuckets := base
// 对于小b来说，溢出桶是不可能的。
// 避免计算的开销。
if 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 {
// dirtyalloc was previously generated by
// the above newarray(t.bucket, int(nbuckets))
// but may not be empty.
buckets = dirtyalloc
size := t.bucket.size * nbuckets
if t.bucket.ptrdata != 0 {
memclrHasPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
if base != nbuckets {
// 我们预先分配了一些溢出桶。为了使跟踪这些溢出桶的开销降至最低，我们使用约定:如果预先分配的溢出桶的溢出指针为nil，那么通过碰撞该指针可以获得更多可用性。
// 最后一个溢出桶需要一个安全的非空指针;用桶。
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}根据key 查找值：
// mapaccess1 returns a pointer to h[key]. 相反，永远不会返回nil
// 它将返回一个对elem类型的0对象的引用if键不在map中。
// NOTE: 返回的指针可以使整个映射保持活跃，所以不要这样保持很长时间。
// 根据key 查找到对应的value
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapaccess1)
racereadpc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled && h != nil {
msanread(key, t.key.size)
}//......校验逻辑
//如果 h 什么都没有，返回value类型的零值
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
if h.flags&hashWriting != 0 { //并发的读写冲突
throw("concurrent map read and map write")
}
//计算hash值，// 不同类型 key 使用的 hash 算法在编译期确定
hash := t.hasher(key, uintptr(h.hash0))
// 求低 B 位的掩码.
// 比如 B=5，那 m 就是31，低五位二进制是全1。减1是因为我们是从0 开始
m := bucketMask(h.B)
// b 就是 当前key对应的 bucket 的地址
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil { //如果存在旧有的桶
if !h.sameSizeGrow() { //如果当前的增长与原来的桶的长度不同，则减少m
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) //得到key 在旧有的桶的位置
if !evacuated(oldb) { //如果当前桶还未迁移则修改桶的地址，指向旧桶
b = oldb
}
}
top := tophash(hash) //得到hash 高8位的值。hash在64位系统中占64位bit
bucketloop:
for ; b != nil; b = b.overflow(t) {
// b.overflow(t) 这里特别的说明一下是从溢出桶中读取value
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top { //找到对应key
if b.tophash[i] == emptyRest { //走到最后还没有到下一个桶
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) //得到key的地址
if t.indirectkey() { //如果keyc存储的是地址
k = *((*unsafe.Pointer)(k)) //则得到存储地址的值
}
if t.key.equal(key, k) { //比较两个key 是否相同
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) //得到key对应的value
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
return unsafe.Pointer(&zeroVal[0]) //没有找到返回零值
}定位公式：
// key 定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// value 定位公式
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))b 是 bmap 的地址，这里 bmap 还是源码里定义的结构体，只包含一个 tophash 数组，经编译器扩充之后的结构体才包含 key，value，overflow 这些字段。dataOffset 是 key 相对于 bmap 起始地址的偏移：
//这是被编译器扩充后的bmap
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}桶内槽位记录：
emptyRest = 0 // 此单元格为空，并且在更高的索引或溢出处不再有非空单元格。
emptyOne = 1 // this cell is empty
evacuatedX = 2 // key/elem is valid. Entry has been evacuated to first half of larger table. 与扩容相关
evacuatedY = 3 // same as above, but evacuated to second half of larger table.与扩容相关
evacuatedEmpty = 4 // 槽位和桶都被清空了
minTopHash = 5 // 正常填充的单元格的最小tophash值。
// flags
iterator = 1 // 可能有一个使用桶的迭代器
oldIterator = 2 // 可能有一个使用旧桶的迭代器
hashWriting = 4 // a goroutine is writing to the map
sameSizeGrow = 8 // 当前的map 是增长到了一个相同大小的桶
//计算桶是否迁出
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > emptyOne && h < minTopHash
}
//只取了 tophash 数组的第一个值，判断它是否在 1-5 之间。对比上面的常量，当 top hash 是 evacuatedEmpty、evacuatedX、evacuatedY 这三个值之一，说明此 bucket 中的 key 全部被搬迁到了新 bucket。
// tophash calculates the tophash value for hash.计算key的高8位
func tophash(hash uintptr) uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
top += minTopHash
}
return top
}Node: 这里说一下，扩容分为扩容和旧桶元素迁移两个部分。
使用 key 的 hash 值可以快速定位到目标 key，然而，随着向 map 中添加的 key 越来越多，key 发生碰撞的概率也越来越大。bucket 中的 8 个 cell 会被逐渐塞满，查找、插入、删除 key 的效率也会越来越低。最理想的情况是一个 bucket 只装一个 key，这样，就能达到 O(1) 的效率，但这样空间消耗太大，用空间换时间的代价太高。
Go 语言采用一个 bucket 里装载 8 个 key，定位到某个 bucket 后，还需要再定位到具体的 key，这实际上又用了时间换空间。
当然，这样做，要有一个度，不然所有的 key 都落在了同一个 bucket 里，直接退化成了链表，各种操作的效率直接降为 O(n)，是不行的。
因此，需要有一个指标来衡量前面描述的情况，这就是装载因子。Go 源码里这样定义 装载因子：
loadFactor := count / (2^B)2^B再来说触发 map 扩容的时机：在向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容：
扩容条件：
// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
// 计算负载因子是否超过 6.5
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// tooManyOverflowBuckets 报告溢出桶对于一个有1<<B桶的map是否过多。
// Note 大多数溢流桶必须很少使用;
// 如果使用密集，那么我们已经触发了常规地图的增长。
// 检查条件是noverflow 溢出桶是否大于2^15
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
//B=15 是一个中间值，既不会太小导致频繁的扩容，也不会太大
if B > 15 {
B = 15
}
// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
return noverflow >= uint16(1)<<(B&15)
}
这里解释一下这种触发扩容的原理：
第 1 点：我们知道，每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。
第 2 点：是对第 1 点的补充。就是说在装载因子比较小的情况下，这时候 map 的查找和插入效率也很低，而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小，即 map 里元素总数少，但是 bucket 数量多（真实分配的 bucket 数量多，包括大量的 overflow bucket）。
不难想像造成这种情况的原因：不停地插入、删除元素。先插入很多元素，导致创建了很多 bucket，但是装载因子达不到第 1 点的临界值，未触发扩容来缓解这种情况。之后，删除元素降低元素总数量，再插入很多元素，导致创建很多的 overflow bucket，但就是不会触犯第 1 点的规定，你能拿我怎么办？**overflow bucket 数量太多，导致 key 会很分散，查找插入效率低得吓人，**因此出台第 2 点规定。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难。
对于命中条件 1，2 的限制，都会发生扩容。但是扩容的策略并不相同，毕竟两种条件应对的场景不同。
(2^B)（2^B）（2^B * 2）对于条件 2，其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升。
对于条件 2 的解决方案，有一个极端的情况：如果插入 map 的 key 哈希都一样，就会落到同一个 bucket 里，超过 8 个就会产生 overflow bucket，结果也会造成 overflow bucket 数过多。移动元素其实解决不了问题，因为这时整个哈希表已经退化成了一个链表，操作效率变成了 O(n)。
前面说了扩容的条件，下面看一下扩容到底是怎么做的：由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，在搬迁过程中map会阻塞，非常影响性能。因此 Go map 的扩容采取了一种称为 “渐进式” 的方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个bucket。
hashGrow()growWork()growWork()mapassignmapdelete扩容的函数：
//只有才插入map的时候才有可能触发这个函数
func hashGrow(t *maptype, h *hmap) {
// If we've hit the load factor, get bigger.
// Otherwise, there are too many overflow buckets,
// so keep the same number of buckets and "grow" laterally.
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) { //如果不是超过负载因子的情况下就是等容扩容
bigger = 0
h.flags |= sameSizeGrow
}
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) //构建扩容后的新newbuckets
flags := h.flags &^ (iterator | oldIterator)
//清零h.flags 中iterator和oldIterator标志位
if h.flags&iterator != 0 { //修改迭代对应桶
flags |= oldIterator
}
// commit the grow (atomic wrt gc)
// 修改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 {
// Promote current overflow buckets to the old generation.将当前溢出桶推广到老一代
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
}
// the actual copying of the hash table data is done incrementally
// by growWork() and evacuate().
}迁移桶的函数：
//迁移的函数，我们可以发现，每次迁移我们只会迁移两个桶的数据。当我们新增map和删除map时都会进行桶迁移操作
func growWork(t *maptype, h *hmap, bucket uintptr) {
// make sure we evacuate the oldbucket corresponding
// to the bucket we're about to use 确保我们将旧的桶与我们将要使用的桶相对应的桶清空
evacuate(t, h, bucket&h.oldbucketmask())
// evacuate one more oldbucket to make progress on growing再疏散一个旧水桶，以取得进展
if h.growing() { //还没有完成全部旧桶的迁移
evacuate(t, h, h.nevacuate)
}
}//具体执行的迁移函数
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) //得到旧桶的大小
newbit := h.noldbuckets() //得到旧桶的大小
if !evacuated(b) {
// TODO: reuse overflow buckets instead of using new ones, if there
// is no iterator using the old buckets. (If !oldIterator.)
// xy contains the x and y (low and high) evacuation destinations.
var xy [2]evacDst
x := &xy[0] //记录低桶的信息
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))//old桶的地址
x.k = add(unsafe.Pointer(x.b), dataOffset) //old桶的key地址
x.e = add(x.k, bucketCnt*uintptr(t.keysize)) //old桶的value地址
if !h.sameSizeGrow() {
// Only calculate y pointers if we're growing bigger.
// Otherwise GC can see bad pointers.
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() {
//计算哈希以做出撤离决定(我们是将这个key/elem发送到桶x或桶y)。
hash := t.hasher(k2, uintptr(h.hash0))
if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
//如果key != key (NaNs)，那么散列可能(也可能是)完全不同于旧的散列。此外，它是不可复制的。在存在迭代器的情况下，需要可再现性，因为我们的疏散决策必须匹配迭代器所做的任何决策。
//幸运的是，我们可以自由地以任何方式发送这些密钥。此外，tophash对于这些类型的键是没有意义的。
//我们让低一点的tophash驱动撤离决定。我们为下一层重新计算一个新的随机tophash，以便在倍数增长后，这些键将均匀分布在所有桶中。
//简单的来说这类型的key是不稳定的，我们只能通过迭代来获得它
useY = top & 1 //
top = tophash(hash)
} else {
if hash&newbit != 0 { //计算hash低位的B-1 位是否为1
useY = 1
}
}
}
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}
b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY if useY ==1 表示这个槽位的数据迁移到了新的位置
// 找到实际的目的bucket.
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 // mask dst.i as an optimization, to avoid a bounds check
if t.indirectkey() {
*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
} else {
typedmemmove(t.key, dst.k, k) // copy elem
}
if t.indirectelem() {
*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
typedmemmove(t.elem, dst.e, e)
}
//从这里我们就可以知道，此时会将原来key与key之间间隔为空的位置填满
dst.i++
// These updates might push these pointers past the end of the
// key or elem arrays. That's ok, as we have the overflow pointer
// at the end of the bucket to protect against pointing past the
// end of the bucket.
dst.k = add(dst.k, uintptr(t.keysize))
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
// 如果没有协程在使用老的 buckets，就把老 buckets 清除掉，帮助gc
if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
// Preserve b.tophash because the evacuation
// state is maintained there.
ptr := add(b, dataOffset)
n := uintptr(t.bucketsize) - dataOffset
memclrHasPointers(ptr, n) //从ptr开始向后清理n个长度的内存
}
}
if oldbucket == h.nevacuate { //当前的迁移标志位与要迁移的旧桶是否相同
advanceEvacuationMark(h, t, newbit) //修改迁移标志位
}
}// 增加迁移标志位
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
h.nevacuate++
// Experiments suggest that 1024 is overkill by at least an order of magnitude.
// Put it in there as a safeguard anyway, to ensure O(1) behavior.
stop := h.nevacuate + 1024
if stop > newbit {
stop = newbit
}
for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { //将迁移设置为最新的下一个标志位bucketEvacuated()检查h.nevacuat代表的桶是否已经完成迁移
h.nevacuate++
}
if h.nevacuate == newbit { // newbit == # of oldbuckets
//表示迁移已经完成了
// Growing is all done. Free old main bucket array.
h.oldbuckets = nil
// Can discard old overflow buckets as well.
// If they are still referenced by an iterator,
// then the iterator holds a pointers to the slice.
if h.extra != nil {
h.extra.oldoverflow = nil
}
h.flags &^= sameSizeGrow //将flags 中的sameSizeGrow 标志位置为0
}
}插入修改map:
//像mapaccess(), 但是如果key 不存在我们新建立一个
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
if raceenabled {
callerpc := getcallerpc()
pc := funcPC(mapassign)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled {
msanread(key, t.key.size)
} // 逻辑判断
if h.flags&hashWriting != 0 { //并发冲突写
throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0))
// Set hashWriting after calling t.hasher, since t.hasher may panic,
// in which case we have not actually done a write.
h.flags ^= hashWriting
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
bucket := hash & bucketMask(h.B) //计算B-1位的数
if h.growing() { //如果我们进行了扩容，则进行桶迁移
growWork(t, h, bucket)
}
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) //得到桶的位置
top := tophash(hash)
var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer
bucketloop:
for { //找到key 对应的值，或者遍历完所有的溢出桶
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top { //找到第一个为空的位置
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))
}
if b.tophash[i] == emptyRest { //当后面也没有数据时，跳出最外层的for循环
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if !t.key.equal(key, k) {
continue
}
// already have a mapping for key. Update it.已经有key的映射。更新它。
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
goto done
}
ovf := b.overflow(t) //得到b桶的溢出桶
if ovf == nil {
break
}
b = ovf
}
// Did not find mapping for key. Allocate new cell & add entry.
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
// 如果我们达到最大装载系数，或者我们有太多的溢出桶，而我们还没有在增长的中间，开始增长。
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again增长表会使所有东西失效，所以再试一次
}
if inserti == nil { //如果到这里还是没有找到插入的位置，我们需要构建一个新的溢出桶
// all current buckets are full, allocate a new one.
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
// 增加key 与elem的存储位置
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:
if h.flags&hashWriting == 0 { //如果被修改了map写标志位，则报错
throw("concurrent map writes")
}
h.flags &^= hashWriting //将写标志置为0
if t.indirectelem() {
elem = *((*unsafe.Pointer)(elem))
}
return elem //返回key 对应value的地址
}删除map:
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapdelete)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled && h != nil {
msanread(key, t.key.size)
}
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return
} //逻辑检查
if h.flags&hashWriting != 0 { //没有写冲突
throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0)) //计算hash
// Set hashWriting after calling t.hasher, since t.hasher may panic,
// in which case we have not actually done a write (delete).
h.flags ^= hashWriting //增加写标志
bucket := hash & bucketMask(h.B) //计算桶的位置
if h.growing() { //如果正在迁移桶，则进行桶的迁移
growWork(t, h, bucket)
}
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 !t.key.equal(key, k2) {
continue
}
// Only clear key if there are pointers in it.只有他们是指针时才清除键。
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.ptrdata != 0 {
memclrHasPointers(k, t.key.size)//清空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) //清空elem
} else {
memclrNoHeapPointers(e, t.elem.size)//清空elem
}
b.tophash[i] = emptyOne //设置当前的槽位为空
//如果已经将桶内最后的数据删除了，那么需要上溯，将前面也是为空的状态修改为emptyRest
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
}
}
for { //桶内已经没有数据了
b.tophash[i] = emptyRest //修改当前槽位状态为空，并且后面也没有数据的标志位
if i == 0 {
if b == bOrig {
break // 已经到初始桶了，结束。
}
// 发现前一个桶，进行检查
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
i = bucketCnt - 1
} else {
i--
}
if b.tophash[i] != emptyOne { //遇到非空，则结束
break
}
}
notLast:
h.count--
break search
}
}
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
}迭代map：
首先我们都知道map的迭代是无序的。其实大家知道我们的迁移是渐进的，可能存在旧桶与新桶同时存在的情况，此时我们就没有办法保证map的迭代有序了。为了保证map的迭代在全周期都是相同的，那么go在设计的时候就特别的让map 在任何时候都是无序的。
map的迭代是通过hiter结构和对应的两个辅助函数实现的。hiter结构由编译器在调用辅助函数之前创建并传入，每次迭代结果也由hiter结构传回。下方的it即是hiter结构体的指针变量。
初始化迭代器mapiterinit()
mapiterinit()函数主要是决定我们从哪个位置开始迭代，为什么是从哪个位置，而不是直接从hash数组头部开始呢？《go程序设计语言》好像提到过，hash表中数据每次插入的位置是变化的（其实是因为实现的原因，一方面hash种子是随机的，这导致相同的数据在不同的map变量内的hash值不同；另一方面即使同一个map变量内，数据删除再添加的位置也有可能变化，因为在同一个桶及溢出链表中数据的位置不分先后），所以为了防止用户错误的依赖于每次迭代的顺序，map作者干脆让相同的map每次迭代的顺序也是随机的。
迭代顺序随机的实现方式也简单，直接从随机的一个位置开始就行了：
- it.startBucket：这个是hash数组的偏移量，表示遍历从这个桶开始
- it.offset：这个是桶内的偏移量，表示每个桶的遍历都从这个偏移量开始
于是，map的遍历过程如下：
- 从hash数组中第it.startBucket个桶开始，先遍历hash桶，然后是这个桶的溢出链表。
- 之后hash数组偏移量+1，继续前一步动作。
- 遍历每一个桶，无论是hash桶还是溢出桶，都从it.offset偏移量开始。（如果只是随机一个开始的桶，range结果还是有序的；但每个桶都加it.offset偏移，这个输出结果就有点扑朔迷离，大家可以亲手试下，对同一个map多次range）
- 当迭代器经过一轮循环回到it.startBucket的位置，结束遍历。
//mapiterinit初始化用于映射范围的hiter结构体。
// The hiter struct pointed to by 'it' is allocated on the stack
// by the compilers order pass or on the heap by reflect_mapiterinit.
//'it'所指向的hiter结构体通过编译器的order pass在堆栈上分配，或者通过reflt_mapiterinit在堆上分配。
// 由于该结构体包含指针，所以两者都需要将hiter设为零。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
if raceenabled && h != nil {
callerpc := getcallerpc()
racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
}
if h == nil || h.count == 0 {
return
}
if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
throw("hash_iter size incorrect") // see cmd/compile/internal/gc/reflect.go
}
it.t = t
it.h = h
// 抓取桶状态的快照
it.B = h.B
it.buckets = h.buckets
if t.bucket.ptrdata == 0 {
// 为溢出桶创建新的溢出桶，在这里我们就可以发现这将使所有相关的溢出桶保持活着，
// 即使表增长和/或溢出桶在我们迭代时被添加到表中。
h.createOverflow()
it.overflow = h.extra.overflow
it.oldoverflow = h.extra.oldoverflow
}
// 决定从哪里开始
r := uintptr(fastrand()) //构建一个32位内的随机数
if h.B > 31-bucketCntBits { //当桶大于28 位时，我们需要计算0-64位的随机数
r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B) //得到在小于桶大小的起始点
it.offset = uint8(r >> h.B & (bucketCnt - 1)) //得到桶内元素的下标
// iterator state
it.bucket = it.startBucket //设置迭代的桶起始点
// 设置我们有一个迭代器。可以与另一个mapiterinit()同时运行。
if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
atomic.Or8(&h.flags, iterator|oldIterator)
}
mapiternext(it) //开始下一个迭代
}迭代过程mapiternext()
上一节迭代循环的过程很清晰了，这里我们说明几个重要的参数：
- it.startBucket：开始的桶
- it.offset：每个桶开始的偏移量
- it.bptr：当前遍历的桶
- it.i：it.bptr已经遍历的键值对数量，i初始为0，当i=8时表示这个桶遍历完了，将it.bptr移向下一个桶
- it.key：每次迭代的结果
- it.value：每次迭代的结果
此外，迭代还需要关注扩容缩容的情况：
- 如果是在迭代开始后才growing，这种情况当前的逻辑没处理，迭代有可能异常。呃，go map不支持并发。
- 如果是先growing，再开始迭代，这是有可能的。这种情况下，会先到旧hash表中检查key对应的桶有没有被疏散，未疏散则遍历旧桶，已疏散则遍历新hash表里对应的桶。
func mapiternext(it *hiter) {
h := it.h
if raceenabled {
callerpc := getcallerpc()
racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
}
if h.flags&hashWriting != 0 {
throw("concurrent map iteration and map write")
}
t := it.t
bucket := it.bucket
b := it.bptr
i := it.i
checkBucket := it.checkBucket //标注当前遍历的桶是否已经完成迁移，noCheck 表示不需要迁移或者是已经完成了迁移
next:
if b == nil { //当b的地址已经为空，表明当前桶的所有元素包括溢出桶已经遍历完成了，b 指向下一个桶
if bucket == it.startBucket && it.wrapped {
// 结束迭代
it.key = nil
it.elem = nil
return
}
if h.growing() && it.B == h.B { //我们开始迭代的时候已经完成了扩容
// 迭代器在一次增长的中间开始，增长还没有完成。
//如果我们正在查看的存储桶还没有被填满(例如，旧的存储桶还没有被清空)，
// 那么我们需要遍历旧的存储桶，只返回将要迁移到这个存储桶的存储桶。
oldbucket := bucket & it.h.oldbucketmask() //得到当前桶在旧桶的位置
b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) //先将b 的地址指向旧桶
if !evacuated(b) { //如果桶还未被迁移
checkBucket = bucket
} else { //已经迁移完成，则将b的地址指向新桶的地址
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
} else { //如果没有扩容迁移桶，设置b 地址指向
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
bucket++
if bucket == bucketShift(it.B) { //表示桶已经到了末尾，将桶的指针标注到map的0 桶位置
bucket = 0
it.wrapped = true //设置已经从桶的末尾移到开始
}
i = 0
}
for ; i < bucketCnt; i++ { //开始遍历当前桶内的元素
offi := (i + it.offset) & (bucketCnt - 1) //这里说明我们桶内的元素也不是从下标0开始的，也是速记产生的
if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { //如果当前槽位为空continue，并迭代下一个槽位
continue
}
k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
if checkBucket != noCheck && !h.sameSizeGrow() {
//这里是扩容的情况下，并且它的桶也发生了增长。我们需要假设在迁移后的情况迭代他们
if t.reflexivekey() || t.key.equal(k, k) { //当key 是不变化的
// 如果旧桶中的项在迭代未改变B(桶的最高位为0)，则跳过它。
hash := t.hasher(k, uintptr(h.hash0))
if hash&bucketMask(it.B) != checkBucket {
continue
}
} else { //当key的值可能改变的情况下，我们进行迁移后高低位的筛选，高位过滤
if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) { //检查如果这个key 是疏散到了evacuatedY（高位）
continue
}
}
}
if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || //这里还暂时不明白
!(t.reflexivekey() || t.key.equal(k, k)) {
// This is the golden data, we can return it.
// OR
// key!=key, so the entry can't be deleted or updated, so we can just return it.
// That's lucky for us because when key!=key we can't look it up successfully.
it.key = k
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
it.elem = e
} else {
// The hash table has grown since the iterator was started.
// The golden data for this key is now somewhere else.
// Check the current hash table for the data.
// This code handles the case where the key
// has been deleted, updated, or deleted and reinserted.
// NOTE: we need to regrab the key as it has potentially been
// updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
rk, re := mapaccessK(t, h, k) //通过key查找，返回key和value指针，用于迭代器(range)。未找到时返回空指针
if rk == nil {
continue // key has been deleted
}
it.key = rk
it.elem = re
}
it.bucket = bucket
if it.bptr != b { //记录当前的桶内的桶位置（对于溢出桶而言的）
it.bptr = b
}
it.i = i + 1 //记录当前在桶内迭代的位置
it.checkBucket = checkBucket //记录当前桶是否是未迁移的
return
}
b = b.overflow(t)
i = 0
goto next
}