map
map 是什么
在go语言中，map的底层采用hash表，用变种拉链法来解决hash冲突问题。
初始化
map是一种无序的基于key-value的数据结构，Go语言中map是引用类型，必须初始化才能使用。
var m map[string]int
m = make(map[string]int)
或者
m := map[string]int{
"apple": 1,
"banana": 2,
}
基本用法
m := map[string]int{
"apple": 1,
"banana": 2,
}
//添加/修改元素
m["pear"] = 3
//判断某个键是否存在
value, ok := m["apple"]
if ok {
fmt.Println(value)
} else {
fmt.Println("not found")
}
//map遍历
//注意顺序是随机的
for key, val := range m {
fmt.Println(key, val)
}
//删除map的键值对
delete(m, "banana")
//map做为切片元素
var mapSlice = make([]map[string]int, 3)
mapSlice[0] = make(map[string]int)
mapSlice[0]["test"] = 0
//切片作为map的值
mm := make(map[string][]string)
mm["city"] = []string{"shaanxi", "hunan"}
mm["city"] = append(mm["city"], "beijing", "shanghai")
线程安全性
线程不安全，如果需要线程安全，可通过两个手段
go 语言 map 的底层结构
map 的访问原理
// 当map中没有对应的key时，会返回value对应类型的零值
v := map[key]
// 当map中没有对应的key时，除了会返回value对应类型的零值,还会返回一个值存不存在的布尔值
v, ok := map[key]
map的赋值原理
有两点需要注意：
-
在对 map 进行赋值操作的时候，map 一定要先进行初始化，否则会 panic
-
map 是非线程安全的，不支持并发读写操作。当有其他线程正在读写 map 时，执行 map 的赋值会报为并发读写错误
map 的扩容
可以看到 map 会在两种情况下触发扩容：
- map 的负载因子已经超过 6.5
- 溢出桶的数量过多
在扩容的时候还有一个条件 !h.growing()，这是因为 map 的扩容并不是一个原子操作不是一次性完成的，所以需要判断一下，当前 map 是否正处于扩容状态，避免二次扩容造成混乱。
而这两种情况下，扩容策略是不同的
- 负载因子已经超过 6.5： 双倍扩容
- 溢出桶的数量过多：等量扩容(一般认为溢出桶数量接近数组同数量时)
什么是负载因子？
负载因子 = 哈希表中的元素数量 / 桶的数量
为什么负载因子是6.5？
源码里对负载因子的定义是6.5，是经过测试后取出的一个比较合理的值，每个 bucket 有 8 个空位，假设map里所有的数组桶都装满元素，没有一个数组桶由溢出桶，那么这是的负载因子刚好是8。而负载因子是6.5的时候，说明数组同快要用完了，存在溢出的情况下，查找一个key很可能要去遍历溢出桶，会造成查找性能下降，所以有必要扩容了
溢出桶的数量过多？
可以想象一下这种情况，先往一个map插入很多元素，然后再删除很多元素？在插入很多元素。会造成什么问题？
由于插入了很多元素，在不是完全理想的情况下，肯定会创建一些溢出桶，但是，又由于没有达到负载因子的临界值，所以不会触发扩容，在删除很多元素，这个时候负载因子又会减小，再插入很多元素，会继续创建更多的溢出桶，导致查找元素的时候要去遍历很差过的溢出桶链表，性能下降，所以在这种情况下要进行扩容，新建一个桶数组，把原来的数据拷贝到里面，这样数据排列更紧密，查找性能更快。