【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: HashMap是基于Map接口构建的数据结构,它以键值对的形式存储元素,允许键和值都为null。由于键的唯一性,HashMap中只能有一个键为null。HashMap的特点是元素的无序性和不重复性。

知识盲点

在这里插入图片描述

概念介绍

HashMap是基于Map接口构建的数据结构,它以键值对的形式存储元素,允许键和值都为null。由于键的唯一性,HashMap中只能有一个键为null。HashMap的特点是元素的无序性和不重复性。

注意,HashMap并不是线程安全的。在多线程环境下,如果不进行适当的同步处理,可能会导致数据不一致或其他并发问题。因此,对于需要高并发访问的场景,建议使用线程安全的替代方案,如ConcurrentHashMap

数据结构

在HashMap的数据结构中,数组和链表是核心组件,但它们在实现上有着根本性的差异。

  • 数组是静态的,一旦创建,其大小就无法改变
    • 数组由于其固定的大小,对于大量数据的处理可能会遇到性能瓶颈。
  • 链表是动态的,可以根据需要随时添加或删除节点。
    • 链表则可以灵活地扩展,更好地应对数据增长的需求,链表在内存使用上可能更加碎片化,因为需要为新节点分配空间并在不再需要时进行回收。

      数组

数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

链表

链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

数组VS链表

  • 数组的特点:查询效率高,插入和删除效率低
  • 链表的特点:查询效率低,插入和删除效率高

哈希表

综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?这就是我们要提起的哈希表。哈希表既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。

非同步和允许使用null之外,HashMap类与Hashtable大致相同。此类不保证映射的顺序,特别是它不保证该顺序恒久不变发生扩容时,元素位置会重新分配

不同JVM版本HashMap的展现形式

JDK8之后的版本,HashMap底层使用数组加(链表或红黑树)的结构完美的解决了数组和链表的问题(循环死锁问题),使的查询和插入,删除的效率都很高。
在这里插入图片描述
HashMap的散列表是懒加载机制,在第一次put的时候才会创建hash表

HashMap VS HashTable

在多线程环境中,HashMap由于其非线程安全的特性,性能可能更高。相比之下,Hashtable通过在实现方法中添加synchronized关键字确保线程安全,因此在性能上可能稍逊一筹。

如果没有特殊需求,建议在常规使用中选择HashMap,多线程环境下,如果需要线程安全的集合,可以使用Collections.synchronizedMap()方法将HashMap转换为线程安全的集合

特性区别对比

在这里插入图片描述

  • 是否允许键为空:值得一提的是,HashMap允许键为null,而Hashtable的键则不可为null。

  • 继承结构的不同 :HashMap是对Map接口的直接实现,而Hashtable不仅实现了Map接口,还继承了Dictionary抽象类。

    • 在这里插入图片描述
    • 在这里插入图片描述
  • 扩充数据量不同 :关于初始容量和扩容策略,HashMap的初始容量为16,而Hashtable的初始容量为11。两者的填充因子默认都是0.75。当需要扩容时,HashMap的容量会翻倍,即capacity * 2; 而Hashtable的容量会在原有基础上增加1,即capacity * 2 + 1。

  • 数据安全的问题 :在单线程环境下或对性能要求较高的场景中,HashMap可能是一个更好的选择。而在多线程环境中,如果需要确保线程安全,则应考虑使用Hashtable或通过Collections.synchronizedMap()方法将HashMap转换为线程安全的集合。

hashcode

在HashMap中,当我们要存储一个键值对时,首先会调用对象的hashCode()方法来获取哈希码。这个哈希码的主要目的是为了确定对象在哈希表中的位置。

为了得到一个更均匀的分布,提高查找效率,hashCode()返回的整数会经过一系列的位操作(如右移和异或)来进一步处理。这些操作的主要目的是为了打乱哈希码的高位和低位,使得不同的键产生的哈希码有更好的随机性,从而减少冲突的可能性。

hashCode的作用

hashCode的存在主要是为了查找的快捷性, hashCode是用来在散列存储结构中确定对象的存储地址的 (用hashcode来代表对象在hash表中的位置) 。

hashCode存在的重要的原因之一就是在HashMap(HashSet其实就是HashMap)中使用(其实Object类的hashCode方法注释已经说明了)。

HashMap之所以速度快,因为他使用的是散列表,根据key的hashcode值生成数组下标(通过内存地址直接查找,不需要判断,但是需要多出很多内存,相当于以空间换时间)

equals方法和hashcode的关系

若重写了equals(Object obj)方法,则有必要重写hashCode()方法
在这里插入图片描述

  • 若两个对象equals(Object obj)返回true,则hashCode()有必要也返回相同的int数
  • 若两个对象equals(Object obj)返回false,则hashCode()不一定返回不同的int数
  • 若两个对象hashCode()返回相同int数,则equals(Object obj)不一定返回true
  • 若两个对象hashCode()返回不同int数,则equals(Object obj)一定返回false

同一对象在执行期间若已经存储在集合中,则不能修改影响hashCode值的相关信息,否则会导致内存泄露问题。

key为null怎么办

key为null的时候,只会放在hashMap的0位置(即key的hashCode为0,对数组长度取余后的下标也是0),不会有链表在HashMap源码中对put方法对null做了处理。

  1. key为null的判断后进入putForNullKey(V value)这个方法,里面for循环是在table[0]链表中查找key为null的元素。

  2. 如果找到,则将value重新赋值给这个元素的value,并返回原来的value。如果没找到则将这个元素添加到table[0]链表的表头。

