当前位置：首页 > ds >正文

新版 Java SE 集合框架 Map 篇

ds 2025/7/21 10:48:13

第1集 · 小试牛刀（上）

1. 考点说明

考察对 java.util.Map 及其常见实现类的基本认知与区别。

2. 你用过哪些 Map 的实现？

表格

复制

实现类	典型使用场景 & 特点简述
HashMap	日常最常用，无序，允许 1 个 null key、多个 null value，非线程安全。
Hashtable	早期遗留类，已过时，线程安全但性能差，不允许任何 null key/value。
LinkedHashMap	继承 HashMap，保持插入顺序或访问顺序，常用于 LRU 缓存。
TreeMap	基于红黑树，按 key 自然顺序或自定义 Comparator 排序，非线程安全。
ConcurrentHashMap	高并发场景首选，线程安全且分段锁/ CAS 优化，不允许 null key/value。

3. HashMap vs Hashtable（面试高频）

表格

复制

对比维度	HashMap	Hashtable
线程安全	❌ 非线程安全	✅ 用 `synchronized` 保证线程安全
底层结构	JDK8 前：数组 + 链表	数组 + 链表（无红黑树优化）
默认初始容量	16	11
扩容方式	`oldCap * 2`	`oldCap * 2 + 1`
null 支持	允许 1 个 null key、多个 null value	不允许任何 null key/value（抛 NPE）
迭代器	fail-fast（快速失败）	fail-fast（快速失败）
性能	高（无锁）	低（全表锁）
适用场景	单线程或外部同步场景	遗留系统，不推荐新项目使用

补充：
若需要线程安全且高性能，优先使用 ConcurrentHashMap（锁粒度更细）。
Hashtable 的 put/get 方法均用 synchronized 修饰，导致并发下吞吐量极低。

第2集对象的比较、排序以及 `hashCode` 和 `equals` 的重写

简介

在 Java 中，对象的比较、排序以及在 Map 和 Set 集合中的使用，经常需要重写 hashCode() 和 equals() 方法。这些方法的正确实现对于保证集合的正确性和性能至关重要。

考点

掌握 hashCode 和 equals 的实现和使用场景。

`hashCode()` 和 `equals()` 方法介绍

`hashCode`

定义：hashCode() 是 Object 类中的一个方法，所有类都继承自 Object。
返回类型：int 类型。
作用：根据一定的 hash 规则（如存储地址、字段、长度等），映射成一个整数值，即散列值。
使用场景：
- 主要用于 HashMap、HashSet 等基于哈希的集合中，以快速定位对象存储位置。
- 散列值用于确定对象在哈希表中的索引位置。

`equals`

定义：equals() 也是 Object 类中的方法，所有类都继承自 Object。
返回类型：boolean 类型。
作用：根据自定义的匹配规则，用于比较两个对象是否相等。
比较逻辑：
- 判断地址是否相同。
- 非空判断和 Class 类型判断。
- 强转。
- 对象里面的字段一一匹配。
使用场景：
- 对象比较。
- 在集合容器中进行排重、比较、排序。

实践建议

一致性：equals() 和 hashCode() 必须保持一致性。如果两个对象通过 equals() 方法比较是相等的，那么它们的 hashCode() 方法必须返回相同的散列值。
重写：当你重写 equals() 方法时，通常也需要重写 hashCode() 方法，以避免违反上述一致性原则。
性能：合理设计 hashCode() 方法可以显著提高基于哈希的集合（如 HashMap、HashSet）的性能。

HashMap 和 TreeMap 应该怎么选择，使用场景

HashMap

底层结构：散列桶（数组+链表），JDK8 引入红黑树优化。
特点：
- 快速的存储和检索。
- 无序。
- 允许一个 null key 和多个 null value。
适用场景：
- 需要快速插入、删除和定位元素。
- 不需要元素有序。

TreeMap

底层结构：平衡二叉树（红黑树）。
特点：
- 可以自定义排序规则。
- 需要实现 Comparator 接口。
- 元素有序。
适用场景：
- 需要元素自然排序或自定义排序规则。
- 例如，实现微信签名工具类时，可能需要使用 TreeMap。

Set 和 Map 的关系

