Golang 中的 map 详解

这篇具有很好参考价值的文章主要介绍了Golang 中的 map 详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Golang 中的 map 详解

一、什么是 map?

1、map 的定义

  在计算机科学里,被称为相关数组、map、符号表或者字典,是由一组 <key, value> 对组成的抽象数据结构,并且同一个 key 只会出现一次。

  两个关键点:map 是由 key-value 对组成的;key 只会出现一次。

  map 的设计也被称为 “The dictionary problem(字典问题)”,它的任务是设计一种数据结构用来维护一个集合的数据,并且可以同时对集合进行增删查改的操作。

2、map 的数据结构

  最主要的数据结构有两种:哈希查找表(Hash table)、搜索树(Search tree)。

  • 哈希查找表(Hash table)
      哈希查找表使用哈希函数将 key 分配到不同的桶(bucket,也就是数组的不同 index),开销主要在哈希函数的计算以及数组的常数访问时间,在很多场景下,哈希查找表的性能很高。

  • 搜索树(Search tree)
      搜索树一般采用自平衡搜索树,包括:AVL 树,红黑树。

  哈希查找表的平均查找效率是 O(1),最差是 O(N),如果哈希函数设计的很好,最坏的情况基本不会出现。自平衡搜索树法的最差搜索效率是 O(logN)。遍历自平衡搜索树,返回的 key 序列,一般会按照从小到大的顺序;而哈希查找表则是乱序的。

二、Golang 中 map 的类型

  Golang 中 map 是一个指针,占用 8 个字节。当使用 make 创建 map 时,底层调用的是 makemap() 函数,makemap() 函数返回的是一个指针,因为返回的是指针,所以 map 作为参数的时候,函数内部能修改map。

func makemap(t *maptype, hint int, h *hmap) *hmap {}

三、map 的底层实现

   源码位于 src\runtime\map.go 中。

  golang 中 map 底层使用的是哈希查找表,用链表来解决哈希冲突。每个 map 的底层结构是 hmap,是由若干个结构为 bmap 的 bucket 组成的数组,每个 bucket 底层都采用链表结构。

hmap 的结构:

type hmap struct {
	count      int            // map中元素的数量,调用len()直接返回此值
	flags      uint8          // 状态标识符,key和value是否包指针、是否正在扩容、是否已经被迭代
	B          uint8          // map中桶数组的数量,桶数组的长度的对数,len(buckets) == 2^B,可以最多容纳 6.5 * 2 ^ B 个元素,6.5为装载因子
	noverflow  uint16         // 溢出桶的大概数量,当B小于16时是准确值,大于等于16时是大概的值
	hash0      uint32         // 哈希种子,用于计算哈希值,为哈希函数的结果引入一定的随机性
	buckets    unsafe.Pointer // 指向桶数组的指针,长度为 2^B ,如果元素个数为0,就为 nil
	oldbuckets unsafe.Pointer // 指向一个旧桶数组,用于扩容,它的长度是当前桶数组的一半
	nevacuate  uintptr        // 搬迁进度,小于此地址的桶数组迁移完成
	extra      *mapextra      // 可选字段,用于gc,指向所有的溢出桶,避免gc时扫描整个map,仅扫描所有溢出桶就足够了
}

// 溢出桶结构
type mapextra struct {
	overflow    *[]*bmap // 指针数组,指向所有溢出桶
	oldoverflow *[]*bmap // 指针数组,发生扩容时,指向所有旧的溢出桶
	nextOverflow *bmap // 指向所有溢出桶中下一个可以使用的溢出桶
}

bmap的结构:

type bmap struct {
    tophash [bucketCnt]uint8    // bucketCnt=8,// 存放key哈希值的高8位,用于决定kv键值对放在桶内的哪个位置
}

