一、什么是Map以及Go语言的Map

1.1 Map的定义

Map是一种由key-value键值对组成的集合，且key只出现一次。也被称为字典，关系数组等。
Map主要有两种数据结构来实现：哈希查找表（Hash table）、搜索树（Search tree）。

1.2 哈希查找表

哈希查找表是通过哈希函数将key分配到不同的bucket，访问时间复杂度最好为O(1)，最差为O(n)。

哈希查找表会存在哈希碰撞问题，不同的key通过哈希函数计算出来的哈希值一样，使得这些key分配到了同一个bucket（简单理解，bucket就是不同的底层数组的索引）。一般处理哈希碰撞问题有两种方法：链表法和开放地址法。
链表法：将出现哈希碰撞而分配到同一个bucket的key，通过链表的方式存储。
开放地址法：出现哈希碰撞时，通过一定的规律，在该bucket底层数组的后面选择空闲位置，用来放置碰撞的那些key。

1.3 搜索树

搜索树一般使用的是自平衡搜索树：AVL树、红黑树。

自平衡搜索树在遍历时会返回从小到大的有序的key，而哈希查找表在遍历时则是无序的。不同的语言在实现Map时可能会采用不同的数据结构去实现，Go语言在实现Map时采用的是哈希查找表的方式。

Map实现了对数据的增删改查功能，且效率相当高效。
将Map和切片Slice对比来说：

切片Slice是对一块连续内存上的数据的统一管理。
Map则是对不连续内存上数据的统一管理，不同的内存在Map结构中存在关联性。
二、Map的创建
创建Map通过var声明的方式或者make()函数的方式创建。 ```go // nil map 需要使用make()初始化后才能添加值 var testMap map[string]string

// 初始化并赋值 map var testMap1 = map[string]string{ “a”: “张三”, “b”: “李四”, “c”: “王五”, }

// 初始化并分配内存 testMap2 := make(map[string]string, 10)

那么，Map到底是如何创建的呢？以下，我们简单的了解一下Map的创建过程。<br />Map结构在Go语言中定义的结构体是：
```go
// 源码路径：go/1.14.1/libexec/src/runtime/map.go:115
// A header for a Go map.
type hmap struct {
    count     int // map 中元素的个数，len(map) 时直接返回该值
    flags     uint8 // 标记位
    B         uint8  // 计算buckets 数组的长度使用。buckets 的长度是2^B
    noverflow uint16 // 从bucket中溢出的数量。（overflow buckets 存储在extra中）
    hash0     uint32 // hash 因子
    buckets    unsafe.Pointer // 指向 buckets（哈希桶） 数组的指针 大小是 2^B. 如果count==0，可能是nil.
    oldbuckets unsafe.Pointer // 发生扩容时，指向 旧buckets 数组的指针，是 新buckets 的一半，非nil时扩容
    nevacuate  uintptr        // 扩容进度，小于此地址的buckets表示迁移完毕
    extra *mapextra // 扩展字段，可选，在溢出（overflow）或者数据增长是使用
}

在执行创建一个Map结构时，会调用到makemap()函数：

//源码路径：go/1.14.1/libexec/src/runtime/map.go:303
// makemap() 用来执行 make(map[k]v, hint) 的逻辑。
// 如果编译器已经确定 该map或者第一个bucket可以在堆栈上创建， 
// 那么 h和bucket 可能都是非nil，或者 h或bucket 可能有一个是非nil。
// 如果 h != nil, 可以直接在h中创建该map。
// 如果 h.buckets != nil, 则h.buckets 指向的bucket 可以作为第一个 bucket.
func makemap(t *maptype, hint int, h *hmap) *hmap {
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }
    // 初始化 Hmap 结构体
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()
    // 计算hmap结构体中的B的值，通过make()创建时指定的int值
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B
    // 分配内存并初始化哈希表
    // 如果 B == 0,h.buckets将暂时不分配内存
    // 如果hint值太大，则初始化分配的内存可能时间长一些.
    if h.B != 0 {
        // 定义bmap结构体 一个bmap即为一个bucket
        var nextOverflow *bmap
        // 创建buckets和nextOverflow
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            // 指定extra的信息
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }
    // 返回结构体指针
    return h
}
// ********************************************************
// 源码路径： go/1.14.1/libexec/src/runtime/map.go:149
// map 中存储具体元素k-v信息的 bucket 结构体.即hmap.buckets包含的单个bucket
// 每个bucket存储8个键值对
type bmap struct {
    // tophash包含每个key键哈希值的的顶部字节(高八位)，简单来说就是记录该key键在bucket中的存放位置。
    // 如果tophash[0]<minTopHash 则表明tophash[0]处于迁移状态。
    // bucketCnt为8
    tophash [bucketCnt]uint8
    // 接着是8个key键和8个value元素。
    // 虽然k1,k2,k3...k8,v1,v2,v3...v8这种排列比k1,v1,k2,v2...k8,v8结构更加复杂，
    // 但是考虑到内存对齐，前一种方式更加合适。
    // 如 map[int64]int8，其中key是int64占8个字节，value是int8占1个字节，
    // kv长度不同，如果按照k,v交替的方式存放，则内存对齐的缘故，v也需要占用8个字节，
    // 如果k,k,v,v方式存放，则8个value则刚好占用一个key的字节空间。
}
// ********************************************************
// 源码位置：go/1.14.1/libexec/src/runtime/map.go:132
// mapextra 表示map中的extra扩展字段，
type mapextra struct {
    // 如果key和value都不包含指针并且是内联的，那么我们就标记bucket不含指针，这样可以避免gc扫描
    // 但是bmap.overflow是一个指针。
    // 为了确保overflow buckets存活，我们会在hmap.extra.overflow和hmap.extra.oldoverflow中添加所有overflow buckets。
    // overflow和oldoverflow仅仅在key和value都不是指针时使用。
    // overflow包含hmap.buckets中的overflow buckets。
    // oldoverflow包含hmap.oldbuckets中的overflow buckets。
    // 间接允许将指向切片的指针存储在hiter中。
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    // nextOverflow拥有一个指向空闲overflow bucket的指针。（预分配的）
    nextOverflow *bmap
}

