#智启新篇谋略#

哈喽民众好！今天我们来聊聊Java中最经典的数据结构之一——HashMap！如果你是Java建筑者，那你一定对它不目生。HashMap 是我们进行键值对存储的好帮衬，着实是我们在平素建筑中离不开的器具。本文会从数据结构、扩容机制、put和查找历程、哈希函数以及JDK 1.7与1.8的互异等多方面，来详备拆解一下HashMap的底层旨趣！Let's 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引入红黑树和尾插法处理突破，幸免了死轮回，提高了多线程环境的安全性。

但愿这篇著作能帮你更深远地意会HashMap！感谢阅读，宽待留言考虑~

我是小米，一个心爱共享技巧的29岁设施员。如果你心爱我的著作，宽待关心我的微信公众号“软件求生”赌钱app下载，获得更多技巧干货！