Java面试加分点!一文读懂HashMap底层实现与扩容机制杨子被吐槽不尊重工作人员,看他对黄圣依的态度就知道为什么了

9次阅读

Java面试加分点!一文读懂HashMap底层实现与扩容机制杨子被吐槽不尊重工作人员,看他对黄圣依的态度就知道为什么了

哈喽大家好!今天咱们来聊聊Java中最经典的数据结构之一——HashMap!如果你是Java开发者,那你一定对它不陌生。HashMap 是我们进行键值对存储的好帮手,几乎是我们在日常开发中离不开的工具。本文会从数据结构、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异等多方面,来详细拆解一下HashMap的底层原理!Lets go~

数据结构:数组 + 链表 + 红黑树

在Java的HashMap中,底层数据结构是数组、链表、红黑树三者的组合。通过键值对的哈希映射,HashMap可以实现快速的数据存取。那么,HashMap是如何把这三种数据结构组合起来的呢?

数组:这是HashMap的核心存储空间,称为table。当我们通过key来存取数据时,实际是把key通过哈希函数映射到table中的某个索引位置。

链表:在HashMap中,链表主要是用来处理哈希冲突的。如果多个key被映射到了同一个数组索引,那么这些冲突的元素会被放在一个链表中,以链表形式存储。

红黑树:在JDK1.8引入了红黑树,以优化链表的查找效率。若一个索引下的链表长度超过8,并且数组长度大于64,HashMap会将链表转换成红黑树。这样可以将查找的时间复杂度从O(n)降到O(log n),大幅度提升性能。

扩容情况:为什么是2的幂次方?

HashMap在扩容机制上也是独具匠心。扩容不仅影响性能,还会影响数据的分布和哈希碰撞,所以在容量和扩容机制设计上,HashMap非常讲究。

默认大小和负载因子:HashMap的默认容量是16,负载因子是0.75。也就是说,当HashMap的填充度超过75%时,就会触发扩容操作,避免因为过多的哈希冲突而降低性能。

扩容机制:扩容发生时,HashMap会将当前容量翻倍,并重新将所有元素重新哈希到新的数组中。

容量始终是2的幂次方:HashMap的容量总是保持2的幂次方。这样设计的原因主要有以下几点:

2的幂次方可以使(n-1) & hash的运算分布更均匀,减少哈希碰撞。

使用位运算&替代取模操作,效率更高。

put方法的过程

HashMap的put方法可以说是HashMap的精髓之一,理解它的执行过程,有助于我们掌握HashMap的存储机制。put方法主要分以下几个步骤:

判断table是否为空:如果table为空,HashMap会进行初始化操作,将容量扩充为默认大小16。

计算hash值和索引位置:通过key的hashCode值经过扰动函数处理后,再通过(n – 1) & hash计算出该元素存放的数组下标index。

检查是否有哈希冲突:检查table[index]处是否已经有节点。

如果没有节点,直接构造一个新的Node节点放入table[index]处;

如果已经有节点,说明发生了哈希冲突,进入下一步判断。

哈希冲突处理:在处理哈希冲突时,HashMap通过链表和红黑树来解决冲突。

若现有节点的key与新节点的key相同,就会用新的value覆盖原有值。

如果不相同,检查现有节点类型,如果是链表节点,则将新节点添加到链表中;如果链表长度超过阈值8且数组长度大于64,会将链表转换为红黑树。

判断是否需要扩容:当插入完成后,HashMap会检查当前容量是否超过负载因子0.75的阈值,如果超过则触发扩容。

哈希函数:扰动函数与hash计算

HashMap的哈希函数不仅仅是简单地用key.hashCode()来决定索引位置,因为直接使用hashCode()的低效与不均匀会导致大量哈希碰撞。因此,HashMap采用了一种“扰动函数”来优化哈希值的计算过程。

HashMap在计算key的哈希值时,先对key的hashCode()进行一次扰动,将hashCode的高16位和低16位进行异或运算。

这个“扰动”能让哈希结果更加均匀分布,尽可能地减少哈希碰撞。

经过扰动处理后的哈希值,最终会通过(n – 1) & hash来计算索引位置,这样可以确保得到的索引位置始终位于数组范围内。

JDK1.7与JDK1.8的区别

在JDK1.7与JDK1.8之间,HashMap的实现有一些关键性变化:

数据结构:JDK1.7中,HashMap采用了“数组+链表”的组合,而JDK1.8中则采用“数组+链表+红黑树”三者结合的结构。在JDK1.8中,当链表长度超过8且数组长度大于64时,链表会转化为红黑树以优化查找性能,避免长链表造成的性能瓶颈。

hash冲突处理方式:在JDK1.7中,链表插入新节点时采用的是头插法,这样做的好处是插入速度较快,但在并发情况下可能会产生死循环(例如在rehash期间)。而在JDK1.8中,链表插入时采用了尾插法,避免了并发扩容时死循环的问题。

扩容过程:JDK1.8中,HashMap的扩容更为智能高效,通过高位运算决定节点位置是否发生变化。扩容时不再重新计算所有节点的哈希值,只需检查每个节点的高位,决定是否需要搬移至新数组。

性能优化:JDK1.8的HashMap在多线程环境下性能优化明显,解决了JDK1.7在并发条件下扩容时可能导致的死循环问题。总体来看,JDK1.8的HashMap在结构上更为合理,更适用于高并发场景。

END

好了,这就是HashMap的底层设计和实现原理,学会这些知识之后,再遇到关于HashMap的面试题,你一定可以轻松应对!

底层结构:HashMap采用数组、链表、红黑树组合的数据结构来存储键值对。

扩容机制:HashMap默认负载因子为0.75,扩容时容量翻倍,始终保持2的幂次方以提高存储效率。

put过程:put方法主要包括判断初始化、计算hash值、解决哈希冲突、扩容等几个步骤。

哈希函数:采用扰动函数,降低哈希碰撞,确保元素均匀分布。

JDK1.7 vs JDK1.8:1.8引入红黑树和尾插法处理冲突,避免了死循环,提高了多线程环境的安全性。

正文完
 0
网站地图