当前位置: 首页 > news >正文

Golang | 每日一练 (3)

💢欢迎来到张胤尘的技术站
💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥

文章目录

  • Golang | 每日一练 (3)
    • 题目
    • 参考答案
      • `map` 实现原理
        • `hmap`
        • `bmap`
        • 数据存储模型
        • 键值底层访问
          • 竞态检测
          • `Sanitizer` 检测
          • 空检查
          • 并发写检查
          • 哈希值计算
          • 桶定位
          • 扩容情况处理
          • 桶内查找
      • 安全并发访问 `map`
        • 使用 `sync.Mutex` 或者 `sync.RWMutex`
        • 并发安全的 `sync.Map`

Golang | 每日一练 (3)

题目

golang 中的 map 是如何实现的?如何安全地并发访问 map

参考答案

map 实现原理

golang 中,map 是一种灵活且高效的数据结构,底层是基于哈希表实现,键值对存储数据。

map 的内部由两个核心结构体组成:hmapbmap

hmap

hmapgolangmap 的底层核心数据结构之一,它封装了哈希表的所有关键信息。源码如下所示:

源码位置:src/runtime/map.go

// 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
}
  • count:表示当前 map 中存储的键值对数量,len() 直接访问它。
  • flags:用于存储一些标志位,例如是否正在扩容、是否需要清理等。
  • B:表示桶的数量为 2^B。例如,如果 B = 3,则桶的数量为 2^3 = 8B 的值决定了 buckets 数组的大小。
  • noverflow:表示溢出桶的数量。当一个桶满了(最多存储 8 对键值对),会创建一个溢出桶,并通过链表连接。
  • hash0:哈希种子,用于计算键的哈希值。通过哈希种子可以避免哈希冲突,增加哈希值的随机性。
  • buckets:指向底层桶数组的指针,桶数组的大小为 2^B,每个桶是一个 bmap 结构体。
  • oldbuckets:在扩容时,旧的桶数组会存储在这里。新的桶数组大小是旧数组的两倍。扩容完成后,oldbuckets 会被释放。
  • nevacuate:用于记录扩容进度的计数器。表示已经迁移完成的桶数量。
  • extra:存储一些可选字段。
bmap

bmap 是存储键值对的“桶”,每个桶可以存储最多 8 对键值对。源码如下所示:

源码位置:src/runtime/map.go

// 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 [abi.MapBucketCount]uint8// Followed by bucketCnt keys and then bucketCnt elems.// NOTE: packing all the keys together and then all the elems together makes the// code a bit more complicated than alternating key/elem/key/elem/... but it allows// us to eliminate padding which would be needed for, e.g., map[int64]int8.// Followed by an overflow pointer.
}
  • tophashabi.MapBucketCount 是一个常量,值为 8。存储每个键的哈希值的最高字节(top byte)。特殊情况:如果 tophash[0] < minTopHash,则表示该桶处于迁移状态,而不是存储键的哈希值。
// Maximum number of key/elem pairs a bucket can hold.
MapBucketCountBits = 3 // log2 of number of elements in a bucket.
MapBucketCount     = 1 << MapBucketCountBits
minTopHash     = 5 // minimum tophash for a normal filled cell.
  • tophash 之后,bmap 会依次存储键和值。键和值的存储方式是连续的:先存储所有键(bucketCnt 个键),然后存储所有值(bucketCnt 个值)。这种设计可以减少内存对齐时的填充,从而节省内存。例如,在 map[int64]int8 的情况下,如果键和值交替存储,可能会因为对齐问题浪费内存。

  • 最后在每个 bmap 的末尾包含一个指向下一个溢出桶的指针(overflow)。当一个桶满了(最多存储 8 对键值对)时,会通过链表的方式创建一个溢出桶,用于存储额外的键值对。

数据存储模型

例如:在64位平台上有一个 map[int]string,键的大小为 8 字节(int64),值的大小为 16 字节(指向字符串数据的指针(8 字节)和字符串的长度(8 字节))。一个 bmap 的内存布局如下所示:

在这里插入图片描述

键值底层访问

map 数据存储模型可知,因为键和值的存储是动态的,访问键和值时就需要通过指针偏移来实现。源码内容如下所示:

源码位置:src/runtime/map.go

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {// ...
}
  • t *maptypemap 的类型信息,例如键的类型、值的类型、哈希函数等。
  • h *hmapmap 的底层结构,包含哈希表的元数据(如桶数组、键值对数量等)。
  • key unsafe.Pointer:查找目标键的指针。
  • 返回值:返回指向值的指针。如果键不存在,则返回值类型的零值的指针。

对于 mapaccess1 源码的流程进行了如下步骤的拆解:

  • 竞态检测
  • Sanitizer 检测
  • 空检查
  • 并发写检查
  • 哈希值计算
  • 桶定位
  • 扩容情况处理
  • 桶查找

