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 | // A header for a Go map. |
B就是buckets数组的长度对数,也就是buckets数组长度为2^B,buckets里面存放着key-value对,buckets也是一个指针,类似于slice中指向数组的指针。
buckets指向的是下面这个东西
1 | type bmap struct { |
编译之后就变成了
1 | type bmap struct { |
其中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排列更加紧密