go-map+sync.map的底层原理
map
哈希冲突解决方式
1.拉链法
2.开放地址法
底层结构
Go 的
map
在源码中由runtime.hmap
结构体表示,buckets-指向桶数组的指针(常规桶),oldbuckets-扩容时指向旧桶数组的指针。
type hmap struct {count int // 当前元素个数(len(map) 直接返回此值)flags uint8 // 状态标志(是否正在扩容、迭代等)B uint8 // 桶的数量为 2^B(哈希桶数量的对数)noverflow uint16 // 溢出桶的大致数量hash0 uint32 // 哈希种子,用于计算键的哈希值buckets unsafe.Pointer // 指向桶数组的指针(常规桶)oldbuckets unsafe.Pointer // 扩容时指向旧桶数组的指针nevacuate uintptr // 扩容时记录下一个要迁移的桶编号extra *mapextra // 可选字段,用于管理溢出桶
}
bmap结构
type bmap struct {// 1. 哈希值的高8位数组(快速比较)tophash [bucketCnt]uint8 // bucketCnt默认为8,每个桶最多存8个键值对// 2. 键数组(具体类型由map定义决定)keys [bucketCnt]KeyType // 例如int、string等// 3. 值数组(具体类型由map定义决定)values [bucketCnt]ValueType// 4. 溢出桶指针(链表结构,处理哈希冲突)overflow *bmap
}
tophash [bucketCnt]uint8 // bucketCnt默认为8,每个桶最多存8个键值对
作用:存储每个键哈希值的前8位,用于快速过滤不匹配的键。一个key会通过哈希函数得到一个哈希值(高八位就是tophash ),哈希值再对map的数量取模得到桶下标,找到自己存放的位置。
keys [bucketCnt]KeyType // 例如int、string等
values [bucketCnt]ValueType
- 容量:每个
bmap
最多存储8个键值对。- 内存排列:
- 键和值分开存储:键数组(
keys
)和值数组(values
)在内存中连续分布。- 对齐优化:根据键和值的大小调整内存对齐,减少碎片。
overflow *bmap
- 作用:当桶已满时,新键值对存入溢出桶,形成链表。
- 示例:
- 插入第9个键值对时,创建新的
bmap
,链接到overflow
指针。- 查找时需遍历链表直到找到匹配项或链表末尾。
为什么键和值要分开存放?
- 键和值分开存储:键数组(
keys
)和值数组(values
)在内存中连续分布。 - 对齐优化:根据键和值的大小调整内存对齐,减少碎片。
map中一个key的查找过程?
1. 哈希计算与桶定位
- 计算键的哈希值
hash := hashFunc(key, h.hash0)
。- 通过掩码运算定位桶:
bucketIndex := hash & (2^B - 1)
(B
为桶数量的指数)。- 确定目标桶
bmap
。2. 桶内查找与插入
遍历
tophash
数组,寻找空槽或匹配的高8位:
- 空槽:
tophash[i] == 0
,表示可插入新键值对。- 匹配:
tophash[i] == hashHigh
,需进一步比较键是否相等。如果key不相等说明槽位被占了,那么查找下一个为空的槽位,如果找到最后发现槽位被占满那么就通过overflow 创建新的bmap插入数据。
go语言中的map怎么解决哈希冲突的?
利用了两种方法拉链法和开放法,看上面的题目回答。
map中一个key的删除过程?
通过哈希值的高八位查找到一个桶的tophash位置,然后把tophash标记为emptyOne的状态,如果当前tophash位置后面所有的位置为空,那么就将当前位置标记为emptyReset状态,这样如果下一次遍历到了emptyReset就不会往后进行查找,提高了查询的效率。
map的扩容
扩容时机
负载因子超标,负载因子超过为 6.5触发双倍扩容。一个桶能存放八个元素,负载因子为6.5的时候表示一个桶中位置快被分配完了,一个桶快满了,很有可能需要遍历溢出桶,那么就会触发双倍扩容。
溢出桶的数量过多的话就触发等量扩容。插入元素过多就会有溢出桶,然后又删除元素,但是map的删除元素不会释放内存,再进行元素的插入,这样会导致元素的排列很松散。所以需要等量扩容重新排列元素位置,让内存更加紧密。
等量扩容
等量扩容:并不扩大容量,buckets数量维持不变,重新做一遍搬迁动作,把松散的键值对重新排列一次,使得同一个 bucket 中的 key 排列地更紧密,节省空间,提高 bucket 利用率,进而保证更快的存取。
双倍扩容
双倍扩容:新建一个buckets数组,新的buckets数量大小是原来的2倍,然后I日buckets数据搬迁到新的buckets.
扩容方式?
map采用渐进式扩容的方式,再插入修改key的时候,会进行元素的搬迁,每一次搬迁1-2个元素,从旧桶中找到一个当前访问的key-value,还有一个是通过迁移编号找到的key-value值,每次移动两个元素,再到新桶中做哈希运算重新放入新桶。
syncmap
Go 语言中的 sync.Map
是专为并发场景设计的线程安全 map,其底层结构通过 读写分离 和 无锁原子操作 优化性能,尤其适合读多写少的场景。
底层结构
type Map struct {mu sync.Mutex // 互斥锁,保护 dirty 的并发写操作read atomic.Value // 存储只读数据(readOnly 结构),通过原子操作访问dirty map[interface{}]*entry // 存储可写数据,访问时需要加锁misses int // 记录从 read 读取失败的次数,触发 dirty 提升为 read
}
type readOnly struct {m map[interface{}]*entry // 存储键值对的指针(entry)amended bool // 标记 dirty 中是否有 read 中不存在的键
}
如果amend为true那么就从dirty当中操作.
type entry struct {p unsafe.Pointer // 指向实际值的指针(可能为 nil、expunged 标记或具体值)
}
entry
的状态管理,p有三种状态,
- 正常值:
entry.p
指向实际值。- 删除标记:
entry.p = nil
(逻辑删除)。- 完全删除:
entry.p = expunged
(一个特殊标记指针),表示键已从dirty
移除。
有几种方法
Store(),更新插入一个key-value
Load(),返回对应的value
Delete(),删除
Range(),对map进行遍历
sync.map插入流程
- 如果read当中不包含这个元素的话,那么就对dirty进行操作,获取锁操作dirty。
- 如果read当中有这个元素并且对应entry指向的状态为nil或者为正常值,直接修改read的值
- 如果read当中有这个元素并且对应entry指向的状态为
expunged
的状态的话,那么不光要在read当中进行修改,还要在dirty当中插入新值。
sync.map删除流程
从read当中找到对应的数据,然后通过entry指针把指向的value置为nil。
如果read当中找不到对应的值,但是存在于dirty,就把dirty当中对应的entry指针指向
expunged状态,
表示键已从dirty
移除。
read map和dirty map怎么互相转换的?
dirty->read
从
read
无锁读取:
- 通过原子操作获取
read.m
,查找键对应的entry
。- 若找到且
entry.p != nil
,直接返回值如果没有找到,那么加锁访问
dirty
,从dirty
读取,并增加misses
计数。当
misses >= len(dirty)
时,将dirty
提升为read
,重置dirty把dirty置空
和misses
。
read->dirty
考虑到dirty->read的情况,在最后将
dirty
提升为read后
,会重置dirty
把dirty置空。此时dirty为空,read不为空。
如果要插入新的数据那么只能从dirty中进行插入,但此时dirty为空,所以dirty需要复制read当中的数据(这个过程就是dirty的重塑),把read当中value的状态=nil的值都标记成expunged状态,那么dirty不会对expunged状态的值进行复制。
相关文章:
go-map+sync.map的底层原理
map 哈希冲突解决方式 1.拉链法 2.开放地址法 底层结构 Go 的 map 在源码中由 runtime.hmap 结构体表示,buckets-指向桶数组的指针(常规桶),oldbuckets-扩容时指向旧桶数组的指针。 type hmap struct {count int // 当前元素个数(len…...
日语学习-日语知识点小记-进阶-JLPT-N2阶段(6): - (1)ても てでも特别强调(2)~もしないで = 聞かないで:根本不做某动作”
日语学习-日语知识点小记-进阶-JLPT-N2阶段(6): - (1)ても てでも特别强调(2)~もしないで 聞かないで:根本不做某动作”。 1、前言(1)情况说…...
读文献方法
虽然读了很多文献,但是并不代表我把读文献这件事真的做到了极致。因此不断优化迭代,反思自己哪里做的不好,非常重要。 阅读学术论文时,采用结构化、分阶段的策略可以显著提高效率。以下是针对这篇流体力学论文的高效阅读方法&…...
对象存储概述
对象存储概述 1. 定义与基本概念 对象存储(Object-based Storage)是一种新型网络存储架构,其核心是将数据作为对象(Object)进行管理,每个对象包含数据本身、元数据(Metadata)和唯一…...
Grallvm技术介绍
GrallVM介绍 GraalVM核心特性 GraalVM 是由 Oracle 开发的高性能运行时环境,基于 HotSpot JVM 构建,支持多语言互操作和 Ahead-of-Time (AOT) 编译。以下是其核心特性: 核心技术 Graal JIT 编译器:替代传统 JVM 的 C2 编译器&am…...
matlab 环形单层柱状图
matlab 环形单层柱状图 matlab 环形单层柱状图 matlab 环形单层柱状图 图片 图片 【图片来源粉丝】 我给他的思路是:直接使用风玫瑰图可以画出。 rose_bar 本次我的更新和这个有些不同!是环形柱状图,可调节细节多; 只需要函数…...
Java调用LLM大模型 - 基于 Spring AI 实现
Spring AI Alibaba实战:Java集成通义千问构建流式对话应用 一、Spring AI核心架构解析 1.1 框架定位与优势对比 graph TDA[Spring AI] --> B[统一API接口]A --> C[多模型支持]A --> D[企业级特性]B --> E(OpenAI/Azure/阿里云)C --> F(LLaMA/Qwen…...
RK | rk3568开发与学习
RK | rk3568开发与学习 时间:2025年4月19日17:20:28 文章目录 RK | rk3568开发与学习1.参考2.资料3.初次使用连接串口网络连接有线连接SSH登录 1.参考 Rockchip: Rockchip-瑞芯微电子股份有限公司 正点原子: 1.正点原子RK3568开发板瑞芯微Linux嵌入式ARM…...
使用Service发布前后端应用程序
使用Service发布前后端应用程序 文章目录 使用Service发布前后端应用程序[toc]一、创建并发布后端应用程序二、创建并发布前端应用程序三、通过前端发送流量进行测试 部署前端(Frontend)微服务和后端(Backend)微服务是比较常见的应…...
测试第四课---------性能测试
作者前言 🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂 🎂 作者介绍: 🎂🎂 🎂 🎉🎉🎉…...
数据结构(6)——队列
目录 前言 一、队列的概念及其结构 二、实现 2.1结构体定义 2.2初始化 2.3销毁链表 2.4尾插入(入队) 2.5头删(出队) 2.6个数 2.7检验是否为空 2.8取队头数据 2.9取队尾数据 三、检验 总结 前言 本文介绍队列&#x…...
在RK3588上使用ZLMediaKit
在RK3588上使用ZLMediaKit ZLMediaKit是一个高性能的流媒体服务器框架,可以在RK3588平台上运行。以下是在RK3588上使用ZLMediaKit的指南: 1. 环境准备 首先确保你的RK3588开发板已安装好Linux系统(如Debian或Ubuntu)。 安装依…...
分布式系统核心原理
CAP定理与权衡实践 CAP定理 一致性(Consistency) 强一致性:所有读写操作均基于最新数据(如银行转账)。 最终一致性:数据副本经过一段时间后达到一致(如社交媒体的点赞数)。 技术实现…...
【进程信号】五、信号集操作接口详解
文章目录 Ⅰ. 操作sigset_t变量接口Ⅱ. sigprocmask(阻塞信号集)Ⅲ. sigpending(未决信号集)Ⅳ. 接口使用代码⚜️sigaction(捕捉信号)Ⅴ. 测试sigaction的一些场景Ⅰ. 操作sigset_t变量接口 还记得我们上面讲过的 sigset_t 类型吗,sigset_t 类型对于每种信号用一个…...
Doris 本地部署集群重启后报错
报错描述 Docker 版本: apache/doris:fe-2.1.9 apache/doris:be-2.1.9 连接 MySQL 报错: ERROR 2003 (HY000): Cant connect to MySQL server on 127.0.0.1:9030 (111)FE 日志: INFO (UNKNOWN fe_e7cff187_69d4_42ee_90be_147e87310549(-1…...
bat脚本转换为EXE应用程序文件
很多时候,我们使用电脑时会编辑bat脚本文件 很多时候,我们制作的玩笑,病毒也会使用这个格式. 但这个格式也有很多缺点 1,如果是需要管理员运行的程序,需要费劲的自己使用管理员身份运行 2,文件并不为大家所熟知,认同度不高 3,可以非常轻松的看到原代…...
爬虫入门与requests库的使用——python爬虫
文章目录 浏览器抓包浏览器抓包介绍浏览器抓包页面介绍 python 爬虫爬虫是什么web网页渲染的方式http 协议http协议对资源的操作requests 库requests 是什么requests 的安装requests库的基础使用requests中不同的请求方式GET传递参数POST传递参数响应内容定制请求头Cookie获取服…...
[Java EE] Spring 配置 和 日志
目录 1. 配置文件 1.1 作用 1.2 Spring Boot 配置文件 1.3 读取配置文件 1.3.1 配置对象 1.3.2 配置集合 1.3.3 配置Map 1.4 yml 优缺点 2. 日志 2.1 日志的作用 2.2 日志的使用 2.3 日志框架 2.3.1 门面模式(外观模式) 2.4 SLF4J 框架介绍 2.5 日志格式的说明 …...
如何0基础学stm32?
如何0基础学stm32? 作为一个混迹嵌入式领域十余年的老兵,每次看到"0基础学STM32"这样的提问,我都忍不住想笑,又有些无奈。这就像问"如何0基础学开飞机"一样—虽然理论上可行,但过程恐怕没那么愉快…...
XCZU27DR‑2FFVE1156I Xilinx Zynq UltraScale+ RFSoC
一、概述 XCZU27DR‑2FFVE1156I 属于 Zynq UltraScale™ RFSoC Gen 2 系列,采用 TSMC 16 nm FinFET 工艺,Speed Grade ‑2,集成了 ARM 处理系统、可编程逻辑与高性能射频数据转换单元,为软件定义无线电、5G 前端、测试测量等场景…...
取值运算符*和地址运算符
在指针的学习中,必不可少的两个操作符:*和&。 在定义一个指针的时候,比如 short *p; 表示一个指向short数据类型的指针,具体表达的意思就是这个指针P指向的一个数据类型是short类型,也就是说操作的这…...
LNA设计
设计目的 为后级提供足够的增益以克服后级电路噪声 尽可能小的噪声和信号失真 确保输入和输出端的阻抗匹配 确保信号线性度 评价标准 噪声系数 功率增益 工作频率和带宽 输入信号功率动态范围 端口电压驻波比 稳定性 基于SP模型的LNA设计 直流分析 S参数分析 设计指标 …...
FPGA——DDS信号发生器设计
文章目录 任务要求一、DDS简介二、设计过程1、相位累加器的设计2、波形存储器设计3、锁相环倍频电路设计4、顶层电路设计 三、设计实现四、运行结果总结参考资料 任务要求 1)利用DDS技术合成正弦波和方波; 2)输出信号的频率范围为10Hz~5MHz,…...
【网络编程】TCP数据流套接字编程
目录 一. TCP API 二. TCP回显服务器-客户端 1. 服务器 2. 客户端 3. 服务端-客户端工作流程 4. 服务器优化 TCP数据流套接字编程是一种基于有连接协议的网络通信方式 一. TCP API 在TCP编程中,主要使用两个核心类ServerSocket 和 Socket ServerSocket Ser…...
数据可视化(Matplotlib和pyecharts)
一 常见图形概念及使用 图表类型适用场景核心特点柱状图(bar)比较不同类别数据(如各地区销售额对比)、时间序列分析(离散时间)高度反映数值大小,支持横向/纵向展示,可叠加分组折线图(plot)连续数据趋势比较(适合展示随时间的变化,如股票价格走势、用户增长趋势)、多变…...
如何系统地入门学习stm32?
如何系统地入门学习stm32? 作为一个在嵌入式领域摸爬滚打十余年的工程师,看到这个问题,我不禁想起自己当年啃着厚重的数据手册,对着一块蓝色的PCB板冥思苦想的日子。STM32的学习之路,说难不算特别难,说简单…...
matlab读取CMEMS海洋温度数据并调整图片的比例
matlab读取CMEMS海洋温度数据并调整图片的比例 matlab读取CMEMS海洋温度数据并调整图片的比例 matlab读取CMEMS海洋温度数据并调整图片的比例 数据的下载见上期: 链接到CMEMS数据下载{python} 本文还会给出另一个关键技巧: 通常设置图片比列直接可以通过…...
ReSearch:基于强化学习的大语言模型推理搜索框架
ReSearch是一种创新性框架,通过强化学习技术训练大语言模型执行"推理搜索",无需依赖推理步骤的监督数据。该方法将搜索操作视为推理链的有机组成部分,其中搜索的时机与方式由基于文本的推理过程决定,而搜索结果进一步引…...
【记录】服务器安装ffmpeg
前言 因为项目中需要用到 ffmpeg 进行图像的一些操作,本文记录下在服务器安装 ffmpeg 的全过程,还是具有一定挑战性的。 系统详情 本文使用的操作系统详情如下 通过 命令 cat /etc/os-release 获取 虽然操作系统为 Rocky Linux,但安装过程是通用的,因为本文记录的是从源代码…...
部署rocketmq集群
容器化部署RocketMQ5.3.1集群 背景: 生产环境单机的MQ不具有高可用,所以我们应该部署成集群模式,这里给大家部署一个双主双从异步复制的Broker集群 一、安装docker yum install -y docker systemctl enable docker --now # 单机部署参考: https://www.cnblogs.com/hsyw/p/1…...
中国AIOps行业分析
基本术语 AIOps是"Artificial Intelligence for IT Operations"(IT运维人工智能)的缩写,它指的是将人工智能技术应用于IT运维领域,基于已有的运维数据(如日志、监控信息、应用信息等),通过机器学习的方式解决自动化运维无法解决的问题6。AIOps将机器学习(ML)…...
C++入门[超详细]
#include <iostream c的标准输入输出流 C的域 using namespace std; namespace本质是一个域 只有域里面的定义代码才能使用 std包含了c输入输出的标准库 缺省 只能从左到右缺省,不能中间空格 void f1(int a10,int b20,int c0) { } f1(); f1(1); f1(1,2); f1(1,2,3); f1(…...
字符串系列一>二进制求和
目录 题目:解析:代码: 题目: 链接: link 解析: 代码: class Solution {public String addBinary(String a, String b) {StringBuffer ret new StringBuffer();int t 0;char[] aa a.toCharArray();char[…...
序列化和反序列化
概念 创建出来的这些对象都存在于JVM中的堆(heap)内存中,只有JVM处于运行状态的时候,这些对象才可能存在。当JVM停止,这些对象也就随之消失。 java序列化可以帮我们实现:将这些对象持久化,并且…...
rebase和merge的区别
目录 1. 合并机制与提交历史 2. 冲突处理方式 3. 历史追溯与团队协作 4. 推荐实践 5. 撤销难度 git rebase和git merge是Git中两种不同的分支合并策略,核心区别在于提交历史的处理方式:merge保留原始分支结构并生成合并提交&am…...
linux查看目录相关命令
查看目录命令 学习目标 能够使用Linux命令查看目录信息 1. 查看目录命令的使用 命令说明ls查看当前目录信息tree以树状方式显示目录信息 ls命令效果图: tree命令效果图: 2. 查看当前目录路径 命令说明pwd查看当前目录路径 pwd命令效果图: 3. 清除终端内容 命令说明clear…...
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val val 的节点,并返回 新的头节点 。 示例 1: 输入:head [1,2,6,3,4,5,6], val 6 输出:[1,2,3,4,5]示例 2: 输入:…...
Cursor新版0.49.x发布
小子看到 Cursor 0.49.x 版本正式发布,截止今天已经有两个小patch版本!本次更新聚焦于 自动化Rules生成、改进的 Agent Terminal 以及 MCP 图像支持,并带来了一系列旨在提升编码效率和协作能力的改进与修复。 以下是本次更新的详细内容&…...
music21:伍佰 泪桥 MIDI 音乐分析
以下是使用 music21 对伍佰《泪桥》MIDI 音乐进行分析的一些可能方面: 基本信息3 曲长:全曲长 2 分 31 秒。音符数量:共 273 个音符。音轨信息:共 2 个音轨,其中 1 个音轨有音符,可视为单轨 MIDI 文件&am…...
Mybatis源码01-SpringBoot启动时mybatis加载过程
使用了mybatis这么久还没有具体探究了SpringBoot启动时候对于mybatis是怎么加载的。 1、首先项目构建时我们会引入相关的依赖: <dependency><groupId>org.mybatis.spring.boot</groupId><artifactId>mybatis-spring-boot-starter</arti…...
springCloud/Alibaba常用中间件全集(上)
文章目录 SpringCloud:一、Consul:服务注册与发现1、下载Consul2、运行Consul3、服务注册①. 导入依赖②. 配置yml③. 启动类添加Consul的启动服务发现注解④. 解决 **硬编码** 问题⑤. 此时便可以将IP地址改为服务名 4、服务配置与刷新①. 引入Consul-Config依赖②. 修改boots…...
嵌入式单片机通过ESP8266连接物联网实验
第一:通过手机APP远程监控和控制 ESP8266驱动RST低电平触发复位,平时需要跟EN一样分别接10k拉高到3.3V 如果是12E/F的话管脚比较多,GPIO15也要接个1K到地 烧录时GPIO要接地,正常工作时将其拉高或者悬空 主要使用串口通信,烧录固件也是通过串口,烧录时,启动烧录程序后…...
Visio导出清晰图片步骤
在Visio里画完图之后如何导出清晰的图片?👇 ①左上角单击【文件】 ②导出—更改文件类型—PNG/JPG ③分辨率选择【打印机】,大小选择【源】,即可。 ④选择保存位置并命名 也可以根据自己需要选择是否需要【透明底】哈。 选PNG 然…...
速查手册:TA-Lib 超过150种量化技术指标计算全解 - 1. Overlap Studies(重叠指标)
速查手册:TA-Lib 超过150种量化技术指标计算全解 - 1. Overlap Studies(重叠指标) TA-Lib(Technical Analysis Library)是广泛使用的金融技术分析库,实现了超过150种技术指标计算函数,适用于股票…...
大模型Rag - 如何评估Rag
一.RAG流程与评估标准补充 RAG(Retrieval-Augmented Generation)是一种结合检索与生成的问答架构。为了确保系统效果,需要从以下三个角度对其评估: 回顾RAG流程 用户提出问题 → 系统检索相关上下文 → 基于上下文由大语言模型…...
复习JUC的总结笔记
JUC基础 调用Thread的start方法会调用start0,start0会调用该Thread类的run方法。Thread类如果传入了Runnable,run方法里会调用Runnable的run方法,如果没有传入,则什么也不会做。也可以通过重写Thread的run方法,让start…...
基于MTF的1D-2D-CNN-GRU-Attention时序图像多模态融合的故障识别,适合研究学习(Matlab完整源码和数据),附模型研究报告
基于MTF的1D-2D-CNN-GRU-Attention时序图像多模态融合的故障识别,适合研究学习(Matlab完整源码和数据),附模型研究报告 目录 基于MTF的1D-2D-CNN-GRU-Attention时序图像多模态融合的故障识别,适合研究学习(…...
5G 毫米波滤波器的最优选择是什么?
新的选择有很多,但到目前为止还没有明确的赢家。 蜂窝电话技术利用大量的带带,为移动用途提供不断增加的带宽。 其中的每一个频带都需要透过滤波器将信号与其他频带分开,但目前用于手机的滤波器技术可能无法扩展到5G所规划的全部毫米波&#…...
构造函数和析构函数
概念:对象的初始化和清理是非常重要的,一个对象在使用之前,需要进行初始化,使用完成后也需要及时清理数据,简单来说构造函数时用来初始化成员属性的,析构函数时用来清理数据的。 C中利用构造函数和析构函数…...
卷积神经网络(CNN)详解
文章目录 引言1.卷积神经网络(CNN)的诞生背景2.卷积神经网络(CNN)介绍2.1 什么是卷积神经网络?2.2 卷积神经网络(CNN)的基本特征2.2.1 局部感知(Local Connectivity)2.2.…...