HashMap的put、get方法详解(附源码)

put方法

HashMap 只提供了 put 用于添加元素,putVal 方法只是给 put 方法调用的一个方法,并没有提供给用户使用。
对 putVal 方法添加元素的分析如下:如果定位到的数组位置没有元素 就直接插入。如果定位到的数组位置有元素就和要插入的 key 比较,如果 key 相同就直接覆盖,如果 key 不相同,就判断 p 是否是一个树节点,如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。
在这里插入图片描述
HashMap HashMap的put()方法用于向HashMap中添加键值对,当调用HashMap的put()方法时,会按照以下详细流程执行(JDK8 1.8版本):

第一步:根据要添加的键的哈希码计算在数组中的位置(索引)。
第二步:检查该位置是否为空(即没有键值对存在)

  • 如果为空,则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的键和值,并保存在数组的对应位置。将HashMap的修改次数(modCount)加1,以便在进行迭代时发现并发修改。

第三步:如果该位置已经存在其他键值对,检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同?

  • 如果相同,则表示找到了相同的键,直接将新的值替换旧的值,完成更新操作。

第四步:如果第一个键值对的哈希码和键不相同,则需要遍历链表或红黑树来查找是否有相同的键:

如果键值对集合是链表结构,从链表的头部开始逐个比较键的哈希码和equals()方法,直到找到相同的键或达到链表末尾。

  • 如果找到了相同的键,则使用新的值取代旧的值,即更新键对应的值。
  • 如果没有找到相同的键,则将新的键值对添加到链表的头部。

如果键值对集合是红黑树结构,在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码,定位到红黑树中的某个节点,然后逐个比较键,直到找到相同的键或达到红黑树末尾。

  • 如果找到了相同的键,则使用新的值取代旧的值,即更新键对应的值。
  • 如果没有找到相同的键,则将新的键值对添加到红黑树中。

第五步:检查链表长度是否达到阈值(默认为8):

  • 如果链表长度超过阈值,且HashMap的数组长度大于等于64,则会将链表转换为红黑树,以提高查询效率。

第六步:检查负载因子是否超过阈值(默认为0.75):

  • 如果键值对的数量(size)与数组的长度的比值大于阈值,则需要进行扩容操作。

第七步:扩容操作:

  • 创建一个新的两倍大小的数组。
  • 将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。
  • 更新HashMap的数组引用和阈值参数。

第八步:完成添加操作。
此外,HashMap是非线程安全的,如果在多线程环境下使用,需要采取额外的同步措施或使用线程安全的ConcurrentHashMap。

源码如下:

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// table未初始化或者长度为0,进行扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// (n - 1) & hash 确定元素存放在哪个桶中,桶为空,新生成结点放入桶中(此时,这个结点是放在数组中)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 桶中已经存在元素(处理hash冲突)else {Node<K,V> e; K k;//快速判断第一个节点table[i]的key是否与插入的key一样,若相同就直接使用插入的值p替换掉旧的值e。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 判断插入的是否是红黑树节点else if (p instanceof TreeNode)// 放入树中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 不是红黑树节点则说明为链表结点else {// 在链表最末插入结点for (int binCount = 0; ; ++binCount) {// 到达链表的尾部if ((e = p.next) == null) {// 在尾部插入新结点p.next = newNode(hash, key, value, null);// 结点数量达到阈值(默认为 8 ),执行 treeifyBin 方法// 这个方法会根据 HashMap 数组来决定是否转换为红黑树。// 只有当数组长度大于或者等于 64 的情况下,才会执行转换红黑树操作,以减少搜索时间。否则,就是只是对数组扩容。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 跳出循环break;}// 判断链表中结点的key值与插入的元素的key值是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等,跳出循环break;// 用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表p = e;}}// 表示在桶中找到key值、hash值与插入元素相等的结点if (e != null) {// 记录e的valueV oldValue = e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue == null)//用新值替换旧值e.value = value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 结构性修改++modCount;// 实际大小大于阈值则扩容if (++size > threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;
}

