一文啃透 Go map：初始化和访问

399次阅读  |  发布于3年以前

咱们一起探索 Go 语言 map 里面的奥妙吧，看看它的内在是怎么构成的，又分别有什么值得留意的地方？

本文将探讨初始化和访问元素相关板块，咱们带着疑问去学习，例如：

数据结构

首先我们一起看看 Go 语言中 map 的基础数据结构，先有一个大致的印象

hmap 基本结构

hmap


type hmap struct {
 count     int
 flags     uint8
 B         uint8
 noverflow uint16
 hash0     uint32
 buckets    unsafe.Pointer
 oldbuckets unsafe.Pointer
 nevacuate  uintptr
 extra *mapextra
}

type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap
 nextOverflow *bmap
}

在这里我们要注意几点，如下：

  1. 如果 keys 和 values 都不包含指针并且允许内联的情况下。会将 bucket 标识为不包含指针，使用 extra 存储溢出桶就可以避免 GC 扫描整个 map，节省不必要的开销
  2. 在前面有提到，Go 用了增量扩容。而 buckets 和 oldbuckets 也是与扩容相关的载体，一般情况下只使用 buckets，oldbuckets 是为空的。但如果正在扩容的话，oldbuckets 便不为空，buckets 的大小也会改变
  3. 当 hint 大于 8 时，就会使用 *mapextra 做溢出桶。若小于 8，则存储在 buckets 桶中

bmap

bmap 基本结构

bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits
...
type bmap struct {
 tophash [bucketCnt]uint8
}

实际 bmap 就是 buckets 中的 bucket，一个 bucket 最多存储 8 个键值对

tophash

tophash 是个长度为 8 的数组，代指桶最大可容纳的键值对为 8。

存储每个元素 hash 值的高 8 位，如果 tophash [0] <minTopHash，则 tophash [0] 表示为迁移进度

keys 和 values

在这里我们留意到，存储 k 和 v 的载体并不是用 k/v/k/v/k/v/k/v 的模式，而是 k/k/k/k/v/v/v/v 的形式去存储。这是为什么呢？

map[int64]int8

在这个例子中，如果按照 k/v/k/v/k/v/k/v 的形式存放的话，虽然每个键值对的值都只占用 1 个字节。但是却需要 7 个填充字节来补齐内存空间。最终就会造成大量的内存 “浪费”

但是如果以 k/k/k/k/v/v/v/v 的形式存放的话，就能够解决因对齐所 "浪费" 的内存空间

因此这部分的拆分主要是考虑到内存对齐的问题，虽然相对会复杂一点，但依然值得如此设计

overflow

可能会有同学疑惑为什么会有溢出桶这个东西？实际上在不存在哈希冲突的情况下，去掉溢出桶，也就是只需要桶、哈希因子、哈希算法。也能实现一个简单的 hash table。但是哈希冲突（碰撞）是不可避免的...

而在 Go map 中当 hmap.buckets 满了后，就会使用溢出桶接着存储。我们结合分析可确定 Go 采用的是数组 + 链地址法解决哈希冲突

初始化

用法

m := make(map[int32]int32)

函数原型

通过阅读源码可得知，初始化方法有好几种。函数原型如下：

func makemap_small() *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap

源码

func makemap(t *maptype, hint int, h *hmap) *hmap {
 if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
  hint = 0
 }

 if h == nil {
  h = new(hmap)
 }
 h.hash0 = fastrand()

 B := uint8(0)
 for overLoadFactor(hint, B) {
  B++
 }
 h.B = B

 if h.B != 0 {
  var nextOverflow *bmap
  h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
  if nextOverflow != nil {
   h.extra = new(mapextra)
   h.extra.nextOverflow = nextOverflow
  }
 }

 return h
}

在这里可以注意到（当 hint 大于等于 8 ）第一次初始化 map 时，就会通过调用 makeBucketArray 对 buckets 进行分配。因此我们常常会说，在初始化时指定一个适当大小的容量。能够提升性能。

若该容量过少，而新增的键值对又很多。就会导致频繁的分配 buckets，进行扩容迁移等 rehash 动作。最终结果就是性能直接的下降（敲黑板）

而当 hint 小于 8 时，这种问题相对就不会凸显的太明显，如下：

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

图示

访问

用法

v := m[i]
v, ok := m[i]

函数原型

在实现 map 元素访问上有好几种方法，主要是包含针对 32/64 位、string 类型的特殊处理，总的函数原型如下：


mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer)

mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer
mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool)

mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool)
mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
...

mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
...

源码

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
 ...
 if h == nil || h.count == 0 {
  return unsafe.Pointer(&zeroVal[0])
 }
 if h.flags&hashWriting != 0 {
  throw("concurrent map read and map write")
 }
 alg := t.key.alg
 hash := alg.hash(key, uintptr(h.hash0))
 m := bucketMask(h.B)
 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
 if c := h.oldbuckets; c != nil {
  if !h.sameSizeGrow() {
   // There used to be half as many buckets; mask down one more power of two.
   m >>= 1
  }
  oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
  if !evacuated(oldb) {
   b = oldb
  }
 }
 top := tophash(hash)
 for ; b != nil; b = b.overflow(t) {
  for i := uintptr(0); i < bucketCnt; i++ {
   if b.tophash[i] != top {
    continue
   }
   k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
   if t.indirectkey {
    k = *((*unsafe.Pointer)(k))
   }
   if alg.equal(key, k) {
    v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
    if t.indirectvalue {
     v = *((*unsafe.Pointer)(v))
    }
    return v
   }
  }
 }
 return unsafe.Pointer(&zeroVal[0])
}

在上述步骤三中，提到了根据不同的类型计算出 hash 值，另外会计算出 hash 值的高八位和低八位。

低八位会作为 bucket index，作用是用于找到 key 所在的 bucket。而高八位会存储在 bmap tophash 中

主要作用是：在上述步骤七中进行迭代快速定位。这样子可以提高性能，而不是一开始就直接用 key 进行一致性对比

图示

总结

我们介绍了 map 类型的以下知识点：

从阅读源码中，得知 Go 本身对于一些不同大小、不同类型的属性，包括哈希方法都有编写特定方法去运行。

总的来说，这块的设计隐含较多的思路，有不少点值得细细品尝 ：）

你觉得 Go map 设计的怎么样呢？

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8