通过对以上Map结构体、创建过程的源码的分析，我们可以总结出Map的创建过程：

对 make(map[k]v, hint)中hint的值进行边界检查；
初始化hmap；
计算hash因子；
通过hint计算B的最小值；
分配内存并初始化哈希表，如果B是0则之后再分配内存，否则立刻分配；
返回初始化完成的hmap的指针。

创建流程图为：
Map-第 2 页.jpg
创建完成的Map的结构为，其中bmap0为一个bucket，tophash用于快速判断key是否在该bucket中：

三、Map的查询

Map查询某个key的value值使用两种方式：

value := map[key]，返回value值，如果key不存在，则返回value类型的零值；
value,ok := map[key] ，返回value值和ok值，其中ok是一个布尔值，用来标记key是否存在；value同上返回零值。

Map键值的查询在源码中使用的是mapaccess系列函数。
其中具有代表性的是以下两个：

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {...}

mapaccess1()对应第1种取值方式，返回value的指针地址，若不存在则返回零值指针。

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {...}

mapaccess2()对应第2种取值方式，返回value的指针地址和key是否存在的布尔值。

以mapaccess1()函数为例，分析源码中查询键值信息的步骤：
注：mapaccess2()和mapaccess1()逻辑几乎一样，只是多返回了一个bool值。

// 源码路径：go/1.14.1/libexec/src/runtime/map.go:394
// mapaccess1 返回h[key]的指针地址，永不返回nil，如果key不存在则返回value类型的零值
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapaccess1)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    // 判断h是否是nil，或者h.count是否是0，若是则返回零值
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0])
    }
    // 判断当前h是否并发读写，若是则抛出异常
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 计算key的hash值
    hash := t.hasher(key, uintptr(h.hash0))
    // 计算key所在bucket的序号
    m := bucketMask(h.B)
    // 根据序号找到bucket地址
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // 如果h.oldbuckets有值，即正在发生扩容。
    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
        }
        // 若扩容未迁移完毕，则到旧的buckets中查询
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // 计算key hash的tophash
    top := tophash(hash)
    // 遍历查询key的位置
bucketloop:
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                // 如果本次没匹配到，而且其他cell又全是空，则直接break
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            // 计算key的位置
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // 查询到key的位置，则返回value的指针地址
            if t.key.equal(key, k) {
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return e
            }
        }
    }
    // 没查找到，则返回value类型零值
    return unsafe.Pointer(&zeroVal[0])
}

根据源码信息，可以得出value := map[key]的执行流程为：

判断h是否是nil，或者h.count是否是0，若是则返回零值；
判断当前h是否并发读写，若是则抛出异常；
计算key的hash值；
计算key所在bucket的地址；
如果h.oldbuckets有值，即正在发生扩容。若扩容未迁移完毕，则到旧的buckets中查询；
遍历查询key的位置，查询到key的位置，则返回value的指针地址，若没查到，则返回value类型零值。

图示为：
Map1-第 3 页.jpg
我们通过一张图能很好的理解，key是如何通过hash和tophash找到具体存放位置的：

四、Map的添加、更新

Map的增加和更新的使用方式比较简单，直接通过 map[key] = value 增加和更新键值对信息。

在Map中，对元素的添加和更新是通过mapassign()函数实现的：

// 源码路径： go/1.14.1/libexec/src/runtime/map.go:571
// 与mapaccess类似，但如果key不在map中，则为其分配一个位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // h为nil，抛异常
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    if raceenabled {
        callerpc := getcallerpc()
        pc := funcPC(mapassign)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled {
        msanread(key, t.key.size)
    }
    // h正在并发读写，抛异常
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    // 计算key 的hash
    hash := t.hasher(key, uintptr(h.hash0))
    // 计算hash值后，设置hashWriting。因为t.hasher可能抛异常，在这种情况下，我们实际上还没有写
    h.flags ^= hashWriting
    // 如果buckets为nil，则初始化
    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }
