map 是什么
在go语言中,map的底层采用hash表,用变种拉链法来解决hash冲突问题。
初始化
map是一种无序的基于key-value的数据结构,Go语言中map是引用类型,必须初始化才能使用。
或者
基本用法
线程安全性
线程不安全,如果需要线程安全,可通过两个手段
go 语言 map 的底层结构
map 的访问原理
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插入很多元素,然后再删除很多元素?在插入很多元素。会造成什么问题?
由于插入了很多元素,在不是完全理想的情况下,肯定会创建一些溢出桶,但是,又由于没有达到负载因子的临界值,所以不会触发扩容,在删除很多元素,这个时候负载因子又会减小,再插入很多元素,会继续创建更多的溢出桶,导致查找元素的时候要去遍历很差过的溢出桶链表,性能下降,所以在这种情况下要进行扩容,新建一个桶数组,把原来的数据拷贝到里面,这样数据排列更紧密,查找性能更快。