【HashMap】深入原理解析

2024-09-06 15:18
文章标签 深入 原理 解析 hashmap

本文主要是介绍【HashMap】深入原理解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【HashMap】深入原理解析

分类: 数据结构 自考


equals与“==”(可以参考自己的另一篇博文)

 

1,基本数据类型(byteshortcharintlongfloatdoubleboolean

使用“== 对比的是具体的值是否相等


2,复合数据类型

“== ”对比的是内存中存放的地址

object中的equals初始行为是比较内存中的地址,但在一些类库中被覆盖掉了如(StringIntegerDate等)

 

故对于复合数据类型使用equals进行比较,未进行覆写的比较的是内存地址,覆写的一般是比较具体的值


注:equals的底层实现

[java]  view plain copy print ?
  1. /** 默认同==,直接比较对象 */    
  2. public boolean equals(Object obj) {    
  3.     return (this == obj);    

 

重写equals要满足几个条件:

 

自反性:对于任何非空引用值x,x.equals(x) 都应返回 true。

对称性:对于任何非空引用值 x 和 y,当且仅当y.equals(x) 返回 true 时,x.equals(y) 才应返回 true。

传递性:对于任何非空引用值 x、y 和 z,如果x.equals(y) 返回 true,并且 y.equals(z) 返回 true,那么 x.equals(z) 应返回 true。

一致性:对于任何非空引用值 x 和 y,多次调用x.equals(y) 始终返回 true 或始终返回 false,前提是对象上 equals 比较中所用的信息没有被修改。

对于任何非空引用值x,x.equals(null) 都应返回 false。

 

对于重写equals就要重写hashCode的问题,可参考博客

http://blog.csdn.net/hejingyuan6/article/details/22398151

 

Java对于eqauls方法和hashCode方法是这样规定的:

 

    1.如果两个对象相同,那么它们的hashCode值一定要相同;

    2.如果两个对象的hashCode相同,它们并不一定相同(这里说的对象相同指的是用eqauls方法比较)。如不按要求去做了,会发现相同的对象可以出现在Set集合中,同时,增加新元素的效率会大大下降。

     3.equals()相等的两个对象,hashcode()一定相等;equals()不相等的两个对象,却并不能证明他们的hashcode()不相等。   

 

        HashMap中我们最常用的就是put(K,V)和get(K)。我们都知道,HashMap的K值是唯一的,那如何保证唯一性呢?

       我们首先想到的是用equals比较,没错,这样可以实现,但随着内部元素的增多,put和get的效率将越来越低,这里的时间复杂度是O(n),假如有1000个元素,put时需要比较1000次。实际上,HashMap很少会用到equals方法,因为其内通过一个哈希表管理所有元素,哈希是通过hash单词音译过来的,也可以称为散列表,哈希算法可以快速的存取元素,当我们调用put存值时,HashMap首先会调用K的hashCode方法,获取哈希码,通过哈希码快速找到某个存放位置,这个位置可以被称之为bucketIndex,通过上面所述hashCode的协定可以知道,如果hashCode不同,equals一定为false,如果hashCode相同,equals不一定为true。

       所以理论上,hashCode可能存在冲突的情况,有个专业名词叫碰撞,当碰撞发生时,计算出的bucketIndex也是相同的,这时会取到bucketIndex位置已存储的元素,最终通过equals来比较,equals方法就是哈希码碰撞时才会执行的方法,所以前面说HashMap很少会用到equals。

       HashMap通过hashCode和equals最终判断出K是否已存在,如果已存在,则使用新V值替换旧V值,并返回旧V值,如果不存在,则存放新的键值对<K, V>到bucketIndex位置。

 

put过程流程图:(这个图很形象啊



 

现在我们知道,执行put方法后,最终HashMap的存储结构会有这三种情况,情形3是最少发生的,哈希码发生碰撞属于小概率事件。到目前为止,我们了解了两件事:

 

     HashMap通过键的hashCode来快速的存取元素。

    当不同的对象hashCode发生碰撞时,HashMap通过单链表来解决,将新元素加入链表表头,通过next指向原有的元素。单链表在Java中的实现就是对象的引用(复合)。

 

解决冲突的两种方式:

 

当系统决定存储 HashMap 中的key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。即我们完全可以把 Map集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value 随之保存在那里即可.

 

实验:

         HashMap程序经过改造,故意的构造出了hash冲突现象,因为HashMap的初始大小16,但是我在hashmap里面放了超过16个元素,并且我屏蔽了它的resize()方法。不让它去扩容。这时HashMap的底层数组Entry[]   table结构如下: 




Hashmap里面的bucket出现了单链表的形式,散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法开放地址法

       链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;

       开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。

 

java.util.HashMap采用的链表法的方式,链表是单向链表。

形成单链表的核心代码如下:

[plain]  view plain copy print ?
  1. void addEntry(int hash, K key, V value, int bucketIndex) {    
  2.     Entry<K,V> e = table[bucketIndex];    
  3.     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
  4.     if (size++ >= threshold)    
  5.         resize(2 * table.length);    
  6. bsp;   

     上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 Entry 对象放入table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序代码的 e 变量是null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。(有Entry对象产生一个Entry链,Entry为null就不产生链)


      HashMap里面没有出现hash冲突时,没有形成单链表时,hashmap查找元素很快,get()方法能够直接定位到元素,但是出现单链表后,单个bucket里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

      

说明:

 

HashMap有两个参数影响其性能:(透彻)

 

       初始容量和加载因子。默认初始容量是16,加载因子是0.75,这是时间和空间成本上一种折衷。容量是哈希表中桶(Entry数组)的数量,初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,通过调用rehash 方法将容量翻倍。

 

       加载因子过高虽然减少了空间开销,但同时也增加了查询成本(加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地降低rehash 操作次数。如果初始容量大于最大条目数除以加载因子(实际上就是最大条目数小于初始容量*加载因子),则不会发生 rehash 操作。

 

        当HashMap存放的元素越来越多,到达临界值(阀值)threshold时,就要对Entry数组扩容,这是Java集合类框架最大的魅力,HashMap在扩容时,新数组的容量将是原来的2倍,由于容量发生变化,原有的每个元素需要重新计算bucketIndex,再存放到新数组中去,也就是所谓的rehash。HashMap默认初始容量16,加载因子0.75,也就是说最多能放16*0.75=12个元素,当put第13个时,HashMap将发生rehash,rehash的一系列处理比较影响性能,所以当我们需要向HashMap存放较多元素时,最好指定合适的初始容量和加载因子,否则HashMap默认只能存12个元素,将会发生多次rehash操作。

这篇关于【HashMap】深入原理解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Spring Boot 3.x 中 WebClient 示例详解析

《SpringBoot3.x中WebClient示例详解析》SpringBoot3.x中WebClient是响应式HTTP客户端,替代RestTemplate,支持异步非阻塞请求,涵盖GET... 目录Spring Boot 3.x 中 WebClient 全面详解及示例1. WebClient 简介2.

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

C#解析JSON数据全攻略指南

《C#解析JSON数据全攻略指南》这篇文章主要为大家详细介绍了使用C#解析JSON数据全攻略指南,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、为什么jsON是C#开发必修课?二、四步搞定网络JSON数据1. 获取数据 - HttpClient最佳实践2. 动态解析 - 快速

Spring Boot3.0新特性全面解析与应用实战

《SpringBoot3.0新特性全面解析与应用实战》SpringBoot3.0作为Spring生态系统的一个重要里程碑,带来了众多令人兴奋的新特性和改进,本文将深入解析SpringBoot3.0的... 目录核心变化概览Java版本要求提升迁移至Jakarta EE重要新特性详解1. Native Ima

spring中的@MapperScan注解属性解析

《spring中的@MapperScan注解属性解析》@MapperScan是Spring集成MyBatis时自动扫描Mapper接口的注解,简化配置并支持多数据源,通过属性控制扫描路径和过滤条件,利... 目录一、核心功能与作用二、注解属性解析三、底层实现原理四、使用场景与最佳实践五、注意事项与常见问题六

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应

MyBatis中$与#的区别解析

《MyBatis中$与#的区别解析》文章浏览阅读314次,点赞4次,收藏6次。MyBatis使用#{}作为参数占位符时,会创建预处理语句(PreparedStatement),并将参数值作为预处理语句... 目录一、介绍二、sql注入风险实例一、介绍#(井号):MyBATis使用#{}作为参数占位符时,会

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析