2022年，我用两万字详细总结HashMap(JDK1.8)底层原理

曾经终败给现在 2023-10-01 16:41 8阅读 0赞

欢迎来到HashMap的学习之旅！

![e2ce56f2a5394919bc3addfcb0c6433b.png][]

**先检测下你对HashMap jdk1.8原理掌握情况**  
1、知晓jdk1.8中，HashMap底层是由数组、链表、红黑树组成  
2、能说清楚什么是hash计算，hash计算实现的原理  
3、了解hash冲突，知道怎么解决hash冲突  
4、明白为什么数组的长度必须为2^n  
5、知道为什么链表长度超过8才转成红黑树  
6、hashCode为什么要右移16位做异或运算  
7、能简述说出HashMap的扩容机制  
8、了解默认负载因子(loadFactor)为什么为0.75  
9、知道扩容时候原数组转移到新数组的特点  
10、能说出来添加元素put的流程

## 前言 ##

如果都会的差不多了，看看本文还有没有可以查缺补漏之处~

--------------------

## HashMap JDK1.8 ##

> **JDK1.8中对HashMap做了哪些改变?**
> 
> 1.  在java1.8中,如果链表的长度超过了8,那么链表将转换为红黑树。(桶的数量必须大于64,小于64的时候只会扩容)
> 2.  发生hash碰撞时,java1.7会在链表的头部插入,而java1.8会在链表的尾部插入
> 3.  在java1.8中,Entry被Node替代。

## 一、HashMap概念 ##

*  HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
 *  HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
 *  HashMap 的实现不是同步的，这意味着它是线程不安全的。它的key、value都可以为null。此外，HashMap中的映射是无序的。

我们现在用的都是 JDK 1.8，底层是由“`数组+链表+红黑树`”组成，而在 JDK 1.8 之前是由“`数组+链表`”组成。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]

## 二、Hash方法 ##

在了解HashMap源码之前，我们要知道hash()方法的用途。

设想，如果我们要查map中的某个value值，是不是要根据相对应的key来查。但key是键对象，我们是需要一个一个进行比对key是否相同才能拿到value值，这样在检索上就会耗费大量的时间，所以有没有什么更快的方法呢。

我们都知道数组有个好处就是查询快，可以根据索引迅速锁定指定位置。  
![在这里插入图片描述][02e94bbce18a47d3ba27f6f7753b8e31.png]  
那我们就想到，能否把key转换为索引，也就是数组下标，这样就可以遵循数组查询原理，更快地找到目标value。

**因此，我们引出了hash计算。将key经过hash计算后，转换为底层数组中的索引值，就可以迅速定位其在HashMap中的位置。如下如所示**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
这样也会有一个额外的好处，两个**相同**的key，它们的hash值也是一样的，就不会被同时存放到数组中，而是在数组同一个索引上被覆盖。

细心的人就会想到，如果两个**不同**的key（元素），得到的hash值是一样的怎么办？也会被覆盖吗？这就是我们接下来要将的**哈希冲突**

## 三、Hash冲突（碰撞） ##

当我们对某个元素进行hash计算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的**哈希冲突**，也叫**哈希碰撞**。哈希函数尽可能地保证计算简单和散列地址分布均匀，但是，数组是一段连续的**固定长度**的空间，并不能百分百保证不发生哈希冲突。

如下图所示，两个不同key进行hash计算后，得到了相同的值，若其中一方会被覆盖，那这不就乱套了嘛，它们分别是两个不同的元素，我们肯定希望是都存在的。  
![在这里插入图片描述][0d750e0db5f844d0b9d821d621eaaaa9.png]  
所以接下来要讨论如何解决hash冲突问题

--------------------

### 重点1：“拉链法”解决hash冲突 ###

Java中HashMap是利用“拉链法”处理hash冲突问题。

