提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

HashMap作为一个面试高频问题相信很多人都对其有一定的了解，例如jdk1.8后，HashMap的数据结构是数组+链表+红黑树、数组的默认初始容量16、加载因子是0.75，2倍扩容，节点数达到8后树化，到6后链化等。
这些面试问题相信大家都有一定的了解，但这些参数背后的逻辑来源部分的同学可能都像过去的我一样知其然而不知其所以然，作为一个开发小白近期也膜拜了各个大佬对HashMap的解析，通过对比源码发现有些细节可能有些许误差，本文尝试以一个小白的视角从头开始读懂HashMap的源码，掌握HashMap的运行原理。

一、HashMap是什么？

HashMap是一种通过哈希表+红黑树的结构实现的Map实现类，通过下图可以了解HashMap的继承关系，简单来说HashMap通过数组结构存储K-V结构的数据（通过对key进行Hash运算计算存储数组下标），通过链表解决哈希冲突问题，通过红黑树解决链表长度过长时的查询效率问题。

ps：在开始解析源码之前我们简单了解一下位运算，由于位运算的计算效率要远远大于算数运算，HashMap中大量运用了位运算来代替部分我们熟悉的算数运算方式。每当我们在解析过程中遇到一种位运算方式时我们会对其进行一个简单的了解。

二、HashMap内置参数

在解析HashMap的方法之前我们首先了解一下HashMap中自带的内置参数都有什么，在此我们先根据参数注解简单了解下参数大概都有什么作用，具体如何使用在后续方法解析中了解

1.内置静态常量

首先我们先来了解HashMap类中重要的6个静态常量，规定了我们的6个默认参数。

1.1.DEFAULT_INITIAL_CAPACITY（默认初始容量）

源码如下：

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

通过命名可得知该参数为默认初始容量，值为1<<4也就是16。

通过源码的注解我们发现对这一项参数HashMap并没有过多解读，只是说明该参数必须为2的倍数，具体原因暂且不知，看看在后续的方法解读中能否了解。

ps：<<为左移运算符，也就是二进制数字00000001向左位移4次变成00010000，我们可以模拟下左移运算，00000001向左位移一位变成00000010，通过二进制换算为2，位移两位为00000100，换算二进制为4，由此得知，每向左移运算一位等于算术运算乘2，那1<<4也就是1*（2^4）=16，自此我们了解了这一常量值为16。

1.2.MAXIMUM_CAPACITY（最大容量）

源码如下：

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

根据命名得知该参数为最大容量，值为2^30=1073741824。（对于该值我们只需要了解最大容量默认为2的30次幂即可）

接下来看一下注解，我们发现注解说明为当我们通过任意构造函数传入的值大于该数则替换为该数，那是否是说HashMap最大的容量就是1<<30呢？我们暂时先保持疑虑。

ps:在这里说一下为什么最大容量为1<<30而不是1<<31或更高呢，我们了解int类型的长度为4字节32个bit也就是32个二进制位，而int类型的最高位也就是最左边这一位是用来控制该整数的正负，当1<<31运算完成后会修改最高位我们会得到-2147483648这一值，所以HashMap最大容量赋值用的是1<<30而不是1<<31

1.3.DEFAULT_LOAD_FACTOR（默认加载因子）

源码如下：

        /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

这个值就是我们耳熟能详的默认加载因子了，可看到该参数的值就是我们相当熟悉的加载因子为0.75f。

注解则相当简单，在构造函数没有指定时使用的加载因子。

ps：在此简单了解一下为什么默认加载因子为0.75，加载因子是指当HashMap中存储的元素/最大空间值的阀值，当超过这个值时，会对该数组大小进行扩容。加载因子越小，哈希冲突出现的概率越小，但会浪费一定的空间，而加载因子越大，空间利用率越高，但哈希冲突的概率会增加，这时候我们就需要在哈希冲突和空间利用率中取舍，通过翻看源码介绍时我们可以发现这样一段说明：

这段官方为我们介绍了一下为何会使用0.75作为加载因子，简单理解就是在理想状态下，节点出现的概率在hash桶中成泊松分布，同时给出了桶中对应节点数和出现的概率，可以发现当加载因子为0.75时节点数达到8的概率已经十分小了。

1.4.TREEIFY_THRESHOLD（树化阈值）

源码如下：

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

根据命名得知该参数为树化阈值，值为8。

通过解读源码注解得知这个值是使用树的阈值，当桶中的元素至少达到该值后将该桶内的数据结构由链表转化为红黑树，同时要求该值必须大于2且应该至少为8，用以符合在收缩时移除树转换回链表的假设。

1.5.UNTREEIFY_THRESHOLD（链化阈值）

源码如下：

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

根据命名得知该参数为取消树化的阈值（链化阈值），值为6。

通过解读源码注解得知这个值是在调整大小期间取消树化的阈值，当桶中元素数小于6时，会将红黑树转换回链表，并且最多为6。

1.6.MIN_TREEIFY_CAPACITY（最小树化容积）

源码如下：

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

根据命名得知该参数为最小树化容积，值为64。

通过解读源码注解可了解该值为最小可进行树化的表容量，防止在表容量较小时出现一个桶存储过多数据的情况，最小值应为4倍的TREEIFY_THRESHOLD，以避免调整大小和树化之间的冲突。

ps:网上查到的大多数解读HashMap的资料对于该参数都未进行解读，根据注解我们暂时带着一个疑问进行后续方法源码的解读，难道桶元素数大于8时就一定会进行树化么？是否还有其它要求？难道说表大小小于64的时候都不进行树化？如果不树化那元素数大于8时会发生什么？让我们带着以上疑问继续探寻。

2.内置成员变量

接下来让我们了解一下HashMap中的6个成员变量。

2.1 table

源码如下

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

被transient 修饰的一个Node类型的数组，泛型为K-V结构，Node类是HashMap维护的一个内部类，内部包含hash、key、value、next四个参数，是一个单向链表。

通过对注解的解析了解到这个变量只有在第一次使用的时候进行初始化，且长度一定为2的幂（划重点，默认初始容量要求是二的倍数，现在table这个数组也要求是二的幂，在之后我们探寻下为什么又这个强制要求），同时在某些操作中也允许长度为0。

2.2 entrySet

源码如下

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

保存缓存的entrySet（）方法得到的HashMap中K-V键值对各个映射关系的集合。set存储泛型为Map接口的Entry<K,V>。

//TODO 未完待续

总结