Go 底层原理丨map（非 swiss 版本）

特此声明，本篇是笔者与 Google Gemini 3Pro 共创所作，非常庆幸在当今 AI 时代下获取知识已是如此便利，且也为学习者从第一性原理理解所学知识大大降低了门槛。不过本篇的篇章安排和叙述逻辑，均由笔者把控和审阅，欢迎放心阅读。

1. 整体设计思想

Go map（no swiss 版本） 本质上是一个哈希表，采用以下核心设计：

1. 桶式哈希：数据被组织成桶（bucket）数组
2. 链式溢出：每个桶最多存储 8 个键值对，超过则链接溢出桶
3. 渐进式扩容：扩容时采用增量迁移，避免一次性拷贝大量数据
4. 分离存储：键和值分别连续存储（而非交替存储），减少内存对齐的填充开销

2. 核心数据结构

本篇以 Go1.25 版本的源码为基准进行展开，完整源码可参考官方代码：map_noswiss.go。

2.1 hmap（map 头部结构）

type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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)
	clearSeq   uint64

	extra *mapextra // optional fields
}

• count：map 中元素个数
• B：桶数量的对数（桶数 = 2^B）
• buckets：当前桶数组 []bmap 指针
• oldbuckets：扩容时的旧桶数组 []bmap
• nevacuate：扩容迁移进度计数器
• hash0：哈希种子（防止哈希碰撞攻击）

2.2 bmap（桶结构）

// A bucket for a Go map.
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [abi.OldMapBucketCount]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

内存布局（运行时动态生成）：

[tophash0][tophash1]...[tophash7]
[key0][key1]...[key7]
[value0][value1]...[value7]
[overflow pointer]

tophash 的作用：

• 存储哈希值的高 8 位，用于快速比较
• 特殊值标记桶的状态（空槽、已迁移等）

2.3 特殊状态值

	// Possible tophash values. We reserve a few possibilities for special marks.
	// Each bucket (including its overflow buckets, if any) will have either all or none of its
	// entries in the evacuated* states (except during the evacuate() method, which only happens
	// during map writes and thus no one else can observe the map during that time).
	emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
	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 // cell is empty, bucket is evacuated.
	minTopHash     = 5 // minimum tophash for a normal filled cell.

	// flags
	iterator     = 1 // there may be an iterator using buckets
	oldIterator  = 2 // there may be an iterator using oldbuckets
	hashWriting  = 4 // a goroutine is writing to the map
	sameSizeGrow = 8 // the current map growth is to a new map of the same size

2.4 总结图

3. 核心操作

3.1 初始化（makemap）

• make

  m := make(map[int]string, 10)
  

  底层：调用 runtime/map.go 中的 makemap()

  func makemap(t *maptype, hint int, h *hmap) *hmap {
  
    // 1. 计算预期的 map 大小
  	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
  	if overflow || mem > maxAlloc {
  		hint = 0
  	}
  
  	// 2. 创建一个新的 hmap
  	if h == nil {
  		h = new(hmap)
  	}
  	h.hash0 = fastrand()
  
  	// 3. 计算 B
  	B := uint8(0)
  	for overLoadFactor(hint, B) {
  		B++
  	}
  	h.B = B
  
  	if h.B != 0 {
      // 4. 根据 B 创建桶和溢出桶
  		var nextOverflow *bmap
  		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
  		if nextOverflow != nil {
        // 5. 将溢出桶的数据存在 mapextra 中
  			h.extra = new(mapextra)
  			h.extra.nextOverflow = nextOverflow
  		}
  	}
  
  	return h
  }
  

• 字面量（底层还是先调用 makemap，然后再做赋值）

  • 元素少于 25 个时，一个一个简单赋值
  • 元素多个 25 个时，转为循环赋值

3.2 查找操作（mapaccess1/mapaccess2）

底层调用了 runtime/map.go 中的 mapaccess1() 或者 mapaccess2 方法：

• v := m[k] 调用 mapaccess1()
• v,k := m[k] 调用 mapaccess2()