**“拉链法”原理**  
HashMap是一个数组，数组中的每个元素是链表。put元素进去的时候，会通过计算key的hash值来获取到一个index，根据index找到数组中的位置，进行元素插入。**当新来的元素的hash值与索引位置上的元素冲突时，就采用尾插法的形式插入到该索引上（jdk1.7是头插法，jdk1.8改为了尾插法）**

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
另外，当hash计算出来之后，就可以用hash值去代替两个key对象进行比较达到存取操作。所以每一个链表节点Node<K,V>都包含这四个属性

static class Node<K,V> implements Map.Entry<K,V> {
        
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

![在这里插入图片描述][013b6e303c1442aca1805b204fafa81a.png]  
key：键对象  
Value：值对象  
hash：hash值  
next：指向下一个节点

--------------------

### 重点2：为什么jdk1.8从头插法改为了尾插法？ ###

**因为在并发情况下，头插法会出现链表成环的问题，头插法有链表成环的问题，所以jdk1.8 才采用尾插法来替代头插法**

--------------------

另外链表也不是无限长的，它有一个界限，**如果链表的长度超过了8就会自动转换为红黑树**。

--------------------

### 重点3：为什么链表超过8转换为红黑树 ###

让我们来看看官方的解释，这里涉及到了泊松分布

Because TreeNodes are about twice the size of regular nodes, we
    use them only when bins contain enough nodes to warrant use
    (see TREEIFY_THRESHOLD). And when they become too small (due to
    removal or resizing) they are converted back to plain bins.  In
    usages with well-distributed user hashCodes, tree bins are
    rarely used.  Ideally, under random hashCodes, the frequency of
    nodes in bins follows a Poisson distribution
    (http://en.wikipedia.org/wiki/Poisson_distribution) with a
    parameter of about 0.5 on average for the default resizing
    threshold of 0.75, although with a large variance because of
    resizing granularity. Ignoring variance, the expected
    occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
    factorial(k)). The first values are:
    0:    0.60653066
    1:    0.30326533
    2:    0.07581633
    3:    0.01263606
    4:    0.00157952
    5:    0.00015795
    6:    0.00001316
    7:    0.00000094
    8:    0.00000006
    more: less than 1 in ten million

这个数据的大概意思是，**在一定条件下，链表长度符合泊松分布，链表长度达到8的概率非常低。而且转换为红黑树需要的代价还是很高的，所以我们尽量不想它转换为红黑树，又不想让链表长度太长（影响查询效率）所以采用8作为链表转换为红黑树的极限最为合适。**

--------------------

## 四、HashMap1.8源码分析 ##

### Part1：hash计算原理 ###

之前我们提到，为了利用数组索引进行快速查找，我们需要先将 key值映射成数组下标.，采取的就是hash算法。问题是，我们要采用怎样的hash算法呢？

`能不能直接用hashCode返回hash值？`  
不能。hashCode返回的是int值，它的范围是在-2147483648-2147483647。如果存的元素并不多，总不可能为了得到索引创建一个这么大的数组空间吧。

**jdk1.8给出的hash算法分为两个步骤：①先得到扰动后的key的hashCode：(h = key.hashCode() )^ (h >>> 16) ②再将hashCode映射成有限的数组下标index：(n - 1) & hash**

现在来看看hash算法如何将key转换为数组下标的

#### （一）(h = key.hashCode() )^ (h >>> 16) ####

第一部分内容是为了得到“扰动”后的hash值

/**
         * 将指定的值与此映射中的指定键相关联。如果映射先前包含键的映射，则替换旧值
         *
         * 参数：key – 与指定值关联的键
         *      value – 与指定键关联的值 
         * 
         * 返回：与key关联的前一个值，如果没有key映射，则返回null 。
         */
        public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }

首先，key不为空的时候，`hash(key)`方法会对`hashCode`值做一个高低16位异或运算

static final int hash(Object key) {
        
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

实现过程就是这段代码`(h = key.hashCode()) ^ (h >>> 16);`，key不为空的时候，进行这些操作，给定一些数据，计算过程如下：

![在这里插入图片描述][69ee8ace5ff647a7a56f375fcbb3d1e1.png]

看到这你可能会产生两个问题 1)为什么要将hashCode向右移16位？ 2)为什么要做异或运算？

