高频面试题-JDK源码篇(HashMap)

r囧r小猫 2023-01-22 15:46 71阅读 0赞

#### 前言 ####

我觉得HashMap是一个高频面试题，甚至被问烂了，如果你还不懂HashMap原理，你很幸运，看了这边文章之后你将不存在这个问题！这里整理了一下HahsMap可能会被问到的知识点，从源码的角度去做了一些分析，当然你可以试着自己先回答一下：

1.  HashMap底层用到了那些数据结构？
2.  为什么要用到链表结构？
3.  为什么要用到红黑树？
4.  HashMap如何扩容的？
5.  HashMap是如何Put一个元素的？
6.  HashMap是如何Get一个元素的？
7.  什么是Hash冲突
8.  还有哪些解决Hash冲突的方式？

#### 1. HashMap底层用到了那些数据结构？ ####

HashMap用到了数组，链表，红黑树 。 数组中的每一个元素都是一个Key-Value键值对结构的Node对象,数组初始长度为16。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70]  
HashMap源码如下：

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { 
    
    	 /** 16 初始容量 * The default initial capacity - MUST be a power of two. */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /** 最大容量 * 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;
    
        /** 扩容因子，元素个数达到容量的75%开始扩容 * The load factor used when none specified in constructor. */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /** 链表节点数达到8，转换为红黑树 * 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;
    
        /** 红黑树节点个数小于6转为链表 * 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;
       
        ...省略...
    
    	//一个 Node 代表一个key-value 键值对，也是数组中的一个元素
    	static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;//key的hash值 
            final K key;  //键
            V value;      //值
            Node<K,V> next; //指向下一个Node
       }

#### 2. HashMap为什么要用到链表结构？ ####

使用链表是为了解决Hash冲突问题，这就要说到HashMap存储元素的位置映射算法了，HashMap通过 `hash(key) % 16` 算法来计算某个key在数组中的存放位置 ，通过hash算法得到 key的hash值，对数组长度(16)取余数，结果为0到15其中一个数字，正好对应数组的索引位置。

而Hash冲突就是两个不同的 key ，使用Hash函数得到了相同的Hash值(这是有可能的)，这就意味着两个各不同键值对计算出了相同的存储位置（一个位置怎么能放两个键值对呢？）这就是Hash冲突。

HashMap使用 链地址法 来解决Hash冲突，其实就是把相同位置的元素以链表的方式进行存储，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 1]  
你现在应该知道Node节点对象中的 next 的作用了。

#### 3. 还有哪些解决Hash冲突的方式？ ####

*  第一种：拉链法/链地址法 ：把Hash碰撞的元素指向一个链表，HashMap用的就是这种方法
 *  第二种：开放寻址法：当 p=h(key)出现冲突，就以p为基础产生另一个Hash，如：p1=h§，直到不冲突了把元素放在该位置
 *  第三种：再散列法：准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个
 *  第四种：建立公共溢出区：把Hash表分为基本表和溢出表，把和基本表冲突的元素移到溢出表

#### 4. HashMap为什么要用到红黑树？ ####

HashMap`使用红黑树是为了解决链表过长，查询变慢的问题`大家都知道红黑树的查询性能是及其可观的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 2]

如果HashMap出现Hash冲突的情况变多，那么链表的长度会越来越长，由于链表的查询方式是从前往后一个一个遍历，查询速度比较慢，所以当`链表长度达到 8 的时候 ，HashMap会把链表变成一个红黑树`结构来提高查询效率 , 当删除元素，`红黑树的节点数小于6又会把红黑树变回链表` ， 下面这2个字段就是红黑树和链表的转换阈值：

/** 链表节点数达到8，转换为红黑树 * 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;
    
        /** 红黑树节点个数小于6转为链表 * 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;

#### 5.为什么HashMap要使用红黑树而不是用AVL平衡树 ####

这就要说到AVL树和红黑树的特点了，这里简单说一下，红黑树的查询性能略微逊色于AVL树，因为相比AVL树红黑树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上优于AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多

总结：`AVL查询性能好，增删性能差，红黑树查询和增删性能相对折中`，实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择红黑树。

HashMap选择红黑树就是因为我们使用Map查询和增删该都会涉及到。

为什么不使用多叉树？多叉树和用于大数据存储，或者文件系统存储，不太适合HashMap这种小数据量存储结构。

#### 6. HashMap如何扩容的？ ####

HashMap的扩容因子是0.75，也就是说当数组中的`已存储节点数（Node） > 数组容量 ∗ 扩容因子时`，就需要扩容，调整数组的大小为当前的 `2 倍`

/** 扩容因子，元素个数达到容量的75%开始扩容 * The load factor used when none specified in constructor. */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

扩容的方式是`创建 2 倍容量的新的数组，然后把所有元素重新hash到新的数组中`(数组长度变量，需要重新计算元素的存储位置)。

#### 7. HashMap是如何Put一个元素的？ ####

put执行流程如下：

1.  为key计算出hash值
2.  根据key的hash值计算出存储位置`(16 - 1) & hash 等同于 hash % 16`
3.  取出该位置的值，如果为空，就把传入的key-value包装成Node，加入该位置
4.  如果该位置已经有值了，就出现了hash碰撞了，该Node后面可能有一个链表，或者红黑树
5.  判断该位置的元素的key和传入的key是否一样，如果一样就做值的覆盖操作
6.  如果该位置的元素的key和传入的key不一样， 那就判断Node的类型是不是红黑树
7.  如果是红黑树就走红黑树的添加流程
8.  如果不是红黑树，就遍历链表，取出该位置的元素，使用next往后遍历 。如果遍历的过程中某个Key和传入的key一致了，就覆盖值，否则遍历到最后next为nul，就把传入的新元素存储到链表尾。
9.  同时要判断链表的元素如果大于8了要进行红黑树的转换。

put方法源码

public V put(K key, V value) { 
        return putVal(hash(key), key, value, false, true);
    }

计算hash值

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

put主流程

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                      boolean evict) { 
           Node<K,V>[] tab; Node<K,V> p; int n, i;
           //1.如果数组是空的，调用 resize() 初始化数组
           if ((tab = table) == null || (n = tab.length) == 0)
               //tab就是数组， n是数组长度
               n = (tab = resize()).length;
               	
            // 2.计算位置： (n - 1) & hash 等同于 hash % 16 ，计算key的存储位置
            // 3.取出该位置的元素是否为空
           if ((p = tab[i = (n - 1) & hash]) == null)
           	//4.如果为空，就创建一个新Node，把当前的key-value存储进去
               tab[i] = newNode(hash, key, value, null);
           else { 
          		//到这里说明hash冲突了，该位置有元素，那么就有2种执行方案：
          		//如果有和当前传入key相同的key存住，覆盖值，如果没有和传入的key相同的key，那就添加元素
               Node<K,V> e; K k;
               //5.如果key相等，hash值也相等，进行值的覆盖
               if (p.hash == hash &&
                   ((k = p.key) == key || (key != null && key.equals(k))))
                   e = p;
                //6.如果不满足第5步，那就要进行链表或者红黑树的遍历了 ， 这里在判断是不是红黑树
               else if (p instanceof TreeNode)
               	//走红黑树的添加流程
                   e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
               else { 
               	//7.到这里就是链表了 ， 循环链表
                   for (int binCount = 0; ; ++binCount) { 
                   	//8.通过next一个一个往下遍历，如果某一个node的next为空 ，说明找到最后一个Node了，
                   	//就把新的key-value加入最后一个元素的next
                       if ((e = p.next) == null) { 
                       	
                           p.next = newNode(hash, key, value, null);
                           //这里在判断是否要做红黑树转变
                           if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                               treeifyBin(tab, hash);
                           break;
                       }
                       //9.如果在遍历的过程中，找到了和传入的key一样的key，hash值也一样，那就进行值的覆盖
                       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;	//10.用新的值覆盖老的值
                   afterNodeAccess(e);
                   return oldValue;
               }
           }
           ++modCount;
           if (++size > threshold)
               resize();
           afterNodeInsertion(evict);
           return null;
       }

#### 8. HashMap是如何Get一个元素的？ ####

其实根据put流程就能推断出Get流程

1.  根据key计算hash值
2.  根据hash % 16 计算出Key的存储位置
3.  把该位置的元素取出来，使用传入的key和该位置第一个元素的 key进行比较，如果相同，就返回
4.  如果第一个元素不是查找的元素，就进行链表或者红黑树的遍历
5.  如果第一个节点类型是TreeNode，就走红黑树的查找流程
6.  如果类型不是TreeNode，就遍历链表，一边遍历一遍比较key，如果key相同就返回值，直到next为null。

get方法入口：

public V get(Object key) { 
            Node<K,V> e;
            //hash(key):计算key的hash值
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

get主流程：

final Node<K,V> getNode(int hash, Object key) { 
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
            //计算key存储位置，取出该位置的元素
                (first = tab[(n - 1) & hash]) != null) { 
                //检查是不是第一个元素，比较key，如果是直接返回
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    //直接返回第一个元素
                    return first;
                    //如果next不为空，开始遍历链表
                if ((e = first.next) != null) { 
               		 //如果是红黑树，就遍历红黑树
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do { 
                    	//一直next遍历下一个元素，然后比较key，知道遍历完
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

#### 9.你知道HashMap在多线程下死循环问题吗 ####

这个问题在JDK1.8中已经得到解决，在JDK1.7及以前是有这个问题，造成原因是因为之前HashMap链表插入元素使用的是`头插法`，当HashMap扩容后，进行元素重新Hash位置重排的时候会出现`链表上的元素循环指向`的问题。

比如：有链表上元素按照：A -> B -> C 顺序排列，三者Hash值相同 ， 现在HashMap扩容，然后进行元素重新Hash，A,B,C三者由于Hash值相同，在新的数组中依然会计算出相同的存储位置。

我们可以这样理解，链表上的元素在进行重新Hash的时候是先取第一个元素A进行Hash，然后存储到数组上的某个位置 ， 然后再取B进行Hash,同样存储到该位置，由于使用头插法，所以形成了下图第二部的效果：B -> A , 这时你已经意识到问题了，在之前的链表上是： A -> B， 而重新Hash之后变成了B -> A ，其实这里就出现了元素相互引用的问题，即：死循环。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 3]  
`JDK1.8通过链表元素尾插法解决了这个问题`，尾插法可以维持原有链表的顺序：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 4]

#### 10.在多线程环境中能使用HashMap吗？ ####

不能，HashMap暴露给外界的方法并不是同步的，在多线程环境中是可能会出现线程安全问题，在多线程环境中可以使用HashTable ，或者ConcurrentHashMap。 `HashTable直接使用 synchronized` 同步锁来保证线程安全，比较古老现在基本不用了。ConcurrentHashMap是JUC并发库中的容器 ，它是专门为多线程环境设计，并发控制使用 `Synchronized 和 CAS` 来操作，性能良好，在JDK1.8中ConcurrentHashMap也使用到了数组链表红黑树的结构来存储数据。

#### 11.HashMap和HashTable的区别 ####

HashTable是HashMap的线程安全版本，也是比较老旧的一个map,HashTable方法是加了同步锁，线程安全，性能会受到影响。而HashMap没有加同步锁，线程不安全，但是性能更高。

Hashtable既不支持Null key也不支持Null value ， 而HashMap值可以为null，key支持一个key为nul。

文章到这就结束了，喜欢的话就给个好评吧！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70]: /images/20221020/d6f78b8927164715863de70426cb195a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 1]: /images/20221020/b54dc878d23a40249600fefa8aad95c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 2]: /images/20221020/621d47b22c3342628c6f907c2a2be219.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 3]: /images/20221020/b76b10192d074827a6a1483f041c45f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 4]: /images/20221020/3e2f8ec076424122bd7ffeb9b06342fe.png