核心概念：
- Set 不保存重复的元素，存储一组唯一的对象。
- Set 的每一种实现都是对应 Map 里面的一种封装。
具体实现：
- HashSet 对应 HashMap。
- TreeSet 对应 TreeMap。

常见 Map 的排序规则是怎样的？

按添加顺序：
- 使用 LinkedHashMap。
按自然排序：
- 使用 TreeMap。
自定义排序：
- 使用 TreeMap(Comparator c)。

实践建议

一致性：当重写 equals() 方法时，通常也需要重写 hashCode() 方法，以保持一致性。
性能：合理选择 Map 的实现类可以显著提高程序的性能和可读性。
封装：Set 的实现类都是对 Map 的封装，理解这一点有助于更好地使用集合框架。

第4集编程语言面试题之新版 Java SE 集合框架 Map 篇 <进阶>

简介

进阶考察集合框架里面基础 Map 面试题。

考点

考查 Map 的横向和纵向知识点。

如何实现线程安全且效率高的 Map？

问题：如果需要线程安全，且效率高的 Map，应该怎么做？

答案：在多线程环境下，可以使用 java.util.concurrent 包下的 ConcurrentHashMap，或者使用 Collections.synchronizedMap() 方法来包装一个 Map。ConcurrentHashMap 虽然是线程安全的，但是他的效率比 Hashtable 要高很多。

ConcurrentHashMap：
- 提供了比 Hashtable 更高的并发性能。
- 使用分段锁或其他同步机制来减少锁的竞争。
- 适用于高并发场景。
Collections.synchronizedMap()：
- 通过包装一个 Map 来提供线程安全性。
- 每次操作都需要获取锁，可能影响性能。
- 适用于并发需求不高的场景。

为什么 `Collections.synchronizedMap` 后是线程安全的？

问题：为什么使用 Collections.synchronizedMap 包装后返回的 map 是线程安全的？

答案：使用 Collections.synchronizedMap() 包装后返回的 map 是加锁的。这意味着每次访问或修改 map 时都需要获取锁，从而确保同一时间只有一个线程可以执行这些操作，避免了多线程环境下的数据不一致问题。

加锁机制：
- 可以指定一个锁对象，所有线程在访问 map 时都需要获取这个锁。
- 如果不指定锁对象，那么会使用 map 本身作为锁，这可能会导致死锁。

实践建议

选择正确的 Map 实现：根据应用场景选择最合适的 Map 实现，以平衡线程安全性和性能。
避免死锁：在使用 Collections.synchronizedMap() 时，注意避免使用 map 本身作为锁对象，以防止死锁。
考虑使用 ConcurrentHashMap：在高并发场景下，优先考虑使用 ConcurrentHashMap，它提供了更好的并发性能。

通过理解和掌握这些 Map 相关的进阶知识，可以确保在多线程环境下正确地使用集合，从而提高程序的健壮性和性能。

第5集编程语言面试题之新版 Java SE 集合框架 Map 篇 <深入底层>

简介

深入探讨 HashMap 的实现原理。

考点

是否掌握 HashMap 的底层实现。

看过 `HashMap` 源码吗，介绍下你了解的 `HashMap`

答案：我看过 HashMap 的源码，以下是我对 HashMap 的理解：

底层结构

数组+链表+红黑树（JDK 8 引入红黑树优化）：
- HashMap 的底层是一个数组，数组的每个元素是一个链表，即数组和链表的结合体。
- 在 JDK 1.8 中，当链表的长度超过一定阈值（默认为8）时，链表会转换为红黑树，以优化搜索性能。

核心组件

Node<K,V>[] table：数组，数组的元素是 Entry（Node 继承自 Entry）。
Entry：元素是一个 key-value 的键值对。
- 它持有一个指向下一个 Entry 的引用，table 数组的每个 Entry 元素同时也作为当前 Entry 链表的首节点，也指向了该链表的下个 Entry 元素。

性能优化

在 JDK 1.8 中，链表的长度大于8时，链表会转换成红黑树，以提高搜索效率。

图示说明

JDK 1.7 及之前版本的 HashMap 结构图

在 JDK 1.7 及之前的版本中，HashMap 使用数组和链表来存储元素。当发生哈希冲突时，元素会被存储在同一个数组索引下的链表中。

