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

golang map真有那么随机吗?——map遍历研究

在随机选取map中元素时,本想用map遍历的方式来返回,但是却并没有通过测试。

那么难道map的遍历并不是那么的随机吗?

以下代码参考go1.18

hiter是map遍历的结构,主要记录了当前遍历的元素、开始位置等来完成整个遍历过程

// A hash iteration structure.
// If you modify hiter, also change cmd/compile/internal/reflectdata/reflect.go
// and reflect/value.go to match the layout of this structure.
type hiter struct {// 指向下一个遍历key的地址key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).// 指向下一个遍历value的地址elem        unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).// map类型t           *maptype// map headerh           *hmap// 初始化时指向的bucketbuckets     unsafe.Pointer // bucket ptr at hash_iter initialization time// 当前遍历到的bmapbptr        *bmap          // current bucketoverflow    *[]*bmap       // keeps overflow buckets of hmap.buckets aliveoldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive// 开始桶startBucket uintptr        // bucket iteration started at// 桶内偏移量offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)// 是否从头遍历了wrapped     bool           // already wrapped around from end of bucket array to beginningB           uint8// 正在遍历的槽位i           uint8// 正在遍历的桶位bucket      uintptr// 用于扩容时进行检查checkBucket uintptr
}

mapiterinit为开始遍历的方法,主要是确定初始遍历的位置

// mapiterinit initializes the hiter struct used for ranging over maps.
// The hiter struct pointed to by 'it' is allocated on the stack
// by the compilers order pass or on the heap by reflect_mapiterinit.
// Both need to have zeroed hiter since the struct contains pointers.
func mapiterinit(t *maptype, h *hmap, it *hiter) {// 若map为空,则跳过遍历过程it.t = tif h == nil || h.count == 0 {return}if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go}it.h = h// grab snapshot of bucket state// 迭代器快照记录map桶信息it.B = h.Bit.buckets = h.bucketsif t.bucket.ptrdata == 0 {// Allocate the current slice and remember pointers to both current and old.// This preserves all relevant overflow buckets alive even if// the table grows and/or overflow buckets are added to the table// while we are iterating.h.createOverflow()it.overflow = h.extra.overflowit.oldoverflow = h.extra.oldoverflow}// decide where to start// 开始bucket选择随机数的低B位// 偏移量选择随机数高B位与桶数量,显然这个桶数量是不包括溢出桶的r := uintptr(fastrand())if h.B > 31-bucketCntBits {r += uintptr(fastrand()) << 31}it.startBucket = r & bucketMask(h.B)it.offset = uint8(r >> h.B & (bucketCnt - 1))// iterator state// 更新迭代器桶为初始桶it.bucket = it.startBucket// Remember we have an iterator.// Can run concurrently with another mapiterinit().// 标记可能有迭代正在使用桶和旧桶if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {atomic.Or8(&h.flags, iterator|oldIterator)}mapiternext(it)
}

从上面的代码分析我们便可以看出随机选取的元素并不是真的随机,溢出桶并不包含在随机选择的范围里面

在具体的遍历过程,存在以下疑问

  • 如果在扩容中,如何进行遍历?
  • 如何保证不遗漏?
  • 如何防止重复遍历?
