Skip to content

map.md

Latest commit

 

History

History
228 lines (196 loc) · 16.4 KB

map.md

File metadata and controls

228 lines (196 loc) · 16.4 KB

本章知识点

  • go version: go version go1.10.1 darwin/amd64
  • map 基本结构
  • map创建、读取
  • map 删除及内存释放
  • sync.Map并发安全
  • 常见问题

一、map基本结构

源码地址： go1.10/src/runtime/hashmap.go

map的底层结构是hmap（即hashmap的缩写），核心元素是一个由若干个桶（bucket，结构为bmap）组成的数组，每个bucket可以存放若干元素（通常是8个），key通过哈希算法被归入不同的bucket中。当超过8个元素需要存入某个bucket时，hmap会使用extra中的overflow来拓展该bucket。下面是hmap的结构体。

type hmap struct {
	count     int // # 元素个数
	flags     uint8
	B         uint8  // 说明包含2^B个bucket
	noverflow uint16 // 溢出的bucket的个数
	hash0     uint32 // hash种子

	buckets    unsafe.Pointer // buckets的数组指针
	oldbuckets unsafe.Pointer // 结构扩容的时候用于复制的buckets数组
	nevacuate  uintptr        // 搬迁进度（已经搬迁的buckets数量）

	extra *mapextra
}

在extra中不仅有overflow，还有oldoverflow（用于扩容）和nextoverflow（prealloc的地址）。

type mapextra struct {
     overflow    *[]*bmap
     oldoverflow *[]*bmap
     nextOverflow *bmap
}
type bmap struct {
    tophash [bucketCnt]uint8
}
  • tophash用于记录8个key哈希值的高8位，这样在寻找对应key的时候可以更快，不必每次都对key做全等判断。
  • 注意后面几行注释，hmap并非只有一个tophash，而是后面紧跟8组kv对和一个overflow的指针，这样才能使overflow成为一个链表的结构。但是这两个结构体并不是显示定义的，而是直接通过指针运算进行访问的。
  • kv的存储形式为”key0key1key2key3…key7val1val2val3…val7″，这样做的好处是：在key和value的长度不同的时候，节省padding空间。如上面的例子，在map[int64]int8中，4个相邻的int8可以存储在同一个内存单元中。如果使用kv交错存储的话，每个int8都会被padding占用单独的内存单元（为了提高寻址速度）。

二、map 创建、读取

创建

创建其实就是完成内存的申请，以及一些初始值的设定。那么这里假设创建的空间较大，也就是说将 overflow 区域的初始化，也一并放在这里记录。

// hint 代表的 capacity
func makemap(t *maptype, hint int64) *hmap  {
    // 条件检查
    t.keysize = sys.PtrSize = t.key.size
    t.valuesize = sys.PtrSize = t.elem.size

    // 通过 hint 确定 hmap 中最小的 B 应该是多大。
    // B 与后面的内存空间申请，以及未来可能的扩容都有关。B 是一个基数。
    // overLoadFactor 考虑了装载因子。golang 将其初始设置为 0.65
    B := uint8(0)
    for ; overLoadFactor(hint, B); B++ {}

    // golang 是 lazy 形式申请内存
        if B != 0 {
        var nextOverflow *bmap
        buckets, nextOverflow = makeBucketArray(t, B)
        if nextOverflow != nil {
            extra = new(mapextra)
            extra.nextOverflow = nextOverflow
        }
    }
    // 后面就是将内存地址关联到 hmap 结构，并返回实例
    h.count = 0  // 记录存储的 k/v pari 数量。扩容时候会用到
    h.B = B  // 记录基数
    h.flags = 0 // 与状态有关。包含并发控制，以及扩容。

    ...
}
// makeBucketArray 会根据情况判断是否要申请 nextOverflow 。
func makeBucketArray(t *maptype, b uint8) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := uintptr(1 << b)
    nbuckets := base
    if b >= 4 {
        // 向上调整 nbuckets
    }

    // 注意，是按照 nbuckets 申请内存的
    buckets = newarray(t.bucket, int(nbuckets))

    // 处理 overflow 情况，
    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
}

读取

读取有 mapaccess1 和 mapaccess2 两个，前者返回指针，后者返回指针和一个 bool，用于判断 key 是否存在。这里只说 mapaccess1。 指针是 value field中存储的地址

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 如果为空或者长度为 0，那么就返回一个 0 值

// 如果正在被写入，那么抛出异常


// 获取 key 的 hash 值