[bucket1]---[bucket2]---[bucket3]---...---[bucketN]|           |           |         |E1          E2          E3        EN|           |           |         |...         ...         ...       ...

数组（bucket）：HashMap 的底层是一个数组，每个数组元素称为一个桶（bucket）。
链表（Entry）：每个桶可以存储一个链表，链表中存储的是 Entry 对象，每个 Entry 对象包含 key、value 和指向下一个 Entry 的引用。

JDK 1.8 版本的 HashMap 结构图

在 JDK 1.8 中，HashMap 引入了红黑树来优化链表过长时的性能问题。当链表长度超过 TREEIFY_THRESHOLD（默认为8）时，链表会转换成红黑树。

链表结构

当链表长度未超过阈值时，结构如下：

[bucket1]---[bucket2]---[bucket3]---...---[bucketN]|           |           |         |E1          E2          E3        EN|           |           |         |...         ...         ...       ...

红黑树结构

当链表长度超过阈值时，链表会转换成红黑树，结构如下：

[bucket1]                               [bucket2]/                                  /         \E1                                  E2           E4/  \                                /  \        /  \
E2   E3                              E5   E6    E7   E8
|     |                              |     |    |     |
E4   E5                                ...   ...  ...   .../  \                                           /  \...   ...                                       ...   ...

红黑树：是一种自平衡二叉查找树，通过颜色标记（红色和黑色）来确保树的平衡，从而提高搜索、插入和删除操作的性能。

总结

数组：HashMap 的底层是一个数组，用于存储桶。
链表：每个桶可以存储一个链表，用于解决哈希冲突。
红黑树：当链表长度超过一定阈值时，链表会转换成红黑树，以提高性能。

代码示例

public class HashMap<K,V> {static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;Entry(int hash, K key, V value, Entry<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}}transient Node<K,V>[] table;static final int TREEIFY_THRESHOLD = 8; // 链表转换为红黑树的阈值
}

实践建议

理解底层结构：深入理解 HashMap 的底层结构（数组+链表+红黑ds树）有助于更好地使用和优化 HashMap。
关注性能优化：了解 JDK 1.8 中引入的红黑树优化，可以帮助在高并发场景下选择合适的数据结构。
源码阅读：阅读 HashMap 的源码可以加深对其内部工作机制的理解，有助于在面试中展示技术深度。

哈希碰撞解释及常见解决办法

什么是哈希碰撞？

哈希碰撞指的是不同的 key 通过哈希函数计算得到的哈希值相同，即它们需要被放到同一个桶（bucket）中。

常见的解决办法有哪些？

链表法：
- 每个桶（bucket）内部使用链表来存储具有相同哈希值的元素。
- 当发生碰撞时，新元素被添加到链表的末尾。
开放地址法：
- 寻找空的桶来存储元素，而不是使用链表。
- 可以通过线性探测、二次探测或双重哈希等方法来寻找下一个空桶。
再哈希法：
- 使用另一个哈希函数来计算哈希值，如果发生碰撞，则使用新的哈希函数重新计算哈希值。

HashMap 采用哪种方法？

HashMap 采用的是链表法来解决哈希碰撞问题。在 JDK 1.8 及以后的版本中，当链表长度超过一定阈值（TREEIFY_THRESHOLD，默认为8）时，链表会转换为红黑树，以优化性能。

HashMap 底层实现详解

考点

是否掌握 HashMap 的底层实现。

为什么 `HashMap` 底层是数组+链表+红黑树？

答案： HashMap 的底层实现采用了数组、链表和红黑树的组合结构，这种设计是为了在不同的使用场景下提供最优的性能。

数组（Node<K,V>[] table）：
- 数组是 HashMap 的基础结构，用于根据 key 的哈希值确定元素的存储位置。
- 通过哈希函数计算出的索引值，可以直接定位到数组的对应位置，从而快速访问元素。
链表：
- 当多个 key 经过哈希函数计算后得到相同的索引值时，即发生哈希碰撞，这些 key 会通过链表连接起来。
- 链表结构可以解决哈希冲突，将具有相同哈希值的元素存储在同一个桶（bucket）中。
红黑树（JDK 1.8 引入）：
- 当链表长度超过一定阈值（TREEIFY_THRESHOLD，默认为8）时，链表会转换为红黑树。
- 红黑树是一种自平衡的二叉查找树，它可以在 O(log n) 时间复杂度内完成查找、插入和删除操作，从而提高性能。
- 在 HashMap 中，当链表长度超过阈值时，转换为红黑树可以避免因链表过长而导致的性能下降。

