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

导读:本篇文章讲解 Java实习生面试复习(二):HashMap,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

最后修改时间:2022/2/12 补充部分内容

如果你觉得内容对你有帮助的话,不如给个赞🐱‍👓?(σ゚∀゚)σ…:*☆哎哟不错哦

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

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

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

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

HashMap源码分析

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等,使得操作性能会比较高。

threshold 为什么叫扩容门槛?

这里需要注意的是当你new HashMap(指定容量)的时候,它首先会经过tableSizeFor方法的计算,得到最接近指定容量的2的幂次方值,但HashMap的初始化并不是new的时候完成的,而是在第一次put的时候去判断是否需要初始化,此时它会先resize来进行初始化,同时threshold的值会变成threshold * 扩容因子

HashMap 初始化容量是多少?

在不指定capacity情况下,初始化容量是16,但不是初始化的时候就创建了一个16大小的数组,而是在第一次put的时候去判断是否需要初始化,我感觉这有一点懒加载的味道。

并且我们经常在一些文章,包括阿里巴巴开发手册中看到:“集合初始化时,指定集合初始值大小”,如果有很多数据需要储存到 HashMap 中,建议 HashMap 的容量一开始就设置成足够的大小,这样可以防止在其过程中不断的扩容,影响性能,比如HashMap 需要放置1024 个元素,由于没有设置容量初始大小,随着元素不断增加,容量 7 次被迫扩大,resize 需要重建hash 表,严重影响性能

初始化容量为什么是16?为什么每次扩容是2的幂次方?

数学上有个公式,当 b 是 2 的幂次方时,a % b = a &(b-1),所以只有大小是 2 的幂次方时,才能使 hash 值 % n(数组大小) == (n-1) & hash 公式成立。并且位运算(&)效率要比代替取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。

怎么设置一个好的初始化容量?

我们可以借鉴一下HashSet的实现,HashSet底层就是HashMapMath.max ((int) (c.size ()/.75f) + 1, 16),它就是对 HashMap 的容量进行了计算,其意思就是取括号中两个数的最大值(期望的值 / 0.75+1,默认值 16)

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

Node节点是什么?

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

链表什么时候会转换成红黑树?

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

红黑树的平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。以6和8来作为平衡点是因为,中间有个差值7可以防止链表和树之间频繁的转换。假设,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。概括起来就是:链表:如果元素小于8个,查询成本高,新增成本低,红黑树:如果元素大于8个,查询成本低,新增成本高。

什么时候会从红黑树变成链表?

若桶中元素小于等于6时,树结构还原成链表形式

增强 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中引入了红黑树。
在这里插入图片描述

HashMap的新增

我们来看1.8中HashMap的新增图示,就不在晒那一大段的新增代码了。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eztDHzAK-1644646593829)(//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/c7793384445c4d50a87019ac2b636cdd~tplv-k3u1fbpfcp-zoom-1.image)]
我们在文字总结描述一下,新增大概的步骤如下:

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

HashMap的扩容

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eddlFtdv-1644646593829)(//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/b7320d7145d442ab8112a492c9e0470b~tplv-k3u1fbpfcp-zoom-1.image)]

从上图中,我们可以看出HashMap在当前元素个数 > 扩容因子 * 最大容量的时候会触发扩容,那么它是怎么扩容的?
注意:这样的元素个数和数组大小是有区别的,元素个数是指hashmap中node的个数,并不是指数组的大小。

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

HashMap的Hash函数
hash函数是先拿到通过key 的hashcode,是32位的int值,然后让hashcode的高16位和低16位进行异或操作。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这个也叫扰动函数,这么设计原因有:降低hash碰撞,越分散越好;要尽可能高效,因为是高频操作, 因此采用位运算;更深入的可以看看知乎大佬的回答 -> JDK 源码中 HashMap 的 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中对这一步进行了优化,而是通过高位运算(e.hash & oldCap)来确定元素是否需要移动,采用高位运算取代了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

小结:

HashMap 的内容虽然较多,但大多数 api 都只是对数组 + 链表 + 红黑树这种数据结构进行封装而已。那么看完这些,你能举一反三答出一下问题了吗?

  • HashMap的底层数据结构?
  • HashMap的存取原理?
  • Java7和Java8的区别? 为啥会线程不安全? 有什么线程安全的类代替么?
  • 默认初始化大小是多少?为啥是这么多?为啥大小都是2的幂?
  • HashMap的扩容方式?负载因子是多少?为什是这么多?
  • HashMap的主要参数都有哪些?
  • HashMap是怎么处理hash碰撞的?
  • hash的计算规则?

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/15216.html

(0)
小半的头像小半

相关推荐

极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!