func mapiternext(it *hiter) {h := it.h// 如果标记已经写入,则抛出并发迭代写入错误if h.flags&hashWriting != 0 {throw("concurrent map iteration and map write")}t := it.tbucket := it.bucketb := it.bptri := it.icheckBucket := it.checkBucketnext:if b == nil {// 如果再次遇到开始bucket且是从头遍历的,则说明迭代结束,返回if bucket == it.startBucket && it.wrapped {// end of iterationit.key = nilit.elem = nilreturn}// 如果正在迁移过程中,且老桶没被迁移,采用老桶if h.growing() && it.B == h.B {// Iterator was started in the middle of a grow, and the grow isn't done yet.// If the bucket we're looking at hasn't been filled in yet (i.e. the old// bucket hasn't been evacuated) then we need to iterate through the old// bucket and only return the ones that will be migrated to this bucket.oldbucket := bucket & it.h.oldbucketmask()b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))// bucket未迁移,记录bucket// checkBucket在当前map处于迁移而bucket未迁移时,为当前bucket// 否则为noCheckif !evacuated(b) {checkBucket = bucket} else {b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))checkBucket = noCheck}} else {// map处于未迁移,或者bucket迁移完成,采用新桶b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))checkBucket = noCheck}// 推进到下一桶bucket++// 遍历到最后一个桶,要绕回0桶继续遍历if bucket == bucketShift(it.B) {bucket = 0it.wrapped = true}i = 0}// 遍历桶内元素for ; i < bucketCnt; i++ {// 从offset槽开始offi := (i + it.offset) & (bucketCnt - 1)// 跳过空槽if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {// TODO: emptyRest is hard to use here, as we start iterating// in the middle of a bucket. It's feasible, just tricky.continue}// 获取元素key、valuek := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))if t.indirectkey() {k = *((*unsafe.Pointer)(k))}e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))// 扩容迁移时过滤掉不属于当前指向新桶的旧桶元素if checkBucket != noCheck && !h.sameSizeGrow() {// Special case: iterator was started during a grow to a larger size// and the grow is not done yet. We're working on a bucket whose// oldbucket has not been evacuated yet. Or at least, it wasn't// evacuated when we started the bucket. So we're iterating// through the oldbucket, skipping any keys that will go// to the other new bucket (each oldbucket expands to two// buckets during a grow).// 若key是有效的if t.reflexivekey() || t.key.equal(k, k) {// If the item in the oldbucket is not destined for// the current new bucket in the iteration, skip it.// 如果旧桶中的项在迭代中不打算用于当前的新桶,则跳过它。hash := t.hasher(k, uintptr(h.hash0))if hash&bucketMask(it.B) != checkBucket {continue}} else {// 对k!=k,也就是nil之类的,判断是否属于该新桶// 不是,则跳过// Hash isn't repeatable if k != k (NaNs).  We need a// repeatable and randomish choice of which direction// to send NaNs during evacuation. We'll use the low// bit of tophash to decide which way NaNs go.// NOTE: this case is why we need two evacuate tophash// values, evacuatedX and evacuatedY, that differ in// their low bit.if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {continue}}}// 如果当前桶未扩容迁移,或者是每次hash不一致的key,获取到key、value添加到迭代器中if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||!(t.reflexivekey() || t.key.equal(k, k)) {// This is the golden data, we can return it.// OR// key!=key, so the entry can't be deleted or updated, so we can just return it.// That's lucky for us because when key!=key we can't look it up successfully.it.key = kif t.indirectelem() {e = *((*unsafe.Pointer)(e))}it.elem = e} else {// 数据已经迁移情况下,处理键已被删除、更新或删除并重新插入的情况,定位数据,最后添加遍历key、value// The hash table has grown since the iterator was started.// The golden data for this key is now somewhere else.// Check the current hash table for the data.// This code handles the case where the key// has been deleted, updated, or deleted and reinserted.// NOTE: we need to regrab the key as it has potentially been// updated to an equal() but not identical key (e.g. +0.0 vs -0.0).rk, re := mapaccessK(t, h, k)if rk == nil {continue // key has been deleted}it.key = rkit.elem = re}// 迭代器记录进度it.bucket = bucketif it.bptr != b { // avoid unnecessary write barrier; see issue 14921it.bptr = b}it.i = i + 1it.checkBucket = checkBucketreturn}// 遍历溢出桶b = b.overflow(t)i = 0goto next
}

通过以上代码分析,可以看出:

  • 在扩容时遍历,

    • 如果当前遍历的桶已经迁移好了,那么取新桶

    • 如果仍然处于旧桶,则取旧桶。

      但值得注意的是要过滤掉那些不属于该新桶的旧桶元素。因为旧桶在扩容迁移时会分为两块,当前指向的新桶只属于其中之一

  • bucket从初始桶逐渐递增,保证正常桶都能遍历到。此外也保证了完整遍历溢出桶,直到溢出桶为空

  • 通过记录是否从头遍历的标志和起始bucket,以及在扩容过程中过滤不属于该新桶的元素来保证不会重复遍历

