这里为什么 key 和 value 要分开存储， 主要是为了满足 go 的内存对齐规则(感兴趣的可以自行查阅)， key 和 key 之间， value 和 value 之间内存都是对齐的， 不需要单独的填充
bmap 中 tophash
tophash 是用来标识当前 bucket 中每个位置的状态的，其取值如下：
1 2 3 4 5 6
emptyRest = 0 // this cell isempty, and there are no more non-empty cells at higher indexes or overflows. emptyOne = 1 // this cell isempty evacuatedX = 2 // key/elem is valid. Entry has been evacuated tofirst half of larger table. evacuatedY = 3 // same as above, but evacuated to second half of larger table. evacuatedEmpty = 4 // cell isempty, bucket is evacuated. minTopHash = 5 // minimum tophash foranormal filled cell. minTopHash 的意思就是最小的 hash 值，即要求所有的 hash 值不小于该值
funchashGrow(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.
// 写的时候置标志位 // 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.flags&hashWriting != 0 { fatal("concurrent map read and map write") }
// 存储值的 entry type entry struct { // 就是包装了一下 unsafe.Pointer p atomic.Pointer[any] }
// expunged is an arbitrary pointer that marks entries which have been deleted // from the dirty map. // expunged 标识 p 已经从 dirty 里面删除了 var expunged = new(any)
func(m *Map) Swap(key, value any) (previous any, loaded bool) { read := m.loadReadOnly() // 如果 read 里面存在， 则尝试更新 entry（CAS 操作， 保证了并发可见性） if e, ok := read.m[key]; ok { if v, ok := e.trySwap(&value); ok { if v == nil { returnnil, false } return *v, true } }
// 如果上一步更新 entry 没成功
// 先加锁 m.mu.Lock() // 从 read 读取一遍
read = m.loadReadOnly()
// case 1: 如果 read 存在 if e, ok := read.m[key]; ok { // 如果 p 是 expunged, 则需要先将 entry 赋值给 dirty（因为 expunged 数据不会留在 dirty） if e.unexpungeLocked() { m.dirty[key] = e } // 更新 entry, 返回老的 value if v := e.swapLocked(&value); v != nil { loaded = true // 老的 value 赋值给 previous previous = *v } } elseif e, ok := m.dirty[key]; ok { // case 2: read 里面不存在， 但是 dirty 存在， 则用值更新 entry if v := e.swapLocked(&value); v != nil { loaded = true previous = *v } } else { // 如果 read 和 dirty 都不存在
// 如果 amended 为 false(dirty 没有比 read 多数据) ， 则代表进来的是一个新的 key if !read.amended { // We're adding the first new key to the dirty map. // Make sure it is allocated and mark the read-only map as incomplete. m.dirtyLocked() // 然后将 amended 改为 true m.read.Store(&readOnly{m: read.m, amended: true}) } // 将新的值写入 dirty m.dirty[key] = newEntry(value) } m.mu.Unlock() return previous, loaded }
// 更新 entry 的值， 如果 p == expunged， 则更新失败 func(e *entry) trySwap(i *any) (*any, bool) { for { p := e.p.Load() if p == expunged { returnnil, false } if e.p.CompareAndSwap(p, i) { return p, true } } }
// Delete deletes the value for a key. func(m *Map) Delete(key any) { m.LoadAndDelete(key) }
func(m *Map) LoadAndDelete(key any) (value any, loaded bool) { read := m.loadReadOnly() e, ok := read.m[key] // read 不存在则查询 dirty if !ok && read.amended { m.mu.Lock() read = m.loadReadOnly() e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] delete(m.dirty, key) // Regardless of whether the entry was present, record a miss: this key // will take the slow path until the dirty map is promoted to the read // map. m.missLocked() } m.mu.Unlock() } // read 查询到 entry 后执行删除 if ok { return e.delete() } returnnil, false }
func(e *entry)delete() (value any, ok bool) { for { p := e.p.Load() if p == nil || p == expunged { returnnil, false } // 将 entry.p 标记为 nil，数据并没有实际删除 // 真正删除数据并被被置为 expunged，是在 Store 的 tryExpungeLocked 中 if e.p.CompareAndSwap(p, nil) { return *p, true } } }
