Golang 哈希表底层实现原理

news/2024/6/16 9:51:36/文章来源:https://blog.csdn.net/vince1998/article/details/137185380

1、本文讨论Golang的哈希表

Golang哈希表的实现,底层数据结构是数组+单链表,链表节点由8个key、value和键的高八位组成的。为了方便理解,先简单看一个图快速理解。
在这里插入图片描述

我们来看一下Golang哈希表的结构体定义
在这里插入图片描述

简单介绍一下结构体中几个关键的字段,hmap结构体就是Golang哈希表的底层结构体。

buckets为 哈希表 底层实际存储哈希表数据(数组+单链表)的指针变量

oldbuckets,也是存储哈希表数据(数组+单链表)的指针变量。但是,这个oldbuckets是用来存储 旧数据 的,用于在哈希表扩容时,渐进式扩容使用的,渐进式扩容结束时,oldbuckets指向的数据会被删除。后面我们再说扩容的事情。

count 表示当前哈希表中的元素数量,有一个很重要的意义就是,可以通过count知道渐进式扩容什么时候结束

hash0是哈希值的随机种子,这些都不是很重要。

extra是存储溢出桶的,溢出桶其实也是数组+单链表,可以简单理解成它的目的,是为了降低扩容频率而产生的

什么是桶,笔者理解其实就是那个底层数组。。。

介绍完关键几个字段,我们再看一张图便于理解

在这里插入图片描述

可以看到buckets指向的是一个数组,那么数组元素bmap就是一个“单链表”,所以才说Golang哈希表是数组+单链表,我们来看看bmap的数据结构

在这里插入图片描述

链表节点由8个keyvalue键的高八位组成的,overflow是指向下一个节点的指针,topbits就是8个键的高八位,作用是为了加速查找

其实到这里,你已经明白了哈希表整体的结构,那么我们来说说Golang哈希表是什么时候触发扩容扩容行为是什么

2、什么时候触发扩容

(1)溢出桶过多,也就是底层数组过长的时候
(2)负载因子达到某个阈值的时候

为什么溢出桶过多,也会触发扩容行为?

因为当溢出桶过多,但是桶中数据很少的时候。因为这时候键值对比较分散查找性能比较差,需要将键值对聚集一下

3、扩容行为有什么

(1)等量扩容

等量扩容,就是溢出桶过多,也就是底层数组过长的时候触发的,只是把键值对存储的更密集一些

(2)翻倍扩容

创建两倍桶数量两倍数组长度),然后将旧数据渐进式扩容的方式迁移旧数据,新数据直接写到新的桶中,我们看一个图方便理解,什么时候结束扩容?我们之前说了一个count字段,我们记录一下迁移了多少个,就知道是否完全迁移结束了

在这里插入图片描述

什么是渐进式扩容

①就是不一次性把数据复制过去,如果数据量多大,会短时间消耗大量性能

②首先把扩容前的桶标记为旧桶,
----1)查找操作,先看对应桶是否已经迁移没有迁移查旧桶,然后把对应桶数据迁移过去,迁移次数-1,如果迁移次数为0,就表示整个哈希表完成了迁移

更新、删除操作类似,先看是否完成迁移,没有迁移,先在旧桶完成迁移,再到新桶进行相应操作。

写文不易,给个点赞关注吧哈哈

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

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

相关文章

RK3568驱动指南|第十四篇 单总线-第157章 DS18B20驱动框架编写

瑞芯微RK3568芯片是一款定位中高端的通用型SOC,采用22nm制程工艺,搭载一颗四核Cortex-A55处理器和Mali G52 2EE 图形处理器。RK3568 支持4K 解码和 1080P 编码,支持SATA/PCIE/USB3.0 外围接口。RK3568内置独立NPU,可用于轻量级人工…

验证码项目(java实现)

1、Kaptcha详细配置 配置项 配置说明 默认值 kaptcha.border 图⽚边框,合法值:yes , no yes kaptcha.border.color 边框颜⾊,合法值: r,g,b (and optional alpha) 或者 white,black,blue black kaptcha.image.width 图⽚宽 200…

【MATLAB源码-第28期】基于matlab的16QAM定时同步仿真,采用gardner算法,Costa锁相环。

操作环境: MATLAB 2022a 1、算法描述 正交幅度调制(QAM,Quadrature Amplitude Modulation)是一种在两个正交载波上进行幅度调制的调制方式。这两个载波通常是相位差为90度(π/2)的正弦波,因此…

Docker安装教程

1. 安装yum 你的虚拟机需要联网以及yum哦~~ yum -y install docker-ce 1.1 NO package docker-ce available 在执行以上命令时出现以下错误。 NO package docker-ce available. Error: Nothing to do 解决方法: (1) 更新yum,使用yum -y upgrade(耗…

qt窗口的应用与pyinstaller打包APP操作

3月29日 qt打包APP操作 1 先在windows shell 中下载打包软件Pylnstaller pip install pyinstaller2 先进入py项目所在的位置,再执行以下代码(我用的qt版本是PySide6可以根据自己的情况修改) pyinstaller s02.py --noconsole --hidden-import PySide6.QtXml3 因为…

Junit深入讲解(JAVA单元测试框架)

1、此处用的是Junit5&#xff0c;此处pom文件需要引的依赖是 <dependency><groupId>org.junit.jupiter</groupId><artifactId>junit-jupiter-api</artifactId><version>5.9.1</version><scope>test</scope></depende…

Windows部署VisualSVN服务端结合Cpolar实现公网访问内网管理界面

文章目录 前言1. VisualSVN安装与配置2. VisualSVN Server管理界面配置3. 安装cpolar内网穿透3.1 注册账号3.2 下载cpolar客户端3.3 登录cpolar web ui管理界面3.4 创建公网地址 4. 固定公网地址访问 前言 SVN 是 subversion 的缩写&#xff0c;是一个开放源代码的版本控制系统…

蓝桥杯速成5-AD/DA模数转换

一、原理图 上图可知该芯片使用的是iic时序&#xff0c;而不是51单片机的xpt2046时序&#xff0c;iic我们都很熟悉了吧 并且大赛还提供了我们iic底层驱动代码 左上角有AIN0-4四个转换输入通道&#xff0c;和AOUT一个输出通道&#xff0c;由控制字节选择 地址字节&#xff1a;0x…

交通标志识别项目 | 基于Tensorflow+SSD实现道路交通标志识别

项目应用场景 面向智能驾驶或自动驾驶场景道路道路交通标志的识别&#xff0c;在交通标志识别的基础上为下一步的智能决策提供前提 项目效果&#xff1a; 项目细节 > 具体参见项目 README.md (1) 安装依赖 Python3.5、TensorFlow v0.12.0、Pickle、OpenCV-Python、Matplotl…

如何在Ubuntu系统部署Z-blog博客结合cpolar实现无公网IP访问本地网站

文章目录 1. 前言2. Z-blog网站搭建2.1 XAMPP环境设置2.2 Z-blog安装2.3 Z-blog网页测试2.4 Cpolar安装和注册 3. 本地网页发布3.1. Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试5. 结语 1. 前言 想要成为一个合格的技术宅或程序员&#xff0c;自己搭建网站制作网页是绕…

Rust 机器学习图形库 petgraph

一、介绍 Petgraph 是一个开源的图数据结构库&#xff0c;提供了非常丰富的图形类型和算法&#xff0c;并且支持将图形以 Graphviz 格式输出&#xff0c;还允许你为图的节点和边赋予任意类型的数据&#xff0c;从而能够灵活地处理和表示复杂的数据关系。 Petgraph 支持边的方…

FFmpeg 详解

FFmpeg 详解 FFmpeg 详解整体结构不同下载版本的区别常用库常用函数初始化封装格式解码器 版本对比组件注册方式对比FFmpeg 3.x 组件注册方式FFmpeg 4.x 组件注册方式 结构体比对函数对比avcodec_decode_video2()vcodec_encode_video2() 数据结构结构体分析AVFormatContextAVIn…

安全SCDN的威胁情报库对DDOS防护有什么好处

目前网络攻击事件频频发生&#xff0c;DDoS&#xff08;分布式拒绝服务&#xff09;攻击已成为各种企业&#xff08;小到区域性小公司大到各种跨国公司&#xff09;的主要威胁&#xff0c;DDoS 攻击可能会对企业造成重大损害和破坏&#xff0c;比如对目标公司的业务造成产生不利…

什么是ISP住宅IP?相比于普通IP它的优势是什么?

什么是ISP住宅IP&#xff1f; ISP住宅IP是指由互联网服务提供商&#xff08;ISP&#xff09;分配给住宅用户的IP地址。它是用户在家庭网络环境中连接互联网的标识符&#xff0c;通常用于上网浏览、数据传输等活动。ISP住宅IP可以是动态分配的&#xff0c;即每次连接时都可能会…

HarmonyOS 应用开发之PageAbility组件

PageAbility组件概述 PageAbility是包含UI、提供展示UI能力的应用组件&#xff0c;主要用于与用户交互。 开发者通过DevEco Studio开发平台创建PageAbility时&#xff0c;DevEco Studio会自动创建相关模板代码。PageAbility相关能力通过单独的featureAbility实现&#xff0c;…

每天五分钟深度学习:神经网络和深度学习有什么样的关系?

本文重点 神经网络是一种模拟人脑神经元连接方式的计算模型&#xff0c;通过大量神经元之间的连接和权重调整&#xff0c;实现对输入数据的处理和分析。而深度学习则是神经网络的一种特殊形式&#xff0c;它通过构建深层次的神经网络结构&#xff0c;实现对复杂数据的深度学习…

mongodb sharding分片模式的集群数据库,日志治理缺失导致写入数据库报错MongoWriteConcernException的问题总结(下)

一、接着上文 上文介绍了mongodb sharding的分片集群搭建&#xff0c;本文侧重于讲述日志治理。 这里使用linux自带的日志治理工具logrotate&#xff0c;无论是哪个端口的进程&#xff0c;其日志治理方式类似。 查看/data目录下的文件大小&#xff0c; du -hs *二、Logrota…

Docker_介绍

Docker概念介绍 1. Docker架构 从上图得知&#xff0c;Docker分为三部分&#xff0c;客户端&#xff0c;Docker服务端&#xff0c;仓库。 1.1 客户端 平常我们使用的就是客户端&#xff0c;通过客户端命令和Docker引擎进行交互 Docker 是一个客户端-服务器&#xff08;C/S&…

安卓Termux系统安装MariaDB结合内网穿透实现公网连接本地数据库

文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备&#xff0c;尽管最初并非设计为服务器&#xff0c;但是随着技术的进步我们可以将Android配置为生产力工具&#xff0c;变成一个随身…

Docker Desktop 在 Windows 上的安装和使用

目录 1、安装 Docker Desktop 2、使用 Docker Desktop &#xff08;1&#xff09;运行容器 &#xff08;2&#xff09;查看容器信息 &#xff08;3&#xff09;数据挂载 Docker Desktop是Docker的官方桌面版&#xff0c;专为Mac和Windows用户设计&#xff0c;提供了一个简…