java集合之HashMap

HashMap

前言：

HashMap作为面试必备题目，是需要每个java程序员都得研究的，这里总结下JDK8之后HashMap的实现。

一.HashMap的特点？

HashMap是Map的实现类之一，HashMap的底层是hash表，hash表是用来控制键值对中的键的，并且HashMap的键是可以为null的，值也可以为null，存入以及获取的值都是无续的，线程不安全（ConcurrentHashMap、HashTable是线程安全），效率高。在JDK8之前使用数组+链表的方式实现数据存储，发生hash碰撞时采用头插法插入，从JDK8之后开始使用数组+链表+红黑树了，发生hash碰撞时采用尾插法（头插法和尾插法描述的是链表结构的插入）。

二.HashMap的几个主要方法

简单陈述HashMap的几个主要方法。

1.put方法

JDK8开始，put方法里才是真正创建Node（以前是Entry）数组的地方。put方法的处理逻辑是这样的：若是第一次调用put方法，则会先通过resize方法创建一个大小为16的Node数组，然后根据key的hashcode值，通过无符号右移与按位亦或得到hash值，再将hash值与数组长度减一进行按位与操作，就可以得到数组的下标，然后将键值对存入该下标对应的位置。若不是第一次，计算下标的过程一样，只不过还需要判断该位置上是否有其他元素，若已有则调用key的equals方法计进行比对，若equals比较也相等，则更新该节点的值，若不相等则需要遍历链表，进行equals比较，有相等的则更新，没有则在链表的尾部进行插入，这里还需要判断链表的长度，若是大于了8则需要尝试转化红黑树，若是数组长度小于64则选择扩容，否则就会转化红黑树进行存储。

源码展示

2.resize方法

该方法是扩容的方法，当数组长度达到threshold（临界值）就会触发该方法。该方法会将HashMap的数组长度扩大为原来的两倍。该方法的逻辑是：该方法会先判断Node数组是否是空，若是空的话会县创建一个大小为16的Node数组，不是空的话会将原数组的长度进行左移1位，相当于乘以2的效果。

这里只展示了部分代码。

3.get方法

get方法的逻辑：首先根据传入的key计算出对应的数组下标值（hashcode+无符号右移+按位亦或+按位与），判断该位置是否拥有元素，若是拥有则使用equals方法进行比对，比对成功则返回该节点的value值，失败的话判断该节点处的其他值（往下查找）是不是红黑树结构，是则遍历红黑树使用equlas进行比较，查到则返回。不是红黑树则遍历链表结构，依然使用equals方法记性比对。
2. 源码展示
在这里插入图片描述

三.HashMap原理相关问题。

这里列举了很多自问自答的问题，也有面试题，帮助理解HashMap，同时又是面试题的一部分。

1.JDK8前后创建HashMap的区别

HashMap<String,String> hashMap = new HashMap<String,String>();
hashMap.put("key","value");

JDK8之前在执行HashMap的构造方法时就会创建一个数组长度为16的Entry数组，将默认的负载因子0.75f赋给loadFactor（负载因子）。但是从JDK8开始，在执行构造方法时就变成了只将默认的负载因子赋给loadFactor，不会创建数组。创建数组的地方移动到了put方法中，且数组的实现使用Node数组，而不是之前的Entry数组了。

源码展示

从上图中标红的地方我们可以看出，第一次调用put方法肯定会执行resize（）方法，该方法在数组为空的情况下会返回一个数组长度为16的Node数组。

2.HashMap底层是Hash表，Hash表采用何种算法计算hash值？

通过键的hashCode方法计算出hashCode，然后将hashCode与hashCode无符号右移16位的结果进行按位亦或操作。得出的便是hash值。

源码展示

如上代码所示，就是计算hash值的代码，之所以都是使用位运算，是因为位运算的效率远高于加减乘除等其他算数运算。
数组下标的计算
刚刚已经说过，是通过hash值与数组长度减一进行按位与操作获得的，计算出的值就是当前键值对，应该放入的数组的位置。其实还可以使用“取余法”来计算数组的下标，只不过效率上不及位运算操作。

3.若初始化HashMap时给的capacity是10，那么HashMap的数组长度是多少。

是16，如果我们在创建HashMap时指定其数组的长度，HashMap会判断给定的值是否是2的n次方，因为HashMap的数组长度必须是2的n次方，若不是2的n次方，则会通过一系列的无符号右移与按位或操作将初始化的数组长度变为大于给定值的最小的2的n次方。

源码展示

如上所示就是HashMap实现这一机制的代码，为什么要这么做呢？归根结底还是为了更好、更快、更强嘛，首先数组长度必须是2的n次方，如果不是很容易发生hash碰撞，这是jdk开发人员大量实验证明过的，此外，将数组的长度扩大，可以减小当前使用场景数组扩容的次数，扩容是一件很耗费性能的操作，所以也应该尽量规避，所以才会将值扩充到大于指定值的最小的2的n次方。

