一、概述
在golang中map类型是实际开发过程中经常使用到的数据类型，比如在微服务框架中存放[client,service]这样的映射，还有在实现长连接通信[client_id,connection]，再例如rpc框架中[service_id, service_impl]等等。在其实际的定义中：
- 1、底层
map实际上是一个hashtable，存放的数据是被放置到一个数组buckets.每个bucket最多能够存放8个key/value对。而对应的数据则根据其hash(key)的bits低阶位来选择对应的bucket，而对应的高阶位则用来区分在同一个bucket中不同的key-value内容。一旦当前的bucket里面的键值对个数超过8个，则会通过链表的方式拓展其他的bucket。 - 2、扩容
当hashtable增长需要扩容时，则通过分配一个容量是当数组buckets两倍的新数组来存放键值对，并将旧的buckets中的key-value逐步copy到新的buckets中。需要注意一点：当map进行扩容时其对应的iterator遍历旧的table，同时也会检查新的table，防止对应的bucket移到新的table中。 - 3、查询
可以通过Map iterator遍历buckets数组，按照遍历的顺序返回keys(当前bucket--->chain序号[当存放键值对>8个时会以链表的存放到扩展的bucket]--->bucket索引)，在实现map iterator为了保证其iterator语义，并不会在bucket中移动keys，一旦这样做了则会导致keys会被获取到0次或2次。 - 4、负载系数
在实际的应用我们会面临一个问题：当table出现太多overflow情况就需要扩展更多的bucket来支撑，反之，若是太小的话又会造成空间的浪费。
接下来我们先通过源码了解下map的实现。
二、源码
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不仅包含一个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
结论如下：
- 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，所以对迭代器是没有影响的，是安全的。