//实际上编辑期间会动态生成一个新的结构体
type bmap struct {
	topbits  [8]uint8     // 存放key哈希值的高8位,用于决定kv键值对放在桶内的哪个位置
	keys     [8]keytype   // 存放key的数组
	values   [8]valuetype // 存放value的数组
	pad      uintptr      // 用于对齐内存
	overflow uintptr      // 指向下一个桶,即溢出桶,拉链法
}

  buckets是一个bmap数组,数组的长度就是 2^B。每个bucket固定包含8个key和value,实现上面是一个固定的大小连续内存块,分成四部分:tophash 值,8个key值,8个value值,指向下个bucket的指针。

  tophash 值用于快速查找key是否在该bucket中,当插入和查询运行时都会使用哈希哈数对key做哈希运算,获取一个hashcode,取高8位存放在bmap tophash字段中。

  桶里面会最多装 8 个 key,这些 key 之所以会落入同一个桶,是因为它们经过哈希计算后,哈希结果是“一类”的。在桶内,又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置(一个桶内最多有8个位置)。

  如图,B=5 表示hmap的有2^5=32个bmap,buckets是一个bmap数组,其长度为32,每个bmap有8个key。

golang map,golang,golang,数据结构

  桶结构的很多字段得在编译时才会动态生成,比如key和values等

  桶结构中,之所以所有的key放一起,所有的value放一起,而不是key/value一对对的一起存放,目的便是在某些情况下可以省去pad字段,节省内存空间。由于内存对齐的原因,key0/value0/key1/value1… 这样的形式可能需要更多的补齐空间,比如 map[int64]int8 ,1字节的value后面需要补齐7个字节才能保证下一个key是 int64 对齐的。

  golang中的map使用的内存是不会收缩的,只会越用越多。

  每个 bucket 设计成最多只能放 8 个 key-value 对,如果有第 9 个 key-value 落入当前的 bucket,那就需要再构建一个溢出桶 bucket ,通过 overflow 指针连接起来。

四、map 的扩容

1、装载因子(平均每个桶存储的元素个数)

  Go的装载因子阈值常量:6.5,map 最多可容纳 6.5*2^B 个元素。

  装载因子等于 map中元素的个数 / map的容量,即len(map) / 2^B。装载因子用来表示空闲位置的情况,装载因子越大,表明空闲位置越少,冲突也越多。随着装载因子的增大,哈希表线性探测的平均用时就会增加,这会影响哈希表的性能,当装载因子大于70%,哈希表的性能就会急剧下降,当装载因子达到100%,整个哈希表就会完全失效,这个时候,查找和插入任意元素的复杂度都是O(N),因为需要遍历所有元素。

  另外装载因子与扩容、迁移等重新散列(rehash) 行为有直接关系:

  • 在程序运行时,会不断地进行插入、删除等,会导致 bucket 不均,内存利用率低,需要迁移。
  • 在程序运行时,出现装载因子过大,需要做扩容,解决 bucket 过大的问题。

为什么装载因子是6.5?不是8?不是1?
  装载因子是哈希表中的一个重要指标,主要目的是为了平衡 buckets 的存储空间大小和查找元素时的性能高低。实际上这是 Go 官方的经过认真的测试得出的数字,一起来看看官方的这份测试报告。包含四个指标:
golang map,golang,golang,数据结构

  • loadFactor:负载因子,也叫装载因子;
  • %overflow:溢出率,有溢出 bukcet 的百分比;
  • bytes/entry:平均每对 key/alue 的开销字节数;
  • hitprobe:查找一个存在的 key 时,要查找的平均个数;
  • missprobe:查找一个不存在的 key 时,要查找的平均个数。

  Go 官方发现:装载因子越大,填入的元素越多,空间利用率就越高,但发生冲突的几率就变大;反之,装数因子越小,填入的元素越少,冲突发生的几率减小,但空间利用率低,而且还会提高扩容操作的次数。

  根据这份测试结果和讨论,Go 官方取了一个相对适中的值,把 Go 中的 map 的负数因子硬编码为 6.5,这就是 6.5 的选择缘由。这意味着在 Go 语言中,当 map存储的元素个数大于或等于 6.5*桶个数 时,就会发扩容行为。

