欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Golang Map 实现创建,make是如何构造的

程序员文章站 2022-07-27 15:47:41
本文在golang map 数据结构的基础上,学习一个make 是如何构造的。 map 创建示例 在golang 中,初始化一个map 算是有两种方式。 第一种方式默认不指定map的容量,第二种会指定后续map的容量估计为100,希望在创建的时候把空间就分配好。 当make创建map时,底层做了什么 ......


map 创建示例

在golang 中,初始化一个map 算是有两种方式。

example1map := make(map[int64]string)
example2map := make(map[int64]string, 100)

第一种方式默认不指定map的容量,第二种会指定后续map的容量估计为100,希望在创建的时候把空间就分配好。

当make创建map时,底层做了什么

对于不同的初始化方式,会使用不同的方式。下面是提供的几种初始化方法:

// 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

区别在于:
如果不指定 hint,就调用makemap_small;
如果make 第二个参数为int64, 则调用makemap64;
其他情况调用makemap方法。下面我们逐一学习。

makemap_small

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

fastrand 是创建一个seed,在生成hash值时使用。
所以在makemap_small 时,只是创建了一个hmap 的结构体,并没有初始化buckets.

makemap64

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

makemap64 是对于传入的第二个参数为int64 的变量使用的。 如果hint的值大于int最大值,就将hint赋值为0,否则和makemap 初始化没有差别。为什么不把大于2^31 - 1 的map 直接初始化呢?因为在hmap 中 count 的值就是int,也就是说map最大就是 2^31 - 1 的大小

makemap

这个是初始化map的核心代码了,需要我们慢慢品味。

一开始,我们需要了解下maptype这个结构, maptype 标识一个map 数据类型的定义,当然还有其他的类型,比如说interfacetype,slicetype,chantype 等。maptype 的定义如下:

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
}

maptype 里面存储了kv的对象类型,bucket类型,以及kv占用内存的大小。以及bucketsize的大小,还有一些标记字段(flags)。在map 实现时,需要用到这些字段做偏移计算等。

下面是 makemap 的代码:

// 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
}

首先,通过bucketsize 和hint 的值,计算出需要分配的内存大小mem, 以及是否会overflow (大于指针的最大地址范围),如果溢出或者申请的内存大于最大可以申请的内存时,就设置hint为0了,直接不初始化buckets了。

接着,和makemap_small 一样,初始化一个随机的种子。

然后,计算b的值. 在overloadfactor 中,判断了hint 的大小。如果小于等于8,那b就不再赋值,直接不初始化数据。如果b大于8,那就计算b了。这里涉及到一个填充因子的概念。大概意思就是说,每个hash值(也就是pos)中,平均放多少个kv数据,默认是6.5;所以判断标准就是hint 必须满足如下的条件:

hint < 6.5 * (1 << b)

通过增加b的值,直到上面的表达式满足为止。这样b就初始化好了。

最后,申请一个bucket数组,赋值给buckets,如果有多申请出来的buckets,那就赋值给extra.nextoverflow, 当溢出之后,从多申请出来的buckets 里面取(也是为了避免内存分配)。

下面就详细看下初始化一个buckets的构建。

makebucketarray

makebucketarray 用于初始化一个bucket 数组。也就是hmap 中的buckets,下面是相关代码:

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
}

这里用到了比较多的指针计算,需要细细品读。

  • 首先,就是就是通过b计算一个base值,base = 1 << b (2 ^ b)
    nbuckets 是需要申请的数组的长度,正常情况下 base 值就是数组长度。但是,如果 base 大于16时,会预分配一些需要后期做overflow的bucket。这个overflow的计算规则如下:
    nbuckets += bucketshift(b - 4)
    sz := t.bucket.size * nbuckets
    up := roundupsize(sz)
    if up != sz {
      nbuckets = up / t.bucket.size
    }

在base 的基础上,多分配 base / 16 长度的bucket。然后根据内存的分配规则(包括了页大小和内存对齐等规则),计算出合适的分配内存的大小,然后计算出 bucket 的分配个数 nbuckets.

  • 其次,如果有之前未分配内存,那就初始化一个数组(终于等到了这一步),如过有dirtyalloc, 那就使用dirtyalloc 的内存(其实是用来清除map中数据使用的),然后把dirtyalloc中不需要的数据清除引用。

  • 最后,如果除了需要申请的base 长度的bucket外,还多申请了一些bucket,下面是对多申请的数据做的处理:

    // 上面添加了一些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))

先计算出多申请出来的内存地址 nextoverflow,然后计算出 申请的最后一块bucket的地址,然后将最后一块bucket的overflow指针(指向链表的指针)指向buckets 的首部。 原因呢,是为了将来判断是否还有空的bucket 可以让溢出的bucket空间使用。

原文链接:https://www.cnblogs.com/-lee/p/12777254.html