源码级别深入HashMap的实现原理，来碾碎大厂那些神一般的面试题

阅读先导

HashMap作为jdk类库中最重要的集合之一，在众多大厂面试中频频问到，而且问的问题都不是背背概念就能回答上来的。废话不多说，先来看看常见的HashMap相关的典型面试题有哪些：

1、jdk8中对HashMap做了哪些改变？

2、说说HashMap中put方法的执行过程？

3、为什么ConcurrentHashMap比HashTable效率要高？

4、jdk1.7中头插法的死循环是怎么形成的？

5、说说HashMap用到的数据结构都有哪些？红黑树有哪些特点？

5、为什么链表转红黑树的值是8，而不是6或7？为什么红黑树转成链表的时候设置的值是6，而不是8呢？

一、HashMap概述

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

Map是JDK类库提供的java对K-V结构的抽象类的定义，是java实现散列表（hash表）这种数据结构的的基础定义，而HashMap就是Map接口实现的一员。所以HashMap就是JDK对散列表这种数据结构的实现之一。

通过HashMap官方文档的描述可知：

1、HashMap实现了Map接口，提供了Map相关方法的实现。同时支持null作为key和value；

2、作用大致和Hashtable功能相似，不同在于Hashtable保证线程安全，同时不容许有null的key和value；

3、当构造一个实例的时候最好给一个合适的capacity和loadFactor，如果太大或者太小都会影响性能；

4、一般情况不需要修改系统默认capacity=16，loadFactor=0.75f，多数情况下认为是一个合理的值，能提供良好的性能；

5、HashMap不是一个同步集合，如果要保重线程安全，需要用Map m = Collections.synchronizedMap(new HashMap(...))来包装；

6、在迭代的同时进行remove操作，会抛出ConcurrentModificationException异常；

7、HashMap在1.8以后用“数组+链表+红黑树”实现。

二、源码分析

1、核心常量

    // 缺省的容量大小，必须是2的指数
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大容 必须是2的指数 <= 1<<30.
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 转换成红黑树的链表长度
    static final int TREEIFY_THRESHOLD = 8;
    // 树转链表的长度
    static final int UNTREEIFY_THRESHOLD = 6;
    // 转换成数的hash表的大小
    static final int MIN_TREEIFY_CAPACITY = 64;

2、数据结构,数组+链表+红黑树

        A、hash表数组结构：

transient Node[] table;

        B、hash表节点Node结构：

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

    C、红黑树Node结构：

static final class TreeNode extends linkedHashMap.Entry {
      TreeNode parent;  // red-black tree links
      TreeNode left;
      TreeNode right;
      TreeNode prev;    // needed to unlink next upon deletion
      boolean red;
      TreeNode(int hash, K key, V val, Node next) {
          super(hash, key, val, next);
      }
    }

3、整体结构图

4、四个构造函数

//构造函数1
public HashMap(int initialCapacity, float loadFactor) {
    //指定的初始容量非负
    if (initialCapacity < 0)
        throw new IllegalArgumentException(Illegal initial capacity:  +
                                           initialCapacity);
    //如果指定的初始容量大于最大容量,置为最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //填充比为正
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException(Illegal load factor:  +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值
}

//构造函数2
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//构造函数3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//构造函数4用m的元素初始化散列映射
public HashMap(Map m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

5、put方法的实现

put方法是调用putVal来实现具体功能的，实现逻辑如下：

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node[] tab; 
    Node p; 
        int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        // 如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
        // 表示有冲突,开始处理冲突
    else {
        Node e; 
        K k;
            // 检查第一个Node，p是不是要找的值
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                    // 指针为空就挂在后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                        //如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，　　　　　　　　　　　　　
　　　　　　　　　　　　    //treeifyBin首先判断当前hashMap的长度，如果不足64，只进行
                    //resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                    // 如果有相同的key值就结束遍历
                if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
            //就是链表上有相同的key值
        if (e != null) { // existing mapping for key，就是key的Value存在
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;//返回存在的Value值
        }
    }
    ++modCount;
        // 如果当前大小大于门限，门限原本是初始容量*0.75
    if (++size > threshold)
        resize();//扩容两倍
    afterNodeInsertion(evict);
    return null;
}

A、判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；

B、根据键值key计算hash值得到插入的数组索引i，如果tab[i]==null，直接新建节点添加，否则转入C

C、判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),之后分别处理。

6、get方法的实现

get方法委托getNode来实现具体逻辑，代码如下：

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
   Node[] tab;//Entry对象数组
   Node first,e; //在tab数组中经过散列的第一个位置
   int n;
   K k;
   // 找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]
   //也就是说在一条链上的hash值相
   if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
        // 检查第一个Node是不是要找的Node
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同
             return first;
        // 检查first后面的node
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            // 遍历后面的链表，找到key值和hash值都相同的Node*/
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

大致总结为：get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)]，先判断first的key是否与参数key相等，如果不等就遍历后面的链表找到相同的key值返回对应的Value值即可。

