Golang Map实现原理

一、map的操作

声明 map的零值为 nil 。nil 映射既没有键，也不能添加键。

var m map[string]int

初始化

//运行时初始化
m = make(map[string]int)

// 字面量初始化
m1 := map[string]string{ 
   "key":"2",
}

增删改查

m[key] = elem //Insert or update an element in map m

elem = m[key]  //当从映射中读取某个不存在的键时，结果是映射的元素类型的零值。
elem, ok = m[key] 

delete(m, key) //内置函数，删除容器中的元素

二、map的实现原理

2.1 资料

对照看下这两篇文章，带着问题看下源码细节，再回味一番就清楚了，豁然开朗的赶脚。

2.2 实现map的关键要素

哈希函数

让哈希函数的结果能够尽可能的均匀分布，然后通过工程上的手段解决哈希碰撞的问题。
Golang中每个类型的哈希函数在程序启动后是确定的，在类型的信息中。

哈希冲突

线性探测法：
- 数组实现
- 当前哈希表写入新的数据时发生了冲突，就会将键值对写入到下一个不为空的位置；
- 查找对应key会继续查找后面的元素，直到内存为空或者找到目标元素；
拉链法：
- 数组+链表/红黑树；
- 自动扩容；

2.3 map的内部实现

1. 数据结构

type hmap struct {
        count     int   
        flags     uint8   //状态标示：iterator  = 1，oldIterator = 2，hashWriting = 4，sameSizeGrow = 8；
        B         uint8    //桶的个数=2^B
        noverflow uint16 //溢出桶的个数，B<16时为精确值，否则为近似值；
        hash0     uint32 

        buckets    unsafe.Pointer 
        oldbuckets unsafe.Pointer // 扩容时保存老的桶；
        nevacuate  uintptr //重新分配的桶个数；

        extra *mapextra 
}

type mapextra struct {
    overflow    *[]*bmap //没有指针时，溢出桶挂在这；
    oldoverflow *[]*bmap
    nextOverflow *bmap // map初始化时，预分配了一些溢出桶；
}

type bmap struct {
    topbits  [8]uint8   //每个key哈希值的高8位，加速访问；
    keys     [8]keytype //先key后value，节省内存；
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

image

2. 初始化 runtime.makemap

新建hmap;
根据传入的map初始化数量计算出桶的大小；
使用 runtime.makeBucketArray 创建用于保存桶的数组。桶少数据少时只创建桶，桶多数据量大时创建溢出桶。正常情况下，正常桶跟溢出桶在内存空间连续；

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b)
    nbuckets := base
    if b >= 4 {
        nbuckets += bucketShift(b - 4)
        sz := t.bucket.size * nbuckets
        up := roundupsize(sz)
        if up != sz {
            nbuckets = up / t.bucket.size
        }
    }

    buckets = newarray(t.bucket, int(nbuckets))
    if base != nbuckets {
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
        last.setoverflow(t, (*bmap)(buckets))
    }
    return buckets, nextOverflow
}

注意代码：

预分配的溢出桶在nextOverflow中，extra中overflow存的是真正有使用的溢出桶；
为了跟踪预分配的溢出桶，nextOverflow中每个桶的overflow设为nil，可以直接移动指针。最后一个设为not nil，表示没有桶可以用了；

3. 读取流程

runtime.mapaccess1

检查并发写；
key的哈希值低B位拿到桶编号b；key的哈希值高8位拿到tophash；
- 正在扩容，计算oldB，如果oldB没有分配完成，b=oldB;
遍历桶中tophash，相等则判断key，也会遍历溢出桶；
- b.tophash[i] == emptyRest 后边都是空值，已经结束，返回零值；
- 找到，返回value；
- 找不到返回零值；

Range
随机选一个桶，然后顺序遍历其他桶。引入随机顺序，说明golang中的map遍历并不可靠。

4. 写入流程 runtime.mapassign

检查并发写；
增加写标记h.flags ^= hashWriting；
计算bucket编号b；
- 正在扩容，growWork重新分配对应的bucket，分配完再多分配一个桶；（保证写入的桶已经分配了数据）
- 计算tophash值；
bucketloop找位置：
- 找到->step6;
- 没有找到，没有位置需要增加cell或者溢出桶；->step5
- 没有找到，有位置塞到末尾；->step5
增加元素，首先扩容检查；
- 需要扩容，hashGrow只是创建没有分配数据，重新回到step3；
- 不需要扩容，增加元素或者增加溢出桶newoverflow（先尝试在nextoverflow分配，判断加入overflow数组）；
检查并发写，释放写标记；

5. 删除流程 runtime.mapdelete

检查并发写，设置写标记h.flags ^= hashWriting；
计算bucket编号b；
- 正在扩容，growWork重新分配对应的bucket，分配完再多分配一个桶；（保证写入的桶已经分配了数据）
- 计算tophash值；
遍历正常桶溢出桶search找位置：
- 已经到结尾，结束；
- 没找到，结束；
- 找到，b.tophash[i] = emptyOne；假如该元素在结尾，改为一串的emptyRest状态，并且传到上一个桶；注意桶的数目没有变，即使桶里边都是emptyRest状态。
检查并发写，释放写标记；

6. 扩容流程

6.1 扩容检查：

装载因子已经超过 6.5；overLoadFactor
哈希使用了太多溢出桶；tooManyOverflowBuckets (插入删除，因为删除没有移动元素，除了在末尾之外，新增元素会跳过被删的空元素)

6.2 扩容入口： runtime.hashGrow

创建新的正常桶跟溢出桶，并把原来的正常桶挂到oldbuckets上，原来的溢出桶挂在oldoverflow；此时nevacuate跟noverflow都是0；
the actual copying of the hash table data is done incrementally by growWork() and evacuate().

6.3 数据再分配： runtime.growWork

判断一个桶有没有重新分配完成

func evacuated(b *bmap) bool {
    h := b.tophash[0]
    return h > emptyOne && h < minTopHash
  }

扩容

等量扩容：初始化x一个目的地数组结构；成倍扩容：初始化x+y两个目的地数组结构；
判断分到哪个新桶。假如目标桶已经满了，创建溢出桶；
判断更新nevacuate，假如nevacuate=旧桶数目，结束扩容；

  if h.nevacuate == newbit { // newbit == # of oldbuckets
      // Growing is all done. Free old main bucket array.
      h.oldbuckets = nil
      // Can discard old overflow buckets as well.
      // If they are still referenced by an iterator,
      // then the iterator holds a pointers to the slice.
      if h.extra != nil {
          h.extra.oldoverflow = nil
      }
      h.flags &^= sameSizeGrow
  }

读取会读旧桶、写入跟删除会把旧桶重新分配到新桶；

2.4 总结

Golang使用tophash加速访问；
Golang使用溢出桶延缓扩容；
哈希在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，整个扩容过程并不是原子的，而是通过 runtime.growWork 增量触发的，在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流；除了这种正常的扩容之外，为了解决大量写入、删除造成的内存泄漏问题，哈希引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会对哈希进行『内存整理』减少对空间的占用。