again:
    // 获取bucket的序号
    bucket := hash & bucketMask(h.B)
    // 若正在扩容，则继续迁移
    if h.growing() {
        growWork(t, h, bucket)
    }
    // 计算bucket中bmap的指针地址
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    // 计算key hash的tophash
    top := tophash(hash)
    var inserti *uint8
    var insertk unsafe.Pointer
    var elem unsafe.Pointer
    // 遍历判断key的tophash和buckets中的是否一致
bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            // 如果tophash不一致，则寻找空闲位置，并记录该位置，此时记录的是第一个空闲可插入数据的位置
            if b.tophash[i] != top {
                if isEmpty(b.tophash[i]) && inserti == nil {
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                }
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // 判断key与当前遍历到的k是否相等，不相等则跳过
            if !t.key.equal(key, k) {
                continue
            }
            // 如果key存在，则更新
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            // 结束，直接跳到done代码块
            goto done
        }
        // 遍历完毕则结束遍历
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        // 当前遍历到的位置
        b = ovf
    }
    // 没找到则分配新的cell，即bucket的空位置
    // 如果并未扩容 且 达到了最大的负载系数 overLoadFactor 或 太多溢出桶 bucket overflow，则开始进行扩容
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }
    // 此时，没找到空闲的位置，则需要新开辟一块进行键值对的存储
    if inserti == nil {
        // 当前所有的buckets都满了，需要分配一个新的
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }
    // 放置k-v
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
    h.count++
done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    // 返回value的指针地址
    return elem
}

通过对源码的分析我们可以梳理出Map增加和修改元素的过程为：

判断h是否为nil；
判断h是否正在并发读写；
计算key 的hash 并设置hashWriting；
如果buckets为nil，则初始化；
获取key的bucket的序号；
若map正在扩容迁移，则继续还行迁移；
找到bucket中bmap的地址，并计算key的tophash；
进入遍历：遍历判断key的tophash和buckets中的是否一致；
遍历中：如果tophash不一致，则寻找空闲位置，并记录该位置，此时记录的是第一个空闲可插入数据的位置；
遍历中：如果key存在，则更新，结束遍历。然后返回value的地址；
遍历中：如果key没找到，则结束遍历，往下执行；
没找到key则分配新的cell，即bucket的空位置；
如果并未扩容且达到了最大的负载系数 overLoadFactor 或太多溢出桶 bucket overflow，则开始进行扩容；
如果没找到空闲的位置，则新开辟一块内存进行键值对的存储，即overflow bucket；
返回value的地址。

整个添加和修改元素的逻辑是比较长的，含有，基本判断，逻辑计算，遍历对比，开辟新空间放置kv等逻辑。
最终的赋值并没有在mapassign()函数中进行，而是最后返回了value的指针。

五、Map的删除

删除Map键值对是通过 delete(map, key) 函数进行。其中map参数表示要删除键值对的Map，key参数表示Map的key键。

Map中的delete()操作是通过源码中的mapdelete()函数完成的。
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer){...}
具体执行逻辑为：

判断h是否为nil，或者h.count是否是0，若是则直接返回；
判断是否有其他协程在写操作，若有，则抛异常；
计算key的hash并找到key所在的bucket序号；
如果正在扩容迁移，则继续迁移；
获取key所在bmap地址，并计算key的tophash；
遍历找寻key的位置。找到后将该位置的k-v清零，将count-1，将bmap原tophash位置标记为Empty。
六、总结
以上我们了解了Go语言Map的结构，Map的创建，Map中元素的查询、添加、修改和删除的实现逻辑。
Map是使用哈希查找表法实现的，并通过链表法解决哈希冲突。
通过key的哈希值将不同的key分配到不同的bucket（哈希桶）中，每个bucket存储8个键值对（8个cell）。
如果一个bucket不够用，元素占满了8个cell，则会分配一个新的overflow bucket（溢出桶），并通过bucket的overflow指针字段关联。
查询、添加、修改、删除操作在底层源码中核心的逻辑在于通过key去获取具体的bucket信息。

最后，我们还需要知道以下关于Map的信息：

Map遍历通过for...range...的方式，并且Map的遍历是无序的；
Map的key非必要不要用float浮点数，以及NaN非数；
Map不是一个线程安全的结构，同时读写一个Map会报错。如有需要可以使用sync.Map包；
创建Map的函数makemap()返回的是一个指针，创建Slice函数makeslice()函数的返回的是一个结构体。所以，当 Map 和 Slice 作为函数参数时，在函数参数内部对 Map 的操作会影响 Map 自身；而对 Slice 却不会（如对Slice进行append()之后，原Slice并不会更改）。

主要原因为：一个是指针（ hmap），一个是结构体（ slice）。Go 语言中的函数传参都是值传递，在函数内部，参数会被 copy 到本地。hmap指针 copy 完之后，仍然指向同一个 map，因此函数内部对 map 的操作会影响实参。而 slice 被 copy 后，会成为一个新的 slice，对它进行的操作不会影响到实参。

参考文档：
深度解密Go语言之map
深入Go的Map使用和实现原理
 字典变量里存的是什么？
Go基础系列：map类型
 Go语言基础之map

面向搜索编程

Go数据类型-Map