Java实习生面试复习(二):HashMap

我是一名很普通的双非大三学生,跟很多同学一样,有着一颗想进大厂的梦。接下来的几个月内,我将坚持写博客,输出知识的同时巩固自己的基础,记录自己的成长和锻炼自己,备战2021暑期实习面试!奥利给!!

Map这个大家庭真的是成员很多呢,我们可以简单回忆一下有哪些,我这里例举几个: HashMap、TreeMap、LikedHashMap、ConcurrentHashMap(线程安全)、WeekHashMap、HashTable 。不记的话,可以搜搜其他文章回顾一下哦。本文只讨论HashMap

HashMap基本是我们在日常使用中频率特别高的一个数据结构类型了,同时也是面试经常问到的,围绕着HashMap能展开一系列问题,比如:

  • HashMap底层是如何实现的?
  • HashMap的扩容机制?
  • HashMap为什么会出现死循环?
  • HashMap在1.7和1.8有什么区别?做了哪些优化?

本文不对源码做过深的讨论,因为我觉得实习生应该还不需要了解的那么透彻,我们需要做的是知道这些东西,源码什么的,每一步怎么做的,感兴趣的同学可以自己看一下。

HashMap源码分析

1.HashMap中常见的属性

//HashMap的 初始容量为 16
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

 //最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;

 //默认的扩容因子
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
 //转换红黑树的临界值,当链表长度大于此值时,会把链表结构转换为红黑树结构
 static final int TREEIFY_THRESHOLD = 8;

 //转换链表的临界值,当元素小于此值时,会将红黑树结构转换成链表结构
 static final int UNTREEIFY_THRESHOLD = 6;

 //当数组容量大于 64 时,链表才会转化成红黑树
 static final int MIN_TREEIFY_CAPACITY = 64;

 //记录迭代过程中 HashMap 结构是否发生变化,如果有变化,迭代时会 fail-fast
 transient int modCount;

 //HashMap 的实际大小,可能不准(因为当你拿到这个值的时候,可能又发生了变化)
 transient int size;

 //存放数据的数组
 transient Node<K,V>[] table;

 // 扩容的门槛,有两种情况
 // 如果初始化时,给定数组大小的话,通过 tableSizeFor 方法计算,数组大小永远接近于 2 的幂次方,比如你给定初始化大小 19,实际上初始化大小为 32,为 2 的 5 次方。
 // 如果是通过 resize 方法进行扩容,大小 = 数组容量 * 0.75
 int threshold;

 /** HashMap中的内部类 **/
 
 //链表的节点  1.7之前叫Entry,1.8之后叫Node
 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}
 
 //红黑树的节点
 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {}
复制代码

上面已经对属性写了注释,下面在补充一点:

  • 什么是扩容因子("加载因子,负载因子")?扩容因子是用来判断当前数组("哈希桶")什么时候需要进行扩容,假设因子为0.5,那么HashMap的初始化容量是16,则16*0.5 = 8个元素的时候,HashMap就会进行扩容。

  • 为什么扩容因子是0.75?这是均衡了时间空间损耗算出来的值,因为当扩容因子设置比较大的时候,相当于扩容的门槛就变高了,发生扩容的频率变低了,但此时发生Hash冲突的几率就会提升,当冲突的元素过多的时候,变成链表或者红黑树都会增加了查找成本( hash 冲突增加,链表长度变长 )。而扩容因子过小的时候,会频繁触发扩容,占用的空间变大,比如重新计算Hash等,使得操作性能会比较高。

  • HashMap初始化容量是多少?在不指定capacity情况下,初始化容量是16,但 不是初始化的时候就创建了一个16大小的数组,而是在第一次put的时候去判断是否需要初始化 ,我感觉这有一点懒加载的味道。并且我们经常在一些文章,包括阿里巴巴开发手册中看到:" 集合初始化时,指定集合初始值大小 ",如果有很多数据需要储存到 HashMap 中,建议 HashMap 的容量一开始就设置成足够的大小,这样可以防止在其过程中不断的扩容,影响性能,比如 HashMap 需要放置1024 个元素,由于没有设置容量初始大小,随着元素不断增加,容量 7 次被迫扩大,resize 需要重建hash 表,严重影响性能

  • 初始化容量为什么是16?为什么每次扩容是2的幂次方?因为在使用是2的幂的数字的时候,Length-1的值是所有二进制位全为1,这种情况下,index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。这是为了实现均匀分布。深入解释可以看这篇文章: HashMap中hash(Object key)原理,为什么(hashcode >>> 16)。

  • Node节点是什么?。node节点在1.7之前也叫entry节点,是HashMap存储数据的一个节点,主要有四个属性,hash,key,value,next,其实就是一个标准的链表节点,很容易理解。

  • 链表什么时候会转换成红黑树?当链表长度大于等于 8 时,此时的链表就会转化成红黑树,转化的方法是:treeifyBin,此方法有一个判断, 当链表长度大于等于 8,并且整个数组大小大于 64 时 ,才会转成红黑树,当数组大小小于 64 时,只会触发扩容,不会转化成红黑树

  • 增强 for 循环进行删除,为什么会出现ConcurrentModificationException?因为增强 for 循环过程其实调用的就是迭代器的 next () 方法,当你调用 map#remove () 方法进行删除时,modCount 的值会 +1,而这时候迭代器中的 expectedModCount 的值却没有变,导致在迭代器下次执行 next () 方法时,expectedModCount != modCount 就会报 ConcurrentModificationException 的错误。这其实是一种 快速失败的机制java.util下面的集合类基本都是快速失败的,实现都一样,都是依靠这两个变量。

