码猿笔记

V1

2022/04/15阅读:41主题:全栈蓝

HashMap面试题总结(从浅到深,持续更新)

HashMap的key可以为null吗?

HashMap 最多只允许一条记录的键为 null(多个会覆盖),允许多条记录的值为 null

HashMap 是线程安全的吗?

HashMap 是线程不安全的。

如何保证HashMap线程安全?

  • 使用Collections.synchronizedMap方法,使HashMap具有线程安全的能力
Map m = Collections.synchronizedMap(new HashMap(...))
  • 或者使用 ConcurrentHashMap,ConcurrentHashMap 是一个 Segment 数组, Segment 通过继承ReentrantLock 来进行加锁,所以每次需要加锁的操作锁住的是一个 segment,这样只要保证每个 Segment 是线程安全的,也就实现了全局的线程安全

有几种方式遍历HashMap?

  1. Map.Entry
Map<Integer , Integer> map = new HashMap<>();
map.put(13);
map.put(2,4);
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
for (Map.Entry<Integer, Integer> entry : entries) {
    System.out.println("key="+entry.getKey()+",value="+entry.getValue());
}
  1. keySet
Set<Integer> keySet = map.keySet();
for (Integer key : keySet) {
    System.out.println("key="+key+",value="+map.get(key));
}
  1. values
Collection<Integer> values = map.values();
for (Integer value : values) {
    System.out.println("value="+value);
}
  1. Lambda表达式
map.forEach((key , value)->{
 System.out.println("key="+key+",value="+value);
});

负载因子是多少?它有什么用

一般来说,默认的负载系数(0.75)在时间和空间成本之间提供了一个很好的权衡。较高的值减少了空间开销,但增加了查找成本(反映在HashMap类的大多数操作中,包括get和put)。在设置map的初始容量时,应考虑其期望的表项数及其负载因子,以尽量减少重哈希操作的次数。如果初始容量大于最大条目数除以负载因子,则不会发生重新哈希操作。

jdk 1.7 和 jdk 1.8 HashMap的区别?

  • jdk 1.7 由数组+链表组成,查找的时候,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话, 需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)。
  • jdk 1.8 数组+链表+红黑树 组成,为了降低这部分的开销,在 Java8 中, 当满足一定条件时,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

链表转红黑树要满足什么条件?

  1. 链表中的元素的个数为8个或超过8个
  2. 当前数组的长度大于或等于64才会把链表转变为红黑树。

为什么要满足当前数组的长度大于或等于64才会把链表转变为红黑树

链表转变为红黑树的目的是为了解决链表过长,导致查询和插入效率慢的问题,而如果要解决这个问题,也可以通过数组扩容,把链表缩短也可以解决这个问题。所以在数组长度还不太长的情况,可以先通过数组扩容来解决链表过长的问题。

为什么阈值定义为8?

阈值定义为8和hashcode碰撞次数的泊松分布有关,主要是为了寻找一种时间和空间的平衡。 红黑树中的TreeNode是链表中的Node所占空间的2倍,虽然红黑树的查找效率为o(logN),要优于链表的o(N),但是当链表长度比较小的时候,即使全部遍历,时间复杂度也不会太高。因此要寻找一种时间和空间的平衡,即在链表长度达到一个阈值之后再转换为红黑树。 之所以是8,是因为Java的源码贡献者在进行大量实验发现,hash碰撞发生8次的概率已经降低到了0.00000006,几乎为不可能事件,如果真的碰撞发生了8次,那么这个时候说明由于元素本身和hash函数的原因,此时的链表性能已经已经很差了,操作的hash碰撞的可能性非常大了,后序可能还会继续发生hash碰撞。所以,在这种极端的情况下才会把链表转换为红黑树,链表转换为红黑树也是需要消耗性能的,为了挽回性能,权衡之下,才使用红黑树,提高性能的,大部分情况下hashMap还是使用链表。

红黑树转链表的阈值为6,主要是因为,如果也将该阈值设置于8,那么当hash碰撞在8时,会发生链表和红黑树的不停相互激荡转换,白白浪费资源。中间有个差值7可以防止链表和树之间的频繁转换, 假设一下: 如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果HashMap不停的插入,删除元素,链表个数在8左右徘徊,就会频繁的发生红黑树转链表,链表转红黑树,效率会很低下。

参考文章:https://blog.csdn.net/G_whang/article/details/113855384

HashMap 怎么确定数组下标的?

根据数组长度n和key的hashcode,对((n-1)&hashcode)得到数组下标。

为什么HashMap的数组的大小是2的幂?

取余操作中如果除数是2的幂次等价于其除数减一的与操作,也就是说hash%length=hash&(length-1)。数组的下标是通过与运算获取到的,而不是通过取余,与运算比取余运算速度更快,但是也有一个前提条件,就是数组的长度得是一个2的幂。

HashMap put流程

  1. 对key进行hash算法,得到一个hashcode
  2. 如果数组长度为0或者为null,对数组进行扩容,得到数组长度n
  3. 通过 key的hashcode&数组长度n 计算出数组下标
  4. 如果数组下标位置中没有数据,将put进来的数据封装Node对象并存到给下标位置
  5. 如果数组下标位置有数据p,即发生hash碰撞,如果key存在,覆盖数据
  6. 如果数据p属于红黑树,会把新数据插入到红黑树中
  7. 如果以上都不是就遍历链表,遍历链表过程中统计链表长度,当链表长度超过8 进行treeifyBin 红黑树化链表
  8. treeifyBin树化中如果数组长度小于64或数组为null则进行扩容,否则 数组长度大于等于64 链表转红黑树

HashMap 是如何扩容的?

  1. HashMap的扩容指的就是数组的扩容, 因为数组占用的是连续内存空间,所以数组的扩容其实只能新开一个新的数组,然后把老数组上的元素转移到新数组上来,这样才是数组的扩容
  2. 先新建一个2被数组大小的数组
  3. 然后遍历老数组上的每一个位置,如果这个位置上是一个链表,就把这个链表上的元素转移到新数组上去
  4. 在jdk8中,因为涉及到红黑树,这个其实比较复杂,jdk8中其实还会用到一个双向链表来维护红黑树中的元素,所以jdk8中在转移某个位置上的元素时,会去判断如果这个位置是一个红黑树,那么会遍历该位置的双向链表,遍历双向链表统计哪些元素在扩容完之后还是原位置,哪些元素在扩容之后在新位置,这样遍历完双向链表后,就会得到两个子链表,一个放在原下标位置,一个放在新下标位置,如果原下标位置或新下标位置没有元素,则红黑树不用拆分,否则判断这两个子链表的长度,如果超过8,则转成红黑树放到对应的位置,否则把单向链表放到对应的位置。
  5. 元素转移完了之后,在把新数组对象赋值给HashMap的table属性,老数组会被回收到。

To be continued

能力一般,水平有限,如有错误,请多指出。 如果对你有用点个关注给个赞呗 更多文章可以关注一下我的微信公众号suncodernote

分类:

后端

标签:

Java

作者介绍

码猿笔记
V1