go语言中对map底层原理、扩容机制、无序遍历、线程安全、冲突方式、负载因子、性能对比等方面介绍

2023-06-01 00:00:00 等方面 遍历 扩容

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 缓存失效,需要加锁,冲突变多,性能急剧下降

相关文章