Java集合面试题

type

status

date

slug

summary

集合和数组的区别

数组是固定长度的；集合可变长度的。

数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。

数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

List，Set，Map的区别

特性	List	Set	Map
存储结构	有序集合	无序集合	键值对（key-value）集合
元素顺序	元素按插入顺序排列	元素无序，某些实现按自然顺序或插入顺序	key无序排列，某些实现按自然顺序或插入顺序
元素重复	允许重复	不允许重复	键不允许重复，值可以重复
null支持	允许null值	允许一个null值（取决于实现）	允许一个null键，多个null值
常见实现	ArrayList, LinkedList,~~Vector~~	HashSet, TreeSet, LinkedHashSet	HashMap, TreeMap, LinkedHashMap,HashTable
底层结构	ArrayList：动态数组 LinkedList：双向链表 ~~Vector：动态数组~~	HashSet（无序）：哈希表（基于HashMap实现） TreeSet（有序）：红黑树 LinkedHashSet（有序）：哈希表+双向链表（基于LinkedHashMap实现）HashSet的子类	HashMap：哈希表（数组）~~+链表~~+红黑树 TreeMap：红黑树LinkedHashMap：哈希表（数组）+双向链表 HashTable：哈希表（数组）+链表
线程安全	非线程安全使用Collections.synchronizedList或CopyOnWriteArrayList实现线程安全 ~~Vector：线程安全~~	非线程安全使用Collections.synchronizedSet或CopyOnWriteArraySet实现线程安全	非线程安全使用Collections.synchronizedMap或ConcurrentHashMap实现线程安全 HashTable：线程安全
适用场景	需要按顺序存储元素允许重复元素的场景	需要去重的集合需要快速插入和删除元素	需要通过键快速查找值需要存储键值对的场景

Java集合的快速失败机制 “fail-fast”

是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。

例如：

假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。

原因：

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

解决办法：

在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized

使用CopyOnWriteArrayList来替换ArrayList

如何确保一个集合不能被修改

可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

Iterator 和 ListIterator 有什么区别

Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。

Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前/后遍历）。

ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置

数组和 List 之间的转换

ArrayList 和 LinkedList 的区别

特性	ArrayList	LinkedList
数据结构实现	动态数组	双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
随机访问效率	高效，O(1)	较低，O(n)，线性的数据存储方式，所以需要移动指针从前往后依次查找
增加和删除效率	较低，在非首尾元素的操作需要移动其他元素，O(n)	较高，在非首尾元素的操作只需调整引用，O(1)
内存空间占用	较少，仅存储数据本身，结尾会预留一定的容量空间	较多，每个节点存储数据外还存储两个引用，一个指向前一个元素，一个指向后一个元素（直接后继和直接前驱以及数据）
线程安全	非线程安全	非线程安全
适用场景	频繁读取元素的场景	频繁插入和删除元素的场景

ArrayList扩容

当ArrayList中的元素数量达到当前数组的容量时，添加新元素会触发扩容

HashSet 的实现原理

HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为一个常量对象present，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，HashSet 不允许重复的值

HashSet与HashMap的区别

特性	HashMap	HashSet
接口实现	实现Map接口	实现Set接口
存储内容	存储键值对（Key-Value）	仅存储对象
添加元素方法	使用`put(K, V)`方法添加键值对	使用`add(E)`方法添加元素
哈希码计算	使用键（Key）计算哈希码	使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以`equals()`方法用来判断对象的相等性，如果两个对象不同的话，那么返回false
查找速度	相对较快，基于唯一键进行查找	相对较慢，基于对象进行查找
线程安全性	默认非线程安全，需使用`Collections.synchronizedMap()`或ConcurrentHashMap确保线程安全	默认非线程安全，需使用`Collections.synchronizedSet()`确保线程安全
适用场景	适用于需要快速通过键查找值的场景，如实现缓存、存储配置信息	适用于需要存储唯一元素且不关心顺序的场景，如实现集合操作、去重逻辑

HashMap的实现原理

数据结构：

HashMap 底层使用数组（主体）和链表（JDK8之前主要通过“拉链法”解决哈希冲突）在 JDK 8 之后也可能使用红黑树）来实现。

每个数组位置称为一个桶（bucket），每个桶存储一个链表或红黑树。

如果同一个桶中的元素数量超过阈值（通常为 8），链表（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）会转换成红黑树以提高性能。

哈希函数：

HashMap 通过键的 hashCode() 方法生成哈希值，并根据这个哈希值决定键值对在数组中的存储位置。

哈希值经过进一步处理（例如按位运算）以均匀分布到数组的每个位置，减少哈希冲突。

哈希冲突处理：

当多个键经过哈希函数计算后映射到同一个数组索引（即同一个桶）时，会发生哈希冲突。

HashMap 使用拉链法来解决冲突，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可（或在 JDK 8 之后的红黑树中）。

存储键值对：

当调用 put(K key, V value) 方法时，HashMap 计算键的哈希值并确定该键应该存储在哪个桶中。

如果桶中已经有一个或多个元素，HashMap 会遍历链表或树，以检查是否有相同的键存在。

