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

Go  /  管理员 发布于 2年前   843

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