golang源码分析：map

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的结构

// 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 创建

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

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做了优化，下面时一些实现方法：

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对应位置的状态。

emptyRest      = 0 
emptyOne       = 1 
evacuatedX     = 2 
evacuatedY     = 3
evacuatedEmpty = 4
minTopHash     = 5 

当tophash[i] < 5时，表示存的是状态； 当tophash[i] >= 5时，表示存的是哈希值；

那么问题来了，如果key的哈希值高8位小于minTopHash时，这时候怎么区分是存的状态还是哈希值？

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，这两个就是用来标记老桶数据迁移状态的。