2、触发 map 扩容的时机(插入、删除key)

  • 当装载因子超过6.5时,扩容一倍,属于增量扩容;
  • 当使用的溢出桶过多时,重新分配一样大的内存空间,属于等量扩容;
    (实际上没有扩容,主要是为了回收空闲的溢出桶,节省空间,提高 map 的查找和插入效率)

为什么会出现这种情况?
  这种情况可能是因为map删除的特性导致的。当我们不断向哈希表中插入数据,并且将他们又全部删除时,其内存占用并不会减少,因为删除只是将桶对应位置的tophash置nil而已。
  这种情况下,就会不断的积累溢出桶造成内存泄露,为了解决这种情况,采用了等量扩容的机制,一旦哈希表中出现了过多的溢出桶,会创建新桶保存数据,gc会清理掉老的溢出桶,从而避免内存泄露。

如何定义溢出桶是否太多需要等量扩容呢?两种情况:

  • 当B小于15时,溢出桶的数量超过2^B,属于溢出桶数量太多,需要等量扩容;
  • 当B大于等于15时,溢出桶数量超过2^15,属于溢出桶数量太多,需要等量扩容。

3、扩容策略(怎么扩容?)

  Go 会创建一个新的 buckets 数组,新的 buckets 数组的容量是旧buckets数组的两倍(或者和旧桶容量相同),将原始桶数组中的所有元素重新散列到新的桶数组中。这样做的目的是为了使每个桶中的元素数量尽可能平均分布,以提高查询效率。旧的buckets数组不会被直接删除,而是会把原来对旧数组的引用去掉,让GC来清除内存。

  在map进行扩容迁移的期间,不会触发第二次扩容。只有在前一个扩容迁移工作完成后,map才能进行下一次扩容操作。

4、搬迁策略

  由于map扩容需要将原有的kv键值对搬迁到新的内存地址,如果一下子全部搬完,会非常的影响性能。go 中 map 的扩容采用渐进式的搬迁策略,原有的 key 并不会一次性搬迁完毕,一次性搬迁会造成比较大的延时,每次最多只会搬迁 2 个 bucket,将搬迁的O(N)开销均摊到O(1)的赋值和删除操作上。

  上面说的 hashGrow() 函数实际上并没有真正地“搬迁”,它只是分配好了新的 buckets,并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中,而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或修改、删除 key 的时候,都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否搬迁完毕,具体来说就是检查 oldbuckets 是否为 nil。

五、解决哈希冲突

1、开放寻址法

  如果发生哈希冲突,从发生冲突的那个单元起,按一定的次序,不断重复,从哈希表中寻找一个空闲的单元,将该键值对存储在该单元中。具体的实现方式包括线性探测法、平方探测法、随机探测法和双重哈希法等。开放寻址法需要的表长度要大于等于所需要存放的元素数量。

2、链地址法

  基于数组 + 链表 实现哈希表,数组中每个元素都是一个链表,将每个桶都指向一个链表,当哈希冲突发生时,新的键值对会按顺序添加到该桶对应的链表的尾部。在查找特定键值对时,可以遍历该链表以查找与之匹配的键值对。文章来源地址https://www.toymoban.com/news/detail-620002.html

3、两种方案的比较

  • 内存利用率
      对于链地址法,基于 数组 + 链表 进行存储,链表节点可以在需要时再创建,开放寻址法需要事先申请好足够内存,因此链地址法对内存的利用率高。
  • 适用场景
      链地址法对装载因子的容忍度会更高,适合存储大对象、大数据量的哈希表,而且相较于开放寻址法,它更加灵活,支持更多的优化策略,比如可采用红黑树代替链表。但是链地址法需要额外的空间来存储指针。
      对于开放寻址法,它只有数组一种数据结构就可完成存储,继承了数组的优点,对CPU缓存友好,易于序列化操作,但是它对内存的利用率不高,且发生冲突时代价更高。当数据量明确、装载因子小,适合采用开放寻址法。