可以使用迭代器的remove()方法去删除,因为 Iterator.remove () 方法在执行的过程中,会把最新的modCount 赋值给 expectedModCount,这样在下次循环过程中,modCount 和 expectedModCount 两者就会相等。

HashMap在1.7和1.8有什么区别?做了哪些优化?

从文章开头贴出的代码属性中我们可以看出,1.8版本的HashMap的底层实际上是一个 数组+链表+红黑树 的结构,但是在 1.7的时候是没有红黑树 的,这正是1.8版本中对查询的优化,我们都知道链表的查询时间复杂度是O(n)的,因为它需要一个一个去遍历链表上所有的节点,所以当链表长度过长的时候,会严重影响 HashMap 的性能,而红黑树具有快速增删改查的特点,这样就可以有效的解决链表过长时操作比较慢的问题。于是在1.8中引入了红黑树。

Java实习生面试复习(二):HashMap

HashMap的新增

我们来看 1.8中HashMap的新增 图示,就不在晒那一大段的新增代码了。

Java实习生面试复习(二):HashMap

我们在文字总结描述一下,新增大概的步骤如下:

  1. 判断哈希表(数组)是否为空,第一次put的时候需要扩容(初始化);
  2. 通过 key 的 hash 计算出index,找到数组中对应的位置,并判断是否有值,有就跳转到 6,否则到 3;
  3. 如果 hash冲突,两种解决方案:链表 or 红黑树;
  4. 判断是红黑树,调用红黑树新增的方法;
  5. 如果是链表,递归循环,判断长度会不会大于8,大于8就先转换成红黑树,在调用4;
  6. 根据 onlyIfAbsent 判断是否需要覆盖,然后插入;
  7. 判断是否需要扩容,需要扩容进行扩容,结束。

HashMap的扩容

Java实习生面试复习(二):HashMap

从上图中,我们可以看出HashMap在
当前元素个数 > 扩容因子 * 最大容量

的时候会触发扩容,那么它是怎么扩容的? 注意:这样的元素个数和数组大小是有区别的,元素个数是指hashmap中node的个数,并不是指数组的大小。

  • 扩容:创建一个新的Node(Entry)空数组,长度是原数组的2倍。
  • ReHash:遍历原Node(Entry)数组,把所有的Node重新Hash到新数组。

为什么需要重新计算Hash?

1.7中计算下标:
static int indexFor(int h, int length) {
       return h & (length-1);
}
// n 表示数组的长度,i 为数组索引下标
1.8中计算下标:tab[i = (n - 1) & hash])

// 1.8中的高位运算
if ((e.hash & oldCap) == 0) {
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
}
复制代码

在jdk1.7中有indexFor(int h, int length)方法。jdk1.8里没有1.8中用tab[(n – 1) & hash]代替但原理一样。从上我们可以看出是因为长度扩大以后,Hash的规则也随之改变。这在1.7和1.8中差别不大,但是1.7需要与新的数组长度进行重新hash运算,这个方式是相对耗性能的,而在1.8中对这一步进行了优化,采用高位运算取代了ReHash操作,其实这是一种规律,因为每次扩容,其实元素的新位置就是 原位置+原数组长度 ,不懂的可以看 jdk8之HashMap resize方法详解(深入讲解为什么1.8中扩容后的元素新位置为原位置+原数组长度)

既然说到扩容,那么肯定会扯出1.7HashMap的死循环问题

我们都知道1.7之前,JDK是头插法,考虑头插法的原因是不用遍历链表,提高插入性能,但在JDK8已经改为尾插法了,不存在这个死循环问题,所以问题就出在头插法这。 我觉得这篇文章在这写的很清楚,想深入了解一下产生死循环的过程,可以看这篇文章: 老生常谈,HashMap的死循环 。总结一下来说就是:Java7在多线程操作HashMap时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。Java8在同样的前提下并不会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系。

那么1.8之后,HashMap就是线程安全的了嘛? 首先我们要知道所谓线程安全是对(读/写)两种情况都是数据一致而言的,而只读且不变化的话,HashMap也是线程安全的,之所以不安全是在写的时候,索引构建的时候会产生构建不一致的情况,比如无法保证上一秒put的值,下一秒get的时候还是原值,所以线程安全还是无法保证,所以要问面试官有没有读写并存的情况。且java.util下面的集合类基本都不是线程安全的。所以HashMap 是非线程安全的,我们可以自己在外部加,或者通过 Collections#synchronizedMap 来实现线程安全,Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁;或者使用ConcurrentHashMap

原文 

https://juejin.im/post/5e709e61e51d45270764f9c0

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java实习生面试复习(二):HashMap

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址