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

栏目: IT技术 · 发布时间: 4年前

内容简介:在golang中,它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。
Dig101: dig more, simplified more and know more

在golang中, map 是一个不可或缺的存在。

它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。

这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。

我们不会过多在源码分析上展开,只结合代码示例对其背后设计实现上做些总结,希望可以简单明了一些。

希望看完后,会让你对 map 有更清晰的理解。网上有很多不错的源码分析,会附到文末。

本文分析基于Mac平台上 go1.14beta1 版本。

我们先简单过下map实现hash表所用的数据结构,这样方便后边讨论。

0x01 map的内部结构

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

在这里我们先弄清楚map实现的整体结构

map本质是hash表( hmap ),指向一堆桶( buckets )用来承接数据,每个桶( bmap )能存8组k/v。

当有数据读写时,会用 key 的hash找到对应的桶。

为加速hash定位桶, bmap 里记录了 tophash 数组(hash的高8位)

hash表就会有哈希冲突的问题(不同key的hash值一样,即hash后都指向同一个桶),为此map使用桶后链一个溢出桶( overflow )链表来解决当桶8个单元都满了,但还有数据需要存入此桶的问题。

剩下 noverflow,oldbuckets,nevacuate,oldoverflow 会用于扩容,暂时先不展开

具体对应的数据结构详细注释如下:

(虽然多,先大致过一遍,后边遇到会在提到)

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

这里有几个字段需要解释一下:

  • hmap.B

这个为啥用2的对数来表示桶的数目呢?

这里是为了hash定位桶及扩容方便

比方说, hash%n 可以定位桶, 但 % 操作没有位运算快。

而利用 n=2^B,则hash%n=hash&(n-1)

则可优化定位方式为: hash&(1<<B-1)(1<<B-1) 即源码中 BucketMask

再比方扩容, hmap.B=hmap.B+1 即为扩容到二倍

  • bmap.keys, bmap.elems

在桶里存储k/v的方式不是一个k/v一组, 而是k放一块,v放一块。

这样的相对k/v相邻的好处是,方便内存对齐。比如 map[int64]int8 , v是 int8 ,放一块就避免需要额外内存对齐。

另外对于大的k/v也做了优化。

正常情况key和elem直接使用用户声明的类型,但当其size大于128( MAXKEYSIZE/MAXELEMSIZE )时,

则会转为指针去存储。(也就是 indirectkey、indirectelem

  • hmap.extra

这个额外记录溢出桶意义在哪?

具体是为解决让 gc 不需要扫描此类 bucket

只要bmap内不含指针就不需gc扫描。

mapkeyelem 类型都不包含指针时,但其中的 overflow 是指针。

此时bmap的生成函数会将 overflow 的类型转化为 uintptr

uintptr 虽然是地址,但不会被 gc 认为是指针,指向的数据有被回收的风险。

此时为保证其中的 overflow 指针指向的数据存活,就用 mapextra 结构指向了这些 buckets ,这样bmap有被引用就不会被回收了。

关于uintptr可能被回收的例子,可以看下 go101 - Type-Unsafe Pointers 中 Some Facts in Go We Should Know

0x02 map的hash方式

了解map的基本结构后,我们通过下边代码分析下map的hash

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)

为什么不可以用 []int 作为key呢?

查找源码中hash的调用链注释如下:

// 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()))
  }
  ...
}

如上,我们会发现map的hash函数并不唯一。

它会对不同key类型选取不同的hash方式,以此加快hash效率

这个例子 slice 不可比较,所以不能作为key。

也对,不可比较的类型作为key的话,找到桶但没法比较key是否相等,那map用这个key读写都会是个问题。

还有哪些不可比较?

cmd/compile/internal/gc/alg.goalgtype1 函数中可以找到返回 ANOEQ (不可比较类型)的类型,如下:

  • func,map,slice
  • 内部元素有这三种类型的array和struct类型

0x03 map的扩容方式

map 不可以对其值取地址;

如果值类型为 slicestruct ,不能直接操作其内部元素

我们用代码验证如下:

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

为什么呢?

这是因为 map 内部有渐进式扩容,所以 map 的值地址不固定,取地址没有意义。

也因此,对于值类型为 slicestruct , 只有把他们各自当做整体去赋值操作才是安全的。 go有个issue讨论过这个问题: issues-3117

针对扩容的方式,有两类,分别是:

  • sameSizeGrow

过多的 overflow 使用,使用等大小的buckets重新整理,回收多余的 overflow 桶,提高map读写效率,减少溢出桶占用

这里借助 hmap.noverflow 来判断溢出桶是否过多

hmap.B<=15 时,判断是溢出桶是否多于桶数 1<<hmap.B

否则只判断溢出桶是否多于 1<<15

