Map

Map 是由键值对组成的无序集合,也称为字典。

Map 是基于散列表来实现的,就是 Hash 表,每次迭代 Map 的时候,打印的 Key 和 Value 都是无序的。

其实某个版本之前是有序的,后来给改了 hhh...

声明、初始化

  • Map 需要分配内存,不然不能使用
var dict map[string]int        // 声明,但未分配内存
dict = make(map[string]int)    // 分配内存
dict["s"] = 43

dict := make(map[string]int)
dict["s"] = 43

dict := map[string]int{"s":43}

访问与使用

在 Go 中,是可以获取一个不存在的键的值的,只不过返回的是值类型的零值。

  • 检查一个键对应的值是否存在
    s, exists := dict["s"]
    if exists {
      fmt.Println(s)
    }
    

返回的参数中,第一个是键对应的值,第二个是一个 bool 类型变量,对应这个键值对是否存在

  • 使用 delete 函数删除键值对
    delete(dict, "s")
    

delete 函数接受两个参数,第一个是要操作的 Map,第二个是要删除的 Map 的键。

delete函数删除不存在的键也是可以的......

  • Map 在传递的时候是引用传递,意思就是传递的不是副本。

并发

Map 不是线程安全的,但 sync.Map 是线程安全的,如果懒得自己实现,就直接用 sync.Map 好了。

底层设计

const (
    // 一个 bucket 最多能放的元素数
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits

    // load factor = 13/2
    loadFactorNum = 13
    loadFactorDen = 2

    // 超过这两个 size 的对应对象,会被转为指针
    maxKeySize   = 128
    maxValueSize = 128

    // data offset should be the size of the bmap struct, but needs to be
    // aligned correctly. For amd64p32 this means 64-bit alignment
    // even though pointers are 32 bit.
    dataOffset = unsafe.Offsetof(struct {
        b bmap
        v int64
    }{}.v)

    // tophash 除了放正常的高 8 位的 hash 值
    // 还会在空闲、迁移时存储一些特征的状态值
    // 所以合法的 tophash(指计算出来的那种),最小也应该是 4
    // 小于 4 的表示的都是我们自己定义的状态值
    empty          = 0 // cell is empty
    evacuatedEmpty = 1 // cell is empty, bucket is evacuated.
    evacuatedX     = 2 // key/value is valid.  Entry has been evacuated to first half of larger table.
    evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
    minTopHash     = 4 // minimum tophash for a normal filled cell.

    // flags
    iterator     = 1 // there may be an iterator using buckets
    oldIterator  = 2 // there may be an iterator using oldbuckets
    hashWriting  = 4 // a goroutine is writing to the map
    sameSizeGrow = 8 // the current map growth is to a new map of the same size

    // sentinel bucket ID for iterator checks
    noCheck = 1<<(8*sys.PtrSize) - 1
)

// A header for a Go map.
type hmap struct {
    count     int // map 中的元素个数,必须放在 struct 的第一个位置,因为 内置的 len 函数会从这里读取
    flags     uint8
    B         uint8  // log_2 of # of buckets (最多可以放 loadFactor * 2^B 个元素,再多就要 hashGrow 了)
    noverflow uint16 // overflow 的 bucket 的近似数
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // 2^B 大小的数组,如果 count == 0 的话,可能是 nil
    oldbuckets unsafe.Pointer // 一半大小的之前的 bucket 数组,只有在 growing 过程中是非 nil
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // 当 key 和 value 都可以 inline 的时候,就会用这个字段
}

type mapextra struct {
    // 如果 key 和 value 都不包含指针,并且可以被 inline(<=128 字节)
    // 使用 extra 来存储 overflow bucket,这样可以避免 GC 扫描整个 map
    // 然而 bmap.overflow 也是个指针。这时候我们只能把这些 overflow 的指针
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 包含的是 hmap.buckets 的 overflow 的 bucket
    // oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // 指向空闲的 overflow bucket 的指针
    nextOverflow *bmap
}

// bucket 本体
type bmap struct {
    // tophash 是 hash 值的高 8 位
    tophash [bucketCnt]uint8
    // keys
    // values
    // overflow pointer
}

点击查看 Map 底层设计

在map的应用场景中选择 hash 函数主要考察性能、碰撞概率。 Go 使用的 hash 算法根据硬件选择,如果 CPU 支持 AES,那么使用 AES,否则使用 memhash。

哈希函数会将传入的key值进行哈希运算,得到一个唯一的值。 Go 把生成的哈希值一分为二,比如一个哈希值为:8423452987653321 拆分为 84234529 87653321。

前半部分就叫做高位哈希值,后半部分就叫做低位哈希值。

高位哈希值:用来确定当前的 bucket 有没有所存储的数据的 低位哈希值:用来确定当前的数据存在了哪个 bucket

hmap 是 map 的最外层的一个数据结构,包括了 map 的各种基础信息,如大小、bucket。

buckets 这个参数,它存储的是指向 buckets 数组的一个指针,当 bucket(桶为0时)为nil。

