今天我们来从源码层面分析JAVA的HashMap底层实现原理，我们还是先从HashMap的构造方法来分析。
我们发现HashMap有四个构造方法，
首先还是来分析它的无参构造方法，源码如下：
这个方法比较简单定义了一个数据成员loadFactor的值，设置为0.75。
我们再来看第二个方法HashMap(int)
发现它调用了HashMap(int,float)构造方法，我们再来看这个方法的源码：
这个方法首先判断了initialCapacity是否小于0,假如小于0就抛出IllegalArgumentException的异常。
接着判断initialCapacity是否小于MAXIMUM_CAPACITY这个值
这个是值是2的30次方，假如initialCapacity是否大于了MAXIMUM_CAPACITY这个值。就把initialCapacity赋值为MAXIMUM_CAPACITY这个值。接着判断了传入参数loadFactor的值是否存在参数异常的问题，假如它<=0或者isNan判断这个浮点数是否超过了计算机表示的上限，假如存在异常也抛出IllegalArgumentException的异常。然后设置数据成员loadFactor的值为loadFactor,数据成员threshold为一个tableSizeFor(initialCapacity)的返回值，
这个函数就是用来返回一个最接近cap这个值的2次幂的值，我在这边文章以详细介绍过其原理，感兴趣的话可以去读一下，这里不在赘述。
回到这个构造方法，所以这个方法的最后一句就是初始化HashMap的容量为最接近我们传入的initialCapacity的2次幂值。
我们再来看最后一个构造方法public HashMap(Map<? extends K, ? extends V> m)这个方法源码如下：
首先定义数据成员loadFactor为默认值0,75，接着调用putMapEntries方法，我们再来看这个方法的源码。
该方法首先记录的传入Map对象m的长度记为s，假如s<=0就什么也不干，大于0的话先判断数据成员table是否为空，
table是Node<K,V>的数组Node<K,V>的具体结构如下
它是HashMap内部的一个静态内部类，静态内部类是一种特殊的内部类，它不需要外部类的实例来创建其实例。静态内部类可以有自己的静态成员和非静态成员，但不能直接访问外部类的非静态成员（除非通过外部类的实例）。看了它的数据成员我们知道了这就是一个键值对形式的节点。我们在回到方法：
回到第一个判断判断table是否为空，假如为空，定义一个float，值为s/loadfactor+1,定义了int值t，如果ft 的值小于MAXIMUM_CAPACITY就定义t为ft，否则的话定义t = MAXIMUM_CAPACITY，如果t大于了threshold,就更新threshold为最接近t值的2次幂值。假如table不为空且s>与threshold的值就调用resize函数这是一个非常长的函数我们分块来看。
该方法定义了一个oldTab Node数组记录当前数据成员table即存储数据的Node数组，接着定义了oldCap变量记录的就是oldTab的长度，定义oldThr记录threshold，定义两初始值为0的变量newCap，newThr，是一个判断有三个分支，第一个分支是oldCap是否大于0，大于0的话该分支继续判断oldCap是否大于等于DEFAULT_INITIAL_CAPACITY，将threshold定义为Integer的最大值，返回oldTab，接着将 newCap赋值为oldCap的2倍之后判断newCap是否小于Max_Capacity，判断oldCap是否大于等于DEFAULT_INITIAL_CAPACITY假如两个条件都满足，就复制newThr为oldThr的两倍。接着我们来看第二个分支，第二个分支比较简单，判断oldThr是否大于0，假如大于0，就将newCap赋值为oldThr，第三个分支的情况是将newCap赋值为DEFAULT_INITIAL_CAPACITY，将newThr赋值为DEFAULT_INITIAL_CAPACITY * DEFAULT_Load_Factor转换为的int值。接着继续判断newThr是否等于0，等于0的话定义一个float变量ft初始化值为newCap * loadFactor的值。newThr根据newCap<MAXIMUM_CAPACITY和ft<MAXIMUM_CAPACITY两个条件来进行不同初始化，假如两个都为真就将newThr赋值为ft，否则为Integer的最大值,总的来说这一整段代码块根据不同条件来初始化newThr,newCap两个变量的值。接着将threshold的值为赋为新的newThr.然后在定义一个新的Node数组newTab长度为newCap。，然后将table赋值为newTab。
总结一下这段代码的功能，计算HashMap扩容后新的的阈值threshold，和生成的Node数组容量。
接着这段代码块主要是重新构造扩容后的HashMap的结构，我们具体来看这个过程是怎样进行，这是一个遍历oldCap数组的循环，首先定义了一个Node节点e，将e赋值为当前遍历的节点，判断是否为空，假如不为空，就将旧数组oldCap这个位置的节点定义为空值。接着判断e是否还有next节点是否为空，这个就是用来判断当前节点是否存在哈希冲突的，假如为空我们就可以直接存储e节点在这里它使用用的是一个线性哈希函数(k%数组长度)来确定e的存放位置。但为什么它的写法是e.hash & newCap-1的原因请看我写的这篇文章，里面详细解释了原因。
ArrayDeque的深入理解
https://blog.csdn.net/weixin_61854715/article/details/140295463后面两个判断分支我们已经可以看出HashMap的底层原理，有Hash冲突的节点HashMap底层是使用了两种数据结构存储的，一个是红黑树，一个是链表。第一个判断分支明显可以看出是对节点是红黑树如何处理，第二个节点是对链表如何处理的。对于红黑树的原理讲解可以看我写的这篇文章来了解什么是红黑树，这里不再赘述。
TreeMap的深入理解https://blog.csdn.net/weixin_61854715/article/details/140381501
我们先来看红黑树它是如何进行处理的打开split函数源码:
首先我们得明确split函数不是HashMap里的方法，它是HashMap的内部类TreeNode的方法，接着看该方法的具体实现，首先定义了一个变量b来记录当前的TreeNode的对象，后面定义了4个为null值的TreeNode变量loHead，loTail,hiHead,hiTail。定义两个int类型变量lc，hc，然后开始遍历这颗红黑树，我们来看一看遍历中的具体操作，首先定义了两个TreeNode变量e,赋值为b即这颗红黑树的根节点，然后定义了一个为初始化的TreeNode变量next，，然后遍历开始，首先赋值next为e的next节点，但我们查看TreeNode的定义发现并没有next的定义，我们可以知道这个是TreeNode的父类定义的，
发现TreeNode是Node的一个子类，这代表java中对红黑树节点的处理可以转换为链表节点的处理，回到split方法源码：next = e.next，e.next = null,这两句代码就是将e这个节点单独提取出来，接着使用判断e.hash的值于bit进行&运算，我来解释一下为什么判断的意思，要明白其是什么意思，我们的看bit的含义是什么，回到resize方法使用这个方法的这句话，
传入的值对应bit的是oldCap，oldCap记录的是原先HashMap的Node数组长度。所以说这个bit是数组的长度，我们知道数组长度是一个2次幂的值，所以所以bit的二进制形式是除最高为1其余位均为0的数，对这样的一个值做&运算判断的就是判断这个值对应bit二进制最高位的那个位置的值是0还是1，在这里就是具体判断e节点的hash值的最高位是对应bit二进制最高位的那个位置是0还是1，假如是0的话，后面一段代码就是把这个节点放入头节点为lohead，尾节点为lotail的链表里，使用lc记录该该链表的长度，为1的话就把这个节点放入头节点为hihead,尾节点为hitail的链表里，使用hc记录该链表的长度，相当于我们正在把红黑树拆成两个链表，为什么要这么干呢?为的是区分这些节点是否需要搬离位置index，这两链表存放的就是第一个链表节点是在Hash表扩容后不必搬到新位置的节点，后面的链表是需要搬到新位置的节点，由于我们现在使用的是线性哈希函数，设e的hash值为x，x = m * bit + k,m是一个正整数，k是余数即当前节点在HashMap里的索引值，HashMap扩容是将容量扩大两倍，即把bit扩大两倍那此时hash值是多少呢，我们把x的表达式变形一下，x = m /2 * 2 * bit + k 假如m/2为整数即m为偶数，那么x的索引值不变还是为k，假如m为奇数，我们再次将表达式变形一下，x = m /2 * 2 * bit + k - 0.5 * bit *2 + bit = (m/2 -0.5) * 2 * bit + k + bit,m/2-0.5是一个整数，所以该节点的索引值变为了k + bit。为什么它使用的判断方式是e.hash &bit == 0，由于hashMap的容量一定是2次幂，这个计算就是计算e的hash值是否大于原数组长度，大于原数组hash值对应bit的位一定为1，新hash值就要加上一个bit，否则的话就是新hash值是不变的。举个例子说明这句话的意思：
例如7 % 4 = 3 当我们把4扩大两倍后 7 % 8 =7 由于7>4所以hash值添加了一个4
那么假如是3 % 4 = 0 当我们把4扩大两倍后 3 % 8 =3由于3 < 4所以hash值不变。
所以说这两个链表loHead链表存储的是无需搬动的节点即索引值还是index，hiHead链表存储的是需要搬动到index + bit位置的节点。这给我们带来了一个重要的结论重新hash的过程中节点的hash值要么不变，要么加上一个bit位，画一个图来解释一下这个结论的重要意义，
即所有移动节点一定是移动到后面扩容的空位置，且所有移动到同一位置的节点它原先通过hash函数计算出来的索引值一定是相同的。
明白这个结论的意义后我们继续看下面的代码，下面首先判断toHead链表是否为空，不为空的化判读长度是否小于6即将loHead进行反树化，我们来看一下如何反树化。
打开untreeify源码，该方法首先定义了一个两个Node节点，hd，tl接着开始遍历Node节点，然后定义一个p，该值为map调用replacementNode返回的一个Node节点，这个方法就是把TreeNode转换为Node用的，后面的语句就是构建链表的常规操作这里不再解释，最后返回构建好的链表hd。
回到split方法，另一个判断分支就是判断是否需要树化即元素个数大于6，但里面有一个判断hihead是否等于null原因是因为假如hihead==null证明说所有节点都不需要搬离原位置，那么树结构并没有被破坏，我们也无需进行树化。我们来看一下具体是如何进行树化的，
首先定义一个root变量，为红黑树的根节点，然后开始遍历自己这个Node节点，下面一段代码就是红黑树的构建过程，原理不再细讲，请看我写的另一篇文章，详细介绍了红黑树的构建过程。
对TreeMap的深入理解https://blog.csdn.net/weixin_61854715/article/details/140381501
回到split方法，我们发现下一个判断类似，也是判断hihead链表是否需要进行树化，储存其到hash表的对应位置，这里就不在赘述。split方法到这就分析完毕了，其功能就是将具有hash冲突的节点位置再hashMap扩容后重新进行一个组织，设计非常巧妙。
我们回到resize()方法来看一下对链表是如何处理的。即判断的第三个分支，我们发现和split方法基本一致，只是因为是链表节点操作更加简单这里不在赘述。
到这里resize方法我们分析完了，其功能就是在HashMap扩容后重新哈希的过程。我们回到putMapEntries方法，s>threshold分支我们就分析完了，接着看后面的for循环遍历，这个就是开始放置m里的元素到Hash表里，我们来看一下putVal方法源码看一下具体添加元素的过程。
下面是putVal方法的源码：
首先定义了一个Node数组Tab，Node节点p，以及两个int值n ，i，第一个判断首先将tab赋值为数据成员table，判断是不是为空，或者判断使用n记录tab长度是否为0，满足这两个条件之一就是用resize函数进行重新hash并记录重新hash后HashMap的长度，接着判断放置元素位置是否已经有元素，没有的话直接将元素放到对应位置，有的话就是要对hash冲突进行处理，我们来看第二个判断分支它时如何处理的首先定义定义一个Node节点e，一个键值k，判断p节点的hash值是否等于传入节点的hash值，将k赋值为p节点的key值判断等不等于传入的key判断是否满足这两个条件，接着判断key!=null 和key是否和k相等判断满不满足这两个条件，满足上面两个条件组合中的一个就直接将e节点赋值为p节点，这个分支就是判断传入节点的hash值是否已经存在，接着判断p是否是一个树节点是的话就将e赋为putTreeVal的返回值。putTreeVal原理话这里不在赘述，要了解原理看我上面的链接文章。它的功能就是插入节点到红黑树中去，假如红黑树已存在该键值的元素返回值就是原来的旧的值，不存在的话就是空值。接着我们看最后一个分支，最后一个分支也是对Node节点的处理，即对链表结构的处理，通过遍历链表，找到链表的末尾插入节点，然后判断是否需要树化即bitCount >= TREEIFY_THRESHOLD-1,使用treeifyBin函数对链表进行树化。下面一个判断是遍历链表的时候确定一下该键是否已存在，存在的话直接跳出循环。其实这一段代码块就是判断该键值是否已经存在于HashMap中，存在就把已存在的键值对用e存储起来。
最后一个判断是判断e是否为空，即判断插入值的键值是否已经存在于HashMap中，假如存在即e不为null我们使用变量oldValue先记录下e节点存储的数据，接下来判断假如onlyIfAbsent变量为false或者oldValue为null,这两个条件代表的含义分别是：
!onlyIfAbsent：如果onlyIfAbsent为false（或者更具体地说，如果方法的调用者没有指定“仅当键不存在时才插入”的选项），则无论旧值是否为null，都会更新值。oldValue == null：如果旧值为null，这意味着虽然键已经存在，但之前并没有与之关联的值（即这是一个“占位”的键）。在这种情况下，无论onlyIfAbsent的值如何，都会更新值。
满足这两个条件之一我们就将e节点的值赋为传入的值。这是对键值存在，但存储值为空的情况的处理,即第二个跳出循环的处理，后面调用afterNodeAccess方法。在HashMap中这个方法无语句，是一个空实现体没有意义，然后返回oldValue值，即更新键里面在更新之前的原值。后面的几句话比较简单第一个modCount变量是java中快速失败机制，保证多线程下迭代的安全性具体的请看我这篇文章的补充知识。
后面判断++size > threshold即判断当前HashMap元素个数是否超过阈值threshold，超过调用resize方法进行重新哈希，然后调用afterNodeInsertion方法，这个在HashMap中也是一个空实现体，没有意义，最后返回null，因为这是插入键值不存在的情况。
到这里我们就分析完了HashMap最后一个构造方法，总结一下，经过源码分析我们可以看到HashMap底层原理是是数组+链表+红黑树，我们重点分析了重新哈希过程即resize函数，以及HashMap添加元素，树化，反树化的过程。
