map
Go的map底层是用hash表实现的。
支持字面量初始化和内置函数make初始化。
m := map[string]int{"apple" : 2,"banana" : 3,}
m := make(map[string]int, 10)
make初始化map时指定容量可以有效减少内存分配的次数，有利于提升性能。
map的增删改查操作
m := make(map[string]string, 10)
m["apple"] = "red"
m["apple"] = "green"
delete(m, "apple")
v, exist := m["apple"] // v表示“apple”对呀的value， exist表示m中是否存在“apple”这个key。
多协程操作同一个map会产生读写冲突而引发panic；
未初始化的map值为nil，向值为nil的map添加元素时也会触发panic。
需要并发读写map可以加锁（Mutex，RWMutex）或者直接使用sync.Map。
map底层数据结构
type hmap struct {
count int // 当前保存元素的个数
B uint8 // bucket数组大小
buckets unsafe.Pointer // bucket数组，长度为2^B
oldbuckets unsafe.Pointer // 大小为一半旧的bucket数组，仅用于扩容
}
buckets中存放了2^B个bucket，hash桶说的就是bucket。下面是bucket的数据结构：
type bmap struct {
tophash [8]uint8 // 存储hash值的高8位
data []byte // key value 数据: key/key/key/key/···/value/value/value···，这样做的好处可以节省字节对齐带来的空间浪费。
overflow *bmap // 溢出bucket的地址，指向下一个bucket，将所有冲突的键连接起来
}
// 每个bucket只能存储8个键值对。
// 访问data和overflow成员通过指针偏移来实现。
hash就避免不了hash冲突问题
两个或以上的键被hash到同一个bucket时，就发生了冲突。Go是用链地址法来解决键冲突。但是由于同一个bucket只能存放8个键值对，所有超过8个键值对就会再创建一个bucket，将之后的键值对放入新建的bucket中，并用类似链表的方式将后面的bucket连接起来。
负载因子是用来衡量一个hash表冲突的情况：负载因子=键数量/bucket数量
负载因子过小，说明空间利用率低；
负载因子过大，说明冲突严重，存取效率低。
hash表中的负载因子过大时，需要申请更多的bucket，并需要对所有的键值对重新组织，使其能够均匀分布到bucket中，这个过程称之为rehash。
这里举一个redis的例子，redis中的map（bucket只能存放1个键值对）实现了当负载因子大于1时就会触发rehash，而Go中的map（能够存放8个键值对）在负载因子达到6.5时才会触发rehash过程。
关于扩容
降低负载因子常用的手段就是扩容，每次添加新的元素进map时，都需要判断是否需要扩容，是一种空间换时间的手段。
触发的条件需要满足下面的一条即可：
- 负载因子大于6.5时，即每个bucket中存储的键值对达到6.5对以上；
- overflow的数量大于2^15（32768）。（有点惊人啊）
增量扩容
新建的bucket数组的大小是原先的2倍，这也就很好的解释了上面hmap中oldbuckets的长度是buckets的一半的原因了。然后就是把旧的buckets中的数据搬迁到新的bucket数组中。Go采用的是逐步搬迁策略，即每次访问map都会搬迁2个键值对。
等量扩容
在维持bucket数量不变的情况下，把松散的键值对重新排列一次，使得bucket的使用率更高，保证更快的存取速度。重新组织后overflow的bucket数量会减少，进一步节省空间又提高访问效率。
map的增删改查
实则都是根据键的hash值确定一个bucket，并查询该bucket中是否存在指定的键。
- 查询过程
1.1 根据key计算hash值；
1.2 hash值低位hmap.B取模来确定bucket的位置；
1.3 取hash值高位在tophash数组中查询；
1.4 当前key的hash值与tophash[i]中存储的hash值相等的话，就去data里面找key；
1.5 当前的bucket没找到，就去overflow中的bucket中去找。
需要主要的是，在发生数据搬迁过程中，查找优先从oldbucket中进行；另外，找不到，会返回对应类型的零值，而不是nil
- 添加过程
添加过程和查过过程非常相似，如果已经存在key，则需要更新value值，否则需要在查找到的当前bucket中寻找空余位置插入。
同样在搬迁过程中，新元素是直接添加到新的buckets中，查找过程依然从旧buckets数组中开始
- 删除过程
删除操作也是类似，如果元素存在，则从相应的bucket中delete，不存在则不需要做任何操作。