当使用make创建一个map时，就是创建一个指向hmap结构体指针的变量。hmap包含若干个bucket，每个bucket都是一个指向bmap结构体对象的指针。每个bucket最多只能放8个键值对，当存入第9个时，则通过overflow指针链接到下一个bucket。
1、map底层结构
它实际是调用runtime.makemap函数，主要工作就是初始化hmap结构体的各个字段，例如初始化buckets。
src/runtime/map.go hmap和bmap结构体：
type hmap struct {
count int
// 代表哈希表中的元素个数，调用len(map)时，返回的就是该字段值。
flags uint8
// 状态标志（是否处于正在写入的状态等）
B uint8
// buckets（桶）的对数
// 如果B=5，则buckets数组的长度 = 2^B=32，意味着有32个桶
noverflow uint16
// 溢出桶的数量
hash0 uint32
// 生成hash的随机数种子
buckets unsafe.Pointer
// 指向buckets数组的指针，数组大小为2^B，如果元素个数为0，它为nil。
oldbuckets unsafe.Pointer
// 如果发生扩容，oldbuckets是指向老的buckets数组的指针，老的buckets数组大小是新的buckets的1/2;非扩容状态下，它为nil。
nevacuate uintptr
// 表示扩容进度，小于此地址的buckets代表已搬迁完成。
extra *mapextra
// 存储溢出桶，这个字段是为了优化GC扫描而设计的，下面详细介绍
}
//每个bucket是一个bmap结构体，bmap 结构体如下
type bmap struct{
tophash [8]uint8
keys [8]keytype
// keytype 由编译器编译时候确定
values [8]elemtype
// elemtype 由编译器编译时候确定
overflow uintptr
// overflow指向下一个bmap，overflow是uintptr而不是*bmap类型，保证bmap完全不含指针，是为了减少gc，溢出桶存储到extra字段中
}
type mapextra struct {
//记录所有使用的溢出桶
overflow *[]*bmap
//用于在扩容阶段存储旧桶用到的溢出桶的地址
oldoverflow *[]*bmap
// 指向下一个空闲溢出桶
nextOverflow *bmap
}
当向map中存储一个kv时，[1]通过k的hash值与buckets长度取余，定位到key在哪一个bucket中，[2]hash值的高8位存储在bucket的tophash[i]中，用来快速判断key是否存在。[3]当一个bucket满时，通过overflow指针链接到下一个bucket。
bucket := hash & (1<<h.B)-1) = hash % (2^h.B)
bmap 结构体字段说明：
- tophash 用于快速查找key是否在该bucket中，在实现过程中会使用key的hash值的高8位作tophash值，存放在bmap tophash字段中。tophash字段不仅存储key哈希值的高8位，还会存储一些状态值，用来表明当前桶单元状态。
- bmap中的key和value是各自放在一起的，如k1/k2/...v1/v2...①，而不是key/value/key/value/...（kv形式）这样的形式，这样做的目的是节省空间。例如map[int64]int8，key是8字节，value是1字节，kv长度不同，如果按照②的kv形式存放，则需要考虑value也对齐占有8个字节，这样就会浪费7个字节的存储空间，所以go采用了第1种方式。
- 每个bucket最多只能放8个键值对，如果有第9个，落入当前的bucket，则需要再创建一个bucket，通过overflow指针连接起来。
2、定位元素大体过程
Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。
- 写保护监测
函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行“写”操作，进而导致程序 panic，这也说明了 map 不是线程安全的。
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
- 计算hash值
hash := t.hasher(key, uintptr(h.hash0))
//key经过哈希函数计算后，得到的哈希值如下（主流64位机下共 64 个 bit 位），不同类型的key会有不同的hash函数
10010111 | 000011110110110010001111001010100010010110010101010 │ 01010
- 找到hash对应的bucket
bucket定位：哈希值的低B个bit 位，用来定位key所存放的bucket。如果当前正在扩容中，并且定位到的旧bucket数据还未完成迁移，则使用旧的bucket（扩容前的bucket）
hash := t.hasher(key, uintptr(h.hash0))
// 桶的个数m-1，即 1<<B-1,B=5时，则有0~31号桶
m := bucketMask(h.B)
// 计算哈希值对应的bucket
// t.bucketsize为一个bmap的大小，通过对哈希值和桶个数取模得到桶编号，通过对桶编号和buckets起始地址进行运算，获取哈希值对应的bucket
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 是否在扩容
if c := h.oldbuckets; c != nil {
// 桶个数已经发生增长一倍，则旧bucket的桶个数为当前桶个数的一半
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
// 计算哈希值对应的旧bucket
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 如果旧bucket的数据没有完成迁移，则使用旧bucket查找
if !evacuated(oldb) {
b = oldb
}
}
- 遍历bucket查找
tophash值定位：哈希值的高8个bit 位，用来快速判断key是否已在当前bucket中（如果不在的话，需要去bucket的overflow中查找）
在 bucket 及bucket的overflow中寻找tophash 值（HOB hash）为 151* 的 槽位，即为key所在位置，找到了空槽位或者 2 号槽位，这样整个查找过程就结束了，其中找到空槽位代表没找到。
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
// 未被使用的槽位，插入
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 找到tophash值对应的的key
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
return e
}
}
}
bucket及tophash查找过程：
- 返回key对应的指针
如果通过上面的步骤找到了key对应的槽位下标 i，我们再详细分析下key/value值是如何获取的：
// keys的偏移量
dataOffset = unsafe.Offsetof(struct{
b bmap
v int64
}{}.v)
// 一个bucket的元素个数
bucketCnt = 8
// key 定位公式
k :=add(unsafe.Pointer(b),dataOffset+i*uintptr(t.keysize))
// value 定位公式
v:= add(unsafe.Pointer(b),dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
bucket 里 keys 的起始地址就是 unsafe.Pointer(b)+dataOffset
第 i 个下标 key 的地址就要在此基础上跨过 i 个 key 的大小；
而我们又知道，value 的地址是在所有 key 之后，因此第 i 个下标 value 的地址还需要加上所有 key 的偏移。
3、需要注意的几点
3.1 Go map遍历为什么是无序的
使用 range 多次遍历 map 时输出的 key 和 value 的顺序可能不同。这是 Go 语言的设计者们有意为之，旨在提示开发者们，Go 底层实现并不保证 map 遍历顺序稳定，不要依赖 range 遍历结果顺序。
主要原因有2点：
- map在遍历时，并不是从固定的0号bucket开始遍历的，每次遍历，都会从一个随机值序号的bucket，再从其中随机的cell开始遍历
- map遍历时，是按序遍历bucket，同时按需遍历bucket中和其overflow bucket中的cell。但是map在扩容后，会发生key的搬迁，这造成原来落在一个bucket中的key，搬迁后，有可能会落到其他bucket中了，从这个角度看，遍历map的结果就不可能是按照原来的顺序了。
因此如果不加入随机数，在不发生扩容情况下，一些不熟悉该原理的开发者会认为map是有序的，一旦依赖这个特性，就会引发bug。所以golang直接通过加随机数（在初始化迭代器时会生成一个随机数，决定从哪一个bucket开始迭代）避免问题的发生。这就是map为什么每次遍历顺序是不一样的原因。
3.2 如何让map有序
把key取出来进行排序，再通过key依次从map中取值。
3.3 map并发读写会产生什么情况
map在默认情况下时不支持并发的，这是由于golang的设计者考虑到使用map的场景都不是并发访问，如果map并发读写会产生什么呢？如果并发时写入，则会产生panic。runtime.map 代码判断：
//赋值时检查是否在写入
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
}
//读取数据时检查是否在写入
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
}
3.4 如何安全使用map
Go map不是线程安全的，在使用过程中如果需要保证线程安全，则需要保持同步。
- 使用sync.Mutex或sync.RWMutex进行加锁
- 使用go官方提供的sync.Map替代map
3.5 map中的key可以取地址吗？
不可以，因为key对应的value的内存地址可能因为扩容而变化，所以不允许取地址。也正因为如此，下面代码是错误的。
type Student struct {
name string
}
func main() {
m := map[string]Student{"people": {"zhoujielun"}}
m["people"].name = "wuyanzu"
}