Ref

  1. https://zhuanlan.zhihu.com/p/597348765
  2. https://www.cnblogs.com/cnblogs-wangzhipeng/p/13292524.html
  3. https://qcrao.com/post/dive-into-go-map/

相关文章:

golang map真有那么随机吗?——map遍历研究

在随机选取map中元素时&#xff0c;本想用map遍历的方式来返回&#xff0c;但是却并没有通过测试。 那么难道map的遍历并不是那么的随机吗&#xff1f; 以下代码参考go1.18 hiter是map遍历的结构&#xff0c;主要记录了当前遍历的元素、开始位置等来完成整个遍历过程 // A ha…...

详细分析对比copliot和ChatGPT的差异

Copilot 和 ChatGPT 是两种不同的AI工具&#xff0c;分别在不同领域展现出了强大的功能和潜力&#xff1a; GitHub Copilot 定位与用途&#xff1a;GitHub Copilot 是由GitHub&#xff08;现为微软子公司&#xff09;和OpenAI合作开发的一款智能代码辅助工具。它主要集成于Visu…...

TENT:熵最小化的Fully Test-Time Adaption

摘要 在测试期间&#xff0c;模型必须自我调整以适应新的和不同的数据。在这种完全自适应测试时间的设置中&#xff0c;模型只有测试数据和它自己的参数。我们建议通过test entropy minimization (tent[1])来适应:我们通过其预测的熵来优化模型的置信度。我们的方法估计归一化…...

研发日记,Matlab/Simulink避坑指南(五)——CAN解包 DLC Bug

文章目录 前言 背景介绍 问题描述 分析排查 解决方案 总结 前言 见《研发日记&#xff0c;Matlab/Simulink避坑指南&#xff08;一&#xff09;——Data Store Memory模块执行时序Bug》 见《研发日记&#xff0c;Matlab/Simulink避坑指南(二)——非对称数据溢出Bug》 见《…...

机器人3D视觉引导半导体塑封上下料

半导体塑封上下料是封装工艺中的重要环节&#xff0c;直接影响到产品的质量和性能。而3D视觉引导技术的引入&#xff0c;使得这一过程更加高效、精准。它不仅提升了生产效率&#xff0c;减少了人工操作的误差&#xff0c;还为半导体封装技术的智能化升级奠定了坚实的基础。 传统…...

(十二)Head first design patterns代理模式(c++)

代理模式 代理模式&#xff1a;创建一个proxy对象&#xff0c;并为这个对象提供替身或者占位符以对这个对象进行控制。 典型例子&#xff1a;智能指针... 例子&#xff1a;比如说有一个talk接口&#xff0c;所有的people需要实现talk接口。但有些人有唱歌技能。不能在talk接…...

C++从零开始的打怪升级之路(day21)

这是关于一个普通双非本科大一学生的C的学习记录贴 在此前&#xff0c;我学了一点点C语言还有简单的数据结构&#xff0c;如果有小伙伴想和我一起学习的&#xff0c;可以私信我交流分享学习资料 那么开启正题 今天分享的是关于vector的题目 1.删除有序数组中的重复项 26. …...

《设计模式的艺术》笔记 - 观察者模式

介绍 观察者模式定义对象之间的一种一对多依赖关系&#xff0c;使得每当一个对象状态发生改变时&#xff0c;其相关依赖对象皆得到通知并被自动更新。 实现 myclass.h // // Created by yuwp on 2024/1/12. //#ifndef DESIGNPATTERNS_MYCLASS_H #define DESIGNPATTERNS_MYCLA…...

Java如何对OSS存储引擎的Bucket进行创建【OSS学习】

在前面学会了如何开通OSS&#xff0c;对OSS的一些基本操作&#xff0c;接下来记录一下如何通过Java代码通过SDK对OSS存储引擎里面的Bucket存储空间进行创建。 目录 1、先看看OSS&#xff1a; 2、代码编写&#xff1a; 3、运行效果&#xff1a; 1、先看看OSS&#xff1a; 此…...

ModuleNotFoundError: No module named ‘half_json‘