这也就是为啥 hmap.noverflow ,当其接近 1<<15 - 1 时为近似值, 只要可以评估是否溢出桶过多不合理就行了

  • biggerSizeGrow

count/size > 6.5 (装载因子 : overLoadFactor ), 避免读写效率降低。

扩容一倍,并渐进的在赋值和删除( mapassign和mapdelete )期间,

对每个桶重新分流到 x (原来桶区间)和 y (扩容后的增加的新桶区间)

这里 overLoadFactor (count/size)是评估桶的平均装载数据能力,即map平均每个桶装载多少个k/v。

这个值太大,则桶不够用,会有太多溢出桶;太小,则分配了太多桶,浪费了空间。

6.5是测试后对map装载能力最大化的一个的选择。

源码中扩容代码注释如下:

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

具体扩容 evacuate (迁移)时,判断是否要将旧桶迁移到新桶后半区间( y )有段代码比较有趣, 注释如下:

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没有意义。。。

弄清楚map的结构、hash和扩容,剩下的就是初始化、读写、删除和遍历了,我们就不详细展开了,简单过下。

0x04 map的初始化

map不初始化时为nil,是不可以操作的。可以通过make方式初始化

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

对于这两种map内部调用方式是不一样的

  • small map

当不指定大小或者指定大小不大于8时,调用

func makemap_small() *hmap {

只需要直接在堆上初始化 hmap 和hash种子( hash0 )就行。

  • bigger map

当大小大于8, 调用

func makemap(t *maptype, hint int, h *hmap) *hmap {

hint 溢出则置0

初始化 hmap 和hash种子

根据 overLoadFactor:6.5 的要求, 循环增加 h.B , 获取 hint/(1<<h.B) 最接近 6.5的 h.B

预分配hashtable的bucket数组

h.B 大于4的话,多分配至少 1<<(h.B-4) (需要内存对齐)个bucket,用于可能的 overflow 桶使用,

并将 h.nextOverflow 设置为第一个可用的 overflow 桶。

最后一个 overflow 桶指向 h.buckets (方便后续判断已无 overflow 桶)

0x05 map的读取

对于map的读取有着三个函数,主要区别是返回参数不同

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

计算key的hash,定位当前buckets里桶位置

如果当前处于扩容中,也尝试去旧桶取对应的桶,需考虑扩容前bucket大小是否为现在一半,且其所指向的桶未迁移

然后就是按照bucket->overflow链表的顺序去遍历,直至找到 tophash 匹配且key相等的记录(entry)

期间,如果key或者elem是转过指针(size大于128),需转回对应值。

map为空或无值返回elem类型的零值

0x06 map的赋值

计算key的hash,拿到对应的桶

如果此时处于扩容期间,则执行扩容 growWork

对桶bucket->overflow链表遍历

  • 若有空桶(对应tophash[i]为空),则准备在此空桶存储k/v

  • 若非空,且和tophash相等,且key相等,则更新对应elem

  • 若无可用桶,则分配一个新的overflow桶来存储k/v, 会判断是否需要扩容

最后若使用了空桶或新 overflow 桶,则要将对应 tophash 更新回去, 如果需要的话,也更新 count

0x07 map的删除

获取待删除key对应的桶,方式和mapassign的查找方式基本一样,找到则清除k/v。

这里还有个额外操作:

如果当前tophash状态是:当前cell为空( emptyOne ),

若其后桶或其后的overflow桶状态为:当前cell为空前索引高于此cell的也为空( emptyRest ),则将当前状态也更新为 emptyRest

倒着依次往前如此处理,实现 emptyOne -> emptyRest 的转化

这样有什么好处呢?

答案是为了方便读写删除( mapaccess,mapassign,mapdelete )时做桶遍历( bucketLoop )能减少不必要的空bucket遍历

截取代码如下:

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

0x08 map的遍历

先调用 mapiterinit 初始化用于遍历的 hiter 结构体, 这里会用随机定位出一个起始遍历的桶 hiter.startBucket , 这也就是为啥map遍历无序。

随机获取起始桶的代码如下:

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

在调用 mapiternext 去实现遍历, 遍历中如果处于扩容期间,如果当前桶已经迁移了,那么就指向新桶,没有迁移就指向旧桶

至此,map的内部实现我们就过完了。里边有很多优化点,设计比较巧妙,需要多体会一番。

趁热打铁,你可以去阅读一遍源码,加深一下理解。

附上几篇不错的源码分析文章,代码对应的 go 版本和本文不一致,但变化不大,可以对照着看。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Open Data Structures

Open Data Structures

Pat Morin / AU Press / 2013-6 / USD 29.66

Offered as an introduction to the field of data structures and algorithms, Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues......一起来看看 《Open Data Structures》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具