性能分析

数组：提供快速的随机访问能力。
链表：解决哈希冲突，但当链表过长时，性能会下降。
红黑树：在链表长度超过阈值时，提供更优的性能，特别是在并发访问和大数据量场景下。

图示说明

复制

数组索引 --- 链表/红黑树|          |E1 --- E2  ||          |...       ...

每个数组索引对应一个链表或红黑树，链表或红黑树中的每个节点存储一个 Entry 对象，包含 key、value 和指向下一个节点的引用。

实践建议

理解哈希函数：选择合适的哈希函数可以减少哈希碰撞，提高 HashMap 的性能。
关注性能优化：了解 HashMap 的性能优化机制，如链表转红黑树，可以帮助在实际开发中做出更好的设计决策。
源码阅读：阅读 HashMap 的源码可以加深对其内部工作机制的理解，有助于在面试中展示技术深度。

通过理解和掌握这些 HashMap 相关的底层知识，可以确保在实际开发中正确地使用 HashMap，从而提高程序的性能和可维护性。

为什么选择红黑树而不是其他树结构？

红黑树的特点

自平衡：红黑树是一种自平衡的二叉查找树，通过左旋、右旋、变色等操作来保持树的平衡。
查找效率：红黑树的查找、插入和删除操作的时间复杂度为 O(log n)，这比链表的 O(n) 要高效得多。
实现简单：与其他自平衡二叉查找树（如AVL树）相比，红黑树的实现相对简单，且性能相差不大。

为什么不一直使用红黑树？

资源消耗：对于少量数据，红黑树的平衡操作（如左旋、右旋、变色）会消耗更多的资源。
性能考虑：在数据量较少时，链表的性能已经足够好，且实现简单，不需要额外的平衡操作。

为什么在链表长度达到8时才转换为红黑树？

性能与资源的权衡

前期使用链表：在数据量较少时，使用链表可以减少资源消耗，因为链表的插入和删除操作不需要进行复杂的平衡操作。
后期转换为红黑树：当链表长度超过8时，转换为红黑树可以显著提高查找效率，避免因链表过长而导致的性能问题。

具体原因

查找性能：当链表长度超过一定阈值时，查找性能会急剧下降。红黑树可以提供更优的查找性能。
避免过度转换：设置一个合理的阈值（如8），可以避免在数据量较少时过早地进行树的转换，从而减少不必要的资源消耗。

并发包里面 ConcurrentHashMap 面试题

简介

考察对并发包下的 ConcurrentHashMap 基础和原理的掌握。

考点

是否掌握 ConcurrentHashMap 的基础和原理。

了解 ConcurrentHashMap 吗？为什么性能比 Hashtable 高，说下原理

答案： ConcurrentHashMap 是一种线程安全的 Map，其性能比 Hashtable 高，原因在于它采用了分段锁的思想，锁粒度更细化。

Hashtable：
- 类基本上所有的方法都是采用 synchronized 进行线程安全控制。
- 在高并发情况下，效率较低，因为每次只有一个线程可以访问 Hashtable。
ConcurrentHashMap：
- 采用了分段锁的思想提高性能，锁粒度更细化。
- 允许多个线程同时访问 ConcurrentHashMap 中的不同段。

JDK 1.7 和 JDK 1.8 中的实现区别

JDK 1.7：
- 使用锁分段技术，将数据分成一段段存储，每个数据段配置一把锁，即 segment 类。
- 这个类继承 ReentrantLock 来保证线程安全。
- 技术点：Segment + HashEntry。
JDK 1.8：
- 取消 Segment 这个分段锁数据结构，底层也是使用 Node 数组 + 链表 + 红黑树。
- 实现对每一段数据就行加锁，也减少了并发冲突的概率。
- 技术点：Node + CAS（读）+ Synchronized（写）。