查找流程：

// mapaccess1 实现 v := m[k] 语义，返回指向值的指针
// 核心思路：hash定位桶 → tophash快速过滤 → 完整key比较
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// ============================================
	// 第一部分：安全性检查（Race/Memory Sanitizer）
	// ============================================
	if raceenabled && h != nil {
		// Race Detector：记录读操作，检测并发竞态条件
		callerpc := sys.GetCallerPC()
		pc := abi.FuncPCABIInternal(mapaccess1)
		racereadpc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.Key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		// MSan（Memory Sanitizer）：检查 key 是否已初始化
		msanread(key, t.Key.Size_)
	}
	if asanenabled && h != nil {
		// ASan（Address Sanitizer）：检查 key 的内存访问是否合法
		asanread(key, t.Key.Size_)
	}

	// ============================================
	// 第二部分：边界情况处理
	// ============================================
	if h == nil || h.count == 0 {
		// nil map 或空 map：检查 key 类型是否支持作为 map 的键
		// 例如：不可比较类型（slice、map、func）会在这里 panic
		if err := maps.OldMapKeyError(t, key); err != nil {
			panic(err) // see issue 23734
		}
		// 返回零值的引用（所有零值共享同一个全局 zeroVal）
		return unsafe.Pointer(&zeroVal[0])
	}

	// ============================================
	// 第三部分：并发安全检查
	// ============================================
	if h.flags&hashWriting != 0 {
		// 检测到并发读写：map 不支持并发，立即 fatal
		// 注意：这只能检测到部分并发情况，不是完整的并发保护
		fatal("concurrent map read and map write")
	}

	// ============================================
	// 第四部分：计算哈希值并定位桶
	// ============================================
	// 使用类型特定的哈希函数计算 hash 值（包含随机 seed）
	hash := t.Hasher(key, uintptr(h.hash0))

	// 计算桶掩码：bucketMask(B) = 2^B - 1
	// 用于快速取模：hash & mask 等价于 hash % (2^B)
	m := bucketMask(h.B)

	// 定位到目标桶：使用哈希值的低 B 位索引桶数组
	// 公式：bucket_index = hash & (2^B - 1)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))

	// ============================================
	// 第五部分：处理扩容中的情况
	// ============================================
	if c := h.oldbuckets; c != nil {
		// map 正在扩容中，需要检查旧桶
		if !h.sameSizeGrow() {
			// 情况1：翻倍扩容（容量变为 2 倍）
			// 旧桶数量是新桶的一半，需要将掩码右移一位
			// 例如：B=4 时有 16 个桶，扩容后 B=5 有 32 个桶
			m >>= 1
		}
		// 情况2：等量扩容（sameSizeGrow）
		// 桶数量不变，只是整理碎片，掩码不变

		// 在旧桶数组中定位对应的桶
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))

		// 检查旧桶是否已迁移（evacuated）
		if !evacuated(oldb) {
			// 旧桶还未迁移，从旧桶中查找
			// 这是渐进式扩容的关键：读操作会读取未迁移的旧桶
			b = oldb
		}
		// 如果旧桶已迁移，继续使用新桶 b（前面已计算）
	}

	// ============================================
	// 第六部分：tophash 快速过滤
	// ============================================
	// 提取哈希值的高 8 位作为 tophash
	// tophash 用于快速过滤：只有 tophash 匹配才进行完整 key 比较
	top := tophash(hash)

	// ============================================
	// 第七部分：遍历桶链表查找 key
	// ============================================