// 确认该 key 所在的 bucket 位置 （可能是在 buckets 也有可能在 oldbuckets 中）
// 使用模计算，先计算出如果在 buckets 中，则是在哪个 bucket
// 检测 oldbucket 是否为空，如果不为空，则用上面同样的方式得出在 oldbuckets 的位置
// 并检测该 bucket 是否已经被 evacuate ，如果已经被 evacuate 则使用 buckets， 否则使用 oldbuckets 中的位置
m := uintptr(1)<<h.B - 1
b := (bmap)(add(h.buckets, (hash&m)uintptr(t.bucketsize)))  // buckets 结构
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
}
}


// 得到 bucket 以后，通过 tophash 来再次定位，如果定位不到，则递归该 bucket 的 overflow 域，循环查找。
// 以上步骤有两个结果。
// 1 遍历到最后，都没有找到命中的 tophash ，此时则返回一个零值。
// 2 命中 tophash 则进行 key 比对，相同则返回对应的 val 位置，不同则通过 overflow 继续获

三、map 删除及内存分配

删除

mapdelete 是负责删除的的主体函数

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			b.tophash[i] = empty
			h.count--
		}
	}
}

外层的循环就是在遍历整个 map，删除的核心就在那个empty。它修改了当前 key 的标记，而不是直接删除了内存里面的数据。

empty = 0 // cell is empty

内存释放

m = nil

这之后坐等垃圾回收器回收就好了。

如果你用 map 做缓存，而每次更新只是部分更新，更新的 key 如果偏差比较大，有可能会有内存逐渐增长而不释放的问题。要注意。

四、sync.Map使用

1. sync.Map提供的方法

  • 存储数据,存入key以及value可以为任意类型.
func (m *Map) Store(key, value interface{})
  • 删除对应key
func (m *Map) Delete(key interface{})
  • 读取对应key的值,ok表示是否在map中查询到key
func (m *Map) Load(key interface{}) (value interface{}, ok bool)
  • 针对某个key的存在读取不存在就存储,loaded为true表示存在值,false表示不存在值.
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)
  • 表示对所有key进行遍历,并将遍历出的key,value传入回调函数进行函数调用,回调函数返回false时遍历结束,否则遍历完所有key.
func (m *Map) Range(f func(key, value interface{}) bool)

2. 原理

通过引入两个map,将读写分离到不同的map,其中read map只提供读,而dirty map则负责写.
这样read map就可以在不加锁的情况下进行并发读取,当read map中没有读取到值时,再加锁进行后续读取,并累加未命中数,当未命中数到达一定数量后,将dirty map上升为read map.

另外，虽然引入了两个map，但是底层数据存储的是指针，指向的是同一份值．

具体流程：
如插入key 1,2,3时均插入了dirty map中，此时read map没有key值，读取时从dirty map中读取，并记录miss数

图片描述

当miss数大于等于dirty map的长度时，将dirty map直接升级为read map,这里直接 对dirty map进行地址拷贝．

图片描述

当有新的key 4插入时，将read map中的key值拷贝到dirty map中，这样dirty map就含有所有的值，下次升级为read map时直接进行地址拷贝．

3. 局限性

从以上的源码可知,sync.map并不适合同时存在大量读写的场景,大量的写会导致read map读取不到数据从而加锁进行进一步读取,同时dirty map不断升级为read map.
从而导致整体性能较低,特别是针对cache场景.针对append-only以及大量读,少量写场景使用sync.map则相对比较合适.

对于map,还有一种基于hash的实现思路,具体就是对map加读写锁,但是分配n个map,根据对key做hash运算确定是分配到哪个map中.
这样锁的消耗就降到了1/n(理论值).具体实现可见:https://github.com/orcaman/co…

相比之下, 基于hash的方式更容易理解,整体性能较稳定. sync.map在某些场景性能可能差一些,但某些场景却能取得更好的效果.
所以还是要根据具体的业务场景进行取舍.

五、使用中常见问题

Q：删除掉map中的元素是否会释放内存？

A：不会，删除操作仅仅将对应的tophash[i]设置为empty，并非释放内存。若要释放内存只能等待指针无引用后(即 m=nil 时)被系统gc

Q：如何并发地使用map？

A：map不是goroutine安全的，所以在有多个gorountine对map进行写操作是会panic。多gorountine读写map是应加锁（RWMutex），或使用sync.Map（1.9新增)。

Q：map的iterator是否安全？

A：map的delete并非真的delete，所以对迭代器是没有影响的，是安全的。

reference:
github
juejin
cyeam
segmentfault