不急，第一部分最终产生的hash值是h，但不能直接拿来当数组下标，因为这个数可能很大。所以接下来我们要将其映射成有限长度的数组下标，也就是第二部分内容：(n - 1) & hash

#### （二）(n - 1) & hash ####

第二部分是为了将上一部分的hash值映射成数组下标  
有没有注意调用hash()最后值会返回给putVal作为它参数。调用`putVal`方法后有这样一段代码：

i = (n - 1) & hash

这段代码就是实现数组下标映射  
i 就是最终数组索引值index  
n 是新数组长度  
hash就是参数h（上一步计算返回的hash结果）

计算过程如下：  
**假设数组长度为16，经过(h = key.hashCode() )^ (h >>> 16)得到的hash值的低16位是1101001010100110**（一般数hashmap数组长度都在2^16范围内，所以就用低16位演示了）

> n-1=15  转换为二进制 ==> 1111  
> 与hash值进行相与  
> 1101001010100110  
>           1111  
> 结果是：0110，所以对应的数组下标是6  
> ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_18_color_FFFFFF_t_70_g_se_x_16]

这样两步就完成了key对象映射到指定数组索引上了。诶，有人就会很奇怪，明明hash进行一个&运算就可以找到数组下标了， 为什么还要将key的hashCode>>>16无符号右移16位？又将高低16位进行异或运算呢？这样做的目的是什么。现在，让我们一起来探讨这几个问题

--------------------

#### 重点4：为什么要将key的hashCode>>>16无符号右移16位进行高低异或运算？ ####

如果不这样做，直接使用key的hashCode和数组长度-1做与运算，当数组的长度很短时，只有低位数的hashcode值能参与运算。  
![在这里插入图片描述][ba645d015f5c4bd9852f6efc71353dba.png]  
右移16位是为了让高16位参与进来，再与原hashcode做异或运算，这样可以将高低位二进制特征混合起来，使该hashCode映射成数组下标时可以更均匀。更好地均匀散列，从而减少碰撞，进一步降低hash冲突的几率。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_16_color_FFFFFF_t_70_g_se_x_16]  
拥有高低位特征的hash值再做与运算，映射数组下标的时候就很分散了。

--------------------

#### 重点5：为什么要用异或运算而不是与运算、或运算？ 为了更好的散列分布 ####

与（&）运算的特点是：**同为1才为1，否则为0**  
或（|）运算的特点是 ：**有一个为1，才为1，否则为0**  
异或（^）运算的特点是：**相同为0，不同为1**  
你会发现，一组数据，如果用与运算，大概率二进制结果都是1；如果用或运算，大概率二进制都是0；只有用异或运算才能保证0和1概率相等，才更好地均匀散列分布。

--------------------

### **Part2**：HashMap扩容机制 ###

因为有hash冲突的存在，所以HashMap跟ArrayList底层数组扩容是有很大区别的。官方为了尽量降低hash冲突和提高性能，设定了一个**扩容阈值**，如果HashMap中的元素大小**size**超过了这个**阈值**，就会进行**resize**()扩容。

那么现在就让我们要探讨下HashMap的扩容机制，这也是HashMap底层原理的精髓所在！

#### （一）HashMap初始容量（capacity） ####

