HashMap的底层工作原理(详细版)

2023-12-15 22:23:24

前言:HashMap的一些特性:譬如HashMap可以接受null键值和值,而HashTable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对等等这一些都是必须知道的。下面来深入了解HashMap的底层工作原理:

1 HashMap 的存储机制
a在 Java 1.8 中,如果链表的长度超过了 8且数组长度最小要达到64 ,那么链表将转化为红黑树;链表长度低于6,就把红黑树转回链表; 初始化 当创建一个 HashMap 实例时,它会初始化一个默认大小的数组(默认为16),每个数组元素是一个链表。

总的来说,HashMap 通过散列函数将键映射到数组中,采用链表解决冲突的方法来存储数据。


2 Java 1.8 中 HashMap 的不同
a在 Java 1.8 中,如果链表的长度超过了 8 ,那么链表将转化为红黑树;链表长度低于6,就把红黑树转回链表;
b发生 hash 碰撞时,Java 1.7 会在链表头部插入,而 Java 1.8 会在链表尾部插入;
c在 Java 1.8 中,Entry 被 Node 代替(换了一个马甲)。


3 存储数据 当我们使用 put() 方法添加键值对时,HashMap 首先会计算键的 hashCode() 值,然后根据该值计算该键值对应在数组中的位置(即散列码),如果该位置上还没有元素,则直接把该键值对存储到该位置上;如果该位置上已经有元素了,则将该键值对插入到该位置对应的链表的末尾。
理解:(对Key求Hash值,然后再计算下标,如果没有碰撞,直接放入桶中(碰撞的意思是计算得到的Hash值相同,需要放到同一个bucket中)如果碰撞了,以链表的方式链接到后面
d如果链表长度超过阀值( TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表,如果节点已经存在就替换旧值,如果桶满了(容量16*加载因子0.75),就需要 resize(扩容2倍后重排))


4 访问数据 当我们使用 get() 方法来获取某个键对应的值时,HashMap 首先也会计算该键的 hashCode() 值,然后根据该值找到该键值对应在数组中的位置。如果该位置上没有元素,则返回 null;如果该位置上有元素,则遍历该位置对应的链表,找到与该键相等的键值对,然后返回该键值对的值。

5 扩容 当 HashMap 中存储的键值对数量超过数组大小的75%时,就会触发扩容操作。具体来说,HashMap 会将数组大小翻倍,并重新计算每个键值对在新数组中的位置,然后将所有键值对重新放置到新的数组中。

6 红黑树何时会退化为链表?

①扩容时由于原始hash值不同,重新计算下标,拆分树时,树的个数小于等于6会退化为链表

②remove树节点时,移除之前若 左孩子/左孙子/右孙子节点 有一个不存在个会变为链表

7 hashmap的key能否为null?作为key的对象有什么要求?为什么要重写hashcode,equals

①可以为null,其他的Map实现不一定:Treemap,Hashtable,currentHashMap(会出现空指针)

②作为key对象,必须实现hashCode和equals,并且key的内容不能修改

equals:万一两个元素的hashCode的值相等,通过equals判断是否为相同的元素

注意:如果hashCode值相等,不一定是同一个元素;如果两个元素equals相等,那么是同一个元素

因为 Set 和HashMap的key存储的是不重复的对象,依据 hashCode 和 equals 进行判断,所以存储的对象必须覆写这两个方法。

8.HashMap如何避免内存泄漏问题?

new不同的对象参数内容相同,内存地址不同;

如果没有重写equals底层默认的是使用==比较,比较的是内存地址

解决:重写自定义对象的hashcode和equals方法

9.HashMap的扩容机制?

默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。

总结:

①通过hash的方法,通过put和get存储和获取对象。

存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。

获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。

如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

④HashMap如何解决Hash冲突问题?

链表+红黑树

文章来源:https://blog.csdn.net/m0_73647713/article/details/134934000
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。