Java进阶（HashMap）——面试时HashMap常见问题解读 & 结合源码分析

喜欢ヅ旅行 2024-02-20 10:45 39阅读 0赞

![在这里插入图片描述][83637bce85fb4a4bb69d00610159c3d4.png]

## 前言 ##

List、Set、HashMap作为Java中常用的集合，需要深入认识其原理和特性。

本篇博客介绍常见的关于Java中HashMap集合的面试问题，结合源码分析题目背后的知识点。

关于List的博客文章如下：

*  [Java进阶（List）——面试时List常见问题解读 & 结合源码分析][Java_List_List_ _]

关于的Set的博客文章如下：

*  [Java进阶（Set）——面试时Set常见问题解读 & 结合源码分析][Java_Set_Set_ _]

其他关于HaseMap的文章如下：

*  [Java学数据结构（3）——树Tree & B树 & 红黑树 & Java标准库中的集合Set与映射Map & 使用多个映射Map的案例][Java_3_Tree _ B_ _ _ _ Java_Set_Map _ _Map]
 *  [Java学数据结构（4）——散列表Hash table & 散列函数 & 哈希冲突][Java_4_Hash table _ _ _]

#### 目录 ####

*  前言
 *  引出
 *  HashMap底层结构是什么？
 *   *  JDK 1.7和1.8 对比
     *  源码Node类
 *  HashMap如何解决Hash碰撞问题？HashMap 何时从单链表，转换为红黑树？
 *   *  当链表节点的数量达到8个时，通过treeify转为红黑树
 *  HashMap的扩容机制？HashMap的数组何时需要扩容？
 *   *  1.首次添加元素
     *  2.初始容量16
     *  3.大于16时，双倍扩容
     *  总结分析
 *  HashMap设置长度为11，那么数组的容量为多少？
 *   *  第一个2的幂次方的值
 *  HashMap 何时从红黑树转换为 单链模式？
 *   *  split方法和untreeify方法
 *  HashMap 为什么在多线程并发使用过程中，容易造成死循环/死锁？
 *  如何得到一个线程安全的HashMap集合？
 *  总结

## 引出 ##

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

1.jdk1.7 HashMap：数组+单向链表；  
2.jdk1.8 HashMap：数组+链表（单向）+红黑树；  
3.当链表节点的数量达到8个时，通过treeify转为红黑树；  
4.首次添加元素，初始容量16，大于16时，双倍扩容；  
5.HashMap设置长度，第一个2的幂次方的值；  
6.红黑树元素的高位或者低位节点个数<6时，那么就调用untreeify方法来退回链表结构；  
7.**jdk1.7**采用的是**头插法**，即新来元素在链表起始的位置，而**jdk1.8**采用**尾插法**，可以有效的避免在多线程操作中产生死循环；  
8.ConcurrentHashMap高并发线程安全；

**核心：键值对，KEY不可重复，VALUE可以重复**

## HashMap底层结构是什么？ ##

### JDK 1.7和1.8 对比 ###

**jdk1.7 HashMap：数组+单向链表**

**jdk1.8 HashMap：数组+链表（单向）+红黑树**

### 源码Node类 ###

源码可以看到HashMap内部定义了静态Node类，Node类中成员有

![在这里插入图片描述][214d2f7c93814851bbac527c61275d19.png]

Node<K,V> next;

同样可以看到HashMap内部定义了静态TreeNode类，TreeNode类中成员有

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

TreeNode<K,V> left;
    TreeNode<K,V> right;

可以看出存在红黑树

而TreeNode继承了 LinkedHashMap.Entry，点进查看，可以看到 Entry也继承了 HashMap.Node。所以，TreeNode红黑树是从链表Node中转换过来的

![在这里插入图片描述][3fcc706fa6de4d5cbcb3a536bf96a3a7.png]

整体图：

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

## HashMap如何解决Hash碰撞问题？HashMap 何时从单链表，转换为红黑树？ ##

1.  首先理解什么是hash碰撞问题，HashMap存放的元素的KEY需要经过hash计算得到hash值，而这个hash值可以理解为就是此元素要存放的位置，即数组中的下标；但是**如果两个不同元素经过hash计算后，得到的hash值相同时，即两个元素要存放的位置为同一个位置，产生冲突，这种现象就叫做hash碰撞。**
2.  要想了解HashMap是如何解决hash碰撞的，那我们就需要看看HashMap的put方法的源码中的核心操作