get方法

HashMap的get(Object key)方法用于根据指定的键(key)获取其对应的值(value)。当调用此方法时,会执行与put()方法类似的定位逻辑来查找节点,但过程相对简单,因为它不涉及修改操作。以下是详细的执行流程(JDK 8 1.8版本):

第一步:计算哈希值,定位数组索引

  • 首先,get(key)方法会调用内部的getNode(hash(key), key)方法。
  • getNode方法中,它会根据传入的key计算出其哈希码(hash value)。
  • 然后,通过位运算 (n - 1) & hash(其中n是HashMap内部数组的长度)来精确计算出该key应该位于数组的哪个索引位置(即哪个桶)。

第二步:检查桶内情况,优先检查第一个节点。

  • 定位到数组索引后,系统会检查该位置是否存在节点。
  • 如果该位置为null(即桶为空),则意味着Map中不存在这个keygetNode方法直接返回null
  • 如果该位置不为null,系统会进行一个快速判断:检查该桶中第一个节点的哈希值和key本身是否与要查找的key完全匹配(先比较hash,再用==equals()比较key)。
  • 如果第一个节点就匹配成功,则直接返回这个节点,查找结束。这是对无哈希冲突情况的优化。

第三步:处理哈希冲突,遍历链表或红黑树。

  • 如果第一个节点不匹配,并且该节点后面还存在其他节点(即first.next != null),则说明发生了哈希冲突,需要进一步在链表或红黑树中查找。
  • 判断数据结构:
    • 如果为红黑树:通过 first instanceof TreeNode 判断。如果是,则调用红黑树专属的getTreeNode()方法,在树中进行高效查找。
    • 如果为链表: 则从第二个节点开始,进入一个do-while循环,逐个向后遍历链表中的每个节点。
  • 遍历查找:
    • 在遍历链表或查找红黑树的过程中,对每个节点都进行哈希值和key的比较。
    • 如果在链表或红黑树中找到了完全匹配的节点,则立即返回该节点。
    • 如果遍历完整个链表或红黑树仍未找到匹配项,getNode方法将返回null

第四步:返回最终结果。

  • get方法会接收getNode方法的返回值(一个Node对象或null)。
  • 如果返回的节点对象不为nullget方法会提取并返回该节点的value值。
  • 如果返回的节点为null,则get方法最终也返回null,表示在HashMap中未找到指定的key

源码如下:

// get方法是getNode方法的封装,它处理了getNode返回null的情况
public V get(Object key) {Node<K,V> e;// 调用getNode获取节点,如果节点为null,则返回null,否则返回节点的valuereturn (e = getNode(hash(key), key)) == null ? null : e.value;
}/*** 实现Map.get()和相关方法*/
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 1. 检查table是否初始化,长度是否大于0,以及根据hash计算出的位置上是否有节点if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 2. 检查第一个节点,如果匹配,直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 3. 如果第一个节点不匹配,且存在后续节点if ((e = first.next) != null) {// 3.1 如果是红黑树,调用getTreeNode在树中查找if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 3.2 如果是链表,遍历链表查找do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 4. 如果table为空,或桶为空,或遍历完没找到,则返回nullreturn null;
}

参考链接:https://xiaolincoding.com/interview/collections.html#hashmap%E7%9A%84put%E8%BF%87%E7%A8%8B%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8B

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

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

相关文章

双立柱式带锯床cad【1张总图】+设计说明书+绛重

双立柱式带锯床 摘 要 随着机械制造技术的进步&#xff0c;制造业对于切割设备的精度、效率和稳定性要求越来越高。双立柱式带锯床作为一种重要的切割设备&#xff0c;必须能够满足工业生产对于高精度、高效率的需求。 双立柱式带锯床是一种重要的工业切割设备&#xff0c;其结…

在线JS解密加密配合ECC保护

