0%

Map详解

Map详解

什么是Map

基本上每种计算机语言里面都会内置一个map类型,map是一个由一组key,value组成的数据类型,并且同一个key只会出现一次。同时map支持增删改查四种操作,map的主要实现方式有两种,分别是哈希查找表(hash table)和搜索树(search tree)

哈希表:使用一个哈希函数将key分配到不同的bucket(桶,可以理解成数组中的索引),开销主要是在哈希函数的计算和数组的常数访问时间,很多场景下,我们可以简单的把哈希表的时间复杂度看成O(1)。哈希表通常还会有一个碰撞的问题,所谓的哈希碰撞就是多个key被哈希函数分配到了同一个bucket。一般有两种解决方法:链表法和开放地址法。链表法是将一个bucket实现程一个链表,落在同一个bucket中的key会插入这个链表。而开发地址法则是在发生碰撞之后,通过一定的规律,在空着的bucket里面挑选,用来放置新的key

搜索树:一般使用自平衡二叉树,比如AVL树和红黑树

二者的区别是,自平衡搜索树的时间复杂度最低为O(logN),而哈希表的最差情况是O(N),哈希表平均查找效率是O(1)。 还有一个区别是,遍历自平衡搜索树,返回的key是有序的,而哈希表则是乱序的

Go Map

Go中的Map使用的是哈希表,并且使用链表的方式解决哈希冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// A header for a Go map.
type hmap struct {
// 元素个数,调用 len(map) 时,直接返回此值
count int
flags uint8
// buckets 的对数 log_2
B uint8
// overflow 的 bucket 近似数
noverflow uint16
// 计算 key 的哈希的时候会传入哈希函数
hash0 uint32
// 指向 buckets 数组,大小为 2^B
// 如果元素个数为0,就为 nil
buckets unsafe.Pointer
// 等量扩容的时候,buckets 长度和 oldbuckets 相等
// 双倍扩容的时候,buckets 长度会是 oldbuckets 的两倍
oldbuckets unsafe.Pointer
// 指示扩容进度,小于此地址的 buckets 迁移完成
nevacuate uintptr
extra *mapextra // optional fields
}

B就是buckets数组的长度对数,也就是buckets数组长度为2^B,buckets里面存放着key-value对,buckets也是一个指针,类似于slice中指向数组的指针。

buckets指向的是下面这个东西

1
2
3
type bmap struct {
tophash [bucketCnt]uint8
}

编译之后就变成了

1
2
3
4
5
6
7
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}

其中bmap就是我们所说的哈希桶,每个桶里面最多装下8个key-value对,这些key之所以会落入同一个桶中,是因为他们经过哈希计算之后,得到的结果是一类的(哈希结果得到的后八位相同),之后会根据key计算出来的hash值的高8位来决定key到底落入桶内的那个位置(哪个槽)

其中每个bmap的key1…key8是存放在一起的,value1….value8是存放在一起的,这样的目的是为了节省因为内存对齐造成的空间浪费。

每个bucket设计成最多只能存放8个key-value对,如果有第九个key-value落入当前的bucket,则需要再构建一个bucket,然后通过overflow指针连接起来。

创建map

底层调用的是makemap函数,主要做的工作就是初始化hamp结构体的各种字段,比如计算B的大小,设置哈西种子hash0等等

哈希函数

map的一个关键点在于哈希函数的选择,在程序启动时会检测cpu是否支持aes,如果支持则使用aes hash,否则使用memhash。hash函数有加密型和非加密型,加密型的一般用于加密数据、数字摘要等,典型代表就是md5 sha1 sha256 aes256这种,非加密型的就是查找,而map就是使用的查找hash函数

key定位过程

key经过哈希计算后得到哈希值,共64bit,计算它落到那个桶的时候,会用到最后B个bit位,最后B个bit位的值,就是落入桶的序号、当两个不同的key落在同一个桶中,也就是发生了哈希冲突,解决手段是链表法,从前往后找到第一个空位,这样,在查找某个key的时候先找到对应的桶,然后再去遍历bucket里的key。

在槽内的查找过程:使用高八位的bit值,高八位的值就是槽位,如果在bucket中没找到,并且overflow不为空,还要继续去overflow bucket中查找,直到找到或是所有的key槽位都遍历完

综上,这是一个双重循环的过程,外层循环查找所有bucket和overflow bucket,内层循环遍历单个bucket的所有槽位

get

Go中读取map有两种语法,带comma和不带comma,当要查询的key不在map里,带comma的用法会返回一个bool型变量提示key是否在map中,而不带comma的语法则会返回一个对应类型的零值

遍历

本来map的遍历过程比较简单:遍历所有的bucket以及它后面挂的overflow bucket(第一层遍历),然后挨个遍历bucket中的所有cell(槽),每个bucket包含8个cell,从有key的cell中取出key value

但是现实并没有这么简单,因为扩容并不是一个原子的操作,每次最多只搬运两个bucket,所以如果触发了扩容操作,那么很长时间内,map状态都是处于一种中间态,有些bucket已经搬迁到新家,有些bucket还呆在老地方

因此,遍历如果发生在扩容的过程中,就会涉及到遍历新老bucket的过程

具体是遍历老的bucket,然后再遍历老的bucket裂变到新的bucket里的元素

赋值

调用的是mapassign函数,语法和插入key的过程一样,只不过前者的key在map在不存在,后者存在

具体过程

1.检查map标志位flgas,如果为1则说明其他协程在执行写操作,导致程序panic

2.如果map正在扩容,那么当key定位到了某个bucket后,需要确保这个bucket对应的老bucket完成了迁移,即老bucket的key都要迁移到新的bucket中之后,才能在新的bucket中进行插入或者更新的操作

删除

调用的是底层的mapdelete函数

1.检查标志位flags,如果发现标志位为1,说明其他协程在执行写操作,直接panic

2.计算key的哈希,找到落入的bucket,如果正在扩容中,直接完成一次扩容

3.同样是两层循环,找到key的具体位置,然后删掉

扩容

使用哈希表的目的是快速找到目标key,随着map中添加的key越来越多,key发生碰撞的概率也越来越大,当bucket中的8个cell倍塞满的时候,效率就是最低的,最理想的情况是一个bucket只装一个key,这样就能达到o1的效率,当然这样空间消耗太多了

触发扩容的条件

1.装载因子超过阈值6.5

2.overflow的bucket数量过多,当B<15如果overflow的数量大于2^B,当B>=15,如果overflow的数量大于2^15(装载因子比较小,map的插入和查找效率也很低,但是bucket的数量很多)

两种扩容方式

1.元素太多,bucket太少,将B+1,让bucket的数量翻倍

2.元素不多,但overflow bucket很多,说明很多bucket都没满,开辟一个新的bucket空间,将老bucket中的元素移动到移动到新的bucket,是的一个bucket中的key排列更加紧密