到了这里,关于Golang 中的 map 详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Golang 中的 io 包详解(五):结构体类型介绍

    实现了 io.Reader 接口,并且进行了功能扩展。R 表示 io.Reader 对象,N 表示最多允许读取的字节数。简单示例如下所示: 当读取的字节数超过限制时,LimitedReader 会自动终止读取并返回一个 io.EOF 错误,表示已经达到了总字节数的限制。 实现了 io.Reader、io.ReaderAt 和 io.Seeker 接口

    2024年02月08日
    浏览(43)
  • 数据结构 in Golang:Hash Tables(哈希表)

    水果店的价格表: 苹果 Apple:3元 香蕉 Banana:4元 桃子 Peach:2元 梨 Pear:3元 找到一种水果的价格: 可以使用 binary search,通过名称来查找,耗时:O(logn) 如何只耗时 O(1) 来找到价格呢? Hash 函数:通过一个字符串 - 一个数值 例如: \\\"Apple\\\" - 1 \\\"Banana\\\" - 2 \\\"Peach\\\" - 7 \\\"Pear\\\" - 8 将字符

    2024年02月08日
    浏览(63)
  • golang map json 结构体

    要将JSON转换为Go结构体,您可以使用json.Unmarshal()函数。首先,您需要定义一个与JSON数据结构匹配的Go结构体,然后使用json.Unmarshal()将JSON数据解码为该结构体。 以下是一个示例: 假设有如下JSON数据: 您可以将其转换为Go结构体如下: 在上面的示例中,我们定义了一个名为

    2024年02月08日
    浏览(36)
  • golang 结构体struct转map实践

      1、反射 type sign struct {     Name string `json:\\\"name,omitempty\\\"`     Age  int    `json:\\\"age,omitempty\\\"` }   var s sign s.Name = \\\"csdn\\\" s.Age = 18     //方式1 反射 var data = make(map[string]interface{})   t := reflect.TypeOf(s) v := reflect.ValueOf(s) for i := 0; i t.NumField(); i++ {     data[t.Field(i).Name] = v.Field(i).Interfa

    2024年02月12日
    浏览(41)
  • Golang学习之结构体和内存对齐、map设计思路

    cpu要想从内存读取数据,需要通过地址总线,把地址传输给内存,内存准备好数据,输出到数据总线,交给CPU。 如果地址总线只有8根,那这个地址就只有8位,可以表示256个地址,因为表示不了更多的地址就用不了更大的内存。 所以256就是8根地址总线最大的寻址空间,要使

    2024年02月16日
    浏览(41)
  • Golang 中的 map 为什么是并发不安全的?

      golang 中的 map 是并发不安全的,多个 go 协程同时对同一个 map 进行读写操作时,会导致数据竞争(data race)问题,程序会 panic。   如果一个协程正在写入 map,而另一个协程正在读取或写入 map,那么就有可能出现一些未定义的行为,例如:读取到的值可能是过期的、不

    2024年02月05日
    浏览(57)
  • Golang中map的使用详解及注意事项

    了解Golang中map的声明、自动增长、增加更新、删除等操作。掌握map的初始化、遍历、排序等技巧,以及结构体与OOP相关内容。深入了解Golang中map的使用方法和注意事项。

    2024年02月11日
    浏览(63)
  • 【数据结构】 Map和Set详解

    Map和set是一种专门用来 进行搜索的容器或者数据结构 ,其搜索的效率与其具体的实例化子类有关。以前常见的 搜索方式有: 直接遍历,时间复杂度为O(N),元素如果比较多效率会非常慢 二分查找,时间复杂度为 ,但搜索前必须要求序列是有序的 上述排序比较适合静态类型的

    2024年02月09日
    浏览(46)
  • 【高阶数据结构】Map 和 Set(详解)

    (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是 Scort 目前状态:大三非科班啃C++中 🌍博客主页:张小姐的猫~江湖背景 快上车🚘,握好方向盘跟我有一起打天下嘞! 送给自己的一句鸡汤🤔: 🔥真正的大师永远怀着一颗学徒的心 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏 🎉🎉

    2024年01月23日
    浏览(37)
  • 数据结构 - 7(Map和Set 15000字详解)

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 int[] array ={5,3,4,1,7,8,2,6,0

    2024年02月06日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包