面试必问HashMap

无论是小厂还是大厂面试，HashMap的出场率一直居高不下。作为Java语言中Map数据结构的经典实现，对其内部原理的掌握和理解程度在一定程度上能反映出一个开发人员的水平与实力。

下面我们提供出一些常见面试问法以及对应的官方回答（建议熟读并背诵）：

1. HashMap底层是如何实现的？JDK7和JDK8的实现有何区别？

答：HashMap底层存储元素的数据结构是数组。在存储元素时如果发生了哈希冲突，JDK7使用“链地址法”（俗称“拉链法”）来解决，采用“头插法”进行元素插入。在JDK8中，当哈希冲突不是很严重时，仍然使用“链地址法”解决，但采用的是“尾插法”；而当哈希冲突特别严重，即链表的长度大于8并且数组的容量大于64时，会将链表结构转化成红黑树结构用以解决链表过长带来的性能问题。

2. 加载因子loadFactor为什么是0.75？

答：这是一个基于容量和性能考虑的折衷值。如果加载因子设置过大，带来的好处是扩容的门槛提高，节约了内存空间，但出现哈希冲突的几率会变大，从而导致对元素的操作性能下降；如果加载因子设置过小，带来的好处是扩容门槛降低，数组中存储的元素会比较稀疏，不易出现哈希冲突，对元素的操作性能较高。但会存在一定的空间浪费。于是折衷考虑选择了0.75。

3. 什么时机会触发扩容？JDK8在扩容时做了哪些优化？

答：当存储元素数量大于等于阈值时触发扩容。JDK7在扩容时会对所有元素进行rehash重新哈希计算数组下标；而JDK8在扩容时通过高位运算（哈希码 & 旧容量）来判断元素是否需要移动，如果高位运算结果高一位为0，那么扩容后该元素的位置不会发生变化，如果高位运算结果高一位为1，那么扩容后该元素的位置发生了变化，新的数组下标位置为原下标位置加上原数组长度。

4. 描述插入一个元素的完整过程。

答：首先判断哈希表是否为空，如果为空则表示第一次插入，进行扩容；否则根据键计算出数组下标，然后判断该下标位置的元素是否为null，如果是，则直接插入；否则判断键是否相等（先比较hashCode，哈希码不相等再进行equals比较），如果相等，则直接覆盖值；否则判断是红黑树还是链表，分别执行对应数据结构的插入逻辑。其中链表数据结构在JDK7中使用头插法进行插入，在JDK8中使用尾插法。而红黑树在JDK8才引入，如果已经是红黑树了，则执行红黑树的插入逻辑，如果是链表，在使用尾插法遍历节点时如果发现链表长度大于8了且数组容量小于64时，将链表转换成红黑树后在执行插入，否则执行链表的尾部插入。元素插入完成后，判断哈希表容量是否超过阈值，超过则进行扩容。

5. HashMap的线程不安全体现在哪？如何去应对？

答：在多线程条件下，JDK7的HashMap在扩容时会出现死循环的问题，JDK8的HashMap在插入时会出现值被覆盖的问题。应对这种线程不安全，可以使用同步容器HashTable或并发容器ConcurrentHashMap。推荐使用ConcurrentHashMap。

以上面试题及答案基本可以应对那些普通公司的一问一答式的面试了，背诵就完事了。

但有些面试官可能会追着其中某个点一直往下细问，这个时候光靠上面背诵的这点东西就有点力不从心了，你必须对整个HashMap的原理真正的有一定了解才能够从容去应对。

下面我们针对上面的面试题，阅读JDK8的HashMap源码，真正的去搞懂原理。

如何存储元素？

transient Node<K,V>[] table;

元素都存储在这个Node数组里面，我们来看下Node类：

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> {
    // hash值
    final int hash;
    // 键
    final K key;
    // 值
    V value;
    // 下一个节点
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    // getter/setter/toString/equals/hashCode
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

可以看到是一个单链表的数据结构，也就是说table数组中存储的是一个一个的Node节点，而这每一个Node节点都是一个单链表的头节点，当没有发生哈希冲突时，链表长度为1。

静态变量

下面我们来看一些主要的静态变量：

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

// 最大容量
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;

// 要执行红黑树化的最小数组容量
static final int MIN_TREEIFY_CAPACITY = 64;

有关加载因子loadFactor为什么是0.75？

还记得文章开头的解答吗？这是一个基于容量和性能考虑的折衷值。如果加载因子设置过大，带来的好处是扩容的门槛提高，节约了内存空间，但出现哈希冲突的几率会变大，从而导致对元素的操作性能下降；如果加载因子设置过小，带来的好处是扩容门槛降低，数组中存储的元素会比较稀疏，不易出现哈希冲突，对元素的操作性能较高。但会存在一定的空间浪费。于是折衷考虑选择了0.75。

其实这个答案已经很能说明原因了，但有些面试官就是纠结这个数值为什么是0.75，为什么不是0.74或者0.76等。下面我们尝试用一种八股文来对抗面试官：

为什么加载因子是0.75呢？

理论：通过预测存储桶是否为空，可以避免链接并利用分支预测。如果存储桶为空的可能性超过0.5，则该存储桶可能为空。

证明：s代表大小，n代表增加的键数。根据牛顿二项式定理，存储桶为空的概率为：

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

因此，如果少于log(2)/log(s/(s - 1))个键，当s达到无穷大时并且如果添加的键数使得P(0) = 0.5时，则n/s迅速接近log(2)。

log(2)约等于0.693。

结论：log(2)不是约等于0.693吗？为什么会选择0.75呢？因为阀值需要一个整数，默认初始容量是16，当加载因子等于0.75时乘积才为整数。0.70/0.71/0.72/0.73/0.74...等等，只有0.75的乘积才是整数。

以上理论及证明过程来自 stackoverflow.com

所以问题来了，为什么默认初始容量是16呢？这…，建议准备面下一家公司了…

成员变量

除了存储元素的table数组，还有以下其它成员变量：

// Set缓存，可用于迭代器
transient Set<Map.Entry<K,V>> entrySet;

// map元素个数
transient int size;

// map修改次数，用来实现fail-fast机制
transient int modCount;

// 阀值，当size>threshold时会触发扩容
int threshold;

// 加载因子
final float loadFactor;

如何构造HashMap对象？

一共有四个构造器，但我们常用的只有两个：无参构造器和指定初始容量的构造器。

/**
 * 指定初始容量的构造器，内部调用带两个参数的构造器，传入默认加载因子DEFAULT_LOAD_FACTOR=0.75f
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 无参构造器，使用默认的初始容量：16，默认的加载因子：0.75f
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

一般在开发时，如果我们能提前预估出数据量，建议调用指定初始容量的构造器来创建一个合适容量的HashMap；如果无法预估，最好使用无参构造器。

我们来看下指定初始容量和指定加载因子的构造器：

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;
    // 初始化阀值为初识容量（此处只是进行预初始化，后续调用resize方法时会进行准确赋值）
    this.threshold = tableSizeFor(initialCapacity);
}

初始化赋值的时候，并不会将阀值threshold设置为initialCapacity * loadFactor，而是预初始化成初始容量，此处会调用tableSizeFor方法得到一个大于等于initialCapacity且最近的2的整数次幂的数，然后赋值给threshold，后续第一次调用put方法进行插入时会进行首次扩容，调用resize方法对threshold进行准确赋值。

tableSizeFor方法原理

tableSizeFor方法是得到一个大于等于initialCapacity且最近的2的整数次幂的数。我们来看JDK8是如何进行巧妙实现的：

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;
}

首先我们要知道位运算符号>>>表示无符号右移，忽略符号位，空位都以0补齐。

假设cap = 10，那么n = 9。

执行n != n >>> 1即n = 9 | (9 >>> 1)的步骤是：

• 9的二进制是1001；
• 9 >>> 1即：1001 >>> 1 = 0100；
• 9 | (9 >>> 1) = 1001 | 0100 = 1101。

接下来依次执行：

n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;

过程分别为：

n |= n >>> 2;，此时n = 1101，即：n = 1101 | (1101 >>> 2) = 1101 | 0011 = 1111；

n |= n >>> 4;，此时n = 1111，即：n = 1111 | (1111 >>> 4) = 1111 | 0000 = 1111；

n |= n >>> 8;，此时n = 1111，即：n = 1111 | (1111 >>> 8) = 1111 | 0000 = 1111；

n |= n >>> 16;，此时n = 1111，即：n = 1111 | (1111 >>> 16) = 1111 | 0000 = 1111；

最后的结果为：n = 1111，转换成十进制等于15，return语句中进行三目判断，最后返回的值为：n + 1 = 16。

如何插入元素？

下面我们来看put方法的实现：

public V put(K key, V value) {
    // 计算hash值，调用putVal方法
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 局部变量tab用于接收成员变量table
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // 如果table数组中无元素，则调用resize()扩容得到一个新的Node<K,V>[]数组并赋值给tab，然后得到新数组的长度为n。
        n = (tab = resize()).length;
    // 根据hash值计算待插入元素的数组下标索引i（对2取模可转化成位运算）
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果i位置无元素，则直接创建Node节点进行赋值插入
        tab[i] = newNode(hash, key, value, null);
    else {
        // i位置有元素，说明出现了哈希冲突
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 键key相等则直接进行值覆盖
            e = p;
        // 待插入的键不等于下标i处存储的头节点的键
        else if (p instanceof TreeNode)
            // 判断为红黑树节点，则执行红黑树的插入逻辑
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 否则为链表结构，进行遍历，binCount用来统计链表长度
            for (int binCount = 0; ; ++binCount) {
                // 对e进行赋值
                if ((e = p.next) == null) {
                    // 遍历到尾节点了，e = null
                    // 尾插法插入新元素
                    p.next = newNode(hash, key, value, null);
                    // 判断链表长度binCount >= 7
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 此次循环是第8次，binCount=7，尾插法插入新元素后链表长度为8，调用treeifyBin尝试转换成红黑树
                        // 在treeifyBin方法中，会首先判断tab数组的长度是否小于MIN_TREEIFY_CAPACITY=64，如果小于，则进行resize扩容结束；否则执行树化逻辑。
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 找到了键key相等的节点，结束循环。e = p.next
                    break;
                // 未找到key相等的节点或未遍历到尾部，此时e = p.next，推动链表的遍历。
                p = e;
            }
        }
        // 上面的判断中e的值不为null的情况：即链表中找到了key相等的节点
        if (e != null) { // existing mapping for key
            // 进行值value的覆盖
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 回调钩子，子类LinkedHashMap进行了重写
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 修改次数加一
    ++modCount;
    if (++size > threshold)
        // 容量达到阀值进行扩容
        resize();
    // 回调钩子
    afterNodeInsertion(evict);
    return null;
}

整个put方法的执行流程如下图所示：

如何优雅地进行扩容？

出现扩容的情况有三种：

1. 哈希表为空且第一次执行put方法时，会先进行扩容再存储元素。
2. 当出现哈希冲突，执行尾插法插入元素后，如果链表长度大于8，且数组长度小于MIN_TREEIFY_CAPACITY=64，执行扩容逻辑。
3. 新插入一个键后（元素直接插入、哈希冲突链表尾插、红黑树插入），++size > threshold容量达到阀值，执行扩容逻辑。

下面我们来看下扩容resize的逻辑：

final Node<K,V>[] resize() {
    // 使用oldTab接收旧的数组table
    Node<K,V>[] oldTab = table;
    // 如果oldTab为null引用，说明是第一次调用put方法时进行的扩容，则oldCap旧容量为0；否则为旧数组长度。
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧阀值
    int oldThr = threshold;
    // 定义新容量和新阀值（扩容之后的）
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 旧容量大于0，则原数组有元素，不是第一次调用put
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 旧容量超过最大容量，已无法进行扩容
            // 设置阀值为最大整型数值
            threshold = Integer.MAX_VALUE;
            // 返回旧数组
            return oldTab;
        }
        // 计算新容量：oldCap的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新容量小于最大容量，且旧容量大于等于默认初始容量，则阀值也为原来的两倍
            newThr = oldThr << 1; // double threshold
    }
    // 旧阀值大于0，说明是调用带参构造器创建的HashMap，且此时旧阀值等于带参构造器中指定的初始容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 第一次调用put才会走到这个if分支
        // 新容量等于带参构造器中指定的容量
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 其它情况：调用无参构造器创建的HashMap
        // 新容量为：默认初始容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 新阀值为：默认加载因子 * 默认初始容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 第一次调用put时，走的上面的else if (oldThr > 0)分支，新阀值未进行赋值，所以等于0
    if (newThr == 0) {
        // 计算新阀值：新容量 * 加载因子
        float ft = (float)newCap * loadFactor;
        // 范围控制，转换成int
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 设置阀值
    threshold = newThr;
    // 开辟新容量长度的数组空间
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // table引用指向新数组
    table = newTab;
    // 如果是第一次调用put时执行，oldTab为null。
    if (oldTab != null) {
        // 非首次put方法，原table数组中存在元素，执行rehash
        for (int j = 0; j < oldCap; ++j) {
            // 遍历旧table数组
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 释放旧table的引用 help gc
                oldTab[j] = null;
                // 无哈希冲突
                if (e.next == null)
                    // 新数组newTab赋值
                    // newCap为2的整数幂，hash & 2^n - 1 即对2取模，求出数组下标。
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 红黑树逻辑
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 哈希冲突，有链表，将整个链表分隔成两个部分
                    // loHead/loTail链接出一个不需要移动位置的链表
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead/hiTail链接出一个需要移动位置的链表
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 哈希码 & 旧容量
                        // 结果为0，表示该元素的下标索引值在扩容后不会发生变化
                        if ((e.hash & oldCap) == 0) {
                            // 链接原链表每一个元素至loHead头节点
                            // 第一次执行do-while循环
                            if (loTail == null)
                                // 赋值loHead头节点
                                loHead = e;
                            else
                                // 非第一次执行do-while
                                // 链接至loTail
                                loTail.next = e;
                            // 如果是第一次执行do-while，则loTail=loHead指向头节点
                            // 否则表示loTail右移一位
                            loTail = e;
                        }
                        // 否则，结果不为0，则该元素的下标索引值在扩容后会改变
                        else {
                            // 同样地链接逻辑
                            // 第一次执行do-while循环
                            if (hiTail == null)
                                // 赋值hiHead头节点
                                hiHead = e;
                            else
                                // 非第一次执行do-while
                                // 链接至hiTail
                                hiTail.next = e;
                            // 如果是第一次执行do-while，则hiTail=hiHead指向头节点
                            // 否则表示hiTail右移一位
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 执行完do-while循环后，loTail和hiTail都指向出现哈希冲突的原链表的尾部
                    if (loTail != null) {
                        loTail.next = null;
                        // 下标索引不需要移动，链表loHead整体移动
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 下标索引需要移动到j + oldCap位置，链表hiHead整体移动
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回扩容后的新table数组
    return newTab;
}

可以看到在有哈希冲突时，对链表中的元素并没有进行rehash操作，而是将冲突的链表分隔为两个链表，通过计算e.hash & oldCap，如果结果的高一位为0，则表示该链表节点不需要移动位置，链接至loHead节点；如果结果的高一位为1，则表示该链表节点需要移动位置，链接至hiHead节点。do-while循环结束后，以loHead节点为头节点的链表不需要移动数组下标；而以hiHead节点为头节点的链表需要向右移动旧容量oldCap个位置。原链表各节点之间的相对位置未发生改变。

如何获取元素？

相比于put插入，get获取元素的逻辑就相对简单了。正常从HashMap中获取元素的最好时间复杂度是常数O(1)。在哈希冲突的情况下：最坏时间复杂度是O(n)，最好时间复杂度是O(log n)。

下面我们来看下get方法的逻辑：

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

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;
    Node<K,V> first, e;
    int n;
    K k;
    //  table数组已经初始化，且数组中有元素，且key所在下标索引位置有元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 第一个key相等，直接返回该节点
            return first;
        // key在后面的链表（红黑树）节点中
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                // 执行红黑树的查询逻辑，时间复杂度O(log n)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 遍历链表找到相等的key，返回对应节点。
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

由于在put插入的时候计算下标的方式为(n - 1) & hash，所以get查询的时候以同样方式计算下标，如果该下标位置无元素，那么待查询的key一定不在HashMap中，直接返回null；反之，如果该下标位置有元素，那么则寻找与待查询的key相等的键。

如何判断key相等？

在HashMap中，所有判断key是否相等的逻辑都是：先比较hashCode是否相等，再比较equals是否相等。

这就是为什么建议在重写equals方法的同时最好去重写hashCode方法的一个原因。

两个key如果hashCode相等，equals不一定不等。

线程不安全问题是如何产生的？

对于JDK7，在多线程进行扩容时会产生死循环问题，由于JDK7已成为历史，本文不再赘述，可以参考网上的一些解释。

而对于JDK8，我们可以看看上文中分析的put插入方法，针对第二个if条件分支，如果未发生哈希冲突，则创建新节点直接进行赋值插入。

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

以上代码在JDK8#HashMap.java源码中分别是第630行和第631行。

此处如果多个线程同时对同一个HashMap执行put方法，根据hash计算出的下标i相同且i下标处恰好为null没有元素，同时多个线程恰好刚执行完第630行的if条件判断但还未执行第631行的赋值插入。这个时候，如果多个线程按先后顺序往下执行，那么后执行的线程就会覆盖先执行的线程在i下标处插入的值。

当然在日常的业务开发中，基本上不会使用到HashMap作为成员变量，更多的是用作局部变量进行传参，而且现在已经不推荐使用HashMap进行传参了，除了一些早期项目，或者使用了MyBatis的早期版本ibatis的项目，基本上很少会用到HashMap。

总结

有关HashMap，其实到这里就已经足够了，再往下深入，就是红黑树的查询和插入逻辑了，涉及到红黑树的数据结构和算法，比较复杂。面试如果遇到问红黑树的实现细节的，大可以去反问面试官会不会。

后面有空会专门写一篇文章讲讲红黑树。