可以理解为 hmap 指向了一个空 bucket 数组,并且当 bucket 数组需要扩容时,它会开辟一倍的内存空间,并且会渐进式的把原数组拷贝 即用到旧数组的时候就拷贝到新数组。

bucket 这三部分内容决定了它是怎么工作的:

tophash 存储的是哈希函数算出的哈希值的高八位用来加快索引。 因为把高八位存储起来,这样不用完整比较 key 就能过滤掉不符合的 key,加快查询速度。 当一个哈希值的高8位和存储的高8位相符合,再去比较完整的key值,进而取出value。

第二部分,存储的是key 和value,就是传入的key和value,注意,它的底层排列方式是,key全部放在一起,value全部放在一起。 当key大于128字节时,bucket的key字段存储的会是指针,指向key的实际内容;value也是一样。 这样排列好处是在key和value的长度不同的时候,可以消除padding带来的空间浪费。并且每个bucket最多存放8个键值对。

第三部分,存储的是当bucket溢出时,指向的下一个bucket的指针。

bucket的设计细节:

在 map 中出现冲突时,不是每一个key都申请一个结构通过链表串起来,而是以bmap为最小粒度挂载,一个bmap可以放8个key和value。 这样减少对象数量,减轻管理内存的负担,利于gc。 如果插入时,bmap中key超过8,那么就会申请一个新的bmap(overflow bucket)挂在这个bmap的后面形成链表,优先用预分配的overflow bucket 如果预分配的用完了,那么就malloc一个挂上去。注意golang的map不会shrink,内存只会越用越多,overflow bucket中的key全删了也不会释放

简单概念
  1. hmap存储了一个指向底层bucket数组的指针。
  2. 我们存入的key和value是存储在bucket里面中,如果key和value大于128字节,那么bucket里面存储的是指向我们key和value的指针,如果不是则存储的是值。
  3. 每个bucket 存储8个key和value,如果超过就重新创建一个bucket挂在在元bucket上,持续挂接形成链表。
  4. 高位哈希值:是用来确定当前的bucket(桶)有没有所存储的数据的。
  5. 低位哈希值:是用来确定,当前的数据存在了哪个bucket(桶)
基本流程

查找或者操作map时,首先key经过hash函数生成hash值,通过哈希值的低8位来判断当前数据属于哪个桶(bucket) 找到bucket以后,通过哈希值的高八位与bucket存储的高位哈希值循环比对,如果相同就比较刚才找到的底层数组的key值,如果key相同,取出value。 如果高八位hash值在此bucket没有,或者有,但是key不相同,就去链表中下一个溢出bucket中查找,直到查找到链表的末尾。

碰撞冲突:如果不同的key定位到了统一bucket或者生成了同一hash,就产生冲突。 go是通过链表法来解决冲突的。 比如一个高八位的hash值和已经存入的hash值相同,并且此bucket存的8个键值对已经满了,或者后面已经挂了好几个bucket了。 那么这时候要存这个值就先比对key,key肯定不相同啊,那就从此位置一直沿着链表往后找,找到一个空位置,存入它。 所以这种情况,两个相同的hash值高8位是存在不同bucket中的。

查的时候也是比对hash值和key 沿着链表把它查出来。 还有一种情况,就是目前就 1个bucket,并且8个key-value的数组还没有存满, 这个时候再比较完key不相同的时候,同样是沿着当前bucket数组中的内存空间往后找,找到第一个空位,插入它。 这个就相当于是用寻址法来解决冲突,查找的时候,也是先比较hash值,再比较key,然后沿着当前内存地址往后找。

go语言的map通过数组+链表的方式实现了hash表,同时分散各个桶,使用链表法+bucket内部的寻址法解决了碰撞冲突,也提高了效率。 因为即使链表很长了,go会根据装载因子,去扩容整个bucket数组,所以下面就要看下扩容。

扩容

当链表越来越长,bucket的扩容次数达到一定值,其实是bmap扩容的加载因数达到6.5,bmap就会进行扩容,将原来bucket数组数量扩充一倍, 产生一个新的bucket数组,也就是bmap的buckets属性指向的数组。这样bmap中的oldbuckets属性指向的就是旧bucket数组。

这里的加载因子LoadFactor是一个阈值,计算方式为(map长度/2^B )如果超过6.5,将会进行扩容,这个是经过测试才得出的合理的一个阈值。 因为,加载因子越小,空间利用率就小,加载因子越大,产生冲突的几率就大。所以6.5是一个平衡的值。

map的扩容不会立马全部复制,而是渐进式扩容,即首先开辟2倍的内存空间,创建一个新的bucket数组。只有当访问原来就的bucket数组时, 才会将就得bucket拷贝到新的bucket数组,进行渐进式的扩容。当然旧的数据不会删除,而是去掉引用,等待gc回收。

powered by Gitbook该文件修订时间: 2020-04-10 10:05:54

results matching ""

    No results matching ""

    results matching ""

      No results matching ""