Golang

golang源码之map

2019-03-19  本文已影响1人  神奇的考拉

一、概述

在golang中map类型是实际开发过程中经常使用到的数据类型，比如在微服务框架中存放[client,service]这样的映射，还有在实现长连接通信[client_id,connection]，再例如rpc框架中[service_id, service_impl]等等。在其实际的定义中：

二、源码

type hmap struct {
    count     int // 元素格式
    flags     uint8
    B      uint8  // 包含的buckets数loadFactor * 2^B items)
    noverflow uint16 // overflow时拓展的buckets数
    hash0     uint32 // hash种子

    buckets    unsafe.Pointer // buckets数组指针
    oldbuckets unsafe.Pointer // 扩容时用于复制的数组
    nevacuate  uintptr   // 扩容时copy到新table的buckets数

    extra *mapextra // 可选(见下文)
}

首先呢，map是一个由若干个bucket(对应bmap)组成的数组，并且每个bucket存放不超过8个键值对key-value的元素，则由key通过哈希算法将其归入不同的bucket中。一旦某个bucket中元素超过8个元素就会触发overflow，hmap则通过extra字段对应的mapextra的overflow字段来拓展该bucket。

bmap结构:bmap就是前面在hmap中提到的bucket

type bmap struct {  
    tophash [bucketCnt]uint8
}

从源码可以了解到tophash包含了在一个bucket中每个key对应的hash值的高阶位部分，一旦tophash[0] < minTopHash则tophash[0]就变成evacuation状态。
在这里tophash通过记录当前bucket中8个key的hash值的高8位，在每次查找对应的key时不需要做全等判断，提高查找速度。
在每个bucket(bmap)中存放的数据格式：key1key2...keynval1val2...valn，将所有的keys放置到一起，再将所有的values放置到一起，相对于以交替方式存放key、value：key1/val1/key2/val2/.../.../keyn/valn/要复杂的多；不过通过这种方式能够在key和value长度不同时，能够节省padding的空间，比如定义map[int64]int8，相邻的4个int8能够存放到一个内存单元，若是使用key、value交替则会导致每个int8会被padding占用单独的内存单元.


hmap结构

整个hmap不仅包含一个tophash，还包括8个键值对和一个overflow指针，这样使得overflow以链表的结构出现，一般都是通过指针来访问键值对和overflow的内容。

mapextra结构源码：主要用于当bukcets元素超过8个键值对时，通过链表的方式来解决对应的内容放置。其包含了map上不存在的fields。

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

    nextOverflow *bmap//指向下一个overflow的bucket
}

详见：runtime/map.go源码

三、实例

测试代码如下：
var intMap map[int]int
var cnt = 8192

func main() {
    printMemStats() //打印出memory情况

    initMap()  // 创建map
    runtime.GC()  // 强制执行GC
    printMemStats() // 在强制GC之后 再打印memory情况

    log.Println(len(intMap))  // 查看map的元素个数
    for i := 0; i < cnt; i++ {
        delete(intMap, i) // 执行delete的操作
    }
    log.Println(len(intMap)) // 验证执行delete操作对实际map的元素个数影响

    runtime.GC()  // 强制执行GC
    printMemStats()

    intMap = nil  // 将map置为nil 释放其占用的内存空间
    runtime.GC()
    printMemStats()
}

func initMap() {
    intMap = make(map[int]int, cnt)

    for i := 0; i < cnt; i++ {
        intMap[i] = i
    }
}

func printMemStats() {
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    log.Printf("Alloc = %v TotalAlloc = %v Sys = %v NumGC = %v\n", m.Alloc/1024, m.TotalAlloc/1024, m.Sys/1024, m.NumGC)
}
输出结果
2019/03/19 10:17:17 Alloc = 128 TotalAlloc = 128 Sys = 4868 NumGC = 0
2019/03/19 10:17:17 Alloc = 449 TotalAlloc = 500 Sys = 6338 NumGC = 1
2019/03/19 10:17:17 8192
2019/03/19 10:17:17 0
2019/03/19 10:17:17 Alloc = 451 TotalAlloc = 503 Sys = 6402 NumGC = 2
2019/03/19 10:17:17 Alloc = 138 TotalAlloc = 504 Sys = 6402 NumGC = 3

结论如下：

四、优化

1、删除

delete对应的源码

从源码中可以看到：外层的循环就是在遍历整个 map，删除的核心就在那个empty。它修改了当前 key 的标记，而不是直接删除了内存里面的数据【只是标记为empty，并没有真正删除其对应的数据】

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做缓存，而每次更新只是部分更新，更新的 key 如果偏差比较大，有可能会有内存逐渐增长而不释放的问题。
不过很多人可能很奇怪为嘛要以这种方式来设计map的删除操作呢：在遍历map的时候删除里面的元素，页可以删除没有遍历到的元素，那么为了保证删除了之后遍历不发生异常，是不能将对应位置空间释放掉会触发panic。那么这算不算内存泄漏呢？
若是后续继续对当前的map进行write操作，写入的值刚好命中前面已被“删除”的bucket，则会将当面bucket的empty内容进行覆盖。在这一点上是不能算内存泄漏的。
在实际一些高性能、高并发的场景下，使用map来用来内存存储可能会带来一些挑战，我们可能使用如下的方式来进行map的优化：

2、查询

访问map中key源码
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
        ...省略部分源码
    // do some race detect things
    // do some memory sanitizer thins
 
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 {  // 检测是否并发写，map不是gorountine安全的
        throw("concurrent map read and map write")
    }
    alg := t.key.alg  // 哈希算法 alg -> algorithm
    hash := alg.hash(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
        // 如果老的bucket没有被移动完，那么去老的bucket中寻找
    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
        }
    }
        // 寻找过程：不断比对tophash和key
    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])
}

常见问题

Q：删除掉map中的元素是否会释放内存？
A：不会，删除操作仅仅将对应的tophash[i]设置为empty，并非释放内存。若要释放内存只能等待指针无引用后被系统gc

Q：如何并发地使用map？
A：map不是goroutine安全的，所以在有多个gorountine对map进行写操作是会panic。多gorountine读写map是应加锁（RWMutex），或使用sync.Map（不过不太推荐使用）

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

参考文章

golang map源码详解
Golang map 如何进行删除操作？

上一篇下一篇

猜你喜欢

热点阅读