bucketloop:
	// 外层循环：遍历溢出桶链表（当前桶 → overflow → overflow → ...）
	for ; b != nil; b = b.overflow(t) {
		// 内层循环：遍历当前桶的 8 个槽位
		for i := uintptr(0); i < abi.OldMapBucketCount; i++ {
			// ----------------------------------------
			// 步骤1：tophash 预检（快速路径）
			// ----------------------------------------
			if b.tophash[i] != top {
				// tophash 不匹配，快速跳过
				// 这避免了昂贵的完整 key 比较

				if b.tophash[i] == emptyRest {
					// 优化：遇到 emptyRest 标记
					// 表示当前位置及后续所有槽位（包括溢出桶）都是空的
					// 可以直接结束查找，无需继续遍历
					break bucketloop
				}
				// tophash 为 emptyOne 或其他已占用槽位：继续检查下一个
				continue
			}

			// ----------------------------------------
			// 步骤2：tophash 匹配，获取 key 指针
			// ----------------------------------------
			// 计算 key 的位置：dataOffset + i * keySize
			// 内存布局：[tophash数组][key0][key1]...[key7][value0]...[value7][overflow指针]
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))

			if t.IndirectKey() {
				// 间接 key：key 太大（>128字节），实际存储的是指针
				// 需要解引用获取真实的 key 地址
				k = *((*unsafe.Pointer)(k))
			}

			// ----------------------------------------
			// 步骤3：完整 key 比较（慢速路径）
			// ----------------------------------------
			if t.Key.Equal(key, k) {
				// key 匹配！计算对应的 value 地址
				// value 紧跟在所有 key 之后
				// 位置：dataOffset + 8*keySize + i*valueSize
				e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))

				if t.IndirectElem() {
					// 间接 elem：value 太大，存储的是指针
					// 解引用获取真实的 value 地址
					e = *((*unsafe.Pointer)(e))
				}

				// 返回指向 value 的指针
				return e
			}
			// key 不匹配（tophash 碰撞，false positive）
			// 继续检查当前桶的下一个槽位
		}
		// 当前桶的 8 个槽位都检查完毕，继续检查溢出桶
	}

	// ============================================
	// 第八部分：未找到 key
	// ============================================
	// 遍历完所有桶和溢出桶都未找到 key
	// 返回零值引用（而不是 nil）
	return unsafe.Pointer(&zeroVal[0])
}

关键步骤：

1. 计算 key 的哈希值
2. 用哈希值的低位定位桶（hash & bucketMask）
3. 如果正在扩容，检查旧桶是否已迁移
4. 用哈希值的高 8 位（tophash）快速比较
5. tophash 匹配后，再进行完整的 key 比较
6. 遍历溢出桶链表

3.3 插入/更新操作（mapassign）

底层调用 runtime/map.go 的 mapassign() 方法，跟 mapaccess() 非常像，只不过：

1. 先找找看 key 在不在，在的话，则覆盖新的 value；
2. 如果 key 不在，则插入新的 key 和 value，这里则需要考虑是否需要扩容了；

3.4 删除操作（mapdelete）

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	// 计算哈希值
	hash := t.Hasher(key, uintptr(h.hash0))

	// 设置写标志（在Hasher之后，避免panic时状态不一致）
	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  // 保存原始桶，用于emptyRest优化时回溯
	top := tophash(hash)

search:
	// 遍历桶链表
	for ; b != nil; b = b.overflow(t) {
		// 遍历桶内8个槽位
		for i := uintptr(0); i < abi.OldMapBucketCount; i++ {
			// tophash不匹配，快速跳过
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break search
				}
				continue
			}

			// 获取key并比较
			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
			}

			// 找到了，清理key（帮助GC）
			if t.IndirectKey() {
				*(*unsafe.Pointer)(k) = nil
			} else if t.Key.Pointers() {
				memclrHasPointers(k, t.Key.Size_)
			}

			// 清理value（帮助GC）
			e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
			if t.IndirectElem() {
				*(*unsafe.Pointer)(e) = nil
			} else if t.Elem.Pointers() {
				memclrHasPointers(e, t.Elem.Size_)
			} else {
				memclrNoHeapPointers(e, t.Elem.Size_)
			}

			// 标记为emptyOne
			b.tophash[i] = emptyOne

			// 优化：如果后面都是空的，将连续的emptyOne转为emptyRest
			// 这样后续查找遇到emptyRest可以立即终止
			if i == abi.OldMapBucketCount-1 {
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}

			// 向前回溯，将emptyOne改为emptyRest
			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 = abi.OldMapBucketCount - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}

		notLast:
			h.count--
			// map变空时重置哈希种子，防止哈希碰撞攻击
			if h.count == 0 {
				h.hash0 = uint32(rand())
			}
			break search
		}
	}

	// 清除写标志
	if h.flags&hashWriting == 0 {
		fatal("concurrent map writes")
	}
	h.flags &^= hashWriting
}