下面针对每一步骤进行详细说明。

竞态检测

如果启用了竞态检测,记录当前操作的上下文,以便在发生竞态时能够追踪。

if raceenabled && h != nil {callerpc := getcallerpc()pc := abi.FuncPCABIInternal(mapaccess1)racereadpc(unsafe.Pointer(h), callerpc, pc)raceReadObjectPC(t.Key, key, callerpc, pc)
}
Sanitizer 检测

msanread 会标记对 key 的读取操作,确保该内存区域已经被正确初始化。防止程序读取未初始化的内存,从而避免潜在的未定义行为。

asanread 会检查对 key 的读取操作是否安全,例如是否越界或是否访问了已释放的内存。

if msanenabled && h != nil {msanread(key, t.Key.Size_)
}
if asanenabled && h != nil {asanread(key, t.Key.Size_)
}
空检查

如果 map 为空,直接返回值类型的零值。

if h == nil || h.count == 0 {if err := mapKeyError(t, key); err != nil {panic(err) // see issue 23734}return unsafe.Pointer(&zeroVal[0])
}
并发写检查

如果 map 正在被写入(hashWriting 标志被设置),抛出并发读写错误,这一点也表明 map 并不支持并发安全。

if h.flags&hashWriting != 0 {fatal("concurrent map read and map write")
}
哈希值计算

使用键的哈希函数计算哈希值,其中 h.hash0 是哈希种子,用于避免哈希冲突。

hash := t.Hasher(key, uintptr(h.hash0))
桶定位

代码中使用哈希值的低 B 位(bucketMask(h.B))定位到初始桶。其中 BucketSize 是每个桶的大小(包括键和值的存储)。

m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))
扩容情况处理

如果当前真正在扩容,那么检查旧的桶数组 oldbuckets。如果旧桶尚未迁移完成(!evacuated(oldb)),使用旧桶进行查找。

if c := h.oldbuckets; c != nil {if !h.sameSizeGrow() {// There used to be half as many buckets; mask down one more power of two.// 如果扩容前的桶数量是当前的一半,进一步掩码哈希值m >>= 1}oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))if !evacuated(oldb) {b = oldb}
}
桶内查找
// 获取键的哈希值的最高字节
top := tophash(hash)
bucketloop:// 遍历当前桶及其溢出桶for ; b != nil; b = b.overflow(t) {// 遍历桶内的所有键值对for i := uintptr(0); i < abi.MapBucketCount; i++ {// 检查当前个键的哈希值最高字节是否匹配,如果不相等,说明当前槽位的键与目标键不匹配if b.tophash[i] != top {// 如果遇到空槽(emptyRest)跳出桶循环,因为后续槽位都是空的if b.tophash[i] == emptyRest {break bucketloop}// 不匹配则跳过当前槽位continue}// 计算第 i 个键的地址k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))// 如果键是指针类型,解引用键的指针if t.IndirectKey() {k = *((*unsafe.Pointer)(k))}// 比较传入的键和当前键是否相等if t.Key.Equal(key, k) {// 计算第 i 个值的地址e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))// 如果值是指针类型,解引用值的指针if t.IndirectElem() {e = *((*unsafe.Pointer)(e))}// 返回值的指针return e}}}// 如果未找到,则返回值类型的零值指针return unsafe.Pointer(&zeroVal[0])

根据上一小结中的 bmap 数据存储模型可知,桶内查找中最为重要的就是键的偏移量计算和值的偏移量计算,如下所示:

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))

其中,dataOffsettophash 数组之后的偏移量,i * uintptr(t.KeySize) 是计算得第 i 个键的偏移量。

e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))

其中,dataOffset + abi.MapBucketCount*uintptr(t.KeySize) 是值的起始偏移量(所有键之后);i * uintptr(t.ValueSize) 是第 i 个值的偏移量。

安全并发访问 map

由前一节可知, map 并非并发安全的,直接在多个 goroutine 中并发的修改同一个 map 时,会导致数据竞争和不可预测的行为。

为了安全地并发访问 map,可以采用以下几种方法:

使用 sync.Mutex 或者 sync.RWMutex

代码如下所示:

