面试官：熟悉Java集合？那来聊聊HashMap吧

后端 3年前 0 463

来了，他来了。

发量稀疏的面试官皱着眉头在浏览后端君的简历，正在我坐卧不安的时分，他开口了：“我看你简历上写着熟悉Java调集，那你必定知道HashMap吧？”

我点点头，略懂。

那你先来简略介绍一下你了解的HashMap，你能够把你知道的都说一下。

这么牛？那我H ( 5 {可不客气了，HashMap我可是看过源码的！

略微梳理了一下，后端君开端了。

1. HashMap简述

HashMap是一个根据哈希表完成的无序的key-value容器，它键和值都允许设置为null，可是它是线程不安全的，一起在默认状况下假如HashMap元素超越默3 l 3 . K认容量的0.75时会进行扩容，将容量扩大为本来的两倍。

1.1 HashMap的底层数据结构

在JDK1.7U J b ) b以前HashMap底层是数组和链表完成的，可是为了避免| X 6 p | / ( 4 &同一个数组下标中的链表过于长导致查询功率过低的状L 7 n 9况，从JDK1.8开端在HashMap容量大于64且链表长度大于8时会将链表转化为红黑树f k @ – k ( X ;。

HashMap中每一个元素都以一个Node节点的方式寄存在数组中。

static class Node<S 5 c W D I w =K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

hash特点是键的哈希值，key特点寄存的是键，value特点寄存的是值。

还有一个next特点，便是当两个key的哈希值相一起，这两个元素会被放在数组的= T [ ` 8同一个下标方位中，经过next特点指定一下个Node对象，然后会构成一个链表。

1.2 哈希磕碰

HashMap的底层数据结构首先是一个Node类型的数组，一个Node节点寄存在数组中的方位（即数组下标）是由该O / x 4 p Y i , ^Node节点key特h . Q } N 点的哈希值（也便是ha} f ~ 3 Vsh特点）确定的，可是这就可能产生一种特殊状况——不同Node节点的哈希值相同。

假如存在两个Node节点的hash特点相同，那么它们都N 7 ~ N = O 4会寄存在数组下标为hash的方位，一起会经过Node节点的next特点将这两个节点连接在4 ? T一起，构成一个链^ L ,表，这就解决了哈希抵触的问题。

举个比如，当我在Map中增加一个键为Java值为No1的元素时，JL ` W =ava字符串会经过hash办法来核算哈希值。假定Java字符q / &串的哈希值为D X z l n b u1，那么此时HashMap的结构便是下面这样。

假定这时再放入一个键为PHP值为No2的元素，刚好很不巧假定PHP作为键的哈希值成果也是1，那么这个Node节点也会放在数组下标为1的方位上，一起与Java键构成一个链表O / # z O ( _，如下图所示。

JDK1.7中是头插法，会引起死循环，在JDK1.8中改为运用尾插法。

可是假如产生大量哈希值相同的特殊状况，导致链表很长，就会{ J T S x ; 3严重影响HashMap的功4 4 } e + 2能，因为链表的查询功率需B F N f ] o 9 ~求遍历一切Node节点。

所以在JDK1.: Z q P 9 m I 2 v8引入了红黑树，当链表的长度大于8，且Hash 0 G LMap的容量大于64的时分，就会将链表转化为红黑树。

// JDK1.8 HashMap#^ k {putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean% Y 7 c V evict) {
    // 省掉
    // binCount 是该链表的长度计数器，当链表长度大于等于8时，执行树化办法
    // TREEIFY! K T + e 2 {_THRESHOLD = 8
    if (binCoud , -nt >= TREEIFY_THRESHOLD - 1)
        treeifyBin(tab, hash);
    // 省掉
}

/C w Z + Y : |/ HashMap#treeifyBin    
final void t{ x F x sreeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // M| t l @ ? T UIN_TREEIFY_CAPACITY=64
    // 若 HashMap 的大小小于64，仅扩容，不会转化为红黑树
    if (tab == null || (n = tab.length, ) g) < MIN_TREEIFY_CAPACITY)
        resizx ? t * De();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 代码省掉...
    }
}

1.3 怎样核算键的哈希值

“你刚+ = # m g刚一o 6 9 5 o Z 7向在说键的哈希! Q = ( s ? 0 R值，那它到底是怎样核算的你了解吗？”面试官再次提问。这是要问源码了，作为自称看过源码的人，后端君当然不会落下ht 1 T J * ; Gash函数，所以胸有成竹。

当一个键值对被= } !放入HashMap时，会经过HashMap#hash(Object key)办法来核算该键的哈希值，作为它寄存在HashMap数组中的索引下标值，hash办法的源码如下所示。

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

假如键为null的元素，它会被J C 8 6 d放在HashMapm 7 : V数组下8 m 4 h 5 %标为0的方位。

然后便是键不为null的状况。

h被赋值为键的哈希值
进行h >>> 16运算
将上述两步的成果进行^运算

作为一个在大学时核算机组成原理差点挂科的差等生，后端君关于位运算符其实是有些发憷的，幸而得到查找引擎老师的教训，才搞明白了上述两个位运算符的含义_ b # S。

>>>符号表明无符号右移，右移后高位补0
^是异或运算符，当两者不一起成果为X M : H l 0 y o #1，相一起成果为0

假定h=15，我们来核算一下hash办法的成果，先把15转化为二! w E进制，也便是0000 1111。

h &I 5 8 W -gt;>&gA 6 Kt; 16的成果便是在15的32位二进制中取高半区，也便是0000 0000 0000 0000，最后对这两者做异或运算。

所以终究h=15的键值对将被寄存在HashMap数组下标为15的方位。

上面这段hash办法有一个专业术语叫R [ _ O 9 0 } 4 G做扰动函数，它的效果便是让元素充n x j @ _ z G R分的散列，削减产生哈希磕碰的可能性。

1.4 为什么HashMap是线程不安全的

“看来你对HaY 7 & ashMap仍是有些了解的，那你知道为什么HashMap是线程不安全的吗B 3 B c @ F J？”

线程不安全？那当然是多线程状? r o : ] V :况下没有考虑并发的状况了。假如面试的时分这么答，那基本是凉凉了。

后端君在CSDN上找到一篇比较全面的答复：JDK1.7和JDK1.8中HashMap为什么是线程不安全的？，写的很具体，建议我们能够去看一下。

关于这个问题后端君就不再赘述啦。

总结一下：

在JDK1.7中，并发执行扩容操作时会形成环形链和数据丢失的状况
在J8 j cDK1.8中，并发执行put操作时会产生数据掩盖的状况

2. 红黑树

“既然HashMap在扩容时会将链表树化，那再来说说红黑树吧，你对红黑树有什么了解？”面U J J L试官脸上毫无表情，稳稳地再次抛出一个包袱。

红黑树是一棵特殊的二叉查找树，除了= } 8根节点外，每个非根节点有且只有一个父节点，关于一个节点来说，它的左子树上一切节点的值都小于等于根节点的值，它的右子树上的值都大于等于根节点的值，一起从任一节点到其每个叶子的一切路径都包含相同数目的黑色节点。

根据红黑树这o v } f ~样的结构特性J b | d L X 5 w ^，它的时间复杂度是O(logn)，所以会比链表的O(N)快，这也便是JDK1.8引入红黑树的原因。

“那HashMap的红黑树; L O { 6 B r y是怎样进行保护的呢？比如我插入一个数，怎样确保这棵树仍是一个红黑树？”

这……后端O . C w P君只知道在HashMap会经过左旋右旋来保护一棵红黑树，具体的逻辑……还真不知道，所以只能照实答复。

不过后端君在此附上一篇博文：聊一聊红黑树的左旋和右旋（结合JAVA中TreeMap红黑树完成）$ x M，这儿面那张动图能够说是非| 9 3 { @ Z K 4 (常形象了。

3. 加载因子

“没关系”，面试官终于有表情了，他好像感觉挺满意似的在笑？“那b i } }你之前提到过HashMap在进行扩容的时分有必定的条件，便是元素超越默认容量的0.75，那为什么这个值被定为0.75呢？”

这个0.75是HashMap的加载因子特点，它/ H ` x – =是用来进行扩容判别的。

假定加载因子是0.5，HashMap初始化容量是16，当HashMap中{ @ u有16 * 0.5=8个元素时，HashMap就会进行R 0 , ( e扩容操作。

而HashMap中加载因子为0.75Y s V，是考虑到了功能和容量的平衡。

由加载因子的定义，能够知道它的取值规模是(0, 1]。

假如加载因子过小，那么扩容门槛~ a J P低，扩容频频，这尽管能使元素存储得更稀疏，N i f有效避免了哈希抵触产生，一起操作功能较高，可是会占用更多的空间。
假如加载因子过大，那么扩容门槛高，扩容不频频，尽管占用的空间下降了，可是这会导致元素存储密集，产生哈希抵触的概率大大提h t !高，然后导致存储元素的数据结构愈加复杂（用: V k 6 4 9 N ;于解决哈希抵触），终究导致操作功能下降。
还有一个因素是为了提升扩容功率。因为Hashj z |Map的容量（size特点，构造函数中的initialCapacity变量）有一个要求：它必定s a 是h / { .2的幂。所以加载因子挑选了0.75就能够确保它与容量的乘积为整数。

// 构造函数
public HashMap(int initialCapacity, float loadFactor) {
    // ……
    this.loadFactor = loadFactort  j @ b G ?;// 加载因子
    this.thrs S { h Veshold = tabJ $ tleSizeFor(initialCapacity);
}

/**
 * 回来2的幂
 * Returns a power of two size for the given targ7 Q 8 ~ met capacity.
 * MAXIMUM_CAPACITY = 1 << 30
 */
static finaU t g M L + 9l int tableSizeFor(int cap)x { ] e ] : g b y {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4V y Q ] u;
    n |= n &T p 4 ; Y z g u Kgt;>> 8;
    n |= n >P ] C />> 16;
    return (n < 0) ? 1 : (n &b 2 8 A p gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAa ^ L &PACITY : n + 1y D - Z n R $;
}

4. HashMap4 I S g A ! ? . Q容量! a m j g N

HashMap的默认初始容量是16，而每次扩容是扩容为本来的2倍。这儿的16和2倍就确保了HashMap的容量是2的n次幂，这样规{ I ^ P f划的原因是什么呢？

原因一：与运算高效

与运算&，根据二进制数值，一起为1成m . , (果为1，否则便是0。如1&1=1,1&0=0,0& T { b H ] . Qamp;0=0。运用与运算的原因便是关于核算机来说n 0 ] P 3 n，与运算非常高效。

原因二：有利于元素充涣散列，削减 Hash 磕碰

在给HashMap增加元素的putVal函数中，有这样一段代码：

// n为容量，hash为该元素的hash值
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

它会在增加元素时，经过i = (n - 1) & hash核算该元素在HashMap中的方位。

当 HashMap 的容量为 2 的 n 次幂时，他的二进制值是100000……（n个0），所以n-1的值便是01W s F 7 k $ N Q1111……（n个1），这样的话(n - 1) & hash的值才能够充涣散列。

举个比如，假定容量为16，现在有哈希值为1111，1110，1011，1001四种将被增加，它们与n-1(15的二进制=01111)的哈希值分L W X别为1111、1110、1110、1011，都不相同。

而假定容量不为2的n次幂，假定为10，那么它与上述四个哈希值进行与运算的成果分别是：0101、0100、0001、0001。

能够看到后两个值产生了磕碰，从中能够看出，非2的n次幂会加大哈希磕碰的概率。所以HashMap的容量设置为2的n次幂有利于元素_ ; A 7 B的充涣散列。

5. 死循环

上文在提到为什么HashMap是线程不安全的的时分提到过在JDK1.7中由于哈希磕碰，在同一个数组下标中进行链表元素的新增时是用头插法，会导致死循环，而在JDK1.8中改为运用尾插法，避免了死循环的状况的产生。

允许后端君在此偷个懒，贴出网上比较具体的解说分析博p J g v Q客与视频：

老生常谈，HashMap的死循r v v q p % c N e环【根据JDK1.7】
jdk1.7及1.8r n 8 6 z B 4 5 `HashMap,Q 2 ? Q aConcurrentHashMap完成原理,自己运用,侵删

“小伙子，看来你对HashMap的了解仍是挺多的。”面试官点了点头，对后端君发出了肯定。

“接下来我们再来聊聊其他内容吧……”

6. 小结

你还记得面试官对后端君提出的那些关于D c ] QHashMap的问题吗？来回忆一下吧

HashMap的底层数据结构是怎样样的？
哈希磕碰是什么？怎样解决？
哈希值的核算过程？
为什么HashMap是线程不安全的？
简略说下红黑树的特性
HashMap加载因子为什么默认是0.75？f p D M 3 d I R K
HashMap容量为什么规划成是2的n次幂？
HashM0 G 4ap死循环c / y R , c C ?是怎样回事？0 m 7 o

版权声明：本文为Planeswalker23所创，转载请带上原文链接，感谢。

7. 参考资料

JDK 源码中 HashMap 的 hash 办法原D 2 n D 4 a J 9理是什么？胖君的答复
JDK1.7和JDK1.8中HashMap为什么是线程不安全的？
聊一聊红黑树的左旋和右旋（结合JAVA中Tre2 M s ? @ n } } :eMap红黑树完成）
HashMap初始容量为什么是2的nb + t 8 w次幂及扩容为什么是2倍的方式

本文运用 mdnice 排版

Java