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

【Golang 面试题】每日 3 题(十五)

✍个人博客:Pandaconda-CSDN博客
📣专栏地址:http://t.csdnimg.cn/UWz06
📚专栏简介:在这个专栏中,我将会分享 Golang 面试中常见的面试题给大家~
❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创作的最大动力💪

43. Go Map 的扩容条件

  1. 条件 1:超过负载
  • map 元素个数 > 6.5 * 桶个数
func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactor*bucketShift(B)
}
其中
bucketCnt = 8,一个桶可以装的最大元素个数
loadFactor = 6.5,负载因子,平均每个桶的元素个数
bucketShift(B): 桶的个数
  1. 条件 2:溢出桶太多
  • 当桶总数 < 2 ^ 15 时,如果溢出桶总数 >= 桶总数,则认为溢出桶过多。
  • 当桶总数 >= 2 ^ 15 时,直接与 2 ^ 15 比较,当溢出桶总数 >= 2 ^ 15 时,即认为溢出桶太多了。
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {// If the threshold is too low, we do extraneous work.// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.// "too many" means (approximately) as many overflow buckets as regular buckets.// See incrnoverflow for more details.if B > 15 {B = 15}// The compiler does not see here that B < 16; mask B to generate shorter shift code.return noverflow >= uint16(1)<<(B&15)
}

对于条件 2,其实算是对条件 1 的补充。因为在负载因子比较小的情况下,有可能 map 的查找和插入效率也很低,而第 1 点识别不出来这种情况。

表面现象就是负载因子比较小比较小,即 map 里元素总数少,但是桶数量多(真实分配的桶数量多,包括大量的溢出桶)。比如不断的增删,这样会造成 overflow 的 bucket 数量增多,但负载因子又不高,达不到第 1 点的临界值,就不能触发扩容来缓解这种情况。这样会造成桶的使用率不高,值存储得比较稀疏,查找插入效率会变得非常低,因此有了第 2 扩容条件。

44. Go Map 的扩容机制

  • 双倍扩容:针对条件 1,新建一个 buckets 数组,新的 buckets 大小是原来的 2 倍,然后旧 buckets 数据搬迁到新的 buckets。该方法我们称之为双倍扩容.
  • 等量扩容:针对条件 2,并不扩大容量,buckets 数量维持不变,重新做一遍类似双倍扩容的搬迁动作,把松散的键值对重新排列一次,使得同一个 bucket 中的 key 排列地更紧密,节省空间,提高 bucket 利用率,进而保证更快的存取。该方法我们称之为等量扩容。

45. Go Map 的扩容函数:

上面说的 hashGrow() 函数实际上并没有真正地 “搬迁”,它只是分配好了新的 buckets,并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中,而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或修改、删除 key 的时候,都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否搬迁完毕,具体来说就是检查 oldbuckets 是否为 nil。

func hashGrow(t *maptype, h *hmap) {// 如果达到条件 1,那么将B值加1,相当于是原来的2倍// 否则对应条件 2,进行等量扩容,所以 B 不变bigger := uint8(1)if !overLoadFactor(h.count+1, h.B) {bigger = 0h.flags |= sameSizeGrow}// 记录老的bucketsoldbuckets := h.buckets// 申请新的buckets空间newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)// 注意&^ 运算符,这块代码的逻辑是转移标志位flags := h.flags &^ (iterator | oldIterator)if h.flags&iterator != 0 {flags |= oldIterator}// 提交grow (atomic wrt gc)h.B += biggerh.flags = flagsh.oldbuckets = oldbucketsh.buckets = newbuckets// 搬迁进度为0h.nevacuate = 0// overflow buckets 数为0h.noverflow = 0// 如果发现hmap是通过extra字段 来存储 overflow buckets时if h.extra != nil && h.extra.overflow != nil {if h.extra.oldoverflow != nil {throw("oldoverflow is not nil")}h.extra.oldoverflow = h.extra.overflowh.extra.overflow = nil}if nextOverflow != nil {if h.extra == nil {h.extra = new(mapextra)}h.extra.nextOverflow = nextOverflow}
}

由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址,如果 map 存储了数以亿计的 key-value,一次性搬迁将会造成比较大的延时,因此 Go map 的扩容采取了一种称为 “渐进式” 的方式,原有的 key 并不会一次性搬迁完毕,每次最多只会搬迁 2 个 bucket。

