*HashMap实现原理及源码学习（JDK 1.8.0）*

*HashMap实现原理及源码学习（JDK 1.8.0）*

说明：

（1）笔者对于红黑树还比较懵懂，故在此不做过多解析。

（2）对于HashMap的源码，也只是部分学习。（如有错误之处，欢迎指正）

一、前言部分注释

图-1.1

译>：HashMap的实例有两个影响其性能的参数——“初始容量initial capacity”和“负载因子load factor”，容量指的是哈希表中桶（buckets）的数目，初始容量即为创建哈希表时桶的数目；负载因子是衡量哈希表在自动扩容之前的填充程度的度量，即当哈希表中的条目数超过（负载因子与当前容量的乘积）时，哈希表将会自动扩容为原来桶数目的2倍，然后将已有数据进行重新映射（即内部数据结构将被重建）。

图-1.2

译>：通常，默认负载因子为0.75，该值在时间和空间成本之间提供了很好的折中，较高的值会减少空间开销，但同时会增加查找成本。设置初始容量时，应考虑映射中的预期条目数和负载因子，以最大程度地减少重新哈希操作的数量，如果，初始容量大于预期条目数除以负载因子（即 初始容量*负载因子 > 预期条目数），则不会发生任何重新哈希的操作。

图-1.3

译>：如果要在HashMap的实例中存储许多映射，则创建具有足够大容量的哈希表比让其根据需要自动扩容进行重新哈希操作更有效地存储映射。（使用许多具有相同{@code hashCode（）}的键是降低任何哈希表性能的原因之一，为了改善影响，当键为{@link Comparable}时，此类可以使用键之间的比较顺序帮助打破这种局面。）

图-1.4

译>：由此类（HashMap）提供的所有“集合视图方法”（如keySet(),valueSet(),entrySet()）返回的迭代器都为“<i>fail-fast</i>”，即：如果在创建迭代器后的任何时间对Map进行结构修改（结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已经包含的键相关联的值不是结构修改。），除了通过迭代器本身的 <tt>remove</tt>方法，迭代器将抛出异常 {@link ConcurrentModificationException}。因此，面对（同步）并发修改，迭代器会快速干净地失败操作，不会冒任意不确定行为的风险。（迭代器的快速失败行为仅用于检测错误，不能用于保证正确性。）

二．HashMap的内部实现机制

1.HashMap基本属性

图-2.1.1

注：使用无参构造new一个HashMap实例的时候，系统会默认指定初始容量为16（2的4次方），当然我们也可以通过有参构造自己指定初始容量大小，但必须是2的次幂（且小于等于2的30次方）。同样，也可以在有参构造中指定负载因子，如果不指定则为默认值0.75。（由于迭代遍历所需的时间与桶的数量以及键值映射对的数量成正比，因此如果迭代性能很重要，则不要将初始容量设置过大（负载率过低））

图-2.1.2

图-2.1.3

注：如图所示，Node<K,V>是HashMap的一个内部类，它既是HashMap底层数组的组成元素，又是每个链表的组成元素，其中包括了数组元素所需要的key和value，以及链表元素所需要的next域，hash值是系统在创建Node时通过一定的算法计算出来的int值。

图-2.1.4

注：key不为null时，先调用hashCode()，然后右移16位进行按位异或运算（后面会有进一步的介绍）

图-2.1.5

注：关于tableSizeFor(int cap)中这个精巧的算法，请看https://blog.csdn.net/dagelailege/article/details/52972970

图-2.1.6

*更正：threshold表示数组的扩容阈值（即 当前容量*当前负载因子），并非数组容量。

2.HashMap的构造函数

注：JDK1.8中，HashMap提供了4种构造函数

图-2.2.1

3.HashMap的常用方法

图-2.3.1

图-2.3.2

图-2.3.3

图-2.3.4

图-2.3.5

图-2.3.6

图-2.3.7

图-2.3.8

图-2.3.9

注：对于HashMap的 put 功能实现和扩容操作将单独分析。

4.HashMap的 put 功能具体实现

图解来源：https://www.cnblogs.com/xawei/p/6747660.html

图-2.4.1

源码如下：

图-2.4.2

注：

第1步：

判断table是否为空，若为空，则调用resize()方法进行扩容，实现对数组的初始化，这一点和JDK 1.7有所不同，JDK 1.7是在HashMap的构造函数中进行初始化（即定义的时候），此处是在进行第一次put操作时初始化，可理解为“懒加载”，即用到了才进行初始化。

第2步：

计算元素所要存储的位置，并进行合理添加

图-2.4.3

可以看到，首先将得到key对应的哈希值：【h = key.hashCode()】，然后通过hashCode()的高16位与低16位异或【(h = k.hashCode()) ^ (h >>> 16)】，最后进行取模运算【(n - 1) & hash】得到最终的索引位置。

*>> hashCode()方法是Object类的方法，返回的是对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。

*>> 关于高16位与低16位异或：在JDK1.8的实现中，优化了高位运算的算法，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

*>> 关于取模运算：这个n是table的长度，那么(n - 1)就是table数组元素应有的下标。这个方法非常巧妙，它通过hash & (table.length -1)来得到该对象的存储位置，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，hash & (length - 1) 运算等价于对length取模，也就是hash % length，但是 & 比 % 具有更高的效率。

具体解释请看下图：

来源：https://www.jianshu.com/p/17177c12f849

图-2.4.4

第3步：

判断是否超过最大容量，若超过则进行扩容操作。（下面具体介绍扩容）

5.扩容机制的实现

源码如下：

图-2.5.1

关于链表重排的过程，请耐心看下图：

来源：https://www.jianshu.com/p/17177c12f849

图-2.5.2

三、其他内容（推荐几篇笔者认为挺好的他人博客）

1.HashMap底层实现原理及面试问题

https://blog.csdn.net/suifeng629/article/details/82179996

2.HashMap源码分析——基于jdk1.8

https://www.cnblogs.com/developer_chan/p/10481558.html

3.HashMap线程不安全的体现

首先需要强调一点，HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环(迁移数据使用头插法导致环形链表)和数据丢失是在JDK1.7中出现的问题，在JDK1.8中已经得到解决(迁移数据使用尾插法)，然而1.8中仍会有数据覆盖这样的问题。

https://www.cnblogs.com/developer_chan/p/10450908.html

4.哈希表&哈希碰撞&解决办法

https://blog.csdn.net/hotchange/article/details/80159671

5.面试必备：HashMap/HashTable/ConcurrentHashMap的原理与区别

https://www.cnblogs.com/heyonggang/p/9112731.html