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

HashMap源码分析:put与get方法详解

 HashMap源码分析:put与get方法详解

引言

HashMap是Java集合框架中最重要且最常用的数据结构之一,它提供了高效的键值对存储和检索功能。本文将深入分析HashMap的核心方法——put和get的源码实现,帮助开发者更好地理解HashMap的内部工作机制。

HashMap基本结构

在深入方法分析之前,我们先了解HashMap的基本结构:

- HashMap基于哈希表实现,使用数组+链表+红黑树(JDK8+)的结构
- 默认初始容量为16,负载因子为0.75
- 当链表长度超过8且数组长度大于64时,链表会转换为红黑树

put方法源码分析

 put方法入口

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

put方法调用了putVal方法,其中`hash(key)`计算了key的哈希值。

hash方法

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash方法通过将key的hashCode高16位与低16位进行异或运算,增加了哈希值的随机性,减少了哈希冲突。

putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 步骤1:如果table为空或长度为0,则进行resize初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 步骤2:计算索引位置,如果该位置为空,直接创建新节点if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 步骤3:节点已存在,判断是否为相同keyif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 步骤4:判断是否为树节点else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 步骤5:处理链表情况else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 链表长度超过8,转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 找到相同key的节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 步骤6:key已存在,替换valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 步骤7:检查是否超过阈值,需要扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

putVal方法的主要步骤:

1. 检查并初始化table数组
2. 计算索引位置,如果该位置为空,直接创建新节点
3. 如果该位置已有节点,判断是否为相同key
4. 如果是树节点,调用树节点的插入方法
5. 如果是链表,遍历链表查找相同key或插入到链表末尾
6. 如果找到相同key,替换value
7. 检查是否需要扩容

get方法源码分析

get方法入口

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}

get方法同样先计算key的哈希值,然后调用getNode方法。

getNode方法

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且索引位置有节点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) {// 步骤4:如果是树节点,调用树查找if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 步骤5:遍历链表查找do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

getNode方法的主要步骤:

1. 检查table数组是否初始化且索引位置是否有节点
2. 检查第一个节点是否匹配
3. 如果有后续节点,继续查找
4. 如果是树节点,调用树查找方法
5. 如果是链表,遍历链表查找匹配节点

性能分析

- put操作:平均时间复杂度O(1),最坏情况(所有key哈希冲突)O(n)或O(log n)(树化后)
- get操作:平均时间复杂度O(1),最坏情况O(n)或O(log n)

关键点总结

1. 哈希计算:HashMap通过hash方法优化了key的哈希值分布
2. 冲突解决:使用链表和红黑树解决哈希冲突
3. 动态扩容:当元素数量超过阈值时自动扩容
4. 树化优化:链表过长时转换为红黑树提高查询效率

最佳实践

1. 作为key的对象必须正确实现hashCode和equals方法
2. 预估元素数量,设置合理的初始容量以减少扩容次数
3. 考虑使用自定义对象作为key时的性能影响

结语

通过深入分析HashMap的put和get方法源码,我们不仅理解了其工作原理,也掌握了性能优化的关键点。HashMap的设计体现了空间换时间和分治思想,是Java集合框架中的经典实现。理解这些底层机制有助于我们在实际开发中更合理地使用HashMap,并能够针对特定场景进行优化。

http://www.lryc.cn/news/583193.html

相关文章:

  • 爬楼梯及其进阶
  • Kubernetes 存储入门
  • 由 DB_FILES 参数导致的 dg 服务器无法同步问题
  • 搭建一款结合传统黄历功能的日历小程序
  • 汽车智能化2.0引爆「万亿蛋糕」,谁在改写游戏规则?
  • A1220LUA-T Allegro高精度霍尔效应开关 车规+极致功耗+全极触发 重新定义位置检测标准
  • 【Gin】HTTP 请求调试器
  • 微软官方C++构建工具:历史演变、核心组件与现代实践指南
  • Rust与Cypress应用
  • 在Ubuntu上安装配置 LLaMA-Factory
  • 人工智能-基础篇-27-模型上下文协议--MCP到底怎么理解?对比HTTP的区别?
  • AI应用实践:制作一个支持超长计算公式的计算器,计算内容只包含加减乘除算法,保存在一个HTML文件中
  • Apache Tomcat SessionExample 漏洞分析与防范
  • 【AI大模型】PyTorch Lightning 简化工具
  • Node.js 是什么?npm 是什么? Vue 为什么需要他们?
  • Flutter基础(前端教程⑦-Http和卡片)
  • 【数字后端】- Standard Cell Status
  • SQLZoo 练习与测试答案汇总(复杂题有最优解与其他解法分析、解题技巧)
  • Java 各集合接口常用方法对照表
  • 解决SQL Server SQL语句性能问题(9)——SQL语句改写(7)
  • 如何识别SQL Server中需要添加索引的查询
  • nl2sql的解药pipe syntax
  • Linux入门篇学习——Linux 编写第一个自己的命令
  • 一天一道Sql题(day04)
  • 详解Kafka重平衡机制详解
  • Vue+ElementUI聊天室开发指南
  • Vue3 Element plus table有fixed列时错行
  • 7.神经网络基础
  • 【深度学习】【入门】Sequential的使用和简单神经网络搭建
  • 【机器学习】BeamSearch算法