Golang 哈希表底层实现原理

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.rhkb.cn/news/296831.html

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

相关文章

.NET CORE 分布式事务(四) CAP实现最终一致性

目录 引言: 1.0 最终一致性介绍 2.0 CAP 2.0 架构预览 3.0 .NET CORE 结合CAP实现最终一致性分布式事务 3.1 准备工作(数据库,本文使用的是MySql) 3.1.1 数据模型 3.1.2 DbContext 3.1.3 数据库最终生成 3.2 Nuget引入 3.3 appsettings.json …

【漏洞复现】极简云 download.php 接口处存在任意文件读取漏洞

免责声明:文章来源互联网收集整理,请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失,均由使用者本人负责,所产生的一切不良后果与文章作者无关。该…

OpenHarmony实战:小型系统平台驱动移植

在这一步,我们会在源码目录//device/vendor_name/soc_name/drivers目录下创建平台驱动。 建议的目录结构: device ├── vendor_name │ ├── drivers │ │ │ ├── common │ │ │ ├── Kconfig # 厂商驱动内核菜单入口 │ …

武汉星起航电子商务公司领航跨境电商新纪元,助力品牌走向全球

在全球经济一体化的时代背景下,跨境电商正成为推动国际贸易增长的重要力量。武汉星起航电子商务有限公司,作为一家专注于提供一站式解决方案的跨境电商服务商,凭借其丰富的实战经验和专业团队,在行业中取得了令人瞩目的成绩。 自…

前端学习<四>JavaScript基础——02-JavaScript入门:hello world

开始写第一行 JavaScript:hello world JS 代码的书写位置在哪里呢?这个问题,也可以理解成:引入 JS 代码,有哪几种方式?有三种方式:(和 CSS 的引入方式类似) 行内式&…

前端(动态雪景背景+动态蝴蝶)

1.CSS样式 <style>html, body, a, div, span, table, tr, td, strong, ul, ol, li, h1, h2, h3, p, input {font-weight: inherit;font-size: inherit;list-style: none;border-spacing: 0;border: 0;border-collapse: collapse;text-decoration: none;padding: 0;margi…

014——超声波模块驱动开发Plus(基于I.MX6uLL、SR04和poll机制)

目录 一、基础知识 二、分析为什么打印会影响中断 三、驱动程序 四、应用程序 五、验证及其它 一、基础知识 013——超声波模块驱动开发&#xff08;基于I.MX6uLL与SR04&#xff09;-CSDN博客 二、分析为什么打印会影响中断 asmlinkage __visible int printk(const ch…

戴尔电脑Dell SupportAssist占用内存高,卸载Dell SupportAssist

咨询戴尔客服了解到&#xff0c;SupportAssist是机器出厂自带的一款应用&#xff0c;主要的功能是可以检查驱动更新以及做一些硬件方面的健康检测&#xff0c;有时候后台运行可能会导致进程占用内存比较大&#xff0c;导致访问被的应用崩溃。 咨询卸载不影响之后&#xff0c;然…

【Python系列】 yaml中写入数据

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

使用pytorch构建一个初级的无监督的GAN网络模型

在这个系列中将系统的构建GAN及其相关的一些变种模型&#xff0c;来了解GAN的基本原理。本片为此系列的第一篇&#xff0c;实现起来很简单&#xff0c;所以不要期待有很好的效果出来。 第一篇我们搭建一个无监督的可以生成数字 (0-9) 手写图像的 GAN&#xff0c;使用MINIST数据…

BugKu:Simple SSTI

1.进入此题 2.查看源代码 可以知道要传入一个名为flag的参数&#xff0c;又说我们经常设置一个secret_key 3.flask模版注入 /?flag{{config.SECRET_KEY}} 4.学有所思 4.1 什么是flask&#xff1f; flask是用python编写的一个轻量web开发框架 4.2 SSTI成因&#xff08;SST…

RIP协议(路由信息协议)

一、RIP协议概述 RIP协议&#xff08;Routing Information Protocol&#xff0c;路由信息协议&#xff09;是一种基于距离矢量的内部网关协议&#xff0c;即根据跳数来度量路由开销&#xff0c;进行路由选择。 相比于其它路由协议&#xff08;如OSPF、ISIS等&#xff09;&#…

Spring Cloud微服务入门(二)

微服务的技术栈 服务治理&#xff1a; 服务注册、发现、调用。 负载均衡&#xff1a; 高可用、集群部署。 容错&#xff1a; 避免雪崩、削峰、服务降级。 消息总线&#xff1a; 消息队列、异步通信&#xff0c;数据一致性。 网关&#xff1a; 校验路径、请求转发、服务集成…

使用Python获取红某书笔记详情并批量无水印下载

根据红某手最新版 请求接口必须要携带x-s x-s-c x-t,而调用官方接口又必须携带cookie,缺一不可,获取笔记详情可以通过爬取网页的形式获取&#xff0c;虽然也是无水印&#xff0c;但是一些详情信息只能获取大概&#xff0c;并不是详细的数值&#xff0c;因此既不想自己破解x-s x…

UE5 C++ LevelSequence

前言 最近在用UE C做一些功能&#xff0c;用到了Level Sequence功能&#xff0c;但是看了下UE官方论坛包括一些文章基本没有关于C 处理Level Sequence 这块内容&#xff0c;有的也是一些修改或者源码原理的一些内容分析&#xff0c;接下来我就把我新建Sequence包括一些库的调用…

# 达梦数据库知识点

达梦数据库知识点 测试数据 -- SYSDBA.TABLE_CLASS_TEST definitionCREATE TABLE SYSDBA.TABLE_CLASS_TEST (ID VARCHAR(100) NOT NULL,NAME VARCHAR(100) NULL,CODE VARCHAR(100) NULL,TITLE VARCHAR(100) NULL,CREATETIME TIMESTAMP NULL,COLUMN1 VARCHAR(100) NULL,COLUMN…

云容器引擎CCE弹性伸缩

CCE弹性伸缩介绍 CCE的弹性伸缩能力分为如下两个维度&#xff1a; 工作负载弹性伸缩&#xff1a;即调度层弹性&#xff0c;主要是负责修改负载的调度容量变化。例如&#xff0c;HPA是典型的调度层弹性组件&#xff0c;通过HPA可以调整应用的副本数&#xff0c;调整的副本数会…

ShardingJdbc+Mybatis实现多数据源

Mybatis多数据源 这个是对shardingjdbc应用的一个升级&#xff0c;如果对于shardingjdbc的整合还没看过之前的文章的&#xff0c;可以先看看文章https://blog.csdn.net/Think_and_work/article/details/137174049?spm1001.2014.3001.5501 整合步骤 1、依赖 和全新项目的单…

翻译: 硅谷软件工程师面试:准备所需的一切

没有人有时间去做成百上千道LeetCode题目&#xff0c;好消息是你实际上并不需要做那么多题目就能够在FAANG公司找到工作&#xff01; 我曾经在Grab工作&#xff0c;这是东南亚的一家共享出行公司&#xff0c;但我对工作感到沮丧&#xff0c;想要进入FAANG公司&#xff0c;但我…

Linux------一篇博客了解Linux最常用的指令

&#x1f388;个人主页&#xff1a;靓仔很忙i &#x1f4bb;B 站主页&#xff1a;&#x1f449;B站&#x1f448; &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;Linux &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#…