package mainimport ("fmt""sync"
)func main() {var mu sync.RWMutexmyMap := make(map[int]int)var wg sync.WaitGroupfor i := 0; i < 100; i++ { // 启动100个协程wg.Add(1)go func(val int) {defer wg.Done()mu.Lock() // 加写锁myMap[val] = val * 2mu.Unlock() // 释放写锁}(i)}wg.Wait() // 等待协程结束mu.RLock() // 加读锁fmt.Println("Map content:", myMap)mu.RUnlock() // 释放读锁
}

在读取时使用 mu.RLock()mu.RUnlock(),在写入时使用 mu.Lock()mu.Unlock()。另外 sync.RWMutex 允许多个读操作并发执行,但写操作互斥。

并发安全的 sync.Map

代码如下所示:

package mainimport ("fmt""sync"
)func main() {var myMap sync.Mapvar wg sync.WaitGroupfor i := 0; i < 10; i++ {wg.Add(1)go func(val int) {defer wg.Done()myMap.Store(val, val*2) // 存储键值对}(i)}wg.Wait()// Key: 0, Value: 0// Key: 2, Value: 4// Key: 3, Value: 6// Key: 7, Value: 14// Key: 8, Value: 16// Key: 9, Value: 18// Key: 1, Value: 2// Key: 4, Value: 8// Key: 5, Value: 10// Key: 6, Value: 12myMap.Range(func(key, value interface{}) bool { // 遍历所有键值对fmt.Printf("Key: %v, Value: %v\n", key, value)return true})
}

关于 golang 中的锁和并发编程相关的知识点,这里不在赘述,请后续关注文章 《Golang 并发编程》。

关于 golangmap 更多的知识点,请后续关注文章 《Golang 映射》。

🌺🌺🌺撒花!

如果本文对你有帮助,就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容,请随时向我提问。

在这里插入图片描述

相关文章:

Golang | 每日一练 (3)

&#x1f4a2;欢迎来到张胤尘的技术站 &#x1f4a5;技术如江河&#xff0c;汇聚众志成。代码似星辰&#xff0c;照亮行征程。开源精神长&#xff0c;传承永不忘。携手共前行&#xff0c;未来更辉煌&#x1f4a5; 文章目录 Golang | 每日一练 (3)题目参考答案map 实现原理hmapb…...

企业数据集成:实现高效调拨出库自动化

调拨出库对接调出单-v&#xff1a;旺店通企业奇门数据集成到用友BIP 在企业信息化管理中&#xff0c;数据的高效流转和准确对接是实现业务流程自动化的关键。本文将分享一个实际案例&#xff0c;展示如何通过轻易云数据集成平台&#xff0c;将旺店通企业奇门的数据无缝集成到用…...

提效10倍:基于Paimon+Dolphin湖仓一体新架构在阿里妈妈品牌业务探索实践

1. 业务背景 阿里妈妈品牌广告数据包括投放引擎、下发、曝光、点击等日志&#xff0c;面向运筹调控、算法特征、分析报表、诊断监控等应用场景&#xff0c;进行了品牌数仓能力建设。随着业务发展&#xff0c;基于Lambda架构的数仓开发模式&#xff0c;缺陷日益突出&#xff1a;…...

Deepseek快速做PPT

背景: DeepSeek大纲生成 → Kimi结构化排版 → 数据审查,细节调整 DeepSeek 拥有深度思考能力,擅长逻辑构建与内容生成,它会根据我们的问题进行思考,其深度思考能力当前测试下来,不愧为国内No.1,而且还会把中间的思考过程展示出来,大多时候会给出很多我们意想不到的思…...

论文解读 | AAAI'25 Cobra:多模态扩展的大型语言模型,以实现高效推理

点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入&#xff01; 点击 阅读原文 观看作者讲解回放&#xff01; 个人信息 作者&#xff1a;赵晗&#xff0c;浙江大学-西湖大学联合培养博士生 内容简介 近年来&#xff0c;在各个领域应用多模态大语言模型&#xff08;MLLMs&…...

uniapp修改picker-view样式

解决问题&#xff1a; 1.选中文案样式&#xff0c;比如字体颜色 2.修改分割线颜色 3.多列时&#xff0c;修改两边间距让其平分 展示效果&#xff1a; 代码如下 <template><u-popup :show"showPicker" :safeAreaInsetBottom"false" close&quo…...

HDFS Java 客户端 API

一、基本调用 Configuration 配置对象类&#xff0c;用于加载或设置参数属性 FileSystem 文件系统对象基类。针对不同文件系统有不同具体实现。该类封装了文件系统的相关操作方法。 1. maven依赖pom.xml文件 <dependency><groupId>org.apache.hadoop</groupId&g…...

【华三】STP的角色选举(一文讲透)

【华三】STP的角色选举 一、引言二、STP基础概念扫盲三、根桥选举过程详解四、根端口选举过程详解五、指定端口选举过程详解六、阻塞端口七、总结与配置建议七、附录**1. BPDU字段结构图&#xff08;文字描述&#xff09;****2. 华三STP常用命令速查表** 文章总结 一、引言 在…...

【C#零基础从入门到精通】(二十六)——C#三大特征-多态详解

【C#零基础从入门到精通】(二十六)——C#三大特征-多态详解 在 C# 中,多态是面向对象编程的重要特性之一,它允许不同的对象对同一消息做出不同的响应。多态可以分为静态多态和动态多态,下面将详细介绍它们以及各自包含的知识点。 多态概述 多态性使得代码更加灵活、可扩展…...

宇树科技13家核心零部件供应商梳理!

2025年2月6日&#xff0c;摩根士丹利&#xff08;Morgan Stanley&#xff09;发布最新人形机器人研报&#xff1a;Humanoid 100: Mapping the Humanoid Robot Value Chain&#xff08;人形机器人100&#xff1a;全球人形机器人产业链梳理&#xff09;。 Humanoid 100清单清单中…...

Java集合框架全解析:从LinkedHashMap到TreeMap与HashSet面试题实战

一、LinkedHashMap ①LinkedHashMap集合和HashMap集合的用法完全相同。 ②不过LinkedHashMap可以保证插入顺序。 ③LinkedHashMap集合因为可以保证插入顺序&#xff0c;因此效率比HashMap低一些。 ④LinkedHashMap是如何保证插入顺序的&#xff1f; 底层采用了双向链表来记…...

goland无法debug项目

1、其实个原因是因为正在使用的Delve调试器版本太旧&#xff0c;无法兼容当前的Go语言版本1.2。Delve是Go语言的一个调试工具&#xff0c;用于提供源码级别的调试功能。Go语言每隔一段时间会发布新版本&#xff0c;而相应的调试器Delve也可能会更新以提供新的特性或修复已知问题…...

深入探索 DeepSeek 在数据分析与可视化中的应用

在数据驱动的时代&#xff0c;快速且准确地分析和呈现数据对于企业和个人都至关重要。DeepSeek 作为一款先进的人工智能工具&#xff0c;凭借其强大的数据处理和可视化能力&#xff0c;正在革新数据分析的方式。 1. 数据预处理与清洗 在进行数据分析前&#xff0c;数据预处理…...

python面试题整理

Python 如何处理异常&#xff1f; Python中&#xff0c;使用try 和 except 关键字来捕获和处理异常 try 块中放置可能会引发异常的代码&#xff0c;然后在except块中处理这些异常。 能补充一下finally的作用吗&#xff1f; finally 块中的代码无论是否发生异常都会执行&#xf…...

大型装备故障诊断解决方案

大型装备故障诊断解决方案 方案背景 在全球航空工业迅猛发展的背景下&#xff0c;我国在军用和民用飞机自主研发制造领域取得了显著成就。尤其是在国家大力支持下&#xff0c;国内飞机制造企业攻克了诸多关键技术难题&#xff0c;实现了从设计研发到生产制造再到售后保障的完整…...

基于SpringBoot+vue+uniapp的智慧旅游小程序+LW示例参考

系列文章目录 1.基于SSM的洗衣房管理系统原生微信小程序LW参考示例 2.基于SpringBoot的宠物摄影网站管理系统LW参考示例 3.基于SpringBootVue的企业人事管理系统LW参考示例 4.基于SSM的高校实验室管理系统LW参考示例 5.基于SpringBoot的二手数码回收系统原生微信小程序LW参考示…...

小怿学习日记(七) | Unreal引擎灯光架构

灯光的布局对于HMI场景中车模的展示效果有着举足轻重的地位。本篇内容将简单介绍ES3.1的相关知识&#xff0c;再深入了解Unreal引擎中车模的灯光以及灯光架构。 一、关于ES3.1 1.1 什么是ES3.1 ES3.1这个概念对于美术的同学可能比较陌生&#xff0c;ES3.1指的是OpenGL ES3.1&…...

网络运维学习笔记 013网工初级(HCIA-Datacom与CCNA-EI)DHCP动态主机配置协议(此处只讲华为)

文章目录 DHCP&#xff08;Dynamic Host Configuration Protocol&#xff0c;动态主机配置协议&#xff09;网关配置DHCP服务器配置如果没有DHCP服务器&#xff0c;只在网关上做DHCP服务器&#xff1a; DHCP&#xff08;Dynamic Host Configuration Protocol&#xff0c;动态主…...

javaEE-14.spring MVC练习

目录 1.加法计算器 需求分析: 前端页面代码: 后端代码实现功能: 调整前端页面代码: 进行测试: 2.用户登录 需求分析: 定义接口: 1.登录数据校验接口: 2.查询登录用户接口: 前端代码: 后端代码: 调整前端代码: 测试/查错因 后端: 前端: lombok工具 1.引入依赖…...

HTML/CSS中并集选择器

1.作用:选中多个选择器对应的元素,又称:分组选择器 所谓并集就是或者的含义. 2.语法:选择器1,选择器2,选择器3,......选择器n 多个选择器通过,连接,此处,的含义就是:或. .rich,.beauty{color: blue;} 3.注意事项 1.并集选择器,我们一般竖着写 2.任何形式的选择器,都可以作为并…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...