Golang Map 实现（二）

1
2

example1Map := make(map[int64]string)
example2Map := make(map[int64]string, 100)

1
2
3
4

// hint 就是 make 初始化map 的第二个参数
func makemap(t *maptype, hint int, h *hmap) *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap
func makemap_small() *hmap

1
2
3
4
5

func makemap_small() *hmap {  
  h := new(hmap)
  h.hash0 = fastrand()
  return h
}

1
2
3
4
5
6

func makemap64(t *maptype, hint int64, h *hmap) *hmap {
  if int64(int(hint)) != hint {
    hint = 0
  }
  return makemap(t, int(hint), h)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

type maptype struct {
  typ        _type  // type 类型
  key        *_type // key 的type
  elem       *_type // value 的type
  bucket     *_type // internal type representing a hash bucket
  keysize    uint8  // key 的大小
  valuesize  uint8  // value 的大小
  bucketsize uint16 // size of bucket
  flags      uint32
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// hint 需要创建的 map 大小(预计要添加多少元素)
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)
  }

  // xorshift64+ 算法, 可以研究下
  h.hash0 = fastrand()

  // 计算B 的值
  // 如果大于8，就先申请好。
  // 申请规则就是刚好满足 hint < 6.5 * 2 ^ B 的时候 （B 最大是63）
  // 其中6.5 相当于每个bucket 链表中，平均有6.5个bucket
  // 所以最长的map，应该是 6.5 * 2^63 (正常用肯定不会溢出)
  
  B := uint8(0)
  for overLoadFactor(hint, B) {
    B++
  }
  h.B = B

  // 接着数据初始化, 如果 容量小于等于8的，就在用的时候初始化, B 为0
  if h.B != 0 {
    var nextOverflow *bmap
    // 申请一个buckets 数组
    h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
    if nextOverflow != nil {
      h.extra = new(mapextra)
      h.extra.nextOverflow = nextOverflow
    }
  }

  return h
}

1

hint < 6.5 * (1 << B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) 
	(buckets unsafe.Pointer, nextOverflow *bmap) {
  base := bucketShift(b)
  nbuckets := base
  // 为了防止溢出的迁移，加一点冗余的bucket
  if b >= 4 {  
    // ... 修改nbuckets
  }

  // 如果之前没有分配过，那直接分配
  if dirtyalloc == nil {
    buckets = newarray(t.bucket, int(nbuckets))
  } else {
    // 使用以前分配好的
    buckets = dirtyalloc
    size := t.bucket.size * nbuckets
    if t.bucket.kind&kindNoPointers == 0 {
      memclrHasPointers(buckets, size)
    } else {
      memclrNoHeapPointers(buckets, size)
    }
  }

  if base != nbuckets {
	// 处理多申请出来的bucket
  }
  return buckets, nextOverflow
}

1
2
3
4
5
6

    nbuckets += bucketShift(b - 4)
    sz := t.bucket.size * nbuckets
    up := roundupsize(sz)
    if up != sz {
      nbuckets = up / t.bucket.size
    }

1
2
3
4
5
6
7
8
9

    // 上面添加了一些nbuckets 防止溢出，所以B 值取模就不太合理了，所以有一个mapextra 的数据节点
    // 数据分配也很有趣，从刚申请的buckets数组中，取出后面的一段分给mapextra
    // nextOverflow 分配给mapextra
    nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))

    // 取nextOverflow 里面的最后一个元素
    // 并把最后一个buckets 的末尾偏移的指针指向空闲的bucket (目前就是第一个buckets 了)
    last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
    last.setoverflow(t, (*bmap)(buckets))