map 的底层实现是一个散列表,因此实现 map 的过程实际上就是实现散表的过程。

在这个散列表中,主要出现的结构体有两个,一个叫 hmap(a header for a go map),一个叫 bmap(a bucket for a Go map,通常叫其 bucket)。

这两种结构的样子分别如下所示:

hmap:

image

只需要关心的只有一个,就是标红的字段 buckets 数组。map 中用于存储的结构是 bucket 数组。而 bucket(bmap) 的结构是怎样的呢?

bucket:

image

相比于 hmap,bucket 的结构显得简单一些,标红的字段依然是核心,我们使用的 map 中的 key 和 value 就存储在这里。高位哈希值数组记录的是当前 bucket 中 key 相关的索引,稍后会详细叙述。还有一个字段是一个指向扩容后的 bucket 的指针,使得 bucket 会形成一个链表结构。

image

由此看出 hmap 和 bucket 的关系是这样的:

image

而 bucket 又是一个链表。

image

哈希表的特点是会有一个哈希函数,对传来的 key 进行哈希运算,得到唯一的值,一般情况下都是一个数值。map 中也有这么一个哈希函数,也会算出唯一的值。

Go 把求得的值按照用途一分为二:高位和低位。

image

蓝色为高位,红色为低位。

然后低位用于寻找当前 key 属于 hmap 中的哪个 bucket,而高位用于寻找 bucket 中的哪个 key。上文中提到,bucket 中有个属性字段是高位哈希值数组,这里存的就是蓝色的高位值,用来声明当前 bucket 中有哪些 key,便于搜索查找。

需要特别指出的一点是,map 中的 key/value 值都是存到同一个数组中的。

image

并不是 key0/value0/key1/value1 的形式,这样做的好处是在 key 和 value 的长度不同的时候,可以消除 padding 带来的空间浪费。

map整个的结构图

image

map的扩容

当以上的哈希表增长的时候,Go 语言会将 bucket 数组的数量扩充一倍,产生一个新的 bucket 数组,并将旧数组的数据迁移至新数组。

加载因子

判断扩充的条件,就是哈希表中的加载因子(loadFactor)。

加载因子是一个阈值,一般表示为:散列包含的元素数 除以 位置总数。是一种 产生冲突机会空间使用 的平衡与折中。

加载因子越小,说明空间空置率高,空间使用率小,但是加载因子越大,说明空间利用率上去了,但是“产生冲突机会”高了。

每种哈希表的都会有一个加载因子,数值超过加载因子就会为哈希表扩容。

加载因子公式

map长度 / 2^B

阈值是 6.5。其中 B 可以理解为已扩容的次数。

当 map 长度增长到大于加载因子所需的 map 长度时,就会将产生一个新的 bucket 数组,然后把旧的 bucket 数组移到一个属性字段 oldbucket 中。

注意:并不是立刻把旧的数组中的元素转义到新的 bucket 当中,而是只有当访问到具体的某个 bucket 的时候,才会把 bucket 中的数据转移到新的 bucket 中。

当扩容的时候,map 结构体中会保存旧的数据,和新生成的数组。

image

上面部分代表旧的有数据的 bucket,下面部分代表新生成的新的 bucket。蓝色代表存有数据的 bucket,橘黄色代表空的 bucket。

image

注意:这里并不会直接删除旧的 bucket,而是把原来的引用去掉,利用 GC 清除内存。

map 中数据的删除

  1. 如果 key 是一个指针类型的,则直接将其置为空,等待 GC 清除。
  2. 如果是值类型的,则清除相关内存。
  3. 同理,对 value 做相同的操作。
  4. 最后把 key 对应的高位值对应的数组 index 置为空。

标签: Go

添加新评论