Java 面试题基础（一）HashMap 底层原理

 关注
发布于: 2020 年 07 月 05 日
HashMap 在面试中有多高频就不用说了吧，几乎大部分的面试中都有 HashMap 的身影。为什么它会这么高频呢？一是因为 HashMap 在我们的业务代码中是使用频率最高的类型之一，经常需要在代码中使用；二是 HashMap 涵盖的知识点有很多，比如 hash 算法的优化，寻址算法的优化，hash 碰撞问题，怎么扩容等等。本文就是针对这些问题来剖析的。
一、HashMap 底层实现原理HashMap 的底层数据结构是数组，但是，在 JDK1.7 和 JDK1.8 中解决 hash 碰撞的实现方式是不一样的。JDK1.7 中是以数组+链表的方式解决 hash 碰撞的问题，而 JDK1.8 则在此基础上新增了红黑树结构，当链表大于 8 且容量大于 64 时，链表结构会转换成红黑树结构。这里给出 JDK1.8 中红黑树的组成结构示意图：
JDK1.8 HashMap 组成结构图
那么，JDK1.8 中为什么要增加红黑树呢？因为一旦链表过长，会严重影响 HashMap 的查询性能，极限情况下查询时间复杂度会退化成 O(n)，而红黑树的查询时间复杂度为 O(logn)。
﻿
还有一个问题，为什么链表长度大于 8 且容量大于 64 时才转化为红黑树呢？这是因为红黑树的实现逻辑比较复杂，如果一个链表长度不是很长，即使 O(n) 的时间复杂度也不会导致查询性能问题，反而使用了红黑树会对新增元素的性能产生影响，也就是说元素太少时对红黑树的维护造成的性能下降也许会大于对查询性能的优化。
二、hash 算法和寻址算法的优化我们先看下 JDK1.8 中 hash 算法的代码：
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
这段代码的意思是，先算出 key 的 hashCode 值 h，再与 h 右移 16 位后的值异或。为什么要这样做呢？这里先给出答案，这是为了高低位都参与寻址运算，原因下面再说。
﻿
我们先看下 JDK1.8 对寻址算法的优化运算公式：(n-1) & hash
﻿
默认 HashMap 的数组长度 n 是 16，我们要对数组进行寻址，也就是计算数组下标，通常的做法是使用 hash 值对 n 取模。但是取模运算的性能较低，所以使用 (n-1) & hash 替换取模运算，它的效果是跟取模运算效果是一样的。当然这个效果一样有一个前提，n 是 2m。
﻿
假设 key 值为 name，我们的寻址过程是这样的：
计算 name 的 hashCode 值，如 0000 0000 0011 0011 0111 1010 1000 1011
n-1 的二进制为：0000 0000 0000 0000 0000 0000 0000 1111
计算 (n-1) & hashCode：0000 0000 0000 0000 0000 0000 0000 1011
转换为十进制，得到结果：11
﻿
再假设有另外一个 key 的 hashCode 为：0000 0000 0011 0010 0111 1010 1000 1011，这个 hashCode 与 name 的 hashCode 只有高 16 位中的其中一位不同，但是最后计算出来的数组下标也是 11，因为低 16 位完全相同了。
计算过程如下图所示（红色字体为不同的位）：
直接使用 hashCode 计算下标
由图中我们可以看到，如果两个 key 的 hashCode 低 16 位是完全相同的，只是高 16 位不一样，高 16 位和 n-1 进行与运算，实际上是可以忽略的，因为 n-1 的高 16 位都是 0，0 与其他值进行与运算都是 0，也就相当于高 16 位是没有参与运算的。
﻿
而如果使用 (h = key.hashCode()) ^ (h >>> 16) 公式进行异或后就不一样了，异或后的低 16 位是高 16 位和低 16 位的运算结果，让低 16 位同时保持了高低 16 位的特征，也就是这个过程实际上是让高 16 位也参与到寻址计算中来。具体计算过程如下图所示（红色字体为不同的位）：
hash 算法优化
﻿
从 hash 优化前和优化后的运算结果来看，很明显可以看出区别了。没有 hash 优化前只有低 16 位参与运算，计算出来的数组下标是一样的，而 hash 优化后让高 16 位参与运算，计算出来的数组下标则不一样。前面留下的问题也应该明白原因了，就是为了让高低 16 位都参与运算，尽量降低 hash 冲突的概率。
三、HashMap 是如何解决 hash 碰撞的实际上通过上面对 hash 算法和寻址算法的优化后，hash 碰撞还是会不可避免地出现。解决 hash 碰撞比较常用的两种解决方法是：开放寻址法和拉链法。HashMap 使用的是拉链法，也就是前面提到的链表，当发生 hash 碰撞时，使用链表把冲突的 node 连接起来，当链表长度大于 8 且 n 大于 8 时，转换为红黑树结构。
﻿
除了使用拉链法解决 hash 碰撞问题，也使用了一些手段降低 hash 碰撞的概率。前面提到的 hash 优化是其中之一，还有一个控制手段是负载因子。默认的负载因子是 0.75，这个负载因子是什么意思呢？由于 HashMap 从 API 角度是设计为可以动态扩容的，但是底层的数组是定长的，我们要扩容，就需要重新申请一个更大的数组，把原数组的数据拷贝过去，这个负载因子就是用来控制什么时候扩容的。HashMap 默认的数组长度是 16，0.75 的意思是当数组元素达到 16*0.75=12 时，触发扩容操作，容量更大了，hash 碰撞的概率也会降低。
﻿
默认的负载因子为什么要设置为 0.75 呢？首先要声明一下，这个是在实例化 HashMap 的时候我们是可以自己指定的，但是一般会使用默认的值。其实默认负载因子 0.75 是出于容量和性能的平衡，我们不妨这样假设：
假设负载因子是 1，也就是数组容量满了之后才会触发扩容，此时发生 hash 碰撞的概率是很高的，你想啊，数组 16 个元素，也许插入到 15 个元素之后，后面插入的成百上千个元素都是跟之前的 key 有 hash 碰撞的，也就是数组元素只有 15，但是 node 可能已经有几千个了，链表和红黑树元素会很多，查询性能也就好不到哪去了。
假设负载因子是 0.5，也就是数组用到一半的时候就触发扩容了，这时 hash 碰撞的概率是降低了，但是空间的浪费会比较严重，极限情况下会浪费一半的空间。还有一个就是会频繁地触发扩容，这个操作也会消耗性能。
﻿
所以综上考虑，就取了一个平均数作为默认负载因子。这样扩容不会太频繁，空间浪费也不会太多，同时 hash 碰撞概率也会处于一个相对好接受的值。
四、HashMap 是如何进行扩容的HashMap 默认的数组大小是 16，当数组大小达到负载因子阈值时，比如默认情况下数组大小达到 12 了，就会触发扩容。扩容的时候有两个点是值得我们注意的：2两倍扩容和重新 hash。
1、两倍扩容两倍扩容是因为前面我们提到的寻址算法优化，也就是使用 (n-1) & hash 替代取模操作提高性能，这个式子要和取模操作的结果一致，前提就是 n 要等于 2 的 m 次方。所以为了维护这个结论成功，必须使用两倍扩容。
2、重新 hash数组扩容后，需要重新计算每个元素在新的数组的位置。在 JDK1.7 中，扩容后会重新计算每个元素的 hash 值，但在 JDK1.8 中对这个操作做了优化，它使用的高位运算（e.hash & oldCap）来确定元素位置是否改变，其中 e 为元素，oldCap 为原数组大小。比如当 e.hash = 10（0000 1010），oldCap = 16（0001 0000）时：
e.hash & oldCap 得到结果 0000 0000，高一位 0000 十进制为 0，扩容是不发生位置变化
当 e.hash = 0001 0001 时，e.hash & oldCap 得到结果 0001 0000，高一位 0001 十进制为 1，扩容是位置发送了变化，新的下标位置为：原下标位置+oldCap
五、总结本篇文章分析了 HashMap 的底层实现原理，在 JDK1.7 中是通过数组+链表实现的，JDK1.8 则通过数组+链表+红黑树实现。还介绍了 JDK1.8 中对 hash 算法的优化，让高低 16 位都参与到寻址运算中，数组下标计算也使用 (n-1) & hash 优化了寻址算法。解释了 HashMap 是如何解决 hash 碰撞问题的，HashMap 中是使用拉链法解决，也提到了负载因子的作用。对于数组扩容问题，两倍扩容的原因是 HashMap 使用了  (n-1) & hash 优化对数组的取模寻址算法，算法成立的前提是数组长度必须是 2n;JDK1.8 也对以前扩容后会重新计算每个元素的 hash 进行了优化，改为使用高位运算（e.hash & oldCap）来确定元素的位置是否需要改变，运算结果高一位为 0，则扩容后数组下标不变，高一位为 1，则扩容后的数组下标为：原数组下标+oldCap。