Go中map是一个指针,占用8个字节,指向hmap结构

hmap包含若干个结构为bmap的数组,每个bmap底层都是采用链表结构,bmap通常叫做bucket

hmap结构:

type hmap struct{
    count int //元素数量
  flags uint8 //状态标志
  B uint8 //buckets的对数,如果B=5,则buckets的数量=2^5 = 32
  noverflow uint16 //溢出桶的数量
  hash0  uint32 //hash种子
  buckets unsafe.Pointer //指向buckets数组的指针,数组长度为2^B
  oldbuckets  unsafe.Pointer //如果发生扩容,指向老的buckets数组的指针,
  //oldbuckets数组大小为buckets数组长度的一半,未发生扩容时是null
  nevacuate  uintptr //表示扩容速度,小于此地址的都已经扩容完成
  extra *mapextra //存储溢出桶
}

bmap结构:

type bmap struct {
    tophash [bucketCnt]uint8
  //len为8的数组,用于快速定位key是否在这个bmap中
  //一个桶油8个槽,如果key的高8位在tophash中,则表示该key在这个捅中
}

bmap就是我们所说的桶,一个桶最多存放8个key,这些key之所以存放在一个桶,是因为经过hash计算之后,hash结果的低8位相同,在桶内又会根据hash结果的高8位来决定key到底落入那个位置(共有8个位置)。

bmap结构的定义是一个静态结构,在编译过程中,会扩展成下面的结构:

type bmap struct {
    tophash [8]uint8
  keys  [8]keytype
  values [8]elementtype
  overflow uintptr //指向下一个bmap,溢出捅存放在hmap的extra字段中
}

注意key和value是分开放的,这样的形式,当key和value的类型不一样的时候,key和value占用的字节大小不一样,key/value这种形式可能会因为内存对齐而浪费空间,所以分开放更节省内存空间。

mapextra的结构:

type mapextra struct {
    overflow *[]*bmap //包含的是bmap.buckets的overflow的bucket 
    oldoverflow *[]*bmap//包含的扩容时的是bmap.oldbuckets的overflow的bucket 
    nextoverflow *bmap //指向空闲的overflow bucket的指针
}

当map中的key、value都不含指针时,bmap将完全不包含指针,bmap指向溢出桶的字段overflow是uintptr类型,为了防止overflow被gc掉,所以需要mapextra.overflow将它保存起来。

map遍历

map遍历是无序的,原因有2点:

  • map的遍历时,并不是从0号bucket开始遍历,而是从一个随机序号的bucket,再从其中随机的key开始遍历
  • map在扩容后,可能一部分key已经搬迁到了新的内存,此时key就是无序的了

map是非线程安全的,因为Go官方认为,map的典型应用场景是不需要并发访问的,而不是为了小部分情况,导致大部分程序付出加锁的代价。map可以并发读,但不能并发写,否则会panic。

map的扩容

扩容时机

在向map插入新key的时候,会进行2个条件检查,如果符合就会触发扩容

扩容条件

  1. 超过负载:map元素个数 > 6.5 *桶个数
  2. 溢出桶太多

    1. 当桶总数 < 2 ^ 15时,如果溢出桶总数 > 桶总数,则认为溢出桶太多了
    2. 当桶总数 ≥ 2 ^ 15时,如果溢出桶总数 > 2 ^ 15时,则认为溢出桶太多了

扩容机制

  1. 双倍扩容:针对扩容条件1,新建buckets数组,新的buckets大小为原来的2倍,然后旧的buckets数据搬迁到新的buckets,称之为双倍扩容
  2. 等量扩容:针对扩容条件2,并不扩大容量,buckets数量维持不变,将原来的元素搬迁到一起,将松散的键值对重新排列,使得同一个bucket中的key排列更紧密,节省空间,提高bucket利用率

元素搬迁

并不会在扩容之后立马搬迁,而是在插入或者对key的修改和删除操作时,都会尝试进行搬迁,一次最多搬迁2个bucket

标签: none

添加新评论