HashMap 深度剖析:知识要点与高频面试题全解

本篇文章,我们说一下关于HashMap的相关知识及HashMap常出的高频面试题。

HashMap是什么?

1. 是什么?

HashMap 是 Java 中一个常用的数据结构,它实现了 Map 接口。 alt

由分类图可知,HashMap是Java集合中Map接口的实现类。

2.主要特点

  • 实现了 Map 接口,继承于 AbstractMap。
  • 可以存储键为 null 的键值对,但最多只允许一条记录的键为 null。
  • 不支持线程同步,是非线程安全的。如果在多线程环境下使用且需要线程安全,可以使用 ConcurrentHashMap。
  • 键与值的类型可以相同也可以不同。常见基本类型的包装类如下:boolean(Boolean)、byte(Byte)、short(Short)、int(Integer)、long(Long)、float(Float)、double(Double)、char(Character)。
  • 查找、插入和删除操作的平均时间复杂度为 O(1),在大多数情况下性能出色。
  • 能够高效地存储和检索大量的键值对数据。
  • HashMap 中的元素实际上是对象,一些常见的基本类型可以使用它的包装类。
  • HashMap 的底层结构在 Java 7 中使用的是"数组 + 链表",发生散列冲突的键值对会用头插法添加到单链表中;在 Java 8 中使用的是"数组 + 链表 + 红黑树",发生散列冲突的键值对会用尾插法添加到单链表中,如果链表的长度大于 8 且散列表容量大于 64,会将链表树化为红黑树,在扩容再散列时,如果红黑树的长度低于 6 则会还原为链表。(如下) alt
  • HashMap 的数组长度保证是 2 的整数幂,默认的数组容量是 16,默认装载因子上限是 0.75,扩容阈值是 12(16 * 0.75)。创建 HashMap 对象时,并不会创建底层数组,这是一种懒初始化机制,直到第一次 put 操作才会通过 resize()扩容操作初始化数组。

3. 常见用法

以下是 HashMap 常见的方法:

  • put(key, value):添加键值对到 HashMap 中。
  • get(key):根据键获取对应的值。
  • remove(key):根据键删除对应的键值对。
  • size():获取 HashMap 中的元素数量。
  • clear():删除所有键值对。

示例代码:

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建 HashMap 对象,键为整数类型,值为字符串类型
        HashMap<Integer, String> sites = new HashMap<Integer, String>();

        // 添加键值对
        sites.put(1, "Google");
        sites.put(2, "Runoob");
        sites.put(3, "Taobao");
        sites.put(4, "Zhihu");

        // 输出 HashMap
        System.out.println(sites); 

        // 根据键获取对应的值
        System.out.println(sites.get(3)); 

        // 删除键值对
        sites.remove(4);
        System.out.println(sites); 

        // 清空 HashMap
        sites.clear();
        System.out.println(sites); 
    }
}

HashMap的高频面试题

HashMap是如何存储元素的?

jdk1.8中的hashMap存储结构图示: altjdk1.8中HashMap的put方法: alt

alt

alt

alt

注意:链转化红黑树treeifyBin方法如下

alt

进入treeifyBin方法的if条件中TREEIFY_THRESHOLD的值为8 ,TREEIFY_THRESHOLD-1=7且treeifyBin方法中MIN_TREEIFY_CAPACITY的值为64。故,链表的长度大于 8 且散列表容量大于 64**,是链表转化为红黑树的条件。

答:

简单地说,HashMap 的底层结构在 Java 7 中使用的是"数组 + 链表",发生散列冲突的键值对会用头插法添加到单链表中;在 Java 8 中使用的是"数组 + 链表 + 红黑树",发生散列冲突的键值对会用尾插法添加到单链表中,如果链表的长度大于 8 且散列表容量大于 64,会将链表树化为红黑树。

以JDK1.8为例。在JDK1.8中,HashMap进行put操作过程为:

  • 如果散列表为空时,调用resize()初始化散列表。

  • 计算关于key的hashcode值会计算key值的hash值,将(数组长度-1)和hash值进行&操作,得到数组的下标值。

  • 如果该下标下内容为空,新建node节点,直接添加到散列表中即可。

  • 如果下标内容不为空,分三种情况:

    • 第一种,还没有链化。比较key的hash值和引用或是equals,如果相同,则覆盖value。
    • 第二种,已经链化。遍历链表,判断节点的key值情况(同上),如果相同,则覆盖value;如果不同,则继续遍历链表,直到末尾,若链表的长度大于 8 且散列表容量大于 64,则将链表转红黑树,否则尾插法创建Node节点。(jdk1.7头插,1.8尾插)
    • 第三种,链表已经转化成红黑树。搜索树中节点,判断节点的key值情况,如果相同 ,则替换value,如果不存在,则在树中插入新的TreeNode节点。
  • 如果HashMap中存储的键值对数量超过了阈值,则调用resize()进行扩容。

HashMap中get是如何实现的?

  1. 计算 key 的 hash 值,根据 hash 值找到对应数组下标: (数组长度-1)& hash。
  2. 判断数组该位置处的元素的key值是否刚好就是我们要找的key相同。是,则返回该元素的value,若不是,那么:
    • 如果已经链化,则遍历链表,找到相等的key,返回value。
    • 如果已经形成红黑树,则用红黑树方法找相同的key,找到则返回value。

HashMap扩容问题(什么时候调用resize())?

答:

1.putVal中判断数组的容量capacity为空时,初始化数组table,初始化桶数组长度为16,阈值为16* 0.75 = 12。(负载因子loadfactor默认为0.75).

2.当元素数量size达到阙值时即size > loadfactor * capacity 时,也是在putVal函数中,调用resize(),扩容后的数组大小是原数组的2倍,将原来的元素重新hash放入到新的散列表中去。

