您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > Go语言

Golang 中 map 探究

时间:2022-08-15 13:05:08  来源:  作者:字节跳动技术团队

简介

本文主要通过探究在golang 中map的数据结构及源码实现来学习和了解map的特性,共包含map的模型探究、存取、扩容等内容。欢迎大家共同讨论。

Map 的底层内存模型

在 golang 的源码中表示 map 的底层 struct 是 hmap,其是 hashmap 的缩写

type hmap struct {   // map中存入元素的个数, golang中调用len(map)的时候直接返回该字段   count     int   // 状态标记位,通过与定义的枚举值进行&操作可以判断当前是否处于这种状态   flags     uint8   B         uint8  // 2^B 表示bucket的数量, B 表示取hash后多少位来做bucket的分组   noverflow uint16 // overflow bucket 的数量的近似数   hash0     uint32 // hash seed (hash 种子) 一般是一个素数   buckets    unsafe.Pointer // 共有2^B个 bucket ,但是如果没有元素存入,这个字段可能为nil   oldbuckets unsafe.Pointer // 在扩容期间,将旧的bucket数组放在这里, 新buckets会是这个的两倍大   nevacuate  uintptr        // 表示已经完成扩容迁移的bucket的指针, 地址小于当前指针的bucket已经迁移完成   extra *mapextra // optional fields}

B 是 buckets 数组的长度的对数, 即 bucket 数组的长度是 2^B。bucket 的本质上是一个指针,指向了一片内存空间,其指向的 struct 如下所示:

// A bucket for a Go map.type bmap struct {   tophash [bucketCnt]uint8}

但这只是表面(src/runtime/hashmap.go)的结构,编译期间会给它加料,动态地创建一个新的结构:

type bmap struct {    topbits  [8]uint8    keys     [8]keytype    values   [8]valuetype    pad      uintptr        // 内存对齐使用,可能不需要    overflow uintptr        // 当bucket 的8个key 存满了之后}

bmap 就是我们常说的“桶”的底层数据结构, 一个桶中可以存放最多 8 个 key/value, map 使用 hash 函数 得到 hash 值决定分配到哪个桶, 然后又会根据 hash 值的高 8 位来寻找放在桶的哪个位置 具体的 map 的组成结构如下图所示:

 

Map 的存与取

在 map 中存与取本质上都是在进行一个工作, 那就是:

  1. 查询当前 k/v 应该存储的位置。
  2. 赋值/取值, 所以我们理解了 map 中 key 的定位我们就理解了存取。

底层代码

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {    // map 为空,或者元素数为 0,直接返回未找到    if h == nil || h.count == 0 {        return unsafe.Pointer(&zeroVal[0]), false    }    // 不支持并发读写    if h.flags&hashWriting != 0 {        throw("concurrent map read and map write")    }    // 根据hash 函数算出hash值,注意key的类型不同可能使用的hash函数也不同    hash := t.hasher(key, uintptr(h.hash0))    // 如果 B = 5,那么结果用二进制表示就是 11111 , 返回的是B位全1的值    m := bucketMask(h.B)    // 根据hash的后B位,定位在bucket数组中的位置    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))    // 当 h.oldbuckets 非空时,说明 map 发生了扩容    // 这时候,新的 buckets 里可能还没有老的内容    // 所以一定要在老的里面找,否则有可能发生“消失”的诡异现象    if c := h.oldbuckets; c != nil {        if !h.sameSizeGrow() {            // 说明之前只有一半的 bucket,需要除 2            m >>= 1        }        oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))        if !evacuated(oldb) {            b = oldb        }    }    // tophash 取其高 8bit 的值    top := tophash(hash)    // 一个 bucket 在存储满 8 个元素后,就再也放不下了,这时候会创建新的 bucket,挂在原来的 bucket 的 overflow 指针成员上    // 遍历当前bucket的所有链式bucket    for ; b != nil; b = b.overflow(t) {        // 在bucket的8个位置上查询        for i := uintptr(0); i < bucketCnt; i++ {            // 如果找到了相等的 tophash,那说明就是这个 bucket 了            if b.tophash[i] != top {                continue            }            // 根据内存结构定位key的位置            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))            if t.indirectkey {                k = *((*unsafe.Pointer)(k))            }            // 校验找到的key是否匹配            if t.key.equal(key, k) {                // 定位v的位置                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))                if t.indirectvalue {                    v = *((*unsafe.Pointer)(v))                }                return v, true            }        }    }    // 所有 bucket 都没有找到,返回零值和 false    return unsafe.Pointer(&zeroVal[0]), false}

寻址过程

 


 

Map 的扩容

在 golang 中 map 和 slice 一样都是在初始化时首先申请较小的内存空间,在 map 的不断存入的过程中,动态的进行扩容。扩容共有两种,增量扩容等量扩容(重新排列并分配内存)。下面我们来了解一下扩容的触发方式:

  1. 负载因子超过阈值,源码里定义的阈值是 6.5。(触发增量扩容)
  2. overflow 的 bucket 数量过多:当 B 小于 15,也就是 bucket 总数 2^B 小于 2^15 时,如果 overflow 的 bucket 数量超过 2^B;当 B >= 15,也就是 bucket 总数 2^B 大于等于 2^15,如果 overflow 的 bucket 数量超过 2^15。(触发等量扩容)

第一种情况

 

第二种情况

 

Map 的有序性

先说结论,在 golang 中 map 是无序的,准确的说是无法严格保证顺序的, 从上面的源码中我们可以知道,golang 中 map 在扩容后,可能会将部分 key 移至新内存,由于在扩容搬移数据过程中,并未记录原数据位置, 并且在 golang 的数据结构中也并未保存数据的顺序,所以那么这一部分在扩容后实际上就已经是无序的了。

遍历的过程,其实就是按顺序遍历内存地址,同时按顺序遍历内存地址中的 key。但这时已经是无序的了。但是如果我就一个 map,我保证不会对 map 进行修改删除等操作,那么按理说没有扩容就不会发生改变。但也是因为这样,GO 才在源码中 但是有一个有趣的现象,就算不对 map 进行插入删除等操作致使其扩容,其在遍历过程中仍是无序的。

objMap := make(map[string]int)for i := 0; i < 5; i++ {   objMap[strconv.Itoa(i)] = i}for i := 0 ; i < 5; i ++ {   var valStr1, valStr2 string   for k, v := range objMap {      fmt.Println(k)      fmt.Println(v)      valStr1 += k   }   for k, v := range objMap {      fmt.Println(k)      fmt.Println(v)      valStr2 += k   }   fmt.Println(valStr1 == valStr2)   if valStr1 != valStr2 {      fmt.Println("not equal")   }}fmt.Println("end")

​以上的运行结果是

 

不难看出,即使不对 map 进行扩容,在多次遍历时也是无序的,这是因为 golang 官方在设计时故意加上随机的元素,将遍历 map 的顺序随机化,用来防止使用者用来顺序遍历。

依赖 map 的顺序进行遍历,这是有风险的代码,在 GO 的严格语法规则下,是坚决不提倡的。所以我们在使用 map 时一定要记得其是无序的,不要依赖其顺序。

Map 的并发

首先我们大家都知道,在 golang 中 map 并不是一个并发安全的数据结构,当几个 goruotine 同时对一个 map 进行读写操作时,就会出现并发写问题:fatal error: concurrent map writes。但是为什么 map 是不支持并发安全的呢, 主要是因为成本与效益。

官方答复原因如下:

  • 典型使用场景:map 的典型使用场景是不需要从多个 goroutine 中进行安全访问。
  • 非典型场景(需要原子操作):map 可能是一些更大的数据结构或已经同步的计算的一部分。

性能场景考虑:若是只是为少数程序增加安全性,导致 map 所有的操作都要处理 mutex,将会降低大多数程序的性能。同时 golang 提供了并发安全的 sync map。

, // 不支持并发读写    if h.flags&hashWriting != 0 {        throw("concurrent map read and map write")    }

但是我们又有疑问了,为什么 golang map 并发冲突了不抛一个 error 出来,或者 panic 掉,而是要让程序 panic,选择让程序 crash 崩溃掉。这里是 golang 官方出于权衡风险和 map 使用复杂度场景考虑的,首先 map 在官方中就明确表示不支持并发读写, 所以并发对 map 进行读写操作本身就是不正确的。

场景假设一:如果 map 选择在写入或者读取时增加 error 返回值,会导致程序在使用 map 时就无法像现在一样,需要额外的捕获并判断 err。

场景假设二:如果 map 选择 panic(可被 recover),此时如果出现并发写入数据的场景,就会导致走进 recover 中,如果没有对这种场景进行特殊处理,就会导致 map 中存在脏数据,此时程序在使用 map 时就会引发不可预知的错误,此时排查起来也是很难找到问题的根因的。

所以 golang 在考虑了这些场景后,选择明确的抛出 crash 崩溃异常,使得风险被提前暴露。可以明确的定位到问题点。综上所述我们在使用 map 时,已经要严格保障其是在单线程内使用的,如果有多线程场景,建议使用 sync map 。



Tags:Golang   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
从 Discord 的做法中学习 — 使用 Golang 进行请求合并
正如你可能之前看到的,Discord去年发布了一篇有价值的文章,讨论了他们成功存储了数万亿条消息。虽然有很多关于这篇文章的YouTube视频和文章,但我认为这篇文章中一个名为“数据...【详细内容】
2023-11-24  Search: Golang  点击:(258)  评论:(0)  加入收藏
Golang 中的 Bytes 包详解之 Bytes.Buffer
上篇文章详细讲解了一次性密码 OTP 相关的知识,基于时间的一次性密码 TOTP 是 OTP 的一种实现方式。这种方法的优点是不依赖网络,因此即使在没有网络的情况下,用户也可以生成密...【详细内容】
2023-11-07  Search: Golang  点击:(262)  评论:(0)  加入收藏
使用示例和应用程序全面了解高效数据管理的Golang MySQL数据库
Golang,也被称为Go,已经成为构建强大高性能应用程序的首选语言。在处理MySQL数据库时,Golang提供了一系列强大的库,简化了数据库交互并提高了效率。在本文中,我们将深入探讨一些...【详细内容】
2023-10-29  Search: Golang  点击:(307)  评论:(0)  加入收藏
Golang 中的 String、rune 和 byte
解释StringGo语言中,string就是只读的采用utf8编码的字节切片(slice) 因此用len函数获取到的长度并不是字符个数,而是字节个数。 for循环遍历输出的也是各个字节。runerune是i...【详细内容】
2023-10-25  Search: Golang  点击:(135)  评论:(0)  加入收藏
Golang 中的字符串:常见错误和优秀实践
在这篇文章中,我们将讨论 Golang 中的字符串,并查看一些不同的场景,以避免常见错误。让我们深入探讨!1. 字符串是否可以为 nil?我们已经对 Golang 中的字符串有了基本的了解,但我...【详细内容】
2023-10-24  Search: Golang  点击:(247)  评论:(0)  加入收藏
深入探讨 Golang 中的追加操作
通过实际示例探索 Golang 中的追加操作简介在 Golang 编程领域,append 操作是一种多才多艺的工具,使开发人员能够动态扩展切片、数组、文件和字符串。在这篇正式的博客文章中,...【详细内容】
2023-10-20  Search: Golang  点击:(243)  评论:(0)  加入收藏
手撕 Golang 高性能内存缓存库 bigcache!
1. 前言你好哇!我是小翔。之前写了三篇 #Golang 并发编程 的文章了,这次来换换口味,开个 手撕源码 的新坑!一起来扒一扒 Go 语言高性能 local cache 库 bigcache,看看能不能把开...【详细内容】
2023-09-18  Search: Golang  点击:(292)  评论:(0)  加入收藏
Golang 中的 IO 包详解:常用的可导出函数详解
io.Copyfunc Copy(dst Writer, src Reader) (written int64, err error)用于在 io.Reader 或 io.Writer 之间复制数据,接受两个参数,一个 Writer 和一个 Reader。从 Reader...【详细内容】
2023-08-31  Search: Golang  点击:(279)  评论:(0)  加入收藏
Golang 获取本地 IP 地址方法
在 Golang 中,使用 net 包可以很方便地获取到本机IP地址。借助 net.InterfaceAddrs 方法简单示例代码如下:package mainimport ( "fmt" "net")func main() { addrList, err :=...【详细内容】
2023-07-25  Search: Golang  点击:(236)  评论:(0)  加入收藏
Golang 日志库 zap 如何自定义输出目标?
Zap( https://github.com/uber-go/zap)是一个功能非常丰富、易于使用的 Golang日志库。记录日志时,一般会选择输出到控制台(stdout和stderr)或者输出到文件或者同时输出到两者。z...【详细内容】
2023-05-31  Search: Golang  点击:(333)  评论:(0)  加入收藏
▌简易百科推荐
宝藏级Go语言开源项目——教你自己动手开发互联网搜索引擎
DIYSearchEngine 是一个能够高速采集海量互联网数据的开源搜索引擎,采用 Go 语言开发。Github 地址:https://github.com/johnlui/DIYSearchEngine运行方法首先,给自己准备一杯...【详细内容】
2024-03-12  OSC开源社区    Tags:Go语言   点击:(21)  评论:(0)  加入收藏
Go Gin框架实现优雅地重启和停止
在Web应用程序中,有时候我们需要重启或停止服务器,无论是因为更新代码还是进行例行维护。在这种情景下,我们需要保证应用程序的可用性和数据的一致性。这就需要优雅地关闭和重...【详细内容】
2024-01-30  源自开发者  微信公众号  Tags:Go   点击:(68)  评论:(0)  加入收藏
如何让Go程序以后台进程或daemon方式运行
本文探讨了如何通过Go代码实现在后台运行的程序。最近我用Go语言开发了一个WebSocket服务,我希望它能在后台运行,并在异常退出时自动重新启动。我的整体思路是将程序转为后台...【详细内容】
2024-01-26  Go语言圈  微信公众号  Tags:Go程序   点击:(60)  评论:(0)  加入收藏
深入Go底层原理,重写Redis中间件实战
Go语言以其简洁、高效和并发性能而闻名,深入了解其底层原理可以帮助我们更好地利用其优势。在本文中,我们将探讨如何深入Go底层原理,以及如何利用这些知识重新实现一个简单的Re...【详细内容】
2024-01-25  547蓝色星球    Tags:Go   点击:(68)  评论:(0)  加入收藏
Go 内存优化与垃圾收集
Go提供了自动化的内存管理机制,但在某些情况下需要更精细的微调从而避免发生OOM错误。本文将讨论Go的垃圾收集器、应用程序内存优化以及如何防止OOM(Out-Of-Memory)错误。Go...【详细内容】
2024-01-15  DeepNoMind  微信公众号  Tags:Go   点击:(63)  评论:(0)  加入收藏
Go函数指针是如何让你的程序变慢的?
导读Go 语言的常规优化手段无需赘述,相信大家也能找到大量的经典教程。但基于 Go 的函数值问题,业界还没有太多深度讨论的内容分享。本文作者根据自己对 Go 代码的使用与调优...【详细内容】
2024-01-15  腾讯云开发者  微信公众号  Tags:Go函数   点击:(89)  评论:(0)  加入收藏
Go编程中调用外部命令的几种场景
在很多场合, 使用Go语言需要调用外部命令来完成一些特定的任务, 例如: 使用Go语言调用Linux命令来获取执行的结果,又或者调用第三方程序执行来完成额外的任务。在go的标准库...【详细内容】
2024-01-09  suntiger    Tags:Go编程   点击:(109)  评论:(0)  加入收藏
Go 语言不支持并发读写 Map,为什么?
Go语言的map类型不支持并发读写的主要原因是并发读写会导致数据竞态(data race),这意味着多个 goroutine 可能同时访问并修改同一个 map,从而引发不确定的结果。在Go语言的设计...【详细内容】
2024-01-05  Go语言圈  微信公众号  Tags:Go 语言   点击:(81)  评论:(0)  加入收藏
Go微服务入门到容器化实践
Go微服务入门到容器化实践Go 是一门高效、现代化、快速增长的编程语言,非常适合构建 Web 应用程序。而 Docker 是一种轻量级的容器化技术,能够使得您的应用程序在任何地方运行...【详细内容】
2024-01-01  大雷家吃饭    Tags:Go微服务   点击:(63)  评论:(0)  加入收藏
你是否想知道如何应对高并发?Go语言为你提供了答案!
并发编程是当前软件领域中不可忽视的一个关键概念。随着CPU等硬件的不断发展,我们都渴望让我们的程序运行速度更快、更快。而Go语言在语言层面天生支持并发,充分利用现代CPU的...【详细内容】
2023-12-29  灵墨AI探索室  微信公众号  Tags:Go语言   点击:(110)  评论:(0)  加入收藏
站内最新
站内热门
站内头条