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 = %vn", 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

结论如下：

• NumGC 是垃圾回收次数；Alloc 是对对象大小，单位是 KB；Sys 是从 OS 获取的内存大小，单位是 KB；
• 第一行，没有进行过 GC，默认真用了 100 KB 的内存；
• map初始化完成之后进行一次 GC，此时内存占了 422 KB；
• 接下来就是执行delete操作，可以看到map已经被清空了，也执行了一次 GC，但是内存没有被释放；
• 最后把map置为空，内存才被释放。

四、优化

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的优化：

• 1、去除无用、重复的存储使用
• 2、尽量少用map或map的value尽量少为指针，太多的指针类型会造成GC扫描时间的增加；
• 3、若是用map用作缓存存储，当每次只更新部分，更新的key若是偏差较大，会有可能造成内存逐渐增长而不释放的问题，可以通过定时拷贝map的方式来解决，数十万的int64内存拷贝<100ms的。^_
• 4、释放map所占的内存 则通过map=nil

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 如何进行删除操作？