源码解剖HashMap

 我们将通过以下几个问题进行解答分析：

（1）HashMap 底层实现原理是什么？JDK8 做了哪些优化？

（2）HashMap 的工作原理？HashMap中链表的作用？

（3）为什么要添加红黑树？

（4）加载因子是什么？为什么是0.75？

（5）HashMap 是如何导致死循环的？

HashMap 底层实现原理是什么？JDK8 做了哪些优化？

在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的，JDK 1.8 之后新增了红黑树的组成结构，当链表长度大于 8 时并且容量大于 64 时，链表结构会转换成红黑树结构。

组成结构如下图:

数组中的元素我们称之为哈希桶，每个哈希桶中包含了四个字段：hash、key、value、next，其中 next 表示链表的下一个节点。它的定义如下：

HashMap 的工作原理？

HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry接口）实现，HashMap 通过 put & get 方法存储和获取。

存储对象时，将 K/V 键值传给 put() 方法：

①、调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；

②、调整数组大小（当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n）；

③、i.如果 K 的 hash 值在 HashMap 中不存在，则执行插入；

ii.如果 K 的 hash 值在 HashMap 中存在(发生碰撞)，且它们两者 equals 返回 true，则更新键值对；

iii. 如果 K 的 hash 值在 HashMap 中存在（发生碰撞），且它们两者 equals 返回 false，则插入链表的尾部（JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法）或者红黑树中。

获取对象时，将 K 传给 get() 方法：

①、计算 K 的 hash 值从而获取该键值所在链表的数组下标；

②、顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。

hashCode 是定位的，存储位置；equals是定性的，比较两者是否相等。

HashMap中链表的作用？

从HashMap的工作原理我们可知，HashMap是利用“拉链法”处理Hash的碰撞问题。

补充：Hash碰撞冲突可以使用开放地址法、再哈希法、链地址法（拉链法）、建立一个公共溢出区、等方法解决。

为什么要添加红黑树？为什么链表大于 8才转？

详细介绍请查阅我的另一篇文章 --

HashMap源码分析

主流的JDK版本1.8为例

 加载因子是什么？为什么是0.75？

加载因子也叫扩容因子或负载因子，用来判断什么时候进行扩容的，假如加载因子是0.5，HashMap的初始化容量是16，那么当HashMap中有16*0.5=8个元素时，HashMap就会进行扩容。

那加载因子为什么是 0.75 而不是 0.5 或者 1.0 呢？

这其实是出于容量和性能之间平衡的结果：

(1)当加载因子设置比较大的时候，扩容的门槛就被提高了，扩容发生的频率比较低，占用的空间会比较小，但此时发生Hash冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低；

(2)而当加载因子值比较小的时候，扩容的门槛会比较低，因此会占用更多的空间，此时元素的存储就比较稀疏，发生哈希冲突的可能性就比较小，因此操作性能会比较高。

所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。

HashMap 是如何导致死循环的？

发生死循环的原因是JDK1.7链表插入方式为首部倒序插入，这个问题在JDK1.8得到了改善，变成了尾部正序插入。

有人曾经把这个问题反馈给了 Sun 公司，但 Sun 公司认为这不是一个问题，因为 HashMap 本身就是非线程安全的，如果要在多线程下，建议使用 ConcurrentHashMap 替代，但这个问题在面试中被问到的几率依然很大，所以在这里需要特别说明一下。.