7、resize方法的实现

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    // 如果旧表的长度不是空
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 把新表的长度设置为旧表长度的两倍，newCap=2*oldCap
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/
            newThr = oldThr << 1; // double threshold
    }
    //如果旧表的长度的是0，就是说第一次初始化表
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;//新表长度乘以加载因子
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //下面开始构造新表，初始化表中的数据
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;//把新表赋值给table
    if (oldTab != null) {//原表不是空要把原表中数据移动到新表中  
        // 遍历原来的旧表
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                // 如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重
                else { // preserve order保证顺序
                   //新计算在新表的位置，并进行搬运
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;//记录下一个结点
                       //新表是旧表的两倍容量，实例上就把单链表拆分为两队，
　　　　　　　　　　　　　　//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //lo队不为null，放在新表原位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //hi队不为null，放在新表j+oldCap位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

总结：构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（loadFactor*capacity）重新调整HashMap大小 变为原来2倍大小, 经过resize之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。这样的好处是原来的hash值新增的那个bit是0的话索引没变，是1的话索引变成“原索引+oldCap”，这个设计非常的巧妙，既省去了重新计算hash值的时间，而且由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

三、面试题解析

1、jdk8中对HashMap做了哪些改进？

答：A、在java 1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）；B、发生hash碰撞时，java 1.7 会在链表的头部插入，而java 1.8会在链表的尾部插入，解决了特殊情况下死循环的问题；C、在java 1.8中，Entry被Node替代(换了一个马甲)；

2、说说HashMap中put方法的执行过程？

答：A、判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

B、根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向F，如果table[i]不为空，转向C；

C、判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；

D、判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向E；

E、遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

F、插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

3、当链表长度大于8时，将链表转换成红黑树有什么好处？

因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，所以，当链表长度 >= 8时 ，有必要将链表转换成红黑树。

4、使用HashMap时，当两个对象的 hashCode 相同怎么办？

因为HashCode 相同，不一定就是相等的（equals方法比较），所以两个对象所在数组的下标相同，"碰撞"就此发生。又因为 HashMap 使用链表存储对象，这个Node会存储到链表中。

5、为什么ConcurrentHashMap比HashTable效率要高？

答：HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；

ConcurrentHashMap中JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。

JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry）。锁粒度降低了。

6、jdk1.7中头插法的死循环是怎么形成的？

答：HashMap之所以在并发下的扩容造成死循环，是因为多个线程并发执行时，因为一个线程先完成了扩容，将原Map的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序，于是就会形成一个环形链表，当get表中不存在的元素时，造成死循环。

7、说说HashMap用到的数据结构都有哪些？红黑树有哪些特点？

答：HashMap中用到了数组+链表+红黑树；红黑树有以下特点：

A、每个节点或者是黑色，或者是红色。

B、根节点是黑色。

C、每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

D、如果一个节点是红色的，则它的子节点必须是黑色的。

E、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[这里指到叶子节点的路径]

8、为什么链表转红黑树TREEIFY_THRESHOLD的值是8，而不是6或7？为什么红黑树转成链表UNTREEIFY_THRESHOLD的设置的值是6，而不是8呢？

答：这里有两层意思：第一，开始就用红黑树可以不？这个答案在注释中有阐明，相同数据量下红黑树(TreeNode)占用的空间是链表(Node)的俩倍 , 考虑到时间和空间的权衡 , 只有当链表的长度达到阈值时才会将其转成红黑树；第二，为什么是8不是其它值？其实这个问题在注释中也有阐明，看下面注释：

* 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

作者认为在理想的情况下随机hashCode算法下所有节点的分布频率会遵循泊松分布(Poisson distribution) , 上面也列举了链表长度达到8的概率是0.00000006,也就是说我们几乎不可能会使用到红黑树 , 所以作者使用8作为一个分水岭，所以用了8。

红黑树转成链表的时候为什么是6呢？这个原因是当我们有频繁的添加和删除操作时 ,hash碰撞产生的节点数量 一旦在7附件徘徊就会造成红黑树和链表的频繁转换 , 此时我们大多数的性能就都耗费在了链表 → 红黑树和红黑树 → 链表` ,这样反而就得不偿失了 , 所以作者将长度为7作为一个缓存地段从而选取了6作为红黑树 → 链表的阈值。

9、HashMap 的长度为什么是 2 的 N 次方呢？

为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数 据能均匀的分配，每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现。下面是回答的重点哟：取余（%）操作中如果除数是 2 的幂次，则等价于与其除数减一的与（&）操作（也就是说 hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二进 制位操作 & ，相对于 % 能够提高运算效率。

10、如何规避 HashMap 的线程不安全？

单线程条件下，为避免出现ConcurrentModificationException，需要保证只通过HashMap本身或者只通过Iterator去修改数据，不能在Iterator使用结束之前使用HashMap本身的方法修改数据。因为通过Iterator删除数据时，HashMap的modCount和Iterator的expectedModCount都会自增，不影响二者的相等性。如果是增加数据，只能通过HashMap本身的方法完成，此时如果要继续遍历数据，需要重新调用iterator()方法从而重新构造出一个新的Iterator，使得新Iterator的expectedModCount与更新后的HashMap的modCount相等。多线程条件下，可使用两种方式：Collections.synchronizedMap方法构造出一个同步Map直接使用线程安全的ConcurrentHashMap。

、

四、总结

看源码要更重视原有注释，包括类和方法上的，能帮助我们快速了解相关的功能作用及设计思想。HashMap是JDK类库的重中之重，搞懂源码不光对面试有帮助，对我们个人水平提高也有很多帮助。

由于写的比较仓促，有纰漏地方请多多指教。觉得好请转发、点赞、在看。有想法请文末评论，二哥持续输出面试高频面试题目，跟二哥一起成长，关注二哥不迷路。