/**
         * 默认初始容量 - 必须是 2 的幂
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

面试的时候会常问下面这个问题

--------------------

##### 重点6：为什么初始容量必须是2的幂？ #####

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同。想到的办法就是**取模运算**：hash%length，但是在计算机中取模运算效率与远不如位移运算(&)高。主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。所以官方决定采用使用位运算(&)来实现取模运算(%)，也就是源码中优化为:**hash&(length-1)**。

我们知道，当一个数是 2^n 时, 任意整数对2^n取模等效于：h % 2^n = h & (2^n -1) ，所以初始容量应设置为2^n（而且你会发现 2 ^ n - 1 的二进制都是1111…11这样的，很方便计算机计算）

--------------------

#### （二）HashMap扩容阈值（threshold） ####

//阈值，阈值=（容量*负载因子）
    int threshold;

阈值又被成为临界值，在HashMap中  
它的作用是：若HashMap的size大于threshold时会执行resize扩容操作。  
它的计算公式：阈值(threshold) = 负载因子(loadFactor) x 容量(capacity)

#### （三）HashMap默认负载因子（loadFactor） ####

/**
         * 在构造函数中未指定时使用的负载因子
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子loadFactor的主要作用是：1）计算扩容阈值 2）表示当前数组被填满的程度

--------------------

##### 重点7：为什么默认负载因子是0.75呢？ #####

为什么不是0.5或者1.0？反推法

**（一）若负载因子为1.0**  
此时意味着当数组（默认16）被填满了，才进行扩容。虽然提高了空间利用率，但不可避免的是hash冲突机会却大大增加。我们知道，链表长度超过8的时候会自动转换成红黑树，但创建红黑树的代价很大，底层红黑树越复杂，越不利于查询。**总结，若负载因子为1.0，空间利用率提高了，但是时间代价也增加了。**

**（二）若负载因子为0.5**  
分析方法和上面差不多，负载因子为0.5代表着填充到数组的一半的时候就开始进行扩容。那么，hash冲突会减少，底层链表长度和红黑树高度也随之减少，这样产生的问题就是空间利用率大大下降，也许你只需要1M的空间刚好存储，但你却准备了2M的空间来存储。**总结，若负载因子为0.5，空间利用率下降了，查询效率提高。**

**（三）负载因子为0.75最合适**  
为什么默认负载因子是0.75呢？我看了网上好多人说这是泊松分布的推导结果，但其实不是，这两者之间并没有直接关系能够证明0.75是推导出来的结果。

*我找到的有关官网的第一类解释*

> As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.  
> 意思是：作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。 较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put ）。 在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。 如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

这里并没有直接解释为什么是0.75，只是说负载因子0.75的时候在时间和空间上成本比较折中。

*第二类解释（泊松分布）*  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 3]

很多人查阅资料都知道这是泊松分布结果。以为负载因子0.75就是因此推导的，请你仔细看看这段英文的翻译(重点注意红色圈起来的部分)。

大概意思是说：因为TreeNode的大小约为链表节点的两倍，所以我们只有在一个拉链已经拉了足够节点的时候才会转为tree（参考TREEIFY\_THRESHOLD）。并且，当这个hash桶的节点因为移除或者扩容后resize数量变小的时候，我们会将树再转为拉链。如果一个用户的数据他的hashcode值分布十分好的情况下，就会很少使用到tree结构。**在理想情况下，我们使用随机的hashcode值，loadfactor为0.75情况，尽管由于粒度调整会产生较大的方差，桶中的Node的分布频率服从参数为0.5的泊松分布。下面就是计算的结果：桶里出现1个的概率到为8的概率。桶里面大于8的概率已经小于一千万分之一了。**

也就是说，默认0.75作为加载因子前提下，每个碰撞位置的链表长度超过８的概率非常小，这其实是解释了为什么链表长度超过8要转换为红黑树，而不是推导0.75怎么来的。

**所以我的总结：为什么是0.75这个准确的数还有待考究，官方也没有给出数学推导过程，只是说默认负载因子为0.75在时间和空间成本很折中，链表长度超过8的概率非常小，减少很多时间代价，它是最佳的选择。（如果有结论了欢迎一起讨论，有错之处请指正~）**

参考链接：[https://blog.csdn.net/reliveIT/article/details/82960063][https_blog.csdn.net_reliveIT_article_details_82960063]

--------------------

#### （四）扩容核心：resize() ####

resize()就是HashMap中扩容操作的方法，在resize的时候会将原来的数组rehash重新计算hash值转移到新数组上，但在扩容时使用的rehash方式有个特点是，原数组中的节点`要么就在对应新数组“原位置”上`，`要么就被分配到"原位置+旧容量"这个位置`。

/**
         * 补充一个table成员变量，他就是hashmap存储KV键的节点数组
         * 该表在首次使用时初始化，并根据需要调整大小
         */
        transient Node<K,V>[] table;

