go语言中对map底层原理、扩容机制、无序遍历、线程安全、冲突方式、负载因子、性能对比等方面介绍
map底层原理
map是一个指针占用8个字节(64位计算机),指向hmap结构体,hmap包含多个bmap数组(桶)
type hmap struct {
count int //元素个数,调用len(map)时直接返回
flags uint8 //标志map当前状态,正在删除元素、添加元素.....
B uint8 //单元(buckets)的对数 B=5表示能容纳32个元素 B随着map容量增大而变大
noverflow uint16 //单元(buckets)溢出数量,如果一个单元能存8个key,此时存储了9个,溢出了,就需要再增加一个单元
hash0 uint32 //哈希种子
buckets unsafe.Pointer //指向单元(buckets)数组,大小为2^B,可以为nil
oldbuckets unsafe.Pointer //扩容的时候,buckets长度会是oldbuckets的两倍
nevacute uintptr //指示扩容进度,小于此buckets迁移完成
extra *mapextra //与gc相关 可选字段
}
type bmap struct {
tophash [bucketCnt]uint8
}
//实际上编译期间会生成一个新的数据结构
type bmap struct {
topbits [8]uint8 //key hash值前8位 用于快速定位keys的位置
keys [8]keytype //键
values [8]valuetype //值
pad uintptr
overflow uintptr //指向溢出桶 无符号整形 优化GC
}
map扩容机制
扩容时机:
向 map 插入新 key 的时候,会进行条件检测,符合下面这 2 个条件,就会触发扩容
扩容条件:
1.超过负载 map元素个数 > 6.5(负载因子) * 桶个数
2.溢出桶太多
当桶总数<2^15时,如果溢出桶总数>=桶总数,则认为溢出桶过多
当桶总数>2^15时,如果溢出桶总数>=2^15,则认为溢出桶过多
扩容机制:
双倍扩容:针对条件1,新建一个buckets数组,新的buckets大小是原来的2倍,然后旧buckets数据搬迁到新的buckets。
等量扩容:针对条件2,并不扩大容量,buckets数量维持不变,重新做一遍类似双倍扩容的搬迁动作,把松散的键值对重新排列一次,使得同一个 bucket 中的 key 排列地更紧密,节省空间,提高 bucket 利用率,进而保证更快的存取。
渐进式扩容:
插入修改删除key的时候,都会尝试进行搬迁桶的工作,每次都会检查oldbucket是否nil,如果不是nil则每次搬迁2个桶,蚂蚁搬家一样渐进式扩容
map遍历为什么无序
map每次遍历,都会从一个随机值序号的桶,再从其中随机的cell开始遍历,并且扩容后,原来桶中的key会落到其他桶中,本身就会造成失序
如果想顺序遍历map,先把key放到切片排序,再按照key的顺序遍历map
var sl []int
for k := range m {
sl = append(sl, k)
}
sort.Ints(sl)
for _,k:= range sl {
fmt.Print(m[k])
}
map为什么不是线程安全的
map设计就不是用来多个协程高并发访问的
多个协程同时对map进行并发读写,程序会panic
如果想线程安全,可以使用sync.RWLock 锁
sync.map
这个包里面的map实现了锁,是线程安全的
Map如何查找
1.写保护机制
先插hmap的标志位flags,如果flags写标志位此时是1,说明其他协程正在写操作,直接panic
2.计算hash值
key经过哈希函数计算后,得到64bit(64位CPU)
10010111 | 101011101010110101010101101010101010 | 10010
3.找到hash对应的桶
上面64位后5(hmap的B值)位定位所存放的桶
如果当前正在扩容中,并且定位到旧桶数据还未完成迁移,则使用旧的桶
4.遍历桶查找
上面64位前8位用来在tophash数组查找快速判断key是否在当前的桶中,如果不在需要去溢出桶查找
5.返回key对应的指针
Map冲突解决方式
GO采用链地址法解决冲突,具体就是插入key到map中时,当key定位的桶填满8个元素后,将会创建一个溢出桶,并且将溢出桶插入当前桶的所在链表尾部
Map负载因子为什么是6.5
负载因子 = 哈希表存储的元素个数 / 桶个数
Go官方发现:
装载因子越大,填入的元素越多,空间利用率就越高,但发生哈希冲突的几率就变大。
装载因子越小,填入的元素越少,冲突发生的几率减小,但空间浪费也会变得更多,而且还会提
高扩容操作的次数
Go官方取了一个相对适中的值,把 Go 中的 map 的负载因子硬编码为 6.5,这就是 6.5 的选择缘由。
这意味着在 Go 语言中,当 map存储的元素个数大于或等于 6.5 * 桶个数 时,就会触发扩容行为。
Map和Sync.Map哪个性能好
type Map struct {
mu Mutex
read atomic.Value
dirty map[interface()]*entry
misses int
}
对比原始map:
和原始map+RWLock的实现并发的方式相比,减少了加锁对性能的影响。
它做了一些优化:可以无锁访问read map,而且会优先操作read map,倘若只操作read map就可以满足要求,那就不用去操作write map(dirty),所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式
优点:
适合读多写少的场景
缺点:
写多的场景,会导致 read map 缓存失效,需要加锁,冲突变多,性能急剧下降
相关文章