map 实现原理
什么是 map
map 是 Go 语言提供的一种抽象数据类型。它表示一组无序的键值对的集合。map 最重要的一点是通过 key 来快速检索数据，key 类似于索引，指向数据的值。
map 对 value 的类型没有限制，但是对 key 的类型有严格要求。
key 可以是任意可以用 == 或者 != 操作符比较的类型，比如 string、int、float。所以数组、切片和结构体不能作为 key，但是指针和接口类型可以。
map 类型不支持“零值可用”，未显示赋值的 map 类型变量的零值为 nil。如果尝试对 nil 值的 map 变量进行写操作，将会引发运行时 panic。
var m map[string]int
m["one"] = 1 // panic: assignment to entry in nil map我们必须显式初始化才能使用 map, 有两种方式：一种是使用复合字面值，另一种是使用 make 函数。
var statusText = map[int]string{
200: "OK",
404: "Not Found",
500: "Internal Server Error",
}var m = make(map[string]int)和切片一样，map 也是引用类型，它的内存地址也是在栈上分配的，但是它指向的数据是在堆上分配的。
所以我们在使用 map 的时候无须关心内存分配的问题，也不用担心 map 在函数间传递时会拷贝。
并且在函数中修改 map 的值，在函数外也能看到修改后的值。
map 的基本操作
插入数据
m := make(map[K]V)
m[k1] = v1
m[k2] = v2
m[k3] = v3如果 key 不存在，就是新增元素，如果 key 存在就是修改元素。
获取数据个数
m := map[string]int{
"one": 1,
"two": 2,
"three": 3,
}
println(len(m)) // 3查找和读取
所谓查找就是判断某个 key 是否存在，读取就是根据 key 获取对应的 value。
m := map[string]int{
"one": 1,
"two": 2,
"three": 3,
}
_, ok := m["four"]
if !ok {
println("key four does not exist")
}一个最佳实践是总是使用 comma ok 惯用法读取 map 中的值。
删除数据
借助内置函数 delete 从 map 中删除数据。
m := map[string]int{
"one": 1,
"two": 2,
"three": 3,
}
println(m) // map[one:1 two:2 three:3]
delete(m, "two")
println(m) // map[one:1 three:3]注意：即便要删的数据在 map 中不存在， delete 也不会报错。
遍历
我们可以像对待切片那样通过 for range 语句对 map 进行遍历。
m := map[string]int{
"one": 1,
"two": 2,
"three": 3,
}
for k, v := range m {
Printf("[%s, %d]", k, v)
}
// [one, 1][two, 2][three, 3]
for i := 0; i < len(m); i++ {
Printf("[%s, %d]", k, v)
}
// [one, 1][two, 2][three, 3]
// [two, 2][one, 1][three, 3]
// [one, 1][three, 3][two, 2]对同一个 map 进行多次遍历，每次遍历的顺序可能不一样，因为 map 迭代器时会对起始位置做了随机处理。
map 的内部实现
在编译阶段，Go 编译器会将语法层面的 map 操作重写为运行时对应的函数调用。
m := make(map[keyType]valueType, cap) // m := runtime.makeMap(keyType, valueType, cap)
v := m[key] // v := runtime.mapaccess1(key, m)
v, ok := m[key] // v, ok := runtime.mapaccess2(key, m)
m[key] = value // runtime.mapassign(key, value, m)
delete(m, key) // runtime.mapdelete(key, m)map 的底层数据结构是 hmap，它的定义如下：
type hmap struct {
count int // map 中的元素个数
flags uint8 // 表示 map 的状态
B uint8 // 用于计算 hash 值的位移量
noverflow uint16 // 溢出桶的个数
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // 桶数组指针
oldbuckets unsafe.Pointer // 扩容前的桶数组指针
nevacuate uintptr // 下次 GC 时，需要被转移的桶的个数
extra *mapextra // 指向额外信息的指针
}hmap 的 buckets 字段是一个指针，指向桶数组的指针。hmap 的 extra 字段是一个指针，指向额外信息的指针。
每个 buckets 由三部分组成，分别是 tophash、keys 和 values。
hmap 的 buckets 字段指向的桶数组的结构如下：
type bmap struct {
tophash [8]uint8 // 存储哈希值的高 8 位
data [8]struct { // 存储键值对
key, value unsafe.Pointer
}
}tophash 区域
bmap 的 tophash 字段存储的是哈希值的高 8 位，data 字段存储的是键值对。
tophash 的每个元素都是一个 uint8 类型，占用一个字节，所以 tophash 数组总共占用 8 个字节。
当向 map 插入一条数据或者从 map 按 key 查询数据的时候，运行时会使用哈希函数对 key 做哈希运算并获得一个哈希值 hashcode。 运行时会将 hashcode 一分为二，其中低位区的值用来选定 bucket，高位区的值用来和 tophash 数组中的值进行比较，选定 key。
key 区域
Go 运行时就会为该变量对应的特定的 map 类型生成一个 runtime.maptype 实例，结构体的定义如下：
type maptype struct {
typ _type // map 类型
key *_type // key 类型
elem *_type // value 类型
bucket *_type // 桶类型
keysize uint8 // key 的大小
valuesize uint8 // value 的大小
bucketsize uint16 // 桶的大小
flags uint32 // map 的标记
}value 区域
map 的 value 区域是一个指针，指向 map 的 value 区域。跟 key 类似，也一样会生成一个 runtime.maptype 实例。
但是 Go 运行时采用将 key 和 value 分开存储而不是采用 kv 紧邻存储的方式，这样做的好处是可以节省内存，因为 key 和 value 的类型可能不一样，所以采用分开存储的方式可以节省内存。
还有一点，如果 key 或 value 的大小超过 128 字节，Go 运行时会采用指针的方式存储，而不是直接存储。
// src/runtime/map.go
const (
maxKeySize = 128 // key 的最大大小
maxElemSize = 128 // value 的最大大小
)map 扩容
在使用过程中，在插入元素的个数超过一定数值后，势必存在自动扩容的问题，Go 语言中的 map 也不例外。
Go 运行时的 map 实现中引入了一个 LoadFactor (负载因子)，当 count > LoadFactor * 2^B 或 overflow bucket 过多时，就会触发扩容。
目前 LoadFactor 设置为 6.5 (loadFactorNum/loadFactorDen)
// src/runtime/map.go
const (
loadFactorNum = 13
loadFactorDen = 2
)如果是因为 overflow bucket 过多导致的扩容，实际上运行时会新建一个和现有规模一样的 bucket 的数组，
然后在进行 assign 和 delete 操作时，会将 overflow bucket 中的元素重新分配到新的 bucket 中。
如果是因为当前数据量超出 LoadFactor 指定的水位的情况，那么运行时会建立一个两倍于现有规模的 bucket 数组，元素重新分配也是需要在进行 assign 和 delete 操作时进行。
原 bucket 数组会挂在 hmap 的 oldbuckets 指针下，直至原 buckets 的数组中所有元素都迁移到了新数组。
map 并发
从上面的实现原理可以看到， 充当 map 描述符角色的 hmap 实例自身是有状态的（hmap.flags），且对状态的读写是没有并发保护的，因此 map 不是并发写安全的，不支持并发读写。 如果对 map 进行并发读写，程序运行时会发生 panic。
func doIteration(m map[int]int) {
for k, v := range m {
_ = fmt.Sprintf("key: %d, value: %d", k, v)
}
}
func doWrite(m map[int]int) {
for k, v := range m {
m[k] = v + 1
}
}
func main() {
m := map[int]int{
1: 1,
2: 2,
3: 3,
}
go func() {
for i := 0; i < 1000; i++ {
doIteration(m)
}
}()
go func() {
for i := 0; i < 1000; i++ {
doWrite(m)
}
}()
}
// fatal error: concurrent map iteration and map write我们可以看到如果仅仅是并发读，则 map 是没有问题的。
在 Go 1.9 版本之后引入了支持并发写安全的 sync.Map 类型，可以用来在并发读写的场景下，替换掉 map。
另外考虑到 map 是可以自动扩容的，map 中的 value 位置可能在这一个过程中发生变化，因此 Go 不允许获取 map 中的 value 地址。 这个约束在编译期间就生效。
尽量使用 cap
在使用 map 的时候，我们应该尽量指定 map 的容量，这样可以避免 map 在扩容时重新计算 hash 值，提升性能。
使用 cap 参数的 map 实例的平均写性能是不使用 cap 参数的 2 倍。
总结
- 不要依赖 map 的遍历顺序，它是无序的;
- map 不是线程安全的，不支持并发写;
- 不要尝试获取 map 中元素的地址；
- 尽量使用 cap，提升 map 的平均访问性能。