map初识
map是一个以键值对元素的数据集合，map是一个集合。
map的优点是查找速度非常会，原因是map的底层存储是hash表。
hash表的存储原理：
对key进行计算，计算出hash值，对hash值进行取模，通过取模得到索引。
这种模式快的原因就是可以根据key直接寻找到数据存放的位置，不需要前后逐一对比。
如果取模后索引相等就是hash冲突，解决hash冲突的方法有
-
开放地址法
-
拉链法
map扩容：通过扩容扩大索引值的范围，减少hash冲突的概率
map的特点
- 键不能重复
- 键必须可以算出hash值，可hash的有int、float、string、bool、array这些数据类型（slice不能用作键）
- 无序
map的声明与初始化
//声明一个map并初始化两个值
userInfo := map[string]string{"name":"张三","age":="18"}
//map修改值
userInfo["age"] = "20"
//map新增值
userInfo["email"]="[email protected]"
使用make进行初识化
//也可以写data := make(map[int]int,10)，初始化10个位置放置数据，通常不写
data := make(map[int]int)
data[100] = 998
data[200] = 999
上面两种是最常见的，还有两种不常见的
//这种声明，因为没有初始化，所以键的值为nil，不能具体赋值，只能整体赋值
var row map[string]int
//将data这个map整体赋值给row
row = data
//new返回的是指针，内部也是nil，这种声明也是用于整体赋值，但是赋值要转成指针在赋值
value := new(map[string]int)
value = &data
map常用操作
长度和容量
data := map[string]string("n1":"123","n2":"222")
value := len(data) //2
//容量初始化10,根据给的参数值10，map会计算出一个合适的容量，
//map中包含很多桶，每个桶中可以存8个键值对
info := make(map[string]string,10)
info["n1"] = "111"
info["n2"] = "1111"
v1 := len(info)//2,获取的是键值对的个数而不是容量的大小
增删改查
//添加
data := map[string]string("n1":"123","n2":"222")
data["n3"] = "1"
//修改
data["n1"] = "·12345"
//删除
delete(data,"n2")
//查看
for key,value := range data{
fmt.Println(key,value)
}
变量赋值
v1 := map[string]string("n1":"123","n2":"222")
v2 := v1
fmt.Println(v1)//{"n1":"123","n2":"222"}
fmt.Println(v2)//{"n1":"123","n2":"222"}
注意事项：在slice中扩容会导致指向的地址不同，但是在map中扩容后依然会指向同一地址
底层原理
map由hmap和bmap两个结构体构成
1.hmap中包含map的键值对个数count，哈希因子hash0，用于对key生成hash值，创建bmap的数B，B决定创建桶的个数，是2的B次方
2.将键值对放入bmap，一个bmap中可以 放8个键值对，bmap一般叫做桶，bmap中包含tophash（hash值的高8位），key，value，overflow（指针指向溢出桶）
初始化
//初始化一个可容纳10个元素的map
info := make(map[string]string,10)
第一步：创建一个hmap的结构体对象
第二步：生成一个哈希因子hash0并赋值到hmap中
第三步：根据hint=10，并根据算法规则来创建B，当前B应该为1，创建的桶是2的一次方就是2个桶
hint B
0-8 0
9-13 1
14-26 2
...
第四步：当B少于4时，桶的个数是2的B次方
当B大于等于4时，根据B创建桶的个数规则为2的B次方+2的B减4次方（标准桶加溢出桶）
注释：每个bmap中可以存放8个键值对，当不够存储时需要使用溢出桶，并将当前bmap中的overflow字段指向溢出桶的位置
写入数据
info["n1"] = "111"
在map中写入数据的流程
- 第一步：结合hmap中的哈希因子和键n1生成哈希值
- 第二步：获取哈希值的后B位（B为1就取后一位，B为0时就只有一个桶，不需要考虑放入哪个桶），并根据B的值来决定键值对放到哪个桶中
假设B为1，将桶掩码（B的二进制）和哈希值进行&运算，得到的值决定放入哪个桶
哈希值0101010...100100
桶掩码0000000...000001
结果00000000...000 = 0
- 第三步：确定桶后在桶中写入数据
获取哈希值的高8位tophash，key，value，指向溢出桶的指针overflow
读取数据
value := info[“n1]
- 第一步：结合哈希因子和键生成hash值
- 第二步：获取哈希值的后B位，并根据后B位的值来决定放在哪个桶里
- 第三步：确定桶之后，在根据key的哈希值计算出桶的tophash（高8位），根据tophash和key取桶中查找数据，查找不到会去溢出桶中查找，均未查找到则表示key不存在
扩容
触发扩容的条件：
-
map中数据总个数/桶的个数 > 6.5 ,引发翻倍扩容
-
使用了太多的溢出桶时，也会引发扩容（溢出桶过多会导致map处理过慢），溢出桶过多会引发等量扩容，创建跟溢出桶同样数量的标准桶
当B <= 15时，已使用的溢出桶个数 >= 2的B次方时，引发等量扩容
当B > 15时，已使用的溢出桶个数>= 2的15次方，引发等量扩容