锐客网

  1. 首页 > 睿知 > it技术 > >

go语言map扩容 go语言map扩容原理( 二 )

IT技术函数


Golang把求得的值按照用途一分为二：高位和低位 。
如图所示，蓝色为高位，红色为低位 。然后低位用于寻找当前key属于hmap中的哪个bucket ， 而高位用于寻找bucket中的哪个key 。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找 。需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的 。数组中的顺序是这样的:
并不是key0/value0/key1/value1的形式 ， 这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费。
现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中 ， 高位用于key的快速预览，用于快速试错)
map的扩容
当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍 ， 产生一个新的bucket数组 ， 并将旧数组的数据迁移至新数组 。
加载因子
判断扩充的条件，就是哈希表中的加载因子(即loadFactor) 。
加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数 。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越?。得骺占淇罩寐矢撸?空间使用率?。?但是加载因子越大，说明空间利用率上去了 ， 但是“产生冲突机会”高了 。
每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容 。
Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5 。其中B可以理解为已扩容的次数 。
当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中 。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是 ， 只有当访问到具体的某个bucket的时候 ， 会把bucket中的数据转移到新的bucket中 。
如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组
上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket 。蓝色代表存有数据的bucket，橘黄色代表空的bucket 。
扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：
注意：这里并不会直接删除旧的bucket ， 而是把原来的引用去掉，利用GC清除内存 。
map中数据的删除
如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了 。这里不再赘述 。
值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：
1
2
3
4
1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；
2、如果是值类型的，则清除相关内存 。
3、同理，对``value``做相同的操作 。
4、最后把key对应的高位值对应的数组index置为空 。
彻底理解Golang Map 本文目录如下，阅读本文后，将一网打尽下面Golang Map相关面试题
Go中的map是一个指针 ， 占用8个字节，指向hmap结构体;源码 src/runtime/map.go 中可以看到map的底层结构
每个map的底层结构是hmap，hmap包含若干个结构为bmap的bucket数组 。每个bucket底层都采用链表结构 。接下来，我们来详细看下map的结构
bmap就是我们常说的“桶”，一个桶里面会最多装 8 个 key ， 这些 key 之所以会落入同一个桶 ， 是因为它们经过哈希计算后，哈希结果是“一类”的 ， 关于key的定位我们在map的查询和插入中详细说明 。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有8个位置) 。

推荐阅读


上一篇：学校直播平台下载什么，学校直播平台下载什么APP

下一篇：复制音乐到u盘怎么用，复制音乐到u盘怎么用手机播放