通过源码看看resize()具体怎么怎么进行扩容的，每一步都有标注解，便于大家理解。

final Node<K,V>[] resize() {
        
            Node<K,V>[] oldTab = table;  //保存原数组
            int oldCap = (oldTab == null) ? 0 : oldTab.length;  //保存原数组长度
            int oldThr = threshold;  //原阈值（没有初始化的时候是0）
            int newCap, newThr = 0;  //定义成员变量 新数组长度，新阈值
            if (oldCap > 0) {
          //如果原数组长度>0
                if (oldCap >= MAXIMUM_CAPACITY) {
          //如果原数组长度大于最大容量
                    threshold = Integer.MAX_VALUE; //增加阈值
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  //把数组长度变为原的两倍看是否小于最大容量，且原数组长度大于默认初始容量16
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; //阈值也扩大到原来的2倍
            }
            else if (oldThr > 0) // 如果原阈值>0，将原阈值赋给新数组长度
                newCap = oldThr;
            else {
                       // 零初始阈值表示使用默认值
                newCap = DEFAULT_INITIAL_CAPACITY;  //新容量为16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //新阈值为0.75（默认负载因子）*16（默认初始容量）=12
            }
            if (newThr == 0) {
          //新阈值为0
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;  //新阈值赋值给成员变量threshold
            @SuppressWarnings({
        "rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  //创建一个长度确定的新节点数组
            table = newTab;  //新数组赋值给成员变量table
            /*
            * 以下代码用于转移元素，总之就是
            * 若原数组为空，直接返回新数组
            * 若原数组不为空，把原数组转移到新数组中
            * */
            if (oldTab != null) {
          //原数组不为空
                for (int j = 0; j < oldCap; ++j) {
         //对数组进行遍历
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
         //如果原数组上元素不为空
                        oldTab[j] = null;  //置空，已经用e存储起来了
                        if (e.next == null) //e下一个元素如果为空，说明只有单节点
                            newTab[e.hash & (newCap - 1)] = e; //把e放到新数组中，e要么在 原来的位置 ，要么在 原来的位置+旧容量（后面有解释）
                        else if (e instanceof TreeNode)  //如果e是树节点
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //用拆分树的方式进行转移
                        /*
                        * 这里低位表示：原位置
                        * 高位表示：原位置+旧容量
                        * */
                        else {
         // 非单节点和树节点情况，也就是有链表结构
                            Node<K,V> loHead = null, //低位的头节点
                             loTail = null;  //低位的尾节点
                            Node<K,V> hiHead = null, //高位的头节点 
                            hiTail = null;  //高位尾节点
                            Node<K,V> next;  
                            do {
        
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
         //如果放到新数组原位置上
                                    if (loTail == null) //如果低位尾节点为null，说明位置上没有节点
                                        loHead = e; //e作为头节点
                                    else //低位尾节点不为空，说明位置上有节点了
                                        loTail.next = e; //让低位尾节点下一位指向e
                                    loTail = e; //所以e成为了高位尾节点
                                }
                                else {
         //放到的是 原位置+原容量 位置上
                                    if (hiTail == null) //若高位尾节点没有元素
                                        hiHead = e; //e作为高位头结点
                                    else //高位已有元素时
                                        hiTail.next = e; //让高位尾节点next指向e
                                    hiTail = e; //所以e成为了高位位节点
                                }
                            } while ((e = next) != null);
                            if (loTail != null) {
         //如果低位尾节点不为空
                                loTail.next = null; //让低位下一位为空
                                newTab[j] = loHead; //将原来下标指向低位的链表
                            }
                            //同上
                            if (hiTail != null) {
        
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;  //返回新数组
        }

--------------------

##### 重点8：为什么转移后的元素，要么在“原位置”上，要么在“原位置+旧容量”上？ #####

因为扩容到原来的两倍之后，参与运算的长度，它的二进制位多了一位（下图我用红色标注的数），**如果是1，那么转移后的元素在“原位置+旧容量”上；如果是0，转移后的元素在“原位置上”**

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
是低位还是高位，就取决于与运算后多出来的最高位是0还是1

--------------------

##### 重点9：理解e.hash & oldCap #####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
为什么说if ((e.hash & oldCap) == 0) 是判断是否放到新数组原位置上也就好理解了。oldCap是2^n，也就是100000000…这种二进制形式，它与e.hash(数组索引)相与的结果非0即oldCap，**如果是0则表示放到原位置（低位），反之其他表示放到原位置+旧容量（高位）**  
![在这里插入图片描述][330f4f257a004fafaebcd50f0fb004f6.png]

--------------------

### Part4：添加树节点：putTreeVal() ###

putTreeVal方法是在putVal中被调用，如果当前索引位置是树节点，就会调用该方法添加树节点元素

/**
     * 参数：
     * map：当前的hashmap对象
     * tab：当前hashmap的节点数组
     * h：hash值（要添加的元素的hash值）
     * k：变量键值key
     * v：变量值value
     */
    final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                   int h, K k, V v) {
        
        Class<?> kc = null;
        boolean searched = false;
        TreeNode<K,V> root = (parent != null) ? root() : this; //找到根节点
        for (TreeNode<K,V> p = root;;) {
         //遍历树节点元素
            int dir, ph; K pk;  //节点位置;当前遍历到的节点的hash值;key值
            if ((ph = p.hash) > h) //如果树上元素的hash值大于添加进来元素的hash值
                dir = -1;   //表示添加元素应在树的左节点
            else if (ph < h)  
                dir = 1;    //表示添加元素应在树的右节点
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))//看key是否相同，是则代表找到要覆盖的节点位置
                return p; //返回当前树节点，返回后会赋值给e，最终对value进行覆盖
    
    // 走到这一步说明当前节点的hash值和指定key的hash值是相等的，但是equals不等
            else if ((kc == null && 
                      (kc = comparableClassFor(k)) == null) ||
                     (dir = compareComparables(kc, k, pk)) == 0) {
          //得到方向
                if (!searched) {
         //如果还没有比对完当前节点的所有子节点
                /*
                *那就继续遍历树进行寻找，如果还是没找到key相同的，说明要创建一个新的节点了
                * */
                    TreeNode<K,V> q, ch;
                    searched = true;
                    if (((ch = p.left) != null &&
                         (q = ch.find(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                         (q = ch.find(h, k, kc)) != null))
                        return q;  //如果找到了就返回
                }
                dir = tieBreakOrder(k, pk); //没找到就比较一下当前节点和指定key值，以得到方向
            }
    
            TreeNode<K,V> xp = p;
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
        //根据方向dir决定
            //是去左节点还是右节点，如果是null表示整棵树找完了，但还没有找到符合的节点，就要添加新节点了
                Node<K,V> xpn = xp.next;//xpn作为新节点的next
                TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);//创建新树节点
                if (dir <= 0) //根据方向判断，新节点是在树左边还是右边
                    xp.left = x;
                else
                    xp.right = x;
                xp.next = x; //当前链表中的next节点指向到这个新的树节点
                x.parent = x.prev = xp;//新的树节点的父节点、前节点均设置为当前的树节点
                if (xpn != null) //如果原来xp的next节点不为空
                    ((TreeNode<K,V>)xpn).prev = x;//那么原来的next节点的前节点指向到新的树节点
                moveRootToFront(tab, balanceInsertion(root, x)); //平衡树，确保不会太深，确保树的根节点在数组上
                return null;
            }
        }
    }

### Part5：链表树化：treeifyBin()、treeify() ###

我们知道，当链表的长度超过8的时候，就会转换成红黑树，这个过程就是**树化**，核心代码treeifyBin()和treeify()，前者先将`链表`转化为以树节点存在的`双向链表`，后者将该`双向链表`转换为`红黑树`结构，现在一起来了解下(见注释)

**首先要知道，超过8的链表不会立马转换为树，数组长度要大于树化阈值，才可以，否则要先进行resize扩容到原来的2倍。**

/**
     * 可对其进行树化的 bin 的最小表容量。（否则，如果 bin 中有太多节点，则调整表的大小。）
     * 应至少为 4 * TREEIFY_THRESHOLD 以避免调整大小和树化阈值之间的冲突
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

**treeifyBin()**

/**
     * 替换给定哈希索引处 bin 中的所有链接节点，除非表太小，在这种情况下调整大小
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        
        int n, index; Node<K,V> e;
        //如果当前数组长度小于树化阈值
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize(); //将数组扩容为原来2倍
        else if ((e = tab[index = (n - 1) & hash]) != null) {
         //如果链表的头节点不为空
            TreeNode<K,V> hd = null, tl = null; //定义头节点、尾节点
    		 /**
    		 * 先将树节点全部用双向链表连接起来
    		 */
            do {
        
                TreeNode<K,V> p = replacementTreeNode(e, null); //将链表节点转换为树节点
                if (tl == null)  //如果是第一个节点
                    hd = p;  //把p节点赋值给列表头
                else {
        
                    p.prev = tl; //新节点前一个结点设置为尾部
                    tl.next = p; //尾部下一个节点设置为新节点
                }
                tl = p;  //p节点赋值给尾部tl
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)  //链表头节点放到到数组索引上
                hd.treeify(tab); //树化
        }
    }

**treeify()**

/**
     * 从此节点链接的节点的表单树
     */
    final void treeify(Node<K,V>[] tab) {
        
        TreeNode<K,V> root = null; //树的根节点
        //声明树节点x和next，先把当前节点赋值给x，开始循环
        for (TreeNode<K,V> x = this, next; x != null; x = next) {
        
            next = (TreeNode<K,V>)x.next;  //next节点作为x的下一个节点
            x.left = x.right = null; //x左右孩子为空
            if (root == null) {
          //如果根节点为空，x作为根节点
                x.parent = null; 
                x.red = false; //节点颜色设置为黑色
                root = x;  
            }
            /*
            *以下部分和putTreeVal()添加树节点元素代码是类似的，找到方向，然后进行插入
            * */
            else {
         //根节点不为空
                K k = x.key; 
                int h = x.hash;
                Class<?> kc = null;
                for (TreeNode<K,V> p = root;;) {
        
                    int dir, ph;
                    K pk = p.key;
                    if ((ph = p.hash) > h) //如果root节点的hash值大于
                        dir = -1; //方向左边
                    else if (ph < h) //小
                        dir = 1; //方向右边
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);
    
                    TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
        
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        root = balanceInsertion(root, x);  //平衡树
                        break;
                    }
                }
            }
        }
        moveRootToFront(tab, root);
    }