关键优化：

• 删除后将 tophash 标记为 emptyOne
• 如果后续都是空槽，优化为 emptyRest（加速查找）
• map 为空时重置哈希种子（防止攻击）

4. 扩容机制

4.1 触发条件

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
	return count > abi.OldMapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
// Note that most of these overflow buckets must be in sparse use;
// if use was dense, then we'd have already triggered regular map growth.
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	// If the threshold is too low, we do extraneous work.
	// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
	// "too many" means (approximately) as many overflow buckets as regular buckets.
	// See incrnoverflow for more details.
	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. 负载因子过高：元素数量 > 6.5 * 桶数量 → 翻倍扩容
2. 溢出桶过多：溢出桶数量 ≈ 主桶数量 → 等量扩容（整理碎片）

4.2 扩容实现（hashGrow）

// hashGrow 初始化map扩容
// 实际的数据迁移由 growWork() 和 evacuate() 增量完成
func hashGrow(t *maptype, h *hmap) {
	// 决定扩容策略：
	// 1. 负载因子过高 → 翻倍扩容 (bigger=1, 容量x2)
	// 2. 溢出桶过多   → 等量扩容 (bigger=0, 容量不变，只整理碎片)
	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)

	// 更新迭代器标志：将当前迭代器标记转移到旧迭代器标记
	// 这样正在进行的迭代器知道需要检查oldbuckets
	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}

	// 提交扩容（原子性操作，对GC可见）
	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
	}

	// 注意：这里只是初始化扩容，实际数据迁移是增量进行的
	// 每次写操作（insert/delete）时会调用 growWork() 迁移2个桶
}