请解释一下HashMap的参数loadFactor,它的作用是什么?

答:

loadFactor表示HashMap的拥挤程度,影响hash操作到同一个数组位置的概率。默认loadFactor等于0.75,当HashMap里面容纳的元素已经达到HashMap数组长度的75%时,表示HashMap太挤了,需要扩容,在HashMap的构造器中可以定制loadFactor。

jdk1.8为什么要引入红黑树?

答: 其实主要就是为了解决jdk1.8以前hash冲突所导致的链化严重的问题。改用红黑树之后,查询的时间复杂度(Olog(n))相比链表(O(n))会降低。

HashMap为什么是线程不安全的?

答: 假设两个线程A、B都在进行put操作,并且hash函数计算出的插入下标是相同的,当线程A判断下标位置为空后由于时间片耗尽导致被挂起,而线程B得到时间片后在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,因此线程不安全。

平时在使用HashMap时一般使用什么类型的元素作为Key?

答: 选择Integer,String这种不可变的类型,像对String的一切操作都是新建一个String对象,对新的对象进行拼接分割等,这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的。

HashMap 、 HashTable、ConcurrentHashMap有什么区别?

答:

HashMap

  1. jdk1.7及之前是底层数组+链表实现,可以存储null键和null值,线程不安全。

  2. jdk1.8后,数组+链表+红黑树;可以存储键为 null 的键值对,但最多只允许一条记录的键为 null;初始size为16,扩容:newize = oldsize * 2

HashTable

  1. 底层数组+链表实现,key还是value都不能为null。

  2. 线程安全,在修改数据时锁住整个HashTable,效率低,使用synchronize修饰。初始size为11,扩容:newsize = oldsize * 2+1。

  3. 多线程访问时,只要有一个线程访问或操作该对象,其他线程只能阻塞,并发性能非常差。

ConcurrentHashMap

jdk1.7中:

alt

  1. jdk1.7 中底层segment数组+HashEntry数组+ 链表,采用分段锁来实现线程安全。 底层结构具体描述: ⼀个ConcurrentHashMap ⾥包含⼀个Segment 数组,每个segement包含一个HashEntry数组,每个HashEntry数组元素是一个链表,用于存储键值对数据。

    线程安全具体实现: 采用分段锁的机制。 Segment实现了ReentrantLock ,所以 Segment 是⼀种可重⼊锁,扮演锁的⻆⾊。每个 Segment 守护着⼀个 HashEntry 数组⾥的元素,当一个线程占用锁访问其中一个segement数据时,其他段数据也能被其他线程访问。 缺点: 但是这么做的缺陷就是每次通过 hash 确认位置时需要 2 次才能定位到当前 key 应该落在哪个槽, 通过 hash 值和 段数组长度-1 进行位运算确认当前 key 属于哪个段,即确认其在 segments 数组的位置。再次通过 hash 值和 table 数组长度 - 1进行位运算确认其所在桶。

jdk1.8中

alt

  • jdk1.8中底层采用Node数组+链表/红黑树。

    • 线程安全实现方式:采用 采⽤ CAS 和 synchronized 来保证并发安全,synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点,这样只要 hash 不冲突,就不会产⽣并发,效率⼜提升 N 倍。
  • jdk1.8 彻底放弃segment 而采用node,不再使用分段锁。

  • 线程安全实现机制

    jdk1.7采用segment分段锁机制,segment继承自ReetrantLock。 jdk1.8 采用CAS + synchronized,是对hashtable进行优化,将锁细粒化到每个table的每个元素,来提升并发性能。

  • 链表节点数量大于8时,链表转换为红黑树

  • 时间复杂度:从遍历链表O(n),变成遍历红黑树O(logN)。

推荐使用

在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap替代。

jdk1.7中,hashmap在并发情况下,会出现什么问题?jdk1.8中,hashmap中会出现什么问题?

答: jdk1.7中:

  • 问题:jdk1.7中,链表采用双向链表,在并发情况下,由于采用头插法,多个线程同时在链表头部插入节点时,由于操作不是原子的,可能导致多个线程同时读取链表头,并在相同的头节点上插入新节点。这样就有可能导致多个节点的 next 指针同时指向相同的节点,形成一个环。
  • 解决措施:JDK 1.8 中采用了单向链表,采用尾插法,同时引入了红黑树来替代链表,避免了并发情况下可能成环的问题。

jdk1.8中:

  • 问题:

  • 并发修改异常:在遍历hashmap过程中,若有其他线程对hashmap进行修改(插入、删除),可能会导致并发修改异常。

    • 例如:假设两个线程A、B都在进行put操作,并且hash函数计算出的插入下标是相同的,当线程A判断下标位置为空后由于时间片耗尽导致被挂起,而线程B得到时间片后在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,因此线程不安全。
  • 死锁:在并发情况下,可能存在竞争锁的情况,导致死锁的发生。

  • 解决方法: 使用ConcurrentHashMap代替HashMap。 

以上内容出自本人整理的面试秘籍。 


以上内容出自本人整理的面试秘籍。 *********************************************************** 提取码: fi3x 复制这段内容后打开百度网盘手机App,操作更方便哦


创作不易,如果有帮助到你,请点下方🌸支持我,谢谢!


请关注我,以便及时获取最新内容哦!

#软件开发2024笔面经##java##软件开发笔面经##秋招#
Java 高频面试题 文章被收录于专栏

干货预警!本人大厂在职程序员,根据自身面试经历整理,分享给大家。

全部评论

相关推荐

点赞 评论 收藏
分享
3 10 评论
分享
牛客网
牛客企业服务