### **Part6**：添加元素：putVal() ###

看到这里，说明已经掌握了基本的HashMap底层源码含义了，再来解读putVal就十分轻松了。putVal方法是添加元素的核心，调用map.put(K,V)往Map集合中添加元素，实际上就是调用putVal方法的过程。现在来让我们来看看源码（所有不懂的地方都有注释滴，最后奉上流程图）

/*
    * hash – 原hash值，通过hashcode做高低16位异或运算得到的
    * value – 要放置的值
    * onlyIfAbsent – 作用：不让具有相同的key覆盖旧值，只有不存在值的时候，才可以添加* 值，默认false；如果为true，则不更改现有值
    * evict – 如果为 false，则表处于创建模式。
    */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
        
        //1、如果tab为空或者长度为0，执行resize()方法进行数组扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
    	//2、如果hash计算后的数组索引位置上没有节点那就newNode创建一个节点放到数组对应的索引上
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        
        
        //3、如果数组索引位上有节点，就判断该节点与要放入的节点的hash值、key是否相同
        //  或者满足后进来的key不为空且符合equals方法，就直接跳到代码末尾看条件是否允许直接覆盖value值
            HashMap.Node<K,V> e; K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;  //将p先赋值给临时变量e，后面判断是否允许修改，若允许则直接覆盖value值
                
                //4、如果索引上的节点是树节点，进行树节点添加元素操作
            else if (p instanceof TreeNode)  //如果当前索引上的节点是树节点
                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //是 则进行添加树节点元素的操作
    		
    		//5、不是树节点，说明是链表节点，则对链表节点进行遍历
            else {
          
                for (int binCount = 0; ; ++binCount) {
        
                //6、遍历直到某一个节点后面是null，用尾插法插入新节点，在判断链表是否超过8，超过则转红黑树
                    if ((e = p.next) == null) {
         //遍历发现某节点下一位没有元素了
                        p.next = newNode(hash, key, value, null);   //在最后面插入新节点（尾插法）
                        if (binCount >= TREEIFY_THRESHOLD - 1) //判断链表长度是否有达到转换红黑树的阈值8
                            treeifyBin(tab, hash);  //转化为红黑树
                        break;
                    }
                    //7、加入新节点后链表长度没超过8或者遍历发现有相同的key，就结束循环，准备进行覆盖
                    if (e.hash == hash &&  //发现有相同的key存在
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;  //把e赋值给p，相当于遍历链表一直往下遍历
                }
            }
            //8、e不为空，说明已存在相应key的节点。如果两个条件 1)!onlyIfAbsent 2)旧value为空 
            //  满足其中一个则将新的值覆盖旧值
            if (e != null) {
         
                V oldValue = e.value;  //记录旧值（即原来链表上相同key的节点的value值）
                 //onlyIfAbsent默认false,默认!onlyIfAbsent=true
                if (!onlyIfAbsent || oldValue == null)  //若允许修改或旧值为空
                    e.value = value;  //覆盖旧值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //9、当HashMap中元素个数超过阈值(数组大小*负载因子)时，就进行扩容
        ++modCount;  //结构性次数修改+1
        if (++size > threshold)
            resize();  //扩容
        afterNodeInsertion(evict);
        return null;  
    }

作一个总结

##### 重点10：调用put的全过程（一张流程图搞定） #####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
就是这么简单粗暴

[e2ce56f2a5394919bc3addfcb0c6433b.png]: https://img-blog.csdnimg.cn/e2ce56f2a5394919bc3addfcb0c6433b.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6e3559746022460e9ed8edb8e0082496.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[02e94bbce18a47d3ba27f6f7753b8e31.png]: https://img-blog.csdnimg.cn/02e94bbce18a47d3ba27f6f7753b8e31.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/ae76a19780154d6eab8c475f0f524f73.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[0d750e0db5f844d0b9d821d621eaaaa9.png]: https://img-blog.csdnimg.cn/0d750e0db5f844d0b9d821d621eaaaa9.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/fd824f6ea95d484fa0a262e4c80dd8a9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[013b6e303c1442aca1805b204fafa81a.png]: https://img-blog.csdnimg.cn/013b6e303c1442aca1805b204fafa81a.png
[69ee8ace5ff647a7a56f375fcbb3d1e1.png]: https://img-blog.csdnimg.cn/69ee8ace5ff647a7a56f375fcbb3d1e1.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/2d813a3749ab4a3eb860bc12907d148f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_18,color_FFFFFF,t_70,g_se,x_16
[ba645d015f5c4bd9852f6efc71353dba.png]: https://img-blog.csdnimg.cn/ba645d015f5c4bd9852f6efc71353dba.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_16_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ef5a723bd9c14c2cb3f550d577fa4e1f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_16,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/f66a50e00fcb4bb6bb1061886dcf6a7c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[https_blog.csdn.net_reliveIT_article_details_82960063]: https://blog.csdn.net/reliveIT/article/details/82960063
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/5aa64e1a27c04e5a944042e9a1d761ce.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/74d95b2a0190454da0bd6fe547ab15fb.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16
[330f4f257a004fafaebcd50f0fb004f6.png]: https://img-blog.csdnimg.cn/330f4f257a004fafaebcd50f0fb004f6.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA44CM5Yaw6a2C44CN_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/b4387aeb3a2341eaafc7e9a9c3b551a2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA44CM5Yaw6a2C44CN,size_20,color_FFFFFF,t_70,g_se,x_16