Golang Map实现原理

目录

一、map的操作

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

   var m map[string]int

2. 初始化

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

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

3. 增删改查

   m[key] = elem //Insert or update an element in map m
   
   elem = m[key]  //当从映射中读取某个不存在的键时，结果是映射的元素类型的零值。
   elem, ok = m[key] 
   
   delete(m, key) //内置函数，删除容器中的元素
   

二、map的实现原理

2.1 资料

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

1. 理解 Golang 哈希表 Map 的原理
2. 深度解密Go语言之map Go夜读版本
3. 源码 go/src/runtime/map.go

2.2 实现map的关键要素

哈希函数

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

哈希冲突

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

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 image

2. 初始化 ​runtime.makemap​

1. 新建hmap;
2. 根据传入的map初始化数量计算出桶的大小；
3. 使用 ​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
}

注意代码：

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

3. 读取流程

​runtime.mapaccess1​

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

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

4. 写入流程 ​runtime.mapassign​

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

5. 删除流程 ​runtime.mapdelete​

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

6. 扩容流程

6.1 扩容检查：

1. 装载因子已经超过 6.5；overLoadFactor
2. 哈希使用了太多溢出桶；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
    }
  

• 扩容
  1. 等量扩容：初始化x一个目的地数组结构；成倍扩容：初始化x+y两个目的地数组结构；
  2. 判断分到哪个新桶。假如目标桶已经满了，创建溢出桶；
  3. 判断更新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 总结

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