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

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

时间:2024-01-17 10:02:43浏览次数:29  
标签:Java HashMap 容量 hashCode 链表 源码 哈希 原理 加载

知识盲点

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

概念介绍

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

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

数据结构

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

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

数组

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

链表

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

数组VS链表

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

哈希表

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

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

不同JVM版本HashMap的展现形式

JDK8之后的版本,HashMap底层使用数组加(链表或红黑树)的结构完美的解决了数组和链表的问题(循环死锁问题),使的查询和插入,删除的效率都很高。

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

HashMap的散列表是懒加载机制,在第一次put的时候才会创建hash表

HashMap VS HashTable

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

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

特性区别对比

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

  • 是否允许键为空:值得一提的是,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()方法

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

  • 若两个对象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操作的次数。

标签:Java,HashMap,容量,hashCode,链表,源码,哈希,原理,加载
From: https://blog.51cto.com/alex4dream/9286486

相关文章

  • 开发日记3(java面向对象)
    (一)java面向对象1、面向过程和面向对象很久很久以前,系统学习过C语言,但也只是学过,没有产生过除了考试以外的其他价值。后来工作中很多伙伴都在使用java,虽然当时自己不写java,但很久之前就有个概念,这两种语言还是不同的,一个面向过程、一个面向对象。面向过程比较容易理解,基实过程可以理......
  • 【源码系列#06】Vue3 Diff算法
    专栏分享:vue2源码专栏,vue3源码专栏,vuerouter源码专栏,玩具项目专栏,硬核......
  • Java面向对象
    Java面向对象面向对象编程(Object-OrientedProgramming,OOP)面向对象编程本质:以类的方式组织代码,以对象的组织(封装)数据三大特性:1、封装所谓的封装就是把类的属性和方法使用private修饰,不允许类的调用者直接访问,如果想要操作这些属性使用public的get、set方法。封装的作用:不......
  • Java就业学习 Day2 每日一问:我真能找到工作吗/(ㄒoㄒ)/~~
    Java开发能力:今天只看了面向对象这一节的东西,确实有了好多新的理解。①和equals的区别:说实话我现在才弄懂。。比较的其实是地址,所以如果一个变量可以用==,但对象就不行。②重载与重写的区别:重载是构造器重载,构造器的参数不同。而重写是重写方法,形象来说就是父类的方法我不满意,我......
  • Java数组
    Java数组数组一、数组的声明和创建1、声明dataType[]arrayRefVar;//声明数组2、创建dataType[]arrayRefVar=newdataType[dataSize];//创建一个数组二、初始化及内存分析1、初始化//静态初始化:创建加赋值int[]a={1,2,3};Peo......
  • 不可不看的Java基础知识整理,注释、关键字、运算符
    写在开头万丈高楼平地起,要想学好汉语首先学拼音,想学好英语首先学26个字母,对于编程语言来说,一样的道理,要想学好必须先掌握其基础语法和知识,今天我们就来唠一唠Java语言中那些出现频率极高,又很基础的知识点吧!Java中的注释注释的作用:拨云见日!在日常的工作中,总会遇到很多大段的代......
  • Java动态代理、AOP和装饰器模式
    面向切面编程AOP-AspectOrientedPrograming,主要用于处理核心业务逻辑外的一些东西,比如日志和缓存。这个“切面”可以理解为在代码的某个地方切一刀,在其中加一些东西。装饰器以日志为例,如果没有使用AOP,那么可以使用装饰来实现类似的代码。我们使用装饰器模式来实现一下在执行......
  • java 依赖 stable diffusion
    Java依赖的稳定扩散简介Java的依赖稳定扩散是指将一个Java项目的依赖库从一个环境迁移到另一个环境,确保依赖库在新环境中正常工作。本文将介绍实现这一过程的步骤和相应的代码。流程概览以下是实现Java依赖稳定扩散的步骤概览:步骤描述1.创建空白的Java项目......
  • java实现文心一言流式输出
    Java实现文心一言流式输出教程简介在本教程中,我将教授你如何使用Java实现文心一言流式输出。文心一言是一种短小精悍的句子,适合用于展示在网站的底部或侧边栏等位置。通过流式输出,可以实现每隔一段时间自动更新展示的文心一言。整体流程下面是实现文心一言流式输出的整体流程,可......
  • 线程池源码学习
    使用线程池的好处降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。提高响应速度。当任务到达时,任务可以不需要的等到线程创建就能立即执行。提高线程的可管理性。线程是稀缺资源,如果无限制的创建,不仅会消耗系统资源,还会降低系统的稳定性,使用线程池可以......