![在这里插入图片描述][162fd59f575241e69adb8d38cd325ff7.png]

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
         //添加第一个元素时，会进入这个if结构，table为null，则第一次初始化这个table数组的长度为16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
         //判断添加的元素的KEY经过hash计算得到的下标位置是否为null
            if ((p = tab[i = (n - 1) & hash]) == null)
                //如果是null，则直接添加元素
                tab[i] = newNode(hash, key, value, null);
         //不为null的情况
            else {
        
                Node<K,V> e; K k;
                //如果key相同，则用新的元素添加到旧元素的位置，后续会将就元素返回
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //判断是否为红黑树节点，如果是红黑树节点，则添加为红黑树
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                //链表类型
                else {
        
                    //通过for循环遍历链表节点
                    for (int binCount = 0; ; ++binCount) {
        
                        //如果链表节点next节点为空
                        if ((e = p.next) == null) {
        
                            //则添加至链表的next节点属性中
                            p.next = newNode(hash, key, value, null);
                            //如果链表节点 >= 7 说明链表存在8个已存的元素节点
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                //转为红黑树方法
                                treeifyBin(tab, hash);
                            break;
                        }
                        //如果KEY相同，匹配其他API 如 putIfAbsent()
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //存入新值，返回旧值
                 if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
     ....

### 当链表节点的数量达到8个时，通过treeify转为红黑树 ###

总结：HashMap是通过3层 if 结构来判断，**数组下标位置是否有元素和下标位置的类型是链表还是红黑树**，**然后通过链表和红黑树来解决hash碰撞的问题，当链表节点>=7时（当链表节点的数量达到8个时），会通过treeify转为红黑树**。

## HashMap的扩容机制？HashMap的数组何时需要扩容？ ##

### 1.首次添加元素 ###

HashMap在第一次添加元素时，会进入第一个if结构来初始化数组的长度

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

### 2.初始容量16 ###

//添加第一个元素时，会进入这个if结构，table为null，则第一次初始化这个table数组的长度为16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;

![在这里插入图片描述][48ced5d8af674a36a447b77e04dc7b0d.png]

### 3.大于16时，双倍扩容 ###

此处resize方法就是扩容方法，jdk8中，resize方法除了扩容还增加了初始化的功能，进入此方法我们可以看一下源码

![在这里插入图片描述][77a2cd2f06cf44e18be2ab9961d08af0.png]

final Node<K,V>[] resize() {
        
         Node<K,V>[] oldTab = table;
         int oldCap = (oldTab == null) ? 0 : oldTab.length;
         int oldThr = threshold;
         int newCap, newThr = 0;
         if (oldCap > 0) {
        
             //如果当前数组的长度>=最大值（2^30）时，将预值threshold设置为最大值
             if (oldCap >= MAXIMUM_CAPACITY) {
        
                 threshold = Integer.MAX_VALUE;
                 return oldTab;
             }
             //如果当前数组的长度>=默认的初始长度16，则双倍扩容
             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                      oldCap >= DEFAULT_INITIAL_CAPACITY)
                 newThr = oldThr << 1; // double threshold
         }
         ...

调用resize方法的地方

![在这里插入图片描述][9f5e55a6c56747868065ed3a3a23f470.png]

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
            
              ...
                  ++modCount;
              if (++size > threshold)
                  resize();
              afterNodeInsertion(evict);
              return null;

### 总结分析 ###

1.  从上面可以看出，HashMap在完成put元素存储后，会判断++size是否>了阈值，如果是就会去扩容
2.  下面这个方法是在，put元素为链表节点，并且要转为红黑树时，会调用该方法，该方法会在一开始就判断是否需要扩容

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

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();

1.  判断扩容的核心就是threshold这个值

![在这里插入图片描述][4e8217f6bc944a408fabd4bbe1355bc3.png]

1.  从resize方法中看到，HashMap在扩容时，是之前的**双倍扩容**

## HashMap设置长度为11，那么数组的容量为多少？ ##

### 第一个2的幂次方的值 ###

指定了长度初始化HashMap时，它会将数组的容量经过一系列算法，设置为大于我们自定义值的第一个2的幂次方的值，

即 设置为11 ， 则为2^4=16

![在这里插入图片描述][5b0f5a903f7a4bb2a352ec7dc04a63f4.png]

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

static final int tableSizeFor(int cap) {
        
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

## HashMap 何时从红黑树转换为 单链模式？ ##

![在这里插入图片描述][4fd30a66db9a4872ad08fe6914c217f9.png]

1.  HashMap在resize方法执行时，会将元素从旧数组转入新数组，此时如果转移元素为红黑树结构，那么就会调用split方法来分割红黑树方便转移
2.  **split**方法内部，在分割时，**会生成高位树与低位树两种**，**此时也会进行判断如果红黑树元素的高位或者低位节点个数<6时，那么就调用untreeify方法来退回链表结构**

### split方法和untreeify方法 ###

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

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        
        ...        //lowhead   低位树
            if (loHead != null) {
        
                //在红黑树节点元素往新数组中添加时，会调用split方法来重组这个红黑树
                //此时会判断，红黑树的节点操作次数是否<6，即low树（低位树的节点数）< 6时，会通过untreeify方法来退化为链表
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
        
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            //此时会判断，红黑树的节点操作次数是否<6，即high树（高位树的节点数）< 6时，会通过untreeify方法来退化为链表
            //highhead  高位树 
            if (hiHead != null) {
        
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
        
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
    }

![在这里插入图片描述][9726f66b006b45e690c42d2ee15473fa.png]

## HashMap 为什么在多线程并发使用过程中，容易造成死循环/死锁？ ##

图示：

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

1.  产生死循环的核心原因是因为，**jdk1.7**采用的是**头插法**，即新来元素在链表起始的位置，而**jdk1.8**采用**尾插法**，可以有效的避免在多线程操作中产生以上死循环
2.  但是HashMap不是线程安全的，所以在多线程的场景中，虽然不会出现死锁/死循环，但是还是会出现节点丢失的情况，所以在并发的场景中推荐使用ConcurrentHashMap

## 如何得到一个线程安全的HashMap集合？ ##

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

ConcurrentHashMap concurrentHashMap = new ConcurrentHashMap<>();

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

## 总结 ##

[83637bce85fb4a4bb69d00610159c3d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/9fd6dfc37f824bfabfc3e5826692e518.png
[Java_List_List_ _]: https://blog.csdn.net/Pireley/article/details/134115409
[Java_Set_Set_ _]: https://blog.csdn.net/Pireley/article/details/134116768
[Java_3_Tree _ B_ _ _ _ Java_Set_Map _ _Map]: https://blog.csdn.net/Pireley/article/details/132515507
[Java_4_Hash table _ _ _]: https://blog.csdn.net/Pireley/article/details/132533375
[214d2f7c93814851bbac527c61275d19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/bcc17c1385494b63abbf46fce0fb3929.png
[dad43533ae734507b2f2bfca469294b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/fd9390b4e58a40e3a9eeb4bdde689bf2.png
[3fcc706fa6de4d5cbcb3a536bf96a3a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/e189fe0c759343d2a07c08d62d5fa666.png
[baf76c661504467aa9339f29ae24a82d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/4915f4e2043147b3a8b31bdc69be6f96.png
[162fd59f575241e69adb8d38cd325ff7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/b277d6433e41484381d8ea898f0c3320.png
[f8f4fa59d7dc4b9187ef03e68a245653.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/3d1b792bbd554556a79adb4ece0d59b1.png
[48ced5d8af674a36a447b77e04dc7b0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/6cffdfd541e04504967dbfe6af25dd45.png
[77a2cd2f06cf44e18be2ab9961d08af0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/70db6f4365c2472c82cafe55b98e6218.png
[9f5e55a6c56747868065ed3a3a23f470.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/970e730546cb41e9848e240864d41781.png
[e1eebfed2df343868a512e5aff2f2eb9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/669a0e9956544f178015f85306940139.png
[4e8217f6bc944a408fabd4bbe1355bc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/79ba8c4dce1a4f7d9905e99de09e5946.png
[5b0f5a903f7a4bb2a352ec7dc04a63f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/ccdca7c563fa48f9a089959a811213b3.png
[c3e1d46261c8424cb5ea757ae138b0b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/deb72bfd9af44ba59c00649f550e576c.png
[4fd30a66db9a4872ad08fe6914c217f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/2b6a1a3f96da44aaa7c6e133fe3eab9b.png
[a2952b630cec4717b8c1d9fae104b7e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/58e713a96430466ca2437e351596082a.png
[9726f66b006b45e690c42d2ee15473fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/ad98ad72dcb34ddf9a4d32e846308054.png
[b447a4d8bee740098ce8c697459b037e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/f1e4b26c4eef4f9eb8c4825fbc4e7b02.png
[f1a555d483b44926a4005f22468e9ef2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/98996e3d55224be8989100dc0f0d364a.png