摘要： 剖析 Map 接口的具体应用以及 HashMap 的底层是如何实现的？
本文分享自华为云社区《【图文并茂】深度解析 HashMap 高频面试及底层实现构造！【奔跑吧！JAVA】》，原文作者：灰小猿。
Map 接口大家应该都据说过吧？它是在 Java 中对键值对进行存储的一种罕用形式，同样其中的 HashMap 我置信大家应该也不会生疏，一说到 HashMap，我想略微晓得点的小伙伴应该都说是： 这是存储键值对的，存储形式是数组加链表的模式。 然而其中真正是如何进行存储以及它的底层架构是如何实现的，这些你有理解吗？
可能很多小伙伴该说了，我只须要晓得它怎么应用就能够了，不须要晓得它的底层实现，但其实恰恰相反，只晓得它怎么应用是齐全不够的，而且在 Java 开发的面试之中，HashMap 底层实现的发问和考查曾经是司空见惯的了。所以明天我就来和大家剖析一下 Map 接口的具体应用以及 HashMap 的底层是如何实现的？
小伙伴们缓缓往下看，看完相对会让你播种满满的！
1，Map 接口和 List 接口是什么关系？
对于这个问题，如果非要说这两个接口之间存在怎么的关系的话，那无非就只有一个，就都是汇合。存放数据的。在其余下面，Map 接口和 List 接口的分割其实并不大，为什么这么说？
先来看 List 接口， 对于 List 接口我在之前也和大家提到过，它是继承于 Collection 接口的，是 Collection 接口的子接口，只是用于对数据的单列存储。继承关系如下图：
而 Map 接口是一个顶层接口， 上面蕴含了很多不同的实现类，它是用于对键值对（key:value）进行存储的，继承关系如下图：
所以 Map 接口和 List 接口的关系和应用不要混同了！
2、Map 有哪些罕用的实现类？
下面对于 Map 的继承构造咱们曾经理解了，咱们也看了其中很多不同的实现类，这些类很多也是咱们比拟相熟的，比方 HashMap、TreeMap 以及 HashTable。在面试的时候，面试官往往就还会问，Map 接口下有哪些罕用的实现类以及它们的作用，那么接下来咱们就来对这几个接口进行简略的介绍和剖析一下，
HashMap: 下面也说了，HashMap 的底层实现是数组 + 链表 + 红黑树的模式的，同时它的数组的默认初始容量是 16、扩容因子为 0.75，每次采纳 2 倍的扩容 。也就是说，每当咱们数组中的存储容量达到 75% 的时候，就须要对数组容量进行 2 倍的扩容。
HashTable:HashTable 接口是线程平安，然而很早之前有应用，当初简直属于一个遗留类了， 在开发中不倡议应用。
ConcurrentHashMap: 这是现阶段应用应用比拟多的一种线程平安的 Map 实现类。在 1.7 以前应用的是分段锁机制实现的线程平安的。然而在 1.8 当前应用 synchronized 关键字实现的线程平安。
其中对于 HashMap 的考查和发问在面试中是最频繁的，这也是在日常开发中最应该深刻了解和把握的。所以接下来就次要和大家详细分析一下 HashMap 的实现原理以及面试中的常考问题。
3、请论述 HashMap 的 put 过程？
咱们晓得 HaahMap 应用 put 的形式进行数据的存储，其中有两个参数，别离是 key 和 value，那么对于这个键值对是如何进行贮存的呢？咱们接下来进行剖析一下。
在 HashMap 中应用的是数组 + 链表的实现形式，在 HashMap 的下层应用数组的模式对“雷同”的 key 进行存储，上层对相应的 key 和 value 应用链表的模式进行链接和存储。
留神：这里所说的雷同并不一定是 key 的数值雷同，而是存在某种雷同的特色，具体是哪种特色骂咱们持续往下看！
HashMap 将将要存储的值依照 key 计算其对应的数组下标，如果对应的数组下标的地位上是没有元素的，那么就将存储的元素寄存下来，然而如果该地位上曾经存在元素了，那么这就须要用到咱们下面所说的链表存储了，将数据依照链表的存储程序顺次向下存储就能够了。这就是 put 的简略过程，存储后果如下：
然而咱们有时候存储的数据会很多，那么如果始终应用链表的模式进行数据的存储的话就或造成咱们的链表的长度十分大，这样无论在进行删除还是在进行插入操作都是非常麻烦的，因而对于这种状况应该怎么办呢？
这里就波及到了一个链表中数据存储时，进行“树化”和“链化”的一个过程，那么什么是“树化”和“链化”呢？
当咱们在对键值对进行存储的时候，如果咱们在同一个数组下标下存储的数据过多的话，就会造成咱们的链表长度过长，导致进行删除和插入操作比拟麻烦，所以在 java 中规定， 当链表长度大于 8 时，咱们会对链表进行“树化”操作，将其转换成一颗红黑树（一种二叉树，右边节点的值小于根节点，左边节点的值大于根节点），这样咱们在对元素进行查找时，就相似于进行二分查找了，这样的查找效率就会大大增加。
然而当咱们进行删除操作，将其中的某些节点删除了之后，链表的长度不再大于 8 了，这个时候怎么办？难道就要连忙将红黑树转化为链表的模式吗？其实并不是， 只有当链表的长度小于 6 的时候，咱们才会将红黑树从新转化为链表，这个过程就叫做“链化”。
过程图示如下：
那么为什么要在长度 8 的时候进行“树化”，而在长度小于 6 的时候才进行“链化”呢？为什么不间接在长度小于 8 的时候就进行“链化”？
次要起因是因为： 当删除一个元素，链表长度小于 8 的时候间接进行“链化”，而再减少一个元素，长度又等于 8 的时候，又要进行“树化”，这样重复的进行“链化”和“树化”操作特地的耗费工夫，而且也比拟麻烦。所以程序就规定， 只有当当链表长度大于等于 8 的时候才进行“树化”，而长度小于 6 的时候才进行“链化”，其中对于 8 树化、6 链化这两个阈值心愿大家牢记！
4、链表中是依照怎么的程序存放数据的？
咱们当初曾经晓得了 HashMap 中的元素是如何寄存的，然而有时候面试官可能还会问咱们，在 HashMap 中，向链表中存储元素是在头结点存储的还是在尾节点存储的？
这个咱们须要晓得，对于 HashMap 中链表元素的存储。
在 JDK1.7 以及前是在头结点插入的，在 JDK1.8 之后是在尾节点插入的。
5、Hash(key) 办法是如何实现的？
咱们当初曾经晓得了 HashMap 中的元素是如何存储的了，那么当初就是如何应该依据 key 值进行相应的数组下标的计算呢？
咱们晓得 HashMap 的初始容量是 16 位，那么对于初始的 16 个数据位，如果将数据依照 key 的值进行计算存储，个别最简略的办法就是依据 key 值获取到一个 int 值，办法是：
int hashCode = key.hashCode()
而后对获取到的 hashCode 与 16 进行取余运算，hashCode % 16 = 0~15这样失去的永远都是 0—15 的下标。这也是最最原始的计算 hash(key) 的办法。
然而在理论状况下，这种办法计算的 hash(key) 并不是最优， 寄存到数组中的元素并不是最扩散的，而且在计算机中进行余运算其实是十分不不便的、
所以为了计算结果尽可能的离散，当初计算数组下标最罕用的办法是：先依据 key 的值计算到一个 hashCode，将 hashCode 的高 18 位二进制和低 18 位二进制进行异或运算，失去的后果再与以后数组长度减一进行与运算。最终失去一个数组下标，过程如下：
int hashCode = key.hashCode()
int hash = hash(key) = key.hashCode() 的高 16 位 ^ 低 16 位 &(n-1) 其中 n 是以后数组长度 同时在这里要揭示一点：
在 JDK1.7 和 JDK1.8 的时候对 hash(key) 的计算是略有不同的
JDK1.8 时，计算 hash(key) 进行了两次扰动
JDK1.7 时，计算 hash(key) 进行了九次扰动，别离是四次位运算和五次异或运算
其中扰动可能了解为运算次数
以上就是 Hash(key) 办法的实现过程。
6、为什么 HashMap 的容量始终是 2 的倍数？
HashMap 的容量之所以始终是 2 的倍数，其实是与下面所说的 hash(key) 算法无关的。
起因是只有参加 hash(key) 的算法的（n-1）的值尽可能都是 1 的时候，失去的值才是离散的。如果咱们以后的数组长度是 16，二进制示意是 10000，n- 1 之后是 01111，使得 n - 1 的值尽可能都是 1，对于其余是 2 的倍数的值减 1 之后失去值也是这样的。
所以只有当数组的容量长度是 2 的倍数的时候，计算失去的 hash(key) 的值才有可能是绝对离散的，
7、Hash 抵触如何解决？
什么是 Hash 抵触？就是当我计算到某一个数组下标的时候，该下标上曾经寄存元素了，这就叫 Hash 抵触，很显然，如果咱们计算数组下标的算法不够优良的时候，很容易将存储的数据积攒到同一个下标下面，造成过多的 Hash 抵触。
那么如何解决 hash 抵触？
最应该解决的其实就是让存储的 key 计算失去的数组下标尽可能的离散，也就是要求 hash(key) 尽可能的优化，数组长度是 2 的倍数。这也就是 Hash 抵触的次要解决办法。
具体能够查看上面 HashMap 要害局部的底层源码：
Hash(key) 的底层实现
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}put(key,value) 办法的底层实现
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}8、HashMap 是如何扩容的？
咱们在下面说到了 HashMap 的数组的初始容量是 16，然而很显然 16 个存储位是显然不够的，那么 HashMap 应该如何扩容呢？
在这里须要用到一个参数叫“扩容因子”，在 HashMap 中“扩容因子”的大小是 0.75，
咱们下面也提到过，对于初始长度为 16 的数组，当其中存储的数据长度等于 16*0.75=12 时。就会对数组元素进行扩容，扩容量是原来数组容量的 2 倍，也就是以后是 15 话，再扩容就是扩容 32 个数据位。
9、扩容后元素怎么寄存的？
咱们晓得 HashMap 的数组在进行扩容之后，数组长度是减少的，那么这个时候，前面新扩容的局部就是空的。然而这个时候咱们就应该让前面的数据位空着吗？显然是不可能的，这样会造成内存的很大节约。
因而在 HashMap 的数组扩容之后，原先 HashMap 数组中寄存的数据元素会进行从新的地位调配，从新将元素在新数组中进行存储。以充分利用数组空间。
10、JDK1.7 和 JDK1.8 对 HashMap 的实现比拟
在 JDK1.7 和 JDK1.8 中对 HashMap 的实现是略有不同的，最初咱们依据下面的解说对 JDK1.7 和 JDK1.8 在 HashMap 的实现中的不同进行剖析比拟。
（1）、底层数据结构不同
在 HashMap 的 put 过程中，JDK1.7 时是没有红黑树这一概念的，间接是进行的链表存储，在 JDK1.8 之后才引入了红黑树的概念，来优化存储和查找。
（2）、链表的插入方式不同
在 HashMap 向链表中插入元素的过程中，JDK1.7 时是在表头节点插入的，JDK1.8 之后是在尾节点插入的。
（3）、Hash(key) 的计算形式不同
在 Hash(key) 的计算中，JDK1.7 进行了九次扰乱，别离是四次位运算和五次异或运算，JDK1.8 之后只进行了两次扰动。
（4）、扩容后数存储地位的计算形式不同
在扩容后对存储数据的重新排列上，JDK1.7 是将所有数据的地位打乱，而后依据 hash(key) 进行从新的计算，而在 JDK1.8 之后是对原来的数据下标进行了两次 for 循环。计算出新下标地位只能是在原下标地位或者在原下标地位加上原容量地位。
好了，对于 Map 接口和 HashMap 的底层实现的过程，以及在面试中参考的外围问题就和大家剖析到这里！
点击关注，第一工夫理解华为云陈腐技术~