执行步骤

  • 计算原始哈希码:调用对象的hashCode()方法来获取一个原始的哈希码。
  • 计算哈希表索引:对原始哈希码进行位操作(如右移和异或),与Bucket大小进行取模,得到一个最终的哈希表索引。这个索引用于确定对象在哈希表中的位置。

核心参数

HashMap的实例有两个参数影响其性能:初始容量和加载因子。

  • 容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。
  • 加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度

迭代collection视图所需的时间与HashMap实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

容量探讨

HashMap的最小树形化容量,这个值的意义是:位桶(bin)处的数据要采用红黑树结构进行存储时,整个Table的最小容量(存储方式由链表转成红黑树的容量的最小阈值)当哈希表中的容量大于这个值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化为了避免进行扩容、树形化选择的冲突,这个值不能小于4 * TREEIFY_THRESHOLD(16)

如果很多映射关系要存储在HashMap实例中,则相对于按需执行自动的rehash操作以增大表的容量来说,使用足够大的初始容量创建它将使得映射关系能更有效地存储。

负载因子探讨

加载因子是用于控制哈希表中元素数量与内部数组大小之间关系的参数。

加载因子过高

加载因子越高,哈希表中的元素数量可以更多,但同时可能导致更多的冲突,从而增加查询成本。

加载因子与空间开销

当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行rehash操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数,通常,默认加载因子(0.75)在时间和空间成本上寻求一种折衷。

当加载因子设置得较高时,哈希表中的元素数量可以更多,从而减少了当内部数组需要扩容时所浪费的空间。这似乎是节省了空间,但实际上,这也意味着更高的冲突可能性。

查询成本与加载因子

当哈希表中的元素数量增加时,发生冲突的可能性也增加。这意味着查找特定键的时间会增加,因为可能需要遍历更长的链表(或红黑树,如果链表长度过长)。因此,高的加载因子会增加查询成本。

减少扩容次数和成本

设置初始容量与加载因子

在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少rehash操作次数,如果初始容量大于最大条目数除以加载因子,则不会发生rehash操作。

  • 减少扩容的次数:如果你预计哈希表将包含大量元素,那么选择一个较大的初始容量可能是一个好主意。

  • 较大的初始容量:如果初始容量大于(最大条目数除以加载因子),那么不会发生rehash操作。这意味着,为了减少rehash次数,你可能需要选择一个较大的初始容量。

总结

加载因子是一个权衡参数。高的加载因子可以减少空间浪费,但可能会增加查询成本和rehash操作的次数。

相关文章
|
14天前
|
数据采集 人工智能 Java
Java产科专科电子病历系统源码
产科专科电子病历系统,全结构化设计,实现产科专科电子病历与院内HIS、LIS、PACS信息系统、区域妇幼信息平台的三级互联互通,系统由门诊系统、住院系统、数据统计模块三部分组成,它管理了孕妇从怀孕开始到生产结束42天一系列医院保健服务信息。
28 4
|
21天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
54 2
|
25天前
|
Java
轻松上手Java字节码编辑:IDEA插件VisualClassBytes全方位解析
本插件VisualClassBytes可修改class字节码,包括class信息、字段信息、内部类,常量池和方法等。
75 6
|
8天前
|
Java 数据库连接 开发者
Java中的异常处理机制:深入解析与最佳实践####
本文旨在为Java开发者提供一份关于异常处理机制的全面指南,从基础概念到高级技巧,涵盖try-catch结构、自定义异常、异常链分析以及最佳实践策略。不同于传统的摘要概述,本文将以一个实际项目案例为线索,逐步揭示如何高效地管理运行时错误,提升代码的健壮性和可维护性。通过对比常见误区与优化方案,读者将获得编写更加健壮Java应用程序的实用知识。 --- ####
|
17天前
|
Java 测试技术 API
Java 反射机制:深入解析与应用实践
《Java反射机制:深入解析与应用实践》全面解析Java反射API,探讨其内部运作原理、应用场景及最佳实践,帮助开发者掌握利用反射增强程序灵活性与可扩展性的技巧。
|
22天前
|
存储 算法 Java
Java Set深度解析:为何它能成为“无重复”的代名词?
Java的集合框架中,Set接口以其“无重复”特性著称。本文解析了Set的实现原理,包括HashSet和TreeSet的不同数据结构和算法,以及如何通过示例代码实现最佳实践。选择合适的Set实现类和正确实现自定义对象的hashCode()和equals()方法是关键。
26 4
|
25天前
|
人工智能 监控 数据可视化
Java智慧工地信息管理平台源码 智慧工地信息化解决方案SaaS源码 支持二次开发
智慧工地系统是依托物联网、互联网、AI、可视化建立的大数据管理平台,是一种全新的管理模式,能够实现劳务管理、安全施工、绿色施工的智能化和互联网化。围绕施工现场管理的人、机、料、法、环五大维度,以及施工过程管理的进度、质量、安全三大体系为基础应用,实现全面高效的工程管理需求,满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效,为监管平台提供数据支撑。
34 3
|
2月前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
72 0
|
2月前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
57 0
|
2月前
|
存储 Java C++
Collection-PriorityQueue源码解析
Collection-PriorityQueue源码解析
64 0

推荐镜像

更多