func growWork(t *maptype, h *hmap, bucket uintptr) {
	evacuate(t, h, bucket&h.oldbucketmask())
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

1. 分配新桶数组（2 倍或相同大小）
2. 保存旧桶到 oldbuckets
3. 不立即迁移数据，标记为"正在扩容"
4. 后续每次写操作时增量迁移

4.3 渐进式迁移（evacuate）

// evacuate 将指定的旧桶迁移到新桶
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	// 定位要迁移的旧桶
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
	newbit := h.noldbuckets()  // 旧桶数量（用于计算哈希bit）

	if !evacuated(b) {
		// 准备迁移目标：x（低位）和 y（高位）
		var xy [2]evacDst
		x := &xy[0]
		// x 目标：与旧桶索引相同的新桶位置
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.e = add(x.k, abi.OldMapBucketCount*uintptr(t.KeySize))

		if !h.sameSizeGrow() {
			// 翻倍扩容：还需要准备 y 目标（新增的高位桶）
			// y 的位置 = oldbucket + 旧桶总数
			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, abi.OldMapBucketCount*uintptr(t.KeySize))
		}
		// 等量扩容：只使用 x，所有元素留在原位

		// 遍历旧桶及其溢出链
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			e := add(k, abi.OldMapBucketCount*uintptr(t.KeySize))

			// 遍历桶内8个槽位
			for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) {
				top := b.tophash[i]

				// 空槽位：标记为已迁移的空槽
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}
				if top < minTopHash {
					throw("bad map state")
				}

				// 获取key
				k2 := k
				if t.IndirectKey() {
					k2 = *((*unsafe.Pointer)(k2))
				}

				// 决定迁移到x还是y（仅翻倍扩容需要）
				var useY uint8
				if !h.sameSizeGrow() {
					// 重新计算哈希，根据新增的bit决定去向
					hash := t.Hasher(k2, uintptr(h.hash0))

					if h.flags&iterator != 0 && !t.ReflexiveKey() && !t.Key.Equal(k2, k2) {
						// 特殊情况：NaN key（key != key）
						// 哈希值不可重现，使用tophash的最低bit决定
						// 这样可以保证迭代器看到的结果一致
						useY = top & 1
						top = tophash(hash)
					} else {
						// 正常情况：检查新增的bit位
						// hash & newbit == 0 → 去x（低位）
						// hash & newbit != 0 → 去y（高位）
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}

				// 标记旧槽位已迁移（evacuatedX或evacuatedY）
				if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
					throw("bad evacuatedN")
				}
				b.tophash[i] = evacuatedX + useY  // evacuatedX=2, evacuatedY=3

				// 选择目标桶
				dst := &xy[useY]

				// 目标桶满了，分配新的溢出桶
				if dst.i == abi.OldMapBucketCount {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.e = add(dst.k, abi.OldMapBucketCount*uintptr(t.KeySize))
				}

				// 拷贝tophash
				dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top

				// 拷贝key
				if t.IndirectKey() {
					*(*unsafe.Pointer)(dst.k) = k2  // 拷贝指针
				} else {
					typedmemmove(t.Key, dst.k, k)   // 拷贝值
				}

				// 拷贝value
				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.ValueSize))
			}
		}

		// 清理旧桶的key/value，帮助GC（如果没有迭代器在使用）
		if h.flags&oldIterator == 0 && t.Bucket.Pointers() {
			b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))
			// 保留tophash（用于标记迁移状态）
			ptr := add(b, dataOffset)
			n := uintptr(t.BucketSize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

	// 如果刚好迁移的是nevacuate指向的桶，推进迁移进度
	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

迁移策略：

• 翻倍扩容：一个旧桶分裂到两个新桶（X 和 Y）
  • 根据哈希值的新比特位决定去 X 还是 Y
• 等量扩容：紧凑化，消除碎片
• 每次写操作迁移 2 个桶（当前桶 + nevacuate 桶）

4.4 总结图

5. 迭代器实现

// A hash iteration structure.
// If you modify hiter, also change cmd/compile/internal/reflectdata/reflect.go
// and reflect/value.go to match the layout of this structure.
type hiter struct {
	key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
	elem        unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
	t           *maptype
	h           *hmap
	buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
	bptr        *bmap          // current bucket
	overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
	oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
	startBucket uintptr        // bucket iteration started at
	offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
	wrapped     bool           // already wrapped around from end of bucket array to beginning
	B           uint8
	i           uint8
	bucket      uintptr
	checkBucket uintptr
	clearSeq    uint64
}

关键特性：

1. 随机起始位置：防止依赖迭代顺序
2. 快照机制：记录迭代开始时的 buckets 指针
3. 扩容兼容：同时检查新旧桶，确保不重复/遗漏

6. 负载因子选择

// Picking loadFactor: too large and we have lots of overflow
// buckets, too small and we waste a lot of space. I wrote
// a simple program to check some stats for different loads:
// (64-bit, 8 byte keys and elems)
//  loadFactor    %overflow  bytes/entry     hitprobe    missprobe
//        4.00         2.13        20.77         3.00         4.00
//        4.50         4.05        17.30         3.25         4.50
//        5.00         6.85        14.77         3.50         5.00
//        5.50        10.55        12.94         3.75         5.50
//        6.00        15.27        11.67         4.00         6.00
//        6.50        20.90        10.79         4.25         6.50
//        7.00        27.14        10.15         4.50         7.00
//        7.50        34.03         9.73         4.75         7.50
//        8.00        41.10         9.40         5.00         8.00
//
// %overflow   = percentage of buckets which have an overflow bucket
// bytes/entry = overhead bytes used per key/elem pair
// hitprobe    = # of entries to check when looking up a present key
// missprobe   = # of entries to check when looking up an absent key

Go 选择了 6.5 的负载因子（13/16 ≈ 0.8125）：

• 在空间利用率和性能之间取得平衡
• 约 20% 的桶会有溢出桶

7. 设计亮点

7.1 分离存储优化

将 keys 和 values 分别连续存储，而不是交替存储 key1, val1, key2, val2...，这样可以：

• 减少内存对齐造成的填充浪费
• 例如 map[int64]int8，交替存储需要大量填充

7.2 tophash 快速过滤

• 先比较 8 位 tophash，不匹配直接跳过
• 只有 tophash 匹配才进行完整 key 比较
• 大幅减少昂贵的 key 比较次数

7.3 渐进式扩容

• 避免一次性迁移造成的延迟峰值
• 分摊到后续的每次写操作
• 适合实时系统

7.4 等量扩容（整理碎片）

• 频繁增删导致溢出桶过多时触发
• 保持桶数量不变，重新排列元素
• 消除内存碎片，提升性能

7.5 并发安全检测

• 使用 hashWriting 标志检测并发读写
• 虽然不提供内置锁，但能快速检测到竞态条件
• 帮助开发者发现 bug

8. 并发

8.1 问题

前面分析 map 的访问的时候，我们已经知道 map 明确严禁并发读写。比如：

• 一个协程在读 map，另一个协程在驱逐，就可能出现问题。

所以如果我们非要在并发情况下使用 map 的话，就需要用 mutex 加锁了，但是这样 map 的性能非常差。

8.2 解决 —— sync.Map

8.2.1 底层

• Map

  type Map struct {
  	mu Mutex							// 锁
  	read atomic.Value 		// 指向一个 readOnly 结构体的值
  	dirty map[any]*entry	// 指向一个 map
  	misses int						// 没有命中的个数，即在 read 中读不到的次数
  }
  

• readOnly

  // readOnly is an immutable struct stored atomically in the Map.read field.
  type readOnly struct {
  	m       map[any]*entry	// 存储 map 数据
  	amended bool						// 当 dirtyMap 中有 m 没有的元素的时候，amended 值为 true
  }
  

• entry

  type entry struct {
  	p unsafe.Pointer // 万能指针，指向 value
  }
  

8.2.2 正常读写

• 走 read，读出 value 或者覆盖 value

8.2.3 追加

func (m *Map) Store(key, value interface{}) {
	// 1. 先尝试在 read map 中进行写
  read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

  // 2. read 中没有对应的 key，那就只能追加了，上锁操作 dirty map
	m.mu.Lock()
  // 3. 再读一遍 read map，因为有可能在我们上锁之前的一瞬间，别的协程将 dirty 提升了
	read, _ = m.read.Load().(readOnly)
  // 4. read map 中有了，说明已经被其他协程 dirty 提升了，
	if e, ok := read.m[key]; ok {
    // 4-1. 判断读出来的 entry 是否已经被标记为 unexpunged(已删除)
		if e.unexpungeLocked() {
			// 4-2. 该 enrty 已被标记为删除，那么就需要将其放到 dirty 中
			m.dirty[key] = e
		}
    // 4-3 读出来
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
    // 5. read map 中还是没有，那就读 dirty map
		e.storeLocked(&value)
	} else {
    // 6. dirty map 中还是没有，那就只能往 dirty map 中追加了
		if !read.amended {
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
  // 7. 追加完，解锁
	m.mu.Unlock()
}

// unexpungeLocked 可确保 entry 未标记为已清除。
//
// 如果该 entry 已经被标记为删除了，则必须在解锁 m.mu 之前将其添加到 dirty map 中。
func (e *entry) unexpungeLocked() (wasExpunged bool) {
	return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

8.2.4 追加后的读

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
  // 1. 先在 read 中找
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
  // 2. read 中找不到，就在 dirty 中找
	if !ok && read.amended {
    // 4. 上锁
		m.mu.Lock()
    // 5. 再读一次 read map，因为有可能在我们上锁之前的一瞬间，别的协程将 dirty 提升了
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
    // 6. 还是没在 read 中找到，就只能在 dirty 中找了
		if !ok && read.amended {
			e, ok = m.dirty[key]
      // 7. misses ++ 并判断是否需要 dirty 提升
			m.missLocked()
		}
    // 8. 解锁
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

8.2.5 dirty 提升

当 meisses = len(dirty) 的时候，就砍掉 read，将 dirty 提升到 read 的位置。

func (m *Map) missLocked() {
  // 1. 每在 dirty 中查一次，就 misses++
	m.misses++
	if m.misses < len(m.dirty) {
		return
	}
  // 2. 当 misses = len(m.dirty) 的时候，就 dirty 提升
  // 3. 将 dirtymap 赋值给 read map
  //     这里没有指出 amended，但是因为默认零值是 false，所以这里也将 amended 置为 false 了
	m.read.Store(readOnly{m: m.dirty})
  // 4. dirty 先为 nil，当要追加的时候，再来复制 read map
	m.dirty = nil
  // 5. 重置 misses
	m.misses = 0
}

func (m *Map) Store(key, value interface{}) {
	...
	if e, ok := read.m[key]; ok {
		...
	} else if e, ok := m.dirty[key]; ok {
		...
	} else {
    // 第一次追加到 dirty map 的时候，需要判断看 dirty map 之前是否已经被提升了，可能为 nil
    // 如果是 nil 的话，就需要复制 read map
		if !read.amended {
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
    // 追加 key
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

// 当 dirty map 为 nil 的时候
// 负责将 read map 复制到 dirty map
func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}

	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[interface{}]*entry, len(read.m))
	for k, e := range read.m {
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

8.2.6 删除

• 正常删除

  // Delete deletes the value for a key.
  func (m *Map) Delete(key interface{}) {
  	m.LoadAndDelete(key)
  }
  
  // LoadAndDelete deletes the value for a key, returning the previous value if any.
  // The loaded result reports whether the key was present.
  func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
  	read, _ := m.read.Load().(readOnly)
    // 1. 先从 read map 中找
  	e, ok := read.m[key]
  	...
    // 2. 找到了，就直接在 read map 中删除
  	if ok {
  		return e.delete()
  	}
  	return nil, false
  }
  
  func (e *entry) delete() (value interface{}, ok bool) {
  	for {
  		p := atomic.LoadPointer(&e.p)
  		if p == nil || p == expunged {
  			return nil, false
  		}
      // 3. 直接将 *entry 的 Pointer 置为空
  		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
  			return *(*interface{})(p), true
  		}
  	}
  }
  

  

• 追加后删除

  func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
    // 1. 先在 read map 中找
  	read, _ := m.read.Load().(readOnly)
  	e, ok := read.m[key]
  	if !ok && read.amended {
      // 2. 找不到，就上锁，然后在 dirty map 中找
  		m.mu.Lock()
      // 3. 找的时候一样，还是再次在 read map 中查一遍，防止有 dirty 提升
  		read, _ = m.read.Load().(readOnly)
  		e, ok = read.m[key]
  		if !ok && read.amended {
        // 4. read map 中还是没找到，那就在 dirty map 中找，删的时候，还是 *entry.Pointer = nil
  			e, ok = m.dirty[key]
  			delete(m.dirty, key)
        // 5. misses ++
  			m.missLocked()
  		}
  		m.mu.Unlock()
  	}
  	if ok {
  		return e.delete()
  	}
  	return nil, false
  }
  

  

• 删除后提升 dirty

  func (m *Map) dirtyLocked() {
  	if m.dirty != nil {
  		return
  	}
  
  	read, _ := m.read.Load().(readOnly)
  	m.dirty = make(map[interface{}]*entry, len(read.m))
  	for k, e := range read.m {
      // 不复制标记为 expunged 的
  		if !e.tryExpungeLocked() {
  			m.dirty[k] = e
  		}
  	}
  }
  

  

  

8.3 总结

• sync.Map 使用了两个 map，将“普通读写”和“追加”进行分离；
• 不会引发扩容的操作（查、改）使用 read map；
• 可能引起扩容的操作（增）使用 dirty map；