map 是由 key-value 对组成的；key 只会出现一次.主要的数据结构有两种：哈希查找表（Hash table）、搜索树（Search tree）。哈希查找表一般会存在“碰撞”的问题，就是说不同的 key 被哈希到了同一个 bucket。一般有两种应对方法：链表法和开放地址法。搜索树法一般采用自平衡搜索树，包括：AVL 树，红黑树。
Go 语言采用的是哈希查找表，并且使用链表解决哈希冲突。它是一个无序的key/value对的集合，其中，所有的key都是不同的。然后通过给定的key可以在常数时间复杂度内检索、更新或删除对应的value 在map中的元素不是一个变量，因此不能对map的元素进行取址操作。因为map可能随着元素数量的增加而重新分配内存更大的内存空间，从而导致之前的地址失效,源码位置：runtime/map.go
map实现的两个关键数据结构
1，hmap 定义了map的结构
2，bmap 定义了hmap.buckets中每个bucket的结构
代码语言：javascript复制// map 数据结构
type hmap struct {
count int // 元素的个数, len() 的值
flags uint8
B uint8 // bucket个数为：2^B；可以保存的元素个数：填充因子(默认6.5) * 2^B
noverflow uint16 // 溢出桶数量
hash0 uint32 // 哈希因子
buckets unsafe.Pointer // Buckets数组，大小为 2^B
oldbuckets unsafe.Pointer // 前面的Buckets，在增长时非nil
nevacuate uintptr // 迁移状态，进度
extra *mapextra // optional fields
}
// bucket 数据结构
type bmap struct {
tophash [bucketCnt]uint8 // bucketCnt 是常量=8，一个bucket最多存储8个key/value对
// 后面紧跟着8个key
// 再后面是8个value
// 最后是overflow的指针
} 比如key的类型为string，value的类型uint8, 在考虑到字节对齐的时候，如果使用k/v的格式存储会浪费内存，使用8个key/8个value的格式会更紧凑。
map 创建
代码语言：javascript复制func makemap_small() *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap // hint类型为int64， 实质还是调用的 makemap当创建map时不指定hint大小，如下面所示的m1。那么调用makemap_small来进行创建 当指定了hint(代表初始化时可以保存的元素的个数)的大小的时候，若hint<=8, 使用makemap_small进行创建map，否则使用makemap创建map
代码语言：javascript复制m1 := make(map[string]string)
m2 := make(map[string]string, hint)不提供 hint 的时候，编译器始终会调用 makemap_small 来初始化。
mapassign的处理步骤如下：
1，若h为nil则panic
2，若有其他协程在写入map，则panic相关错误
3，对key进行hash 设置flags为Writing 若h.buckets为nil，则重新分配 进入again处理
4，根据hash获取对应的bucket 若h在扩容，则进行扩容工作 获取bucket对应的*bmap b及hash的高位top 进入bucketloop 遍历bucket 若b的当前topHash不为top
（1）若当前tophash的状态为empty且inserti为nil，则当前tophash的地址赋值给inserti，并获取key及element的地址
（2）若topHash的状态为emptyReset则跳出bucketloop
（3）继续遍历bucket 若b的当前topHash不为top，说明已找到匹配的hash。获取key确认与存入的key是否一致（是否hash冲突），不一致则继续遍历bucket。一致，则确实是否更新，需要更新，则更新对应的key。根据key的地址获取element的地址，跳转done 获取b的overflow buckets，若为nil，则跳出bucketloop;否则将overflow赋值给b，继续bucketloop 如果map没在扩容，新增数据后已超过负载因子或拥有太多的overflow buckets，则进行扩容处理；扩容后进入again 如果inseti为nil，说明所有的buckets已经满了，创建新的overflow，存入 如果key类型t并非指针类型，则获取其指针 如果存储的值类型非指针，获取其指针 将key移动至insertK 更新inserti指向的值为top 进入done 如果有其它goroutine在写入，则panic 如果存储的类型为值类型，则获取其指向的值地址 返回elem
简单总结，存入数据需要经过以下几步：
1，计算hash 根据hash低位从buckets中确认存入bucket的位置
2，根据hash高位确认bucket内的位置 确认key是否存在，若存在则获取数据存入地址
3，否则获取overflow buckets，继续步骤1
4，若需要扩容，则进行扩容，扩容后，继续步骤1
5，如果buckets及overflow buckets均已满，则新建overflow bucket，获取key、elem的地址 存入数据 正常存入值的顺序：buckets overflow buckets 扩容后存入buckets/overflow buckets或者创建overflow buckets后存入，赋值的实现，golang 为了对不同类型k做了优化，下面时一些实现方法：
代码语言：javascript复制func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}
func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {}
func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {}
func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer{}
func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {}tophash
tophash是一个长度为8的数组，它不仅仅用来存放key的哈希高8位，在不同场景下它还可以标记迁移状态，bucket是否为空等。弄懂tophash对我们深入了解map实现非常重要。
当tophash对应的K/V被使用时，存的是key的哈希值的高8位；当tophash对应的K/V未被使用时，存的是K/V对应位置的状态。
代码语言：javascript复制emptyRest = 0
emptyOne = 1
evacuatedX = 2
evacuatedY = 3
evacuatedEmpty = 4
minTopHash = 5 当tophash[i] < 5时，表示存的是状态； 当tophash[i] >= 5时，表示存的是哈希值；
那么问题来了，如果key的哈希值高8位小于minTopHash时，这时候怎么区分是存的状态还是哈希值？
代码语言：javascript复制func tophash(hash uintptr) uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
top = minTopHash
}
return top
}当计算的哈希值小于minTopHash时，会直接在原有哈希值基础上加上minTopHash，确保哈希值一定大于minTopHash。
emptyRest
这个值有两层意思：一是表示该tophash对应的K/V位置是可用的；二是表示该位置后面的K/V位置都是可用的。
赋值：
初始化的时，tophash会被置为emptyRest。
删除map元素时，会判断是否需要把删除key对应的tophash置为emptyRest。
作用：
判断bucket是否为空
当tophash[0]==emptyRest表示整个bucket都是空的，这就是源码里面判断bucket是否为空的方法。
查找时快速判断后面位置是否还需遍历
如在查找时，在一个bucket中，找到tophash[2]位置，发现值为emptyRest，就可以判断该bucket没有该元素，继续查找下一个bucket。
emptyOne
仅表示该tophash对应的K/V位置是可用的，其后面的是否可用不知道。
赋值：
删除map元素时，会把key对应的tophash先置为emptyOne，再继续判断是否需要置为emptyRest。
evacuatedX && evacuatedY
这两个状态与扩容有关，记录元素被迁移到了新桶的部位–X或Y。如果是等位迁移，旧桶的元素必然被迁移到X部；如果是扩容迁移，旧桶元素可能迁移到X部，也可能迁移到Y部。当迁移到X部时，旧桶tophash置为evacuatedX；当迁移到Y部时，旧桶tophash置为evacuatedY。
举个例子说明：扩容迁移，要把旧桶1的元素迁到新桶，因为新桶长度增长了一倍，因此旧桶1元素可能被迁移到新桶的1或5。当元素迁移到了1时，把旧桶tophash置为evacuatedX；反之，迁移到了5时，tophash置为evacuatedY。要注意置的是旧桶的tophash。
旧桶迁移完就被回收了，为啥还要记录每个元素迁移的位置？
想了解原因，我们必须要考虑一个很复杂的场景：遍历map时，开始扩容。map遍历并不是原子操作，在遍历过程中会有数据插入、删除等，会导致map扩容。因为遍历发生在扩容前，因此一直是遍历老桶。这时有两种情况：老桶数据没有迁移，这时直接从老桶返回K/V就可以了；老桶数据已经迁移，这时就需要重新查找map。那怎么判断老桶数据是否迁移？这时就用到evacuatedX和evacuatedY，这两个就是用来标记老桶数据迁移状态的。