在线JS解密加密配合ECC保护 1. ECC加密简介 定义 ECC&#xff08;Elliptic Curve Cryptography&#xff09;是一种基于椭圆曲线数学的公钥加密技术&#xff0c;利用椭圆曲线离散对数问题&#xff08;ECDLP&#xff09;实现高安全性。 背景 1985年&#xff1a;Koblitz&#xff0…

使用 Docker Compose 简化 INFINI Console 与 Easysearch 环境搭建

前言回顾 在上一篇文章《搭建持久化的 INFINI Console 与 Easysearch 容器环境》中&#xff0c;我们详细介绍了如何使用基础的 docker run 命令&#xff0c;手动启动和配置 INFINI Console (1.29.6) 和 INFINI Easysearch (1.13.0) 容器&#xff0c;并实现了关键数据的持久化&…

Word 怎么让段落对齐,行与行之间宽一点?

我们来分两步解决&#xff1a;段落对齐 和 调整行距。 这两个功能都集中在Word顶部的【开始】选项卡里的【段落】区域。 第一步&#xff1a;让段落对齐 “对齐”指的是段落的左右边缘如何排列。通常有四种方式。 操作方法&#xff1a;将鼠标光标点在你想修改的那个段落里的任意…

Attention机制完全解析:从原理到ChatGPT实战

一、Attention的本质与计算步骤 1.1 核心思想 动态聚焦&#xff1a;Attention是一种信息分配机制&#xff0c;让模型在处理输入时动态关注最重要的部分。类比&#xff1a;像人类阅读时用荧光笔标记关键句子。 1.2 计算三步曲&#xff08;以"吃苹果"为例&#xff09; …

2025年3月青少年电子学会等级考试 中小学生python编程等级考试三级真题答案解析(判断题)

博主推荐 所有考级比赛学习相关资料合集【推荐收藏】1、Python比赛 信息素养大赛Python编程挑战赛 蓝桥杯python选拔赛真题详解

HTML5 新特性详解:从语义化到多媒体的全面升级

很多小伙伴本都好奇&#xff1a;HTML5有什么功能是以前的HTML没有的&#xff1f; 今天就给大家说道说道 HTML5 作为 HTML 语言的新一代标准&#xff0c;带来了诸多革命性的新特性。这些特性不仅简化了前端开发流程&#xff0c;还大幅提升了网页的用户体验和功能性。本文将深入…

mac安装docker

1、下载docker-desktop https://www.docker.com/products/docker-desktop/2、安装&#xff0c;双击安装 3、优化docker配置 默认配置 cat ~/Library/Group\ Containers/group.com.docker/settings-store.json {"AutoStart": false,"DockerAppLaunchPath": …

mapbox进阶,绘制不随地图旋转的矩形,保证矩形长宽沿屏幕xy坐标方位

👨‍⚕️ 主页: gis分享者 👨‍⚕️ 感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏:mapbox 从入门到精通 文章目录 一、🍀前言1.1 ☘️mapboxgl.Map 地图对象1.2 ☘️mapboxgl.Map style属性1.3 ☘️line线图层样式1.4 ☘️circle点图层样…

${project.basedir}延申出来的Maven内置的一些常用属性

如&#xff1a;${project.basedir} 是 Maven 的内置属性&#xff0c;可以被 pom.xml 直接识别。它表示当前项目的根目录&#xff08;即包含 pom.xml 文件的目录&#xff09;。 Maven 内置的一些常用属性&#xff1a; 项目相关&#xff1a; ${project.basedir} <!-- 项…

[特殊字符] Python 批量生成词云:读取词频 Excel + 自定义背景 + Excel to.png 流程解析

本文展示如何用 Python 从之前生成的词频 Excel 文件中读取词频数据&#xff0c;结合 wordcloud 和背景图&#xff0c;批量生成直观美观的词云图。适用于文本分析、内容展示、报告可视化等场景。 &#x1f4c2; 第一步&#xff1a;读取所有 Excel 词频文件 import os from ope…