func growWork(t *maptype, h *hmap, bucket uintptr) {// 为了确认搬迁的 bucket 是我们正在使用的 bucket// 即如果当前key映射到老的bucket1,那么就搬迁该bucket1。evacuate(t, h, bucket&h.oldbucketmask())// 如果还未完成扩容工作,则再搬迁一个bucket。if h.growing() {evacuate(t, h, h.nevacuate)}
}

需要注意的是,在 Map 进行扩容时,可能会导致哈希冲突的数量增加,因此扩容后的 Map 的性能可能会有所下降。为了避免这种情况,可以考虑在创建 Map 时指定初始容量,以减少扩容的次数。

相关文章:

【Golang 面试题】每日 3 题(十五)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/UWz06 &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 Golang 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏…...

Docker命令(用法说明详解)

一、常见Docker容器命令 #根据image创建一个新容器并运行&#xff08;即使该image已经存在容器&#xff0c;也会再创建一个新容器&#xff09; docker run IMAGE_NAME #根据image创建一个新容器并运行。 #选项-d&#xff1a;指定容器为后台运行&#xff0c;--name自定义该容器…...

leetcode 热题100(131. 分割回文串)c++

链接&#xff1a;131. 分割回文串 - 力扣&#xff08;LeetCode&#xff09; 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1&#xff1a; 输入&#xff1a;s "aab" 输出&#xff…...

vs2022编译opencv 4.10.0

参考&#xff1a;Windosw下Visual Studio2022编译OpenCV与参考区别在于&#xff0c;没有用cmake GUI&#xff0c;也没有创建build目录&#xff0c;直接用vs2022打开了C:\code\opencv目录&#xff0c;即CMakeLists.txt所在根目录。没有修改默认下载地址&#xff0c;采用手动下载…...

Bash 中的 2>1 | tee 命令详解

Bash 中的 2>&1 | tee 命令详解 在 Linux 和 Unix 系统中&#xff0c;命令行提供了强大的输出控制功能&#xff0c;能够灵活地处理标准输入&#xff08;stdin&#xff09;、标准输出&#xff08;stdout&#xff09;和标准错误&#xff08;stderr&#xff09;。本文将详…...

MySQL数据库的日志

一、概论 日志&#xff08;log&#xff09;是一种记录系统运行时各种状态和事件的文件。 它通常用于系统监控、故障排查、安全审计和性能分析。日志文件可以记录用户操作、系统错误、应用程序行为等信息。日志文件通常包含时间戳、事件类型、事件描述等关键信息&#xff0c;以…...

DataCap 2024.4.1 版本发布:MongoDB 驱动支持、工作流引擎升级

尊敬的 DataCap 用户&#xff1a; DataCap 2024.4.1 版本现已正式发布。本次更新包含多项重要功能升级和性能优化&#xff0c;现将主要更新内容公布如下&#xff1a; 核心功能升级 数据库功能增强 (实现功能) 新增数据库管理功能&#xff1a;支持创建、删除和切换数据库完善表…...

二十三种设计模式-单例模式

单例模式&#xff08;Singleton&#xff09;&#xff1a;确保一个类只有一个实例&#xff0c;并提供一个全局访问点。 单例模式两种实现方法&#xff1a;懒汉式和饿汉式。 懒汉式&#xff08;Lazy Initialization&#xff09; 懒汉式单例模式在第一次被使用时才创建实例&…...

【微服务】SpringBoot 国际化适配方案使用详解

目录 一、前言 二、国际化概述 2.1 微服务中的国际化是什么 2.1.1 国际化概念 2.1.2 为什么需要国际化 2.2 微服务中常用的国际化方法 2.2.1 资源文件分离 2.2.2 使用国际化框架 2.2.3 使用动态模板 2.2.4 使用数据库存储 2.2.5 API设计结合配置中心 三、SpringBoot…...

太阳能电池板缺陷识别数据集,使用yolo,coco json,pasical voc xml格式标注,可识别旁路二极管,电池故障,热点,2234张原始图片

太阳能电池板缺陷识别数据集&#xff0c;使用yolo&#xff0c;coco json&#xff0c;pasical voc xml格式标注&#xff0c;可识别旁路二极管,电池故障,热点,2234张原始图片 以下是该项目的一些用例&#xff1a; 太阳能发电厂监控&#xff1a;该模型可用于自动化检查和识别大型…...