如果找到相同的键，新的值会覆盖旧的值；否则，新的键值对会被添加到链表的末尾或树中。

扩容机制：

HashMap 的容量是动态的，当存储的键值对数量超过负载因子（默认值为 0.75）乘以数组长度时，HashMap 会自动扩容，将数组长度加倍。

扩容时，所有现有的键值对需要重新计算哈希并重新分配到新的桶中，这个过程称为 rehashing。

查询操作：

当调用 get(Object key) 方法时，HashMap 会根据键的 hashCode() 计算出哈希值，并找到对应的桶。

如果桶中有多个元素（即发生哈希冲突），HashMap 会遍历链表或树，逐一调用 equals() 方法比较键，找到匹配的键值对并返回对应的值。

HashMap多线程操作导致死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束

JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap

红黑树

红黑树的每个结点是黑色或者红色。当是不管怎么样他的根结点是黑色。

每个叶子结点（叶子结点代表终结、结尾的节点）也是黑色 [注意：这里叶子结点，是指为空(NIL或NULL)的叶子结点！]。

如果一个结点是红色的，则它的子结点必须是黑色的。每个结点到叶子结点NIL所经过的黑色结点的个数一样的。[确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的！]

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。因为添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转和变色，可以使这颗树重新成为红黑树，旋转和变色的目的是让树保持红黑树的特性。

任何类作为 Map 的 key须满足的条件

1、必须正确重写 hashCode() 和 equals() 方法

如果你想使用一个自定义类作为 Map 的 key，那么该类必须重写 hashCode() 和 equals() 方法。这是因为 Map 使用 hashCode() 来确定对象的存储位置，并使用 equals() 方法来判断两个键是否相等。

hashCode()：两个相等的对象必须返回相同的哈希码。

equals()：如果两个对象被认为是相等的（即 equals() 方法返回 true），那么它们的哈希码也必须相同。

2、不可变性

使用作 Map 的 key 的对象应该是不可变的（或在被用作 key 后不应改变）。如果在将对象作为 key 插入 Map 之后，对象的状态发生了变化，导致其 hashCode() 返回的值改变，这样可能导致对象在 Map 中“丢失”——因为它可能不再位于最初计算出的哈希桶中。

推荐做法：使用不可变对象作为 Map 的 key，例如字符串、基本数据类型的包装类（如 Integer、Float 等）或你定义的不可变类。

3、实现类示例

常见的 Map key 类型包括 String、Integer、Enum 等，它们都正确实现了 hashCode() 和equals() 方法。

如果你创建了一个自定义类作为 Map 的 key，请确保正确重写了 hashCode() 和 equals()。

HashMap和HashTable的区别

特性	HashMap	LinkedHashMap	Hashtable	TreeMap	ConcurrentHashMap
线程安全	否	否	是（所有方法通过 `synchronized` 修饰）	否	是（基于分段锁机制，支持高并发）
效率	高（无同步机制，单线程环境性能优越）	较高（无同步机制，且维护插入顺序）	低（受 `synchronized` 的影响）	较低（由于排序机制开销）	高（锁分段机制，减少锁竞争）
Null 键和 Null 值支持	允许 1 个 `null` 键，多个 `null` 值	允许 1 个 `null` 键，多个 `null` 值	不允许（抛出 `NullPointerException`）	不允许 `null` 键和 `null` 值	不允许 `null` 键和 `null` 值
键值对存储顺序	无序	按插入顺序（可按访问顺序排序）	无序	自然顺序（按键排序）	无序
底层数据结构	数组 + 链表 + 红黑树（JDK 1.8 之后）	数组 + 链表 + 红黑树	数组 + 链表	红黑树	数组 + 链表 + 红黑树（JDK 1.8 之后）
默认初始容量	16	16	11	无初始容量	16
扩容机制	每次扩容为原容量的 2 倍，创建时如果给定了容量初始值，会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证）	每次扩容为原容量的 2 倍	每次扩容为 `2n+1`	不适用	每次扩容为原容量的 2 倍
排序机制	无排序	插入顺序或访问顺序	无排序	按键的自然顺序或自定义排序	无排序
哈希冲突解决机制	JDK 1.8 之后链表长度 >8 时，转为红黑树	JDK 1.8 之后链表长度 >8 时，转为红黑树	使用链表	不适用（基于红黑树，无哈希冲突）	JDK 1.8 之后链表长度 >8 时，转为红黑树
推荐使用场景	单线程环境下的高效选择	需要按插入顺序或访问顺序遍历时	已淘汰，不建议使用	需要排序的场景	多线程环境下的高效选择

ConcurrentHashMap 和 Hashtable实现线程安全方式的区别

ConcurrentHashMap：在JDK1.7的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。）到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后对 synchronized锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；

Hashtable(同一把锁) ：使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

Collections.sort() 的两种使用方式

1、使用 Comparable 接口（默认排序）

如果列表中的元素实现了 Comparable 接口，Collections.sort() 会使用 Comparable.compareTo() 来比较元素。例如：String 类就实现了 Comparable<String>，因此字符串列表可以直接使用 Collections.sort() 进行排序。