模拟网络请求的C++类设计与实现

在C开发中&#xff0c;理解和模拟网络请求是学习客户端-服务器通信的重要一步。本文将详细介绍一个模拟HTTP网络请求的C类库设计&#xff0c;帮助开发者在不涉及实际网络编程的情况下&#xff0c;理解网络请求的核心概念和工作流程。 整体架构设计 这个模拟网络请求的类库主要由…

移动机器人的认知进化:Deepoc大模型重构寻迹本质

统光电寻迹技术已逼近物理极限。当TCRT5000传感器在强烈环境光下失效率超过37%&#xff0c;当PID控制器在路径交叉口产生63%的决策崩溃&#xff0c;工业界逐渐意识到&#xff1a;导引线束缚的不仅是车轮&#xff0c;更是机器智能的演化可能性。 ​技术破局点出现在具身认知架构…

记录一次pip安装错误OSError: [WinError 32]的解决过程

因为要使用 PaddleOCR&#xff0c;需要安装依赖。先通过 conda新建了虚拟环境&#xff0c;然后安装 PaddlePaddle&#xff0c;继续安装 PaddleOCR&#xff0c;上述过程我是在 VSCode的终端中处理&#xff0c;结果报错如下&#xff1a;Downloading multidict-6.6.3-cp312-cp312-…

后端id设置long类型时,传到前端,超过19位最后两位为00

文章目录一、前言二、问题描述2.1、问题背景2.2、问题示例三、解决方法3.1、将ID转换为字符串3.2、使用JsonSerialize注解3.3、使用JsonFormat注解一、前言 在后端开发中&#xff0c;我们经常会遇到需要将ID作为标识符传递给前端的情况。当ID为long类型时&#xff0c;如果该ID…

SpringAI学习笔记-MCP客户端简单示例

MCP客户端是AI与外部世界交互的桥梁。在AI系统中&#xff0c;大模型虽然具备强大的认知能力&#xff0c;却常常受限于数据孤岛问题&#xff0c;无法直接访问外部工具和数据源。MCP协议应运而生&#xff0c;作为标准化接口解决这一核心挑战。该协议采用客户端-服务端架构&#x…

postgresql|数据库|系统性能监控视图pg_stat与postgresql数据库的调优(备忘)

一、 写作初衷 通常,我们使用navicat这样的数据库图形管理工具,只能看到用户层面的表,视图,而系统层面的表,视图,函数是无法看到的,这些表,视图和函数好像也可以称之为内模式;而这些视图,函数的作用是非常大的,其中pg_stat 族系统视图可以得到数据库的详细运行信息…

网络安全护网实战:攻击手段解析与防御策略

在网络安全领域&#xff0c;护网行动中对各类攻击方式和漏洞原理的掌握至关重要。本文将详细解析常见的攻击方式及其背后的漏洞原理&#xff0c;帮助大家提升护网技能。一、常见攻击方式及漏洞原理1. SQL注入漏洞• 定义&#xff1a;将恶意的数据库语句注入到后台数据库去执行&…

使用alist+RaiDrive+webdav将百度夸克网盘变为本地电脑磁盘方法教程

由于每天都要操作网盘不下十几次&#xff0c;频繁启动网盘比较麻烦。 使用百度夸克网盘的webdav服务可以将百度夸克网盘挂载到本地电脑上&#xff0c;就像操作本地电脑硬盘一样操作网盘&#xff0c;非常方便。我们以alistraidrive为例演示。 首先打开百度网盘pan.baidu.com&a…

C# 入门学习教程(二)

文章目录一、操作符详解1、操作符概览2、操作符的本质3、操作符的优先级4、同级操作符的运算顺序5、 各类操作符的示例二、表达式&#xff0c;语句详解1. 表达式的定义2. 各类表达式概览3. 语句的定义4. 语句详解一、操作符详解 C# 中的操作符是用于执行程序代码运算的符号&am…