客户案例:基于慧集通平台集成打通小满CRM+金蝶云星空+钉钉

一、引言 本案例原型公司是一家生物科技公司&#xff0c;公司自开创以来专注于体外诊断生物活性原材料的研究、生产、销售和服务&#xff0c;致力于为全球体外诊断试剂生产企业提供领先且具有竞争力的核心原料和相关辅助产品服务。公司以卓越的产品和优质的服务赢得了客户的广…...

ubuntu 如何使用vrf

在Ubuntu或其他Linux系统中&#xff0c;您使用ip命令和sysctl命令配置的网络和内核参数通常是临时的&#xff0c;这意味着在系统重启后这些配置会丢失。为了将这些配置持久化&#xff0c;您需要采取一些额外的步骤。 对于ip命令配置的网络接口和路由&#xff0c;您可以将这些配…...

Debian-linux运维-ssh配置(兼容Jenkins插件的ssh连接公钥类型)

系统版本&#xff1a;Debian 12.5、11.1 1 生成密钥对 可以用云服务商控制台生成的密钥对&#xff0c;也可以自己在客户端或者服务器上生成&#xff0c; 已经有密钥对就可以跳过这步 用户默认密钥文件路径为 ~/.ssh/id_rsa&#xff0c;可以在交互中指定路径&#xff0c;也可…...

K8S详解(5万字详细教程)

目录 ​编辑 一、集群管理命令 二、命名空间 1. 获取命名空间列表 2. 创建命名空间 3. 删除命名空间 4. 查看命名空间详情 三、Pod 1. Pod概述 2. Pod相位状态 3. 管理命令 3.1 获取命名空间下容器(pod)列表 3.2 查看pod的详细信息 3.3 创建 && 运行 3.4 …...

Redis6为什么引入了多线程?

大家好&#xff0c;我是锋哥。今天分享关于【Redis6为什么引入了多线程&#xff1f;】面试题。希望对大家有帮助&#xff1b; Redis6为什么引入了多线程&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Redis 6 引入了多线程的主要目的是提高性能&#…...

KMP 2024 年总结,Kotlin 崛起的一年

2024 Google I/O 上正式官宣了 KMP&#xff08;Kotlin Multiplatform&#xff09;项目&#xff0c;它是 Google Workspace 团队的一项长期「投资」项目&#xff0c;由 JetBrains 开发维护和开源的项目&#xff0c;简单来说&#xff0c;JetBrains 主导&#xff0c;Google Worksp…...

leecode188.买卖股票的最佳时机IV

这道题目我在买卖股票III就已经得出规律了&#xff0c;具体可看买卖股票的最佳时机||| class Solution { public:int maxProfit(int k, vector<int>& prices) {int nprices.size();vector<vector<int>> dp(n,vector<int>(2*k1,0));for(int j1;j&l…...

分布式消息队列RocketMQ

一、RocketMQ概述 1.1 MQ 概述 MQ&#xff0c;Message Queue&#xff0c;是一种提供消息队列服务的中间件&#xff0c;也成为消息中间件&#xff0c;是一套提供了消息生产、存储、消费全过程API的软件系统。消息即数据 1.2 MQ 用途 MQ的用途总结起来可分为以下三点 限流削峰…...

诗韵--代码之外的生活:2025 元旦歌

2025 元旦歌 1 说明2 正文3 简评 1 说明 又是一年元旦&#xff0c;在公司抽个空&#xff0c;写首诗纪念一下。 本系列博客&#xff1a;诗韵–代码之外的生活 2 正文 2025 元旦歌 一年又一年&#xff0c; 又到新元旦。 恍若零五年&#xff0c; 已是二五年。 工作忙连连&#x…...

SpringBoot项目启动的时候,指定jvm内存大小的3种方式

1. 通过命令行固定参数 在命令行中运行 Spring Boot 应用程序时&#xff0c;可以使用 -Xms 和 -Xmx 选项指定初始和最大堆内存大小。例如&#xff1a; java -Xms512m -Xmx1024m -jar mySpringBootApp.jar 优点&#xff1a; 简单明了 缺点&#xff1a; 是写死的&#xff0c;…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

React hook之useRef

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

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...