4.负载因子是什么？为什么要有负载因子？

负载因子使用参数loadFactor表示，是HashMap中衡量数组使用程度的一个参数，介于0-1之间，越接近于1说明数组里面存储的数据就越多。那为什么需要负载因子呢？因为不同的对象计算出的hashCode值是可能重复的，当Hash值重复时就会发生hash碰撞，这是JDK8以后是采用链表+红黑树来解决Hash碰撞，因此若是负载因子的值较高时，就会导致hash碰撞的概率增加（数据量大，碰到的概率就高嘛），较低时又会导致数组空间浪费，所以权衡了时间与空间，经过大量测试得出0.75是一个较为较好的负载率。

源码展示

HashMap在被创建时负载因子默认就是0.75。

5.Hash碰撞是什么？如何解决？如何规避？

hash碰撞是指多个不同的key计算出的hash值却相同，在JDK8之前使用链表来解决hash碰撞的问题，JDK8开始使用链表+红黑树来解决hash碰撞的问题，当链表的长度大于8，且数组长度大于等于64链表就会转变为红黑树。如何规避hash碰撞或者说如何减少hash碰撞呢？首先HashMap已经做了尽可能的规避hash碰撞的操作，比如将hashcode值进行无符号右移按位亦或操作等，此外我们还可以使用那些不可变更的对象比如String、包装类等来作为key来减少碰撞。
3. 源码展示
在这里插入图片描述

6.HashMap什么情况下扩容，如何扩容？

扩容的情况有两种，第一种：当数组存储的数据达到了threshold(即：capacity*loadFactor)的值时，HashMap就会扩容，扩容为原来数组长度的2倍。第二种：当发生hash碰撞且链表的长度大于8时，且数组长度小于64也会发生扩容。都是将原数组的长度扩大为原先的两倍，这期间或伴随着rehashing的过程，但是这个过程不会重新计算hash值。扩容后的数据的索引只可能是原先的索引或者是原先索引值加上原先数组的长度。
4. 源码展示
java集合之HashMap-小白菜博客
可以看到这里将原数组长度进行了左移1位，也就是将原数组的长度进行了乘以2的操作。

7.链表何时转化为红黑树？为什么转化？为什么这时候转化？

当链表长度大于8时，且数组长度大于等于64。此时链表就会转化为红黑树。为什么链表需要转化为红黑树呢？虽然红黑树的存储节点是链表的2倍大小，但是红黑树的查询效率要高很多。那为什么链表长度大于8才会转化呢，根据官方说法，由泊松分布统计出来的结果当链表长度为8时的概率是0.00000006，已经非常低了。所以说明要是链表能达到8的长度，说明数据量非常大，但是为了规避万一又限制了数组长度必须是大于等于64时才可以转化为红黑树。这样就保证了只有数据量很大时又排除了意外，才会将链表转化为红黑树，这样就可以节省很多时间开销。上面是官方解释为什么是8才转化为红黑树，此外也有这么解释的，链表的时间查询复杂度是o(n),而红黑树（平衡二叉树）的时间复杂度是o(logn)。所以若是底数为2，长度为8时，使用红黑树查询效率刚刚好大于链表（3和4）。

源码展示

这里我们可以看到当链表元素到达9时，就会尝试进行红黑树的转化，但是treeifyBin方法里还会判断数组长度是否是大于等于64，只有都满足了才会转化，否则只是对数组进行扩容。

8.链表是如何转化为红黑树的？

当调用put方法时，一个节点上的元素达到9个就会调用treeifyBin方法，进入该方法后会先判断数组长度是否小于64，若是则调用resize方法进行扩容，而不是转化为红黑树，若是长度已经大于等于64，则会先拿到数组中该节点的值，将其转化为TreeNode对象，然后依次将链表上的所有元素都转化为TreeNode对象并将它们连接起来。遍历完成后才会将新组成的TreeNode放入到主体数组中，最后再调用treeify方法将这些TreeNode节点进行左旋右旋等操作。将节点彻底转化为红黑树。
2. 源码展示
在这里插入图片描述

9.链表可以变成红黑树？红黑树可以变成链表吗？

treeify_threshold该参数默认就是8，且不支持更改，他就是用来控制链表用来转化为红黑树的界限值。同样也有一个untreeify_threshold来控制红黑树转化为链表的界限值，该值默认是6且不支持更改，当删除红黑树的节点时，节点数小于等于6，就会转化为链表。为什么转化为链表呢，因为在6以下，红黑树的查询效率与链表差距不大，但是消耗的空间却要多得多。所以这种情况下还是会转化为链表。

10.该如何使用HashMap

鉴于HashMap的自动扩容机制，且扩容会消耗很大的性能，因此在日常使用中，若是已知存储的数据大致数量，我们应设置的HashMap的数组长度为(n/0.75)+1,这也是阿里开发手册建议的值，为什么要设置这个值呢，自然是因为HashMap的扩容机制是数组使用率达到75%就会扩容，+1是为了规避提前扩容。