08-02 23:26 已编辑门头沟学院 Java 发布于浙江

关注

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 则会还原为链表。（如下）
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存储结构图示： alt jdk1.8中HashMap的put方法： 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是如何实现的？

计算 key 的 hash 值，根据 hash 值找到对应数组下标: （数组长度-1）& hash。
判断数组该位置处的元素的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

jdk1.7及之前是底层数组+链表实现，可以存储null键和null值，线程不安全。
jdk1.8后，数组+链表+红黑树；可以存储键为 null 的键值对，但最多只允许一条记录的键为 null；初始size为16，扩容：newize = oldsize * 2

HashTable

底层数组+链表实现，key还是value都不能为null。
线程安全，在修改数据时锁住整个HashTable，效率低，使用synchronize修饰。初始size为11，扩容：newsize = oldsize * 2+1。
多线程访问时，只要有一个线程访问或操作该对象，其他线程只能阻塞，并发性能非常差。

ConcurrentHashMap

jdk1.7中：

alt

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。