|大厂面试官：说一下JDK1.8 HashMap有哪些亮点？
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
上篇我们介绍了JDK1.7版的HashMap ， 今天我们来讲解下JDK1.8版的HashMap 。
JDK1.7的实现大家看出有没有需要优化的地方？
其实一个很明显的地方就是：当 Hash 冲突严重时 ， 在桶上形成的链表会变的越来越长 ， 这样在查询时的效率就会越来越低；时间复杂度为 O(N) 。
因此JDK1.8 中重点优化了这个查询效率 。
1、JDK1.8 HashMap 数据结构图
我们会发现优化的部分就是把链表结构变成了红黑树 。 原来jdk1.7的优点是增删效率高 ， 于是在jdk1.8的时候 ， 不仅仅增删效率高 ， 而且查找效率也提升了 。
注意：不是说变成了红黑树效率就一定提高了 ， 只有在链表的长度不小于8 ， 而且数组的长度不小于64的时候才会将链表转化为红黑树 。
问题一：什么是红黑树呢？
红黑树是一个自平衡的二叉查找树 ， 也就是说红黑树的查找效率是非常的高 ， 查找效率会从链表的o(n)降低为o(logn) 。 如果之前没有了解过红黑树的话 ， 也没关系 ， 你就记住红黑树的查找效率很高就OK了 。
问题二：为什么不一下子把整个链表变为红黑树呢？
这个问题的意思是这样的 ， 就是说我们为什么非要等到链表的长度大于等于8的时候 ， 才转变成红黑树？在这里可以从两方面来解释
（1）构造红黑树要比构造链表复杂 ， 在链表的节点不多的时候 ， 从整体的性能看来 ，数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高 。 就好比杀鸡焉用牛刀的意思 。
（2）HashMap频繁的扩容 ， 会造成底部红黑树不断的进行拆分和重组 ， 这是非常耗时的 。 因此 ， 也就是链表长度比较长的时候转变成红黑树才会显著提高效率 。
2、HashMap构造方法构造方法一共有四个：
这四个构造方法很明显第四个最麻烦 ， 我们就来分析一下第四个构造方法 ， 其他三个自然而然也就明白了 。 上面出现了两个新的名词：loadFactor和initialCapacity 。 我们一个一个来分析：
（1）initialCapacity初始容量
官方要求我们要输入一个2的N次幂的值 ， 比如说2、4、8、16等等这些 ， 但是我们忽然一个不小心 ， 输入了一个20怎么办？没关系 ， 虚拟机会根据你输入的值 ， 找一个离20最近的2的N次幂的值 ， 比如说16离他最近 ， 就取16为初始容量 。
（2）loadFactor负载因子
负载因子 ， 默认值是0.75 。 负载因子表示一个散列表的空间的使用程度 ， 有这样一个公式：initailCapacity*loadFactor=HashMap的容量 。所以负载因子越大则散列表的装填程度越高 ， 也就是能容纳更多的元素 ， 元素多了 ， 链表大了 ， 所以此时索引效率就会降低 。 反之 ， 负载因子越小则链表中的数据量就越稀疏 ， 此时会对空间造成烂费 ， 但是此时索引效率高 。
3、put方法我们在存储一个元素的时候 ， 大多是使用下面的这种方式 。
在这里HashMap<String Integer> ， 第一个参数是键 ， 第二个参数是值 ， 合起来叫做键值对 。 存储的时候只需要调用put方法即可 。 那底层的实现原理是怎么样的呢？这里还是先给出一个流程图：
上面这个流程 ， 不知道你能否看到 ， 红色字迹的是三个判断框 ， 也是转折点 ， 我们使用文字来梳理一下这个流程：
（1）第一步：调用put方法传入键值对
（2）第二步：使用hash算法计算hash值
（3）第三步：根据hash值确定存放的位置 ， 判断是否和其他键值对位置发生了冲突
（4）第四步：若没有发生冲突 ， 直接存放在数组中即可
（5）第五步：若发生了冲突 ， 还要判断此时的数据结构是什么？
（6）第六步：若此时的数据结构是红黑树 ， 那就直接插入红黑树中
（7）第七步：若此时的数据结构是链表 ， 判断插入之后是否大于等于8
（8）第八步：插入之后大于8了 ， 就要先调整为红黑树 ， 在插入
（9）第九步：插入之后不大于8 ， 那么就直接插入到链表尾部即可 。
上面就是插入数据的整个流程 ， 光看流程还不行 ， 我们还需要深入到源码中去看看底部是如何按照这个流程写代码的 。
鼠标聚焦在put方法上面 ， 按一下F3 ， 我们就能进入put的源码 。 来看一下：
也就是说 ， put方法其实调用的是putVal方法 。 putVal方法有5个参数：
（1）第一个参数hash：调用了hash方法计算hash值
（2）第二个参数key：就是我们传入的key值 ， 也就是例子中的张三
（3）第三个参数value：就是我们传入的value值 ， 也就是例子中的20
（4）第四个参数onlyIfAbsent：也就是当键相同时 ， 不修改已存在的值
（5）第五个参数evict ：如果为false ， 那么数组就处于创建模式中 ， 所以一般为true 。
知道了这5个参数的含义 ， 我们就进入到这个putVal方法中 。
乍一看 ， 这代码完全没有读下去的欲望 ， 第一次看的时候真实恶心到想吐 ， 但是结合上一开始画的流程图再来分析 ， 相信就会好很多 。 我们把代码进行拆分（整体分了四大部分）：
（1）Node<KV>[
tab中tab表示的就是数组 。 Node<KV> p中p表示的就是当前插入的节点
（2）第一部分：
这一部分表示的意思是如果数组是空的 ， 那么就通过resize方法来创建一个新的数组 。 在这里resize方法先不说明 ， 在下一小节扩容的时候会提到 。
（3）第二部分：
i表示在数组中插入的位置 ， 计算的方式为(n - 1) & hash 。 在这里需要判断插入的位置是否是冲突的 ， 如果不冲突就直接newNode ， 插入到数组中即可 ， 这就和流程图中第一个判断框对应了 。
如果插入的hash值冲突了 ， 那就转到第三部分 ， 处理冲突
（4）第三部分：
我们会看到 ， 处理冲突还真是麻烦 ， 好在我们对这一部分又进行了划分
a）第三部分第一小节：
在这里判断table[i
中的元素是否与插入的key一样 ， 若相同那就直接使用插入的值p替换掉旧的值e 。
b）第三部分第二小节：
判断插入的数据结构是红黑树还是链表 ， 在这里表示如果是红黑树 ， 那就直接putTreeVal到红黑树中 。 这就和流程图里面的第二个判断框对应了 。
c）第三部分第三小节：
如果数据结构是链表 ， 首先要遍历table数组是否存在 ， 如果不存在直接newNode(hash key value null) 。 如果存在了直接使用新的value替换掉旧的 。
注意一点：不存在并且在链表末尾插入元素的时候 ， 会判断binCount >= TREEIFY_THRESHOLD - 1 。 也就是判断当前链表的长度是否大于阈值8 ， 如果大于那就会把当前链表转变成红黑树 ， 方法是treeifyBin 。 这也就和流程图中第三个判断框对应了 。
（5）第四部分：
【|大厂面试官：说一下JDK1.8 HashMap有哪些亮点？】插入成功之后 ， 还要判断一下实际存在的键值对数量size是否大于阈值threshold 。 如果大于那就开始扩容了 。
4、resize方法为什么扩容呢？很明显就是当前容量不够 ， 也就是put了太多的元素 。 为此我们还是先给出一个流程图 ， 再来进行分析 。
这个扩容就比较简单了 ， HaspMap扩容就是就是先计算 新的hash表容量和新的容量阀值 ， 然后初始化一个新的hash表 ， 将旧的键值对重新映射在新的hash表里 。 如果在旧的hash表里涉及到红黑树 ， 那么在映射到新的hash表中还涉及到红黑树的拆分 。 整个流程也符合我们正常扩容一个容量的过程 ， 我们根据流程图结合代码来分析：
这代码量同样让人恶心 ， 不过我们还是分段来分析：
（1）第一部分：
根据代码也能看明白：首先如果超过了数组的最大容量 ， 那么就直接将阈值设置为整数最大值 ， 然后如果没有超过 ， 那就扩容为原来的2倍 ， 这里要注意是oldThr << 1 ， 移位操作来实现的 。
（2）第二部分：
首先第一个else if表示如果阈值已经初始化过了 ， 那就直接使用旧的阈值 。 然后第二个else表示如果没有初始化 ， 那就初始化一个新的数组容量和新的阈值 。
（3）第三部分
第三部分同样也很复杂 ， 就是把旧数据复制到新数组里面 。 这里面需要注意的有下面几种情况：
A：扩容后 ， 若hash值新增参与运算的位=0 ， 那么元素在扩容后的位置=原始位置
B：扩容后 ， 若hash值新增参与运算的位!=0 ， 那么元素在扩容后的位置=原始位置+扩容后的旧位置 。
这里面有一个非常好的设计理念 ， 扩容后长度为原hash表的2倍 ， 于是把hash表分为两半 ， 分为低位和高位 ， 如果能把原链表的键值对 ，一半放在低位 ， 一半放在高位 ， 而且是通过e.hash & oldCap == 0来判断 ， 这个判断有什么优点呢？
举个例子：n = 16 ， 二进制为10000 ， 第5位为1 ， e.hash & oldCap 是否等于0就取决于e.hash第5 位是0还是1 ， 这就相当于有50%的概率放在新hash表低位 ， 50%的概率放在新hash表高位 。
5、hash方法Java 8中的散列值优化函数：
源码中模运算就是把散列值和数组长度做一个\"与\"操作：
这也正好解释了为什么HashMap的数组长度要取2的整次幂 ， 因为这样（数组长度-1）正好相当于一个“低位掩码” ， “与”操作的结果就是散列值的高位全部归零 ， 只保留低位值 ， 用来做数组下标访问 。
以初始长度16为例 ， 16-1=15 ， 2进制表示是00000000 00000000 00001111 ， 和某散列值做“与”操作如下 ， 结果就是截取了最低的四位值：
但这时候问题就来了：这样就算我的散列值分布再松散 ， 要是只取最后几位的话 ， 碰撞也会很严重 ， 这时候“扰动函数”的价值就体现出来了：
右位移16位 ， 正好是32位一半 ， 自己的高半区和低半区做异或 ， 就是为了混合原始hashCode的高位和低位 ， 以此来加大低位的随机性 ， 而且混合后的低位掺杂了高位的部分特征 ， 这样高位的信息也被变相保留下来 ， 即降低了哈希冲突的风险又不会带来太大的性能问题 。 这个设计很巧妙！
6、hash冲突通过异或运算能够是的计算出来的hash比较均匀 ， 不容易出现冲突 。 但是偏偏出现了冲突现象 ， 这时候该如何去解决呢？
在数据结构中 ， 我们处理hash冲突常使用的方法有：开发定址法、再哈希法、链地址法、建立公共溢出区 。 而hashMap中处理hash冲突的方法就是链地址法 。
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表 ， 并将单链表的头指针存在哈希表的第i个单元中 ， 因而查找、插入和删除主要在同义词链中进行 。 链地址法适用于经常进行插入和删除的情况 。
7、table数组用transient修饰
从HashMap 的源码 ， 会发现桶数组 table 被申明为 transient 。 transient 表示易变的意思 ， 在 Java 中 ， 被该关键字修饰的变量不会被默认的序列化机制序列化 。 我们再回到源码中 ， 考虑一个问题：桶数组 table 是 HashMap 底层重要的数据结构 ， 不序列化的话 ， 别人还怎么还原呢？
这里简单说明一下吧 ， HashMap 并没有使用默认的序列化机制 ， 而是通过实现readObject/writeObject两个方法自定义了序列化的内容 。 这样做是有原因的 ， 试问一句 ， HashMap 中存储的内容是什么？不用说 ， 大家也知道是键值对 。 所以只要我们把键值对序列化了 ， 我们就可以根据键值对数据重建 HashMap 。 有的朋友可能会想 ， 序列化 table 不是可以一步到位 ， 后面直接还原不就行了吗？这样一想 ， 倒也是合理 。 但序列化 talbe 存在着两个问题：
1）table 多数情况下是无法被存满的 ， 序列化未使用的部分 ， 浪费空间 。
2）同一个键值对在不同 JVM 下 ， 所处的桶位置可能是不同的 ， 在不同的 JVM 下反序列化 table 可能会发生错误 。
以上两个问题中 ， 第一个问题比较好理解 ， 第二个问题解释一下 。 HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置 ， 但如果键没有覆写 hashCode 方法 ， 计算 hash 时最终调用 Object 中的 hashCode 方法 。 但 Object 中的 hashCode 方法是 native 型的 ， 不同的 JVM 下 ， 可能会有不同的实现 ， 产生的 hash 可能也是不一样的 。 也就是说同一个键在不同平台下可能会产生不同的 hash ， 此时再对在同一个 table 继续操作 ， 就会出现问题 。
综上所述 ， 大家应该能明白 HashMap 不序列化 table 的原因了 ， 下面是HashMap自定义的序列化代码：
8、HashMap非线程安全HashMap源码里面方法是没有synchronized或lock处理的 ， 无法保证线程安全 。 于是出现了线程安全的ConcurrentHashMap ， 这个我们后续讲解 。
欢迎小伙伴们留言交流~~
推荐阅读
- 柳州|泪别天使宝宝！柳州1岁大婴儿捐器官救2人
- 尼斯湖水怪|今年尼斯湖水怪第四次官方目击，出现1分41秒，有两个黑色驼峰
- 阿斯利康疫苗|阿斯利康疫苗再遭打击，南非官方报告公布，所有国家瞬间彻底失望
- 医生|23岁男子脑器官病变，一侧肢体偏瘫，医生却说他朋友脱不了干系！
- 科学家|科学家发现的人体“新器官”，真不是经络
- 糖尿病|患上糖尿病，这5个器官受损越来越严重，降低血糖有3招
- 腹腔|腹腔多器官簇移植的麻醉管理
- 衰老|身体各器官衰老时间表！如果能及早预防，衰老或许会慢一些
- 胃疼|“气得胃疼”是真的？原来胃还是个情绪器官
- 异种器官移植|异种器官移植！未来十年，这项科幻般的技术可能颠覆性出现！