问题: ModuleNotFoundError: No module named ‘half_json’ 原因: 缺少jsonfixer包 解决方法: pip install jsonfixerjson修正包地址: https://github.com/half-pie/half-json...

深入探究 Android 内存泄漏检测原理及 LeakCanary 源码分析

深入探究 Android 内存泄漏检测原理及 LeakCanary 源码分析 一、什么是内存泄漏二、内存泄漏的常见原因三、我为什么要使用 LeakCanary四、LeakCanary介绍五、LeakCanary 的源码分析及其核心代码六、LeakCanary 使用示例 一、什么是内存泄漏 在基于 Java 的运行时中&#xff0…...

Linux CentOS使用Docker搭建laravel项目环境(实践案例详细说明)

一、安装docker # 1、更新系统软件包&#xff1a; sudo yum update# 2、安装Docker依赖包 sudo yum install -y yum-utils device-mapper-persistent-data lvm2# 3、添加Docker的yum源&#xff1a; sudo yum-config-manager --add-repo https://download.docker.com/linux/cen…...

第六课:Prompt

文章目录 第六课&#xff1a;Prompt1、学习总结&#xff1a;Prompt介绍预训练和微调模型回顾挑战 Pre-train, Prompt, PredictPrompting是什么?prompting流程prompt设计 课程ppt及代码地址 2、学习心得&#xff1a;3、经验分享&#xff1a;4、课程反馈&#xff1a;5、使用Mind…...

网络安全(初版,以后会不断更新)

1.网络安全常识及术语 资产 任何对组织业务具有价值的信息资产&#xff0c;包括计算机硬件、通信设施、IT 环境、数据库、软件、文档 资料、信息服务和人员等。 漏洞 上边提到的“永恒之蓝”就是windows系统的漏洞 漏洞又被称为脆弱性或弱点&#xff08;Weakness&#xff09;&a…...

开始学习Vue2(脚手架,组件化开发)

一、单页面应用程序 单页面应用程序&#xff08;英文名&#xff1a;Single Page Application&#xff09;简 称 SPA&#xff0c;顾名思义&#xff0c;指的是一个 Web 网站中只有唯一的 一个 HTML 页面&#xff0c;所有的功能与交互都在这唯一的一个页面内完成。 二、vue-cli …...

平替heygen的开源音频克隆工具—OpenVoice

截止2024-1-26日&#xff0c;全球范围内语音唇形实现最佳的应该算是heygen&#xff0c;可惜不但要魔法&#xff0c;还需要银子&#xff1b;那么有没有可以平替的方案&#xff0c;答案是肯定的。 方案1&#xff1a; 采用国内星火大模型训练自己的声音&#xff0c;然后再用下面…...

【自动化测试】读写64位操作系统的注册表

自动化测试经常需要修改注册表 很多系统的设置&#xff08;比如&#xff1a;IE的设置&#xff09;都是存在注册表中。 桌面应用程序的设置也是存在注册表中。 所以做自动化测试的时候&#xff0c;经常需要去修改注册表 Windows注册表简介 注册表编辑器在 C:\Windows\regedit…...

php二次开发股票系统代码:腾讯股票数据接口地址、批量获取股票信息、转换为腾讯接口指定的股票格式

1、腾讯股票数据控制器 <?php namespace app\index\controller;use think\Model; use think\Db;const BASE_URL http://aaaaaa.aaaaa.com; //腾讯数据地址class TencentStocks extends Home { //里面具体的方法 }2、请求接口返回内容 function juhecurl($url, $params f…...

uniapp 在static/index.html中添加全局样式

前言 略 在static/index.html中添加全局样式 <style>div {background-color: #ccc;} </style>static/index.html源码&#xff1a; <!DOCTYPE html> <html lang"zh-CN"><head><meta charset"utf-8"><meta http-…...

acrobat调整pdf的页码和实际页码保持一致

Acrobat版本 具体操作 现在拿到pdf的结构如下&#xff1a; pdf页码实际页码1-10页无页码数11页第1页 操作&#xff0c;选择pdf第10页&#xff0c;右键点击 具体设置 最终效果...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...