Golang Map 深度剖析:原理、实践与面试要点

嘿,小伙伴们!我是 k 哥。今天,咱们来聊聊 Map 。

在 Go 语言这个神奇的世界里,Map 这个有点神秘的数据结构一直都是开发者们特别关注的。

你是不是在用 Map 的时候,对它里面咋工作的感到好奇?是不是碰到复杂操作的时候,特别想弄明白它背后的原理?别着急,今天这篇文章就带你走进 Go 语言 Map 那个神秘的世界,帮你一层一层揭开它的面纱!

从底层的原理,到最佳实践,再到高频面试题的分析,这篇文章会从各个方面满足你的求知心。不管你是刚学的新手,还是经验丰富的老手,相信都能从这里得到宝贵的知识,受到启发。准备好跟我一起开始这场精彩的探索旅程了不?

1 原理

1.1 数据结构
在这里插入图片描述

Map 所涉及的核心数据结构包括两个,即 hmap 和 bmap :

  1. 每当创建一个 map 对象时,在底层都会创建一个 hmap 结构,以用于存储 map 的长度、hash 种子、状态等基础信息。

  2. hmap 指针类型的成员变量 buckets ,指向 bmap 数组。bmap 用于存储键值对。对于相同的键,每次进行 hash 操作后都会定位到 buckets 相同的索引位置进行访问。

  3. 每个 bmap 能够存储 8 个键值对,并且,每个 bmap 设有一个指针,当某个 bmap 存满时,就会申请新的 bmap 进行存储,并与前一个 bmap 构成链表。(通过链地址法解决冲突)

1.1.1 hmap

const (// Maximum average load of a bucket that triggers growth is 6.5.// Represent as loadFactorNum/loadFactorDen, to allow integer math.loadFactorNum = 13loadFactorDen = 2)// A header for a Go map.
type hmap struct {// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.// Make sure this stays in sync with the compiler's definition.count     int // # live cells == size of map.  Must be first (used by len() builtin)flags     uint8B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for detailshash0     uint32 // hash seedbuckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growingnevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)extra *mapextra // optional fields
}// mapextra holds fields that are not present on all maps.
type mapextra struct {// If both key and elem do not contain pointers and are inline, then we mark bucket// type as containing no pointers. This avoids scanning such maps.// However, bmap.overflow is a pointer. In order to keep overflow buckets// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.// overflow and oldoverflow are only used if key and elem do not contain pointers.// overflow contains overflow buckets for hmap.buckets.// oldoverflow contains overflow buckets for hmap.oldbuckets.// The indirection allows to store a pointer to the slice in hiter.overflow    *[]*bmap // 溢出桶数组指针oldoverflow *[]*bmap // 迁移过程中,旧溢出桶数组指针// nextOverflow holds a pointer to a free overflow bucket.nextOverflow *bmap // 还未使用的,提前分配的溢出桶链表
}

每创建一个 map 对象,在 Go 语言底层都会创建 hmap 结构,其成员的含义如下:

  1. count :表示 map 中的数据个数,与 len() 函数相对应。

  2. flags :属于标记字段,用于标记是否正在进行读写操作,以便实现并发读写的检测。

  3. B :代表桶的数量,hash 桶 buckets 的数量为 2^B 个。

  4. noverflow :是溢出桶数量的近似值。

  5. hash0 :为 hash 种子,用于计算 key 的 hash 值。

  6. buckets :是指向由 2^B 个桶所组成的数组的指针。

  7. oldbuckets :指向扩容前的旧 buckets 数组,仅在 map 扩容时发挥作用。

  8. nevacuate :作为计数器,用于标示扩容后搬迁的进度,服务于渐进式迁移。

  9. extra :用于保存溢出桶和未使用溢出桶切片的首地址。

1.1.2 bmap

在这里插入图片描述


const (// Maximum number of key/elem pairs a bucket can hold.bucketCntBits = 3bucketCnt     = 1 << bucketCntBits
)// A bucket for a Go map.
type bmap struct {// tophash generally contains the top byte of the hash value// for each key in this bucket. If tophash[0] < minTopHash,// tophash[0] is a bucket evacuation state instead.tophash [bucketCnt]uint8// Followed by bucketCnt keys and then bucketCnt elems.// Followed by an overflow pointer.
}

bmap 主要用于存储 key-value 对,每个 bmap 能够存储 8 个 key-value 对。bmap 包含 4 个成员变量(尽管在源码中只有一个成员变量 tophash,但实际上在申请内存时,Go 语言会依据 key、value 的具体类型,额外为另外 3 个成员变量分配内存):

  1. tophash 数组,用于存储每个 key hash 之后的高位 hash 值。

  2. key 数组,用于存储 key。

  3. value 数组,用于存储 value。

  4. overflow 溢出指针,指向了下一个 bmap 的地址。

bmap 有个溢出桶指针能指向溢出桶,那 extra 里为啥还得用 *[]*bmap 结构来存所有的溢出桶呢?

这主要是因为 gc 的原因。在早前的 Go 语言版本里,gc 会把 buckets 里的所有对象都扫一遍。要是 map 存的 key-value 对特别多,gc 能花上几百毫秒到好几秒,这就会让一些用 Go 语言开发的服务,接口超时超得厉害。

为了处理这个情况,Go 语言官方改了 map 的实现。要是 map 满足下面这两个条件,那 bmap 里除了 overflow ,就没别的指针了,而且会被 gc 标记成不用扫描:

  • key 和 value 不是指针类型,里面也不含指针(int 类型行,string 类型不行,因为 string 底层的数据结构里有指针)。

  • key 和 value 的大小得小于 128 字节。

但是 bmap.overflow 是指针类型,如果 gc 不扫 buckets ,溢出桶就可能被 gc 错误地回收掉。为了不让这种情况发生,就在 extra 里用 *[]*bmap 来存溢出桶,这样 gc 就能通过 []*bmap 扫到溢出桶(不用扫桶里面的东西),也就不会把溢出桶错误回收了。

1.2 插入或更新

1.2.1 2种异常情况处理

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {// 为nil则panicif h == nil {panic(plainError("assignment to entry in nil map"))}// 并发读写会抛异常,且不能被defer捕获if h.flags&hashWriting != 0 {throw("concurrent map writes")}// 计算key对应的hash值hash := t.hasher(key, uintptr(h.hash0))// 设置正在写标记h.flags ^= hashWriting// 初始化,但是桶为空的,会自动创建桶数组,读写不会panicif h.buckets == nil {

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/402770.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【计算机网络】应用层自定义协议与序列化

记得在上一节我们说过TCP中的读取时需要改进&#xff0c;这节就可以解决读取问题了。 目录 应用层再谈 "协议"网络版计算机方案一方案二 序列化 和 反序列化 重新理解 read、write、recv、send 和 tcp 为什么支持全双工 应用层 再谈 “协议” 我们在UDP与TCP中写的…

支持I2C接口、抗干扰性强、14通道触摸按键的电容式触摸芯片-GTX314L

电容式触摸芯片 - GTX314L是具有多通道触发传感器的14位触摸传感器系列&#xff0c;它是通过持续模式提供中断功能和唤醒功能&#xff0c;广泛适用于各种控制面板应用&#xff0c;可直接兼容原机械式轻触按键的处理信号。 GTX314L芯片内部采用特殊的集成电路&#xff0c;具有高…

基于YOLOv8-pose的手部关键点检测(3)- 实现实时手部关键点检测

目录 前言 1.扩大检测框区域 2.先检测手部&#xff0c;后检测手部关键点 3.正面视角检测 4.侧面视角检测 5.摄像头视角检测 6.遮挡视角检测 7.结论 前言 使用YOLOv8-m对图像进行手部检测&#xff0c;然后扩大检测框区域&#xff0c;并对该区域使用YOLOv8-s-pose使用关键…

大数据技术——实战项目:广告数仓(第六部分)报表数据导出至clickhouse

目录 第11章 报表数据导出 11.1 Clickhouse安装 11.2 Clickhouse建表 11.2.1 创建database 11.2.2 创建table 11.3 Hive数据导出至Clickhouse 第11章 报表数据导出 由于本项目最终要出的报表&#xff0c;要求具备交互功能&#xff0c;以及进行自助分析的能力&#xff0c;…

CSS——字体背景(Font Background)

一、字体族 1、字体的相关样式&#xff1a; ① color 用来设置字体颜色&#xff08;前景颜色&#xff09; ② font-size 字体的大小 和font-size相关的单位&#xff1a; em 相对于当前元素的一个font-size rem 相对于根元素的一个font-size ③ font-family 字体族&#x…

命令行参数环境变量

目录 前言&#xff1a; 命令行参数&#xff1a; 现象&#xff1a; 这些参数的意义&#xff1a; 为什么要这么做&#xff1f; 这些事是谁做的呢&#xff1f; 环境变量 现象&#xff1a; 创建环境变量&#xff1a; 结合程序理解&#xff1a; 前言&#xff1a; 我们在前…

1.Linux_常识

UNIX、Linux、GNU 1、UNIX UNIX是一个分时操作系统&#xff0c;特点是多用户、多任务 实时操作系统&#xff1a;来了请求就去解决请求 分时操作系统&#xff1a;来了请求先存着&#xff0c;通过调度轮到执行时执行 2、Linux Linux是一个操作系统内核 发行版本&#xff1…

C++(10)类语法分析(1)

C(10)之类语法分析(1) Author: Once Day Date: 2024年8月17日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文章可参考专栏: 源码分析_Once-Day的博客-CSDN博客 …

基于单片机的智能晾衣系统设计

摘 要 &#xff1a;在网络信息技术的推动下&#xff0c;智能家居得到了广泛应用&#xff0c;文章根据当前的市场动态&#xff0c;针对基于单片机的智能晾衣系统设计展开论述&#xff0c;具体包括两个方面的内容———硬件设计和软件设计。 关键词 &#xff1a;单片机&#xff…

【数据结构篇】~顺序表

顺序表前言 想要学好数据结构的三大基本功&#xff1a;1.结构体2.指针3.动态内存开辟,这三样将是贯彻整个数据结构的工具。&#xff08;可以去这里了解这三大基本功&#xff09; 顺序表也是线性表的一种&#xff0c;那线性表又是什么呢&#xff1f; 线性表&#xff08;linear …

应急响应-DDOS-技术指南

初步预判 通常&#xff0c;可从以下几方面判断服务器/主机是否遭受DDoS攻击查看防火墙、流量监控设备、网络设备等是否出现安全告警或大量异常数据包。如图所示&#xff0c;通过流量对比&#xff0c;发现在异常时间段存在大量UDP数据包&#xff0c;并且与业务无关。 通过安全设…

uniapp多图上传uni.chooseImage上传照片uni.uploadFile,默认上传9张图

uniapp多图上传uni.chooseImage上传照片uni.uploadFile 代码示例&#xff1a; /**上传照片 多图*/getImage() {uni.chooseImage({count: 9, //默认9sizeType: [original, compressed], //可以指定是原图还是压缩图&#xff0c;默认二者都有sourceType: [album], //从相册选择/…

8 Java常用API(基本语法6)-- Object和Objects类、Math、System、浅克隆和深克隆、手动下载导入第三方jar包

文章目录 前言一、Math(工具类)1 属性2 常见方法二、System(工具类,和系统相关的)1 public static void exit(int status) --- 终止当前运行的 Java 虚拟机。2 public static long currentTimeMillis() --- 以毫秒为单位返回当前unix时间。3 public static void arraycopy(Obj…

在Windows上配置VSCode MinGW+CMake(包括C++多线程编程的两套API:posix和win32)

创建目录 首先&#xff0c;需要电脑上安装VSCode, 并且创建三个文件夹&#xff1a;cmake、MinGW-posix、MinGW-w32 文件下载 下载posix-seh posix和win32分别是c多线程变成的两套API,可根据不同需求安装&#xff0c;现在先下载配置环境需要的几个文件 百度搜索MinGW-64 点…

Apache--简介与基本使用

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 一、Apache简介 Apache HTTP Server&#xff08;在Red Hat发行版中俗称Apache或httpd&#xff09;是由Apache Software Foundation在Apache License…

WPF打印控件内容

当我们想打印控件内容时&#xff0c;如一个Grid中的内容&#xff0c;可以用WPF中PrintDialog类的PrintVisual()方法来实现 界面如下&#xff1a; XAML代码如下 <Grid><Grid.ColumnDefinitions><ColumnDefinition/><ColumnDefinition Width"300"…

pygame开发课程系列(4): 游戏元素

第四章 游戏元素 在本章中&#xff0c;我们将深入探讨如何在 Pygame 中处理游戏元素&#xff0c;包括键盘输入、鼠标输入、图像加载和声音播放。这些元素是构建互动游戏的基础&#xff0c;能够让你的游戏变得更生动、更有趣。 4.1 处理键盘输入 键盘输入是控制游戏角色或元素…

Redis相关介绍

本文介绍了Redis&#xff0c;一种开源的内存数据结构存储系统&#xff0c;强调其高性能、多种数据结构支持、内存存储、持久化策略、发布订阅功能及工作原理。 一、Redis的介绍 Redis&#xff08;Remote Dictionary Server&#xff09;&#xff0c;即远程字典服务&#xff0c…

[000-01-030].第7节:Zookeeper工作原理

1.Zookeeper工作原理&#xff1a; 1.1.Zookeeper的工作机制 1.Zookeeper从设计模式角度来理解&#xff1a;是一个基于观察者模式设计的分布式服务管理框架&#xff1b;2.Zookeeper负责存储和管理大家都关心的数据&#xff0c;然后接受观察者的注册&#xff0c;一旦这些数据的…

Unity Recttransform操作

1、拉伸铺满 RectTransform rect GetComponent<RectTransform>();rect.anchorMin Vector2.zero;rect.anchorMax Vector2.one;rect.SetSizeWithCurrentAnchors(RectTransform.Axis.Horizontal, Screen.width);rect.SetSizeWithCurrentAnchors(RectTransform.Axis.Verti…