【Golang】Golang的Map的底层原理

文章目录

  • 前言
  • 一、介绍
  • 二、使用方式
  • 三、总结


前言

在 Golang 编程中,map 是一种常用的数据结构,用于存储键值对。map 提供了高效的查找、插入和删除操作,是开发者在日常编程中不可或缺的工具。本文将详细介绍 Golang 中 map 的底层原理,帮助读者更好地理解 map 的实现机制和使用方法。


一、介绍

1. map 的基本概念

map 是一种哈希表(Hash Table),通过键(key)来快速查找对应的值(value)。在 Golang 中,map 的定义和使用非常简单

m := make(map[string]int)
m["foo"] = 42
fmt.Println(m["foo"])  // 输出:42

2. map 的底层结构
Golang 中的 map 底层实现是一个哈希表,主要由以下几个部分组成:

  • hmap 结构: 这是 Golang 中 map 的核心数据结构,定义在 runtime/map.go 文件中。hmap 结构包含了 map 的元数据和指向 bucket 数组的指针
- type hmap struct {count     int            // map 中的键值对数量flags     uint8          // 状态标志B         uint8          // bucket 数组的大小是 2^Bnoverflow uint16         // 溢出 bucket 的数量hash0     uint32         // 哈希种子buckets   unsafe.Pointer // 指向 bucket 数组的指针oldbuckets unsafe.Pointer // 扩容时指向旧的 bucket 数组nevacuate uintptr        // 扩容进度extra     *mapextra      // 额外的字段
}
  • bucket 结构: bucket 是 map 的底层存储单元,每个 bucket 存储若干个键值对。bucket 结构包含了键值对的数组和溢出指针。
type bmap struct {tophash [bucketCnt]uint8 // 哈希值的高 8 位keys    [bucketCnt]keytype // 键数组values  [bucketCnt]valuetype // 值数组overflow *bmap // 溢出指针
}

3.哈希函数: map 使用哈希函数将键映射到特定的 bucket。Golang 使用了一个高效的哈希函数来确保键值对均匀分布在各个 bucket 中,减少冲突。

4. 冲突处理
当多个键映射到同一个 bucket 时,会发生哈希冲突。Golang 通过链地址法(chaining)和溢出桶来处理冲突。链地址法在每个 bucket 中使用链表存储冲突的键值对,而溢出桶则用于存储超过容量的键值对。

  • 链地址法: 每个 bucket 中有一个溢出指针,当 bucket 满时,新的键值对会存储在溢出 bucket 中,形成一个链表结构。
type bmap struct {tophash [bucketCnt]uint8 // 哈希值的高 8 位keys    [bucketCnt]keytype // 键数组values  [bucketCnt]valuetype // 值数组overflow *bmap // 溢出指针
}

5. 扩容机制
当 map 中的键值对数量增加到一定程度时,Golang 会自动进行扩容。扩容时,map 会创建一个新的、更大的 bucket 数组,并将原有的键值对重新哈希到新的 bucket 中。扩容可以有效减少冲突,提高查找效率。

  • 扩容条件: 当 map 中的键值对数量超过一定阈值,或者溢出 bucket 的数量过多时,会触发扩容。
  • 扩容过程: 扩容时,map 会创建一个新的 bucket 数组,大小是原来的两倍。然后,将原有的键值对重新哈希到新的 bucket 中。

二、使用方式

1. 创建和初始化 map
在 Golang 中,可以使用 make 函数创建和初始化 map:

m := make(map[string]int)
m["foo"] = 42
fmt.Println(m["foo"])  // 输出:42

也可以使用字面量初始化 map:

m := map[string]int{"foo": 42,"bar": 84,
}
fmt.Println(m["foo"])  // 输出:42

2. 插入和更新键值对
可以通过键访问 map,并进行插入和更新操作:

m := make(map[string]int)
m["foo"] = 42  // 插入键值对
m["foo"] = 84  // 更新键值对
fmt.Println(m["foo"])  // 输出:84

3. 查找键值对
可以通过键查找 map 中的值:

m := make(map[string]int)
m["foo"] = 42
value, exists := m["foo"]
if exists {fmt.Println(value)  // 输出:42
} else {fmt.Println("key not found")
}

4. 删除键值对
可以使用 delete 函数删除 map 中的键值对:

m := make(map[string]int)
m["foo"] = 42
delete(m, "foo")
value, exists := m["foo"]
if !exists {fmt.Println("key not found")  // 输出:key not found
}

5. 遍历 map
可以使用 range 关键字遍历 map 中的所有键值对:

m := map[string]int{"foo": 42,"bar": 84,
}
for key, value := range m {fmt.Printf("%s: %d\n", key, value)
}

三、总结

Golang 中的 map 是一种高效的哈希表数据结构,通过哈希函数和冲突处理机制,实现了快速的查找、插入和删除操作。理解 map 的底层原理有助于开发者在实际编程中更好地使用 map,并优化程序性能。希望通过本文的介绍,读者能够深入了解 Golang 中 map 的实现机制和使用方法。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Linux学习笔记

九月二十六号: 三种网络连接的区别: 克隆的虚拟机文件可以放在另一台电脑上一样使用 LINUX目录结构: 查看linux IP地址的指令: ifconfig 查看ens33对应的 通过Xshell输入reboot会使linux重启 vim使用: 关机&重启命令&用户登录和注销: 用户管理: pwd: 显示当前在哪个…

数字信号处理-FPGA插入不同误码率的模拟源

module data_error_injector (input clk, // 时钟信号,50MHzinput reset, // 复位信号,高有效input DIN_EN, // 数据输入使能,高有效input [7:0] ERROR_LEVEL, // 错误等级…

华为OD机试 - 学生排名(Java 2024 E卷 100分)

华为OD机试 2024E卷题库疯狂收录中,刷题点这里 专栏导读 本专栏收录于《华为OD机试(JAVA)真题(E卷D卷A卷B卷C卷)》。 刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加…

快速学习Django框架以开发Web API

简介 Django是一个高级Python Web框架,它鼓励快速开发和简洁实用的设计。由经验丰富的开发者构建,Django可以为你处理大量的Web开发任务,使你能够专注于编写应用的关键组件。Django的模块化设计、可复用性和广泛的社区支持,使其成为开发Web应用和API的理想选择。 在本文中…

真·香!深度体验 zCloud 数据库云管平台 -- DBA日常管理篇

点击蓝字 关注我们 zCloud 作为一款业界领先的数据库云管平台,通过云化自治的部署能力、智能巡检和诊断能力、知识即代码的沉淀能力,为DBA的日常管理工作带来了革新式的简化与优化。经过一周的深度体验,今天笔者与您深入探讨 zCloud 在数据库…

探索PickleDB:Python中的轻量级数据存储利器

文章目录 探索PickleDB:Python中的轻量级数据存储利器1. 背景:为什么选择PickleDB?2. PickleDB是什么?3. 如何安装PickleDB?4. 简单的库函数使用方法创建和打开数据库设置数据获取数据删除数据保存数据库 5. 应用场景与…

PPT文件设置了修改权限,如何取消权?

不知道大家在使用PPT文件的时候,是否遇到过下面的提示框,这就是PPT文件设置了修改权限,只有输入密码才可以编辑文件。 如果我们没有输入密码,以只读方式进入,那么我们会发现功能栏中的按钮全是灰色,无法使用…

【测试工具篇一】全网最强保姆级教程抓包工具Fiddler(2)

本文接上篇Fiddler介绍,开始讲fiddler如何使用之前,给大家讲讲http以及web方面的小知识,方便大家后面更好得理解fiddler使用。 目录 一、软件体系结构---B/S与C/S架构 B/S架构 C/S架构 二、HTTP基础知识 什么是http请求和响应? http协…

健身房管理新纪元:SpringBoot技术应用

4系统概要设计 4.1概述 本系统采用B/S结构(Browser/Server,浏览器/服务器结构)和基于Web服务两种模式,是一个适用于Internet环境下的模型结构。只要用户能连上Internet,便可以在任何时间、任何地点使用。系统工作原理图如图4-1所示: 图4-1系统工作原理…

vue3 ref,shallowRef,reactive,shallowReactive使用的简单异同点说明

1、这几个都是负责data的存储及读取的&#xff0c;我们常用的是ref,reactive。 2、看一下shallowRef这个,shallowReactive与其类似。 说明&#xff1a;以官网的说明&#xff0c;这个state.value.count 2是不会触发视图更新的&#xff0c;但是如果直接在<script setup lang…

6.0、静态路由

路由器最主要的功能就是转发数据包。路由器转发数据包时需要查找路由表&#xff08;你可以理解为地图&#xff09;&#xff0c;管理员可以直接手动配置路由表&#xff0c;这就是静态路由。 1.什么是路由&#xff1f; 在网络世界中&#xff0c;路由是指数据包在网络中的传输路…

分分钟让你了解Web接口测试!

01 什么是接口 百度说&#xff1a;接口泛指实体把自己提供给外界的一种抽象化物&#xff08;可以为另一实体&#xff09;&#xff0c;用以由内部操作分离出外部沟通方法&#xff0c;使其能被内部修改而不影响外界其他实体与其交互的方式 上面这句有点抽象&#xff0c;网上的资…

Java8新特性/java

1.lambda表达式 区别于js的箭头函数&#xff0c;python、cpp的lambda表达式&#xff0c;java8的lambda是一个匿名函数&#xff0c;java8运行把函数作为参数传递进方法中。 语法格式 (parameters) -> expression 或 (parameters...) ->{ statements; }实战 替代匿名内部类…

如何在 uniapp 中实现图形验证码

全篇大概2000 字&#xff08;含代码&#xff09;&#xff0c;建议阅读时间10分钟。 什么是图形验证码&#xff1f; 图形验证码&#xff08;也称为图片验证码或验证码图像&#xff09;通常用于防止机器人自动提交表单&#xff0c;确保用户是人工操作。 一、需求 我们希望在一个…

基于 Java(SpringBoot)+MySQL 开发古诗词学习网站

古诗词系统设计与实现 引言 编写目的 为了保证项目团队按时保质地完成项目目标&#xff0c;便于项目团队成员更好地了解项目情况&#xff0c;使项目工作开展的各个过程合理有序&#xff0c;有必要以文件化的形式&#xff0c;把对于在项目生命周期内的工作任务范围、各项工作…

基于JavaWeb+MySQL实现口算题卡

爱 math 口算题卡 1. 总体要求 综合运用软件工程的思想&#xff0c;协同完成一个软件项目的开发&#xff0c;掌软件工程相关的技术和方法&#xff1b;组成小组进行选题&#xff0c;通过调研完成项目的需求分析&#xff0c;并详细说明小组成员的分工、项目的时间管理等方面。根…

Sibyl:提升复杂现实世界推理能力的LLM智能体框架

人工智能咨询培训老师叶梓 转载标明出处 大模型&#xff08;LLMs&#xff09;以其卓越的问题解决能力而闻名&#xff0c;这主要归功于它们内在的知识储备、强大的上下文学习能力以及零样本&#xff08;zero-shot&#xff09;能力。然而&#xff0c;这些基于LLM的智能体在长期推…

Jest项目实战(4):将工具库顺利迁移到GitHub的完整指南

开源代码&#xff1a;将工具库迁移到GitHub 随着项目的成熟和完善&#xff0c;将其开源不仅可以获得更多的用户和贡献者&#xff0c;还能促进项目本身的发展。GitHub作为全球最大的开源协作平台&#xff0c;自然成为了大多数开发者的首选。本文将引导您完成将工具库迁移至GitH…

ai面试辅助工具有哪些

目前市场上常见的AI面试辅助工具包括以下几款‌&#xff1a; ‌白瓜面试‌&#xff1a;这是一款专为在线面试和笔试场景设计的AI助手&#xff0c;支持实时语音识别、图片识别、智能辅助回答等功能&#xff0c;适用于多种岗位和面试平台‌ ‌Interview‌&#xff1a;这是一款基…

Redis - Zset 有序集合

一、基本认识 有序集合相对于字符串、列表、哈希、集合来说会有⼀些陌⽣。它保留了集合不能有重复成员的 特点&#xff0c;但与集合不同的是&#xff0c;有序集合中的每个元素都有⼀个唯⼀的浮点类型的分数&#xff08;score&#xff09;与之关 联&#xff0c;着使得有序集合中…