Dig101:Go之读懂map的底层设计

// runtime/map.go
// A header for a Go map.
type hmap struct {
  //用于len(map)
  count     int
  //标志位
  // iterator     = 1 // 可能有遍历用buckets
  // oldIterator  = 2 // 可能有遍历用oldbuckets，用于扩容期间
  // hashWriting  = 4 // 标记写，用于并发写入检测
  // sameSizeGrow = 8 // 用于等大小buckets扩容，减少overflow桶
  flags     uint8

  // 代表可以最多容纳loadFactor * 2^B个元素（loadFactor=6.5）
  B         uint8
  // overflow桶的计数，当其接近1<<15 - 1时为近似值
  noverflow uint16
  // 随机的hash种子，每个map不一样，减少哈希碰撞的几率
  hash0     uint32

  // 当前桶，长度为（0-2^B）
  buckets    unsafe.Pointer
  // 如果存在扩容会有扩容前的桶
  oldbuckets unsafe.Pointer
  // 迁移数，标识小于其的buckets已迁移完毕
  nevacuate  uintptr

  // 额外记录overflow桶信息，不一定每个map都有
  extra *mapextra
}

// 额外记录overflow桶信息
type mapextra struct {
  overflow    *[]*bmap
  oldoverflow *[]*bmap

  // 指向下一个可用overflow桶
  nextOverflow *bmap
}

const(
  // 每个桶8个k/v单元
  BUCKETSIZE  = 8
  // k或v类型大小大于128转为指针存储
  MAXKEYSIZE  = 128
  MAXELEMSIZE = 128
)

// 桶结构 （字段会根据key和elem类型动态生成，见下边bmap）
type bmap struct {
  // 记录桶内8个单元的高8位hash值，或标记空桶状态，用于快速定位key
  // emptyRest      = 0 // 此单元为空，且更高索引的单元也为空
  // emptyOne       = 1 // 此单元为空
  // evacuatedX     = 2 // 用于表示扩容迁移到新桶前半段区间
  // evacuatedY     = 3 // 用于表示扩容迁移到新桶后半段区间
  // evacuatedEmpty = 4 // 用于表示此单元已迁移
  // minTopHash     = 5 // 最小的空桶标记值，小于其则是空桶标志
  tophash [bucketCnt]uint8
}

// cmd/compile/internal/gc/reflect.go
// func bmap(t *types.Type) *types.Type {
// 每个桶内k/v单元数是8
type bmap struct{
  topbits [8]uint8 //tophash
  keys [8]keytype
  elems [8]elemtype
  // overflow 桶
  // otyp 类型为指针*Type,
  // 若keytype及elemtype不含指针，则为uintptr
  // 使bmap整体不含指针,避免gc去scan此类map
  overflow otyp
}

var m = map[interface{}]int{}
var i interface{} = []int{}
//panic: runtime error: hash of unhashable type []int
println(m[i])
//panic: runtime error: hash of unhashable type []int
delete(m, i)

// runtime/map.go
// mapassign，mapaccess1中 获取key的hash
hash := t.hasher(key, uintptr(h.hash0))

// cmd/compile/internal/gc/reflect.go
func dtypesym(t *types.Type) *obj.LSym {
  switch t.Etype {
    // ../../../../runtime/type.go:/mapType
  case TMAP:
    ...
    // 依据key构建hash函数
    hasher := genhash(t.Key())
    ...
  }
}

// cmd/compile/internal/gc/alg.go
func genhash(t *types.Type) *obj.LSym {
  switch algtype(t) {
  ...
  //具体针对interface调用interhash
  case AINTER:
    return sysClosure("interhash")
  ...
  }
}

// runtime/alg.go
func interhash(p unsafe.Pointer, h uintptr) uintptr {
  //获取interface p的实际类型t，此处为slice
  a := (*iface)(p)
  tab := a.tab
  t := tab._type
  // slice类型不可比较，没有equal函数
  if t.equal == nil {
    panic(errorString("hash of unhashable type " + t.string()))
  }
  ...
}

m0 := map[int]int{}
// :negative_squared_cross_mark: cannot take the address of m0[0]
_ = &m0[0]

m := make(map[int][2]int)
// :white_check_mark:
m[0] = [2]int{1, 0}
// :negative_squared_cross_mark: cannot assign to m[0][0]
m[0][0] = 1
// :negative_squared_cross_mark: cannot take the address of m[0]
_ = &m[0]

type T struct{ v int }
ms := make(map[int]T)
// :white_check_mark:
ms[0] = T{v: 1}
// :negative_squared_cross_mark: cannot assign to struct field ms[0].v in map
ms[0].v = 1
// :negative_squared_cross_mark: cannot take the address of ms[0]
_ = &ms[0]
}

// mapassign 中创建新bucket时检测是否需要扩容
if !h.growing() && //非扩容中
  (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  // 提交扩容，生成新桶，记录旧桶相关。但不开始
  // 具体开始是后续赋值和删除期间渐进进行
  hashGrow(t, h)
}

//mapassign 或 mapdelete中 渐进扩容
bucket := hash & bucketMask(h.B)
if h.growing() {
  growWork(t, h, bucket)
}

// 具体迁移工作执行，每次最多两个桶
func growWork(t *maptype, h *hmap, bucket uintptr) {
  // 迁移对应旧桶
  // 若无迭代器遍历旧桶，可释放对应的overflow桶或k/v
  // 全部迁移完则释放整个旧桶
  evacuate(t, h, bucket&h.oldbucketmask())

  // 如果还有旧桶待迁移，再迁移一个
  if h.growing() {
    evacuate(t, h, h.nevacuate)
  }
}

newbit := h.noldbuckets()
var useY uint8
if !h.sameSizeGrow() {
  // 获取hash
  hash := t.hasher(k2, uintptr(h.hash0))
  if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
  // 这里 key != key 是指key为NaNs，
  // 此时 useY = top & 1 意味着有50%的几率到新桶区间
    useY = top & 1
    top = tophash(hash)
  } else {
    if hash&newbit != 0 {
  // 举例来看 若扩容前h.B=3时, newbit=1<<3
  // hash&newbit != 0 则hash形如 xxx1xxx
  // 新hmap的BucketMask= 1<<4 - 1 (1111: 15)
  // 则 hash&新BucketMask > 原BucketMask 1<<3-1 (111: 7)
  // 所以去新桶区间
      useY = 1
    }
  }
}

// 补充一个 key != key 的代码示例
n1, n2 := math.NaN(), math.NaN()
m := map[float64]int{}
m[n1], m[n2] = 1, 2
println(n1 == n2, m[n1], m[n2])
// output: false 0 0
// 所以NaN做key没有意义。。。

// 不指定大小
s := make(map[int]int)
// 指定大小
b := make(map[int]int,10)

mapaccess1: m[k]
mapaccess2: a,b = m[i]
mapaccessk: 在map遍历时若grow已发生，key可能有更新，需用此函数重新获取k/v

bucketloop:
  for ; b != nil; b = b.overflow(t) {
    for i := uintptr(0); i < bucketCnt; i++ {
      if b.tophash[i] != top {
        // 减少空cell的遍历
        if b.tophash[i] == emptyRest {
          break bucketloop
        }
        continue
      }
    ...
  }

r := uintptr(fastrand())
// 随机数不够用得再加一个32位
if h.B > 31-bucketCntBits {
  r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)