【Java 核心面试宝典】Day3、图解 HashMap 高频面试及底层实现架构！
**注意：这里所说的相同并不一定是 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 的高 16 位二进制和低 16 位二进制进行异或运算，得到的结果再与当前数组长度减一进行与运算。最终得到一个数组下标，过程如下：
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
*/
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 循环。计算出新下标位置只能是在原下标位置或者在原下标位置加上原容量位置。
11、HashMap 和 HashTable 对比分析
============================
其实在 HashMap 相关面试的时候，还有一个经常会问到的内容，就是让你对 HashMap 和 HashTable 进行一个对比分析，HashTable 作为一个保留类，虽然现在已经被弃用了，但是很多时候还会用来做一个对比，那么接下来我们就来讲一讲他们的区别，我在这里以一个图表的形式展示一下：
好了，关于 Map 接口和 HashMap 的底层实现的过程，以及在面试中参考的核心问题就和大家分析到这里！
有问题的小伙伴可以在评论区留言提出！觉得不错记得点赞关注哟！
还未添加个人签名 2021.11.08 加入
还未添加个人简介
评论