📊 集合容器面试综述

在Java后端开发的面试中，集合容器几乎是必问的板块。它不仅是Java语言的核心组成部分，更是考察候选人对数据结构、算法复杂度、内存管理以及多线程并发控制能力的试金石。面试官通常不会只问“ArrayList和LinkedList的区别”，而是会层层递进，从底层数组实现问到扩容机制，再深入到红黑树转换条件及并发安全场景。

1. 数据结构基础

数组 vs 链表。理解连续内存与离散内存的优劣，以及它们在随机访问和插入删除操作上的时间复杂度差异（O(1) vs O(n)）。

2. 哈希算法原理

HashMap的核心在于哈希表。理解hashCode()与equals()的契约，以及如何通过扰动函数减少哈希冲突。

3. 并发安全控制

从Vector到CopyOnWriteArrayList，再到ConcurrentHashMap，理解锁机制的演变：互斥锁、分段锁到CAS+synchronized。

📝 List集合：ArrayList与LinkedList深度剖析

2.1 ArrayList 源码解析

ArrayList是基于动态数组实现的列表。其核心特性是支持快速的随机访问，但在中间位置插入或删除元素时效率较低，因为需要移动后续所有元素。

扩容机制详解

默认情况下，ArrayList的初始容量为10。当添加元素超过当前容量时，会触发扩容。扩容策略为：newCapacity = oldCapacity + (oldCapacity >> 1)，即扩容为原来的1.5倍。扩容过程涉及数组拷贝（System.arraycopy），这是一个相对昂贵的操作。因此，在已知数据量大小的场景下，建议指定初始容量以避免频繁扩容。

为什么ArrayList查询快，增删慢？

查询快：底层是数组，通过索引直接计算内存地址，时间复杂度为O(1)。
增删慢：在中间插入或删除元素时，需要调用System.arraycopy()移动大量元素，时间复杂度为O(n)。

2.2 LinkedList 源码解析

LinkedList是基于双向链表实现的。每个节点（Node）包含前驱指针、后继指针和数据域。它在头部和尾部插入/删除元素时效率极高（O(1)），但随机访问效率低（O(n)），因为必须从头或尾遍历。

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	快 (O(1))	慢 (O(n))
头部/尾部增删	慢 (需移动元素)	快 (O(1))
内存占用	较低 (仅存储数据)	较高 (存储前后指针)
线程安全	不安全	不安全

🗺️ Map集合：HashMap与Hashtable的博弈

HashMap核心原理

Hashtable vs HashMap

红黑树转换

1. 存储结构

JDK 1.8之前的HashMap由数组+链表组成。JDK 1.8之后，引入了红黑树。当链表长度超过8且数组长度超过64时，链表会转换为红黑树，将查找时间复杂度从O(n)降低到O(log n)。

2. 哈希冲突解决

HashMap采用链地址法解决冲突。即数组的每个桶中存储一个链表（或红黑树）。当两个不同的Key计算出相同的哈希值（哈希碰撞）时，它们会被存储在同一个桶的链表中。

3. put() 方法流程

判断键值对数组table是否为空或长度为0，若是则初始化。
计算key的hash值，确定在数组中的索引位置i。
若table[i]为空，直接新建节点放入。
若table[i]不为空，判断首节点是否与待插入节点key相同，若是则替换value。
若为首节点是树节点，则调用树插入方法。
若为链表节点，则遍历链表。若key存在则替换value；若不存在则插入链表尾部。
插入后检查链表长度是否>=8，若是且数组长度>=64，则链表转红黑树。
检查元素总数是否超过阈值，若是则扩容。

主要区别对比

线程安全：Hashtable是线程安全的（方法 synchronized 修饰），HashMap是非线程安全的。
Null值支持：Hashtable不允许key或value为null，否则抛出NullPointerException；HashMap允许一个key为null，多个value为null。
哈希算法：Hashtable直接使用key的hashCode()；HashMap会对key的hashCode()进行扰动计算（high bits），以减少哈希冲突。
迭代器：Hashtable的Enumeration是fail-fast的；HashMap的Iterator也是fail-fast的，但行为略有不同。

注意：在实际开发中，如果需要同步的Map，通常推荐使用ConcurrentHashMap，而不是Hashtable，因为Hashtable的锁粒度太粗，性能较差。

为什么选择红黑树？

红黑树是一种自平衡二叉查找树，它保证了最坏情况下的时间复杂度为O(log n)。相比链表，它在数据量大时查找效率显著提升。相比AVL树，红黑树在插入和删除时的旋转操作较少，更适合频繁增删的场景。

转换阈值

链表转红黑树的阈值是8，红黑树转链表的阈值是6。为什么不是7或9？这是泊松分布统计的结果。在哈希函数均匀的情况下，链表长度达到8的概率极低（约千万分之一）。设置阈值6是为了防止在哈希冲突严重时，频繁地在链表和树之间切换，造成性能损耗。

🔒 并发容器：ConcurrentHashMap 深度解析

3.1 演进之路

JDK 1.7

分段锁 (Segment)

ConcurrentHashMap由Segment数组和HashEntry数组组成。Segment继承了ReentrantLock，充当锁的角色。每个Segment保护一个HashEntry数组。线程访问数据时，先锁定对应的Segment，实现了锁粒度细化，提高了并发度。

JDK 1.8

CAS + synchronized

摒弃了Segment，采用Node数组+链表/红黑树结构。锁粒度进一步细化到每个链表/树的头节点。使用CAS（Compare And Swap）进行无锁更新，若CAS失败则使用synchronized锁住头节点。这种设计在并发竞争不激烈时，CAS操作几乎无开销，性能大幅提升。

3.2 核心特性

线程安全：所有操作都是线程安全的。
高性能：通过细粒度锁和CAS机制，支持高并发读写。
弱一致性迭代器：Iterator在构建时不会抛出ConcurrentModificationException，但可能反映或不反映迭代器创建后的所有修改。
空值不支持：Key和Value都不能为null。

💡 集合框架的设计模式与最佳实践

1. 迭代器模式 (Iterator)

Java集合框架广泛使用了迭代器模式。通过iterator()方法返回一个Iterator对象，屏蔽了底层集合的具体实现细节（是数组还是链表），使得客户端代码可以统一的方式遍历集合。

2. 快速失败 (Fail-Fast)

大多数集合类（如ArrayList, HashMap）的迭代器都是fail-fast的。如果在迭代过程中检测到结构被修改（如add/remove元素），会抛出ConcurrentModificationException。这是通过modCount字段实现的。在单线程环境下，这有助于尽早发现代码错误；在多线程环境下，应使用并发容器或手动同步。

3. 集合工具类 Collections

Collections提供了大量静态方法，如sort(), reverse(), shuffle(), synchronizedXxx()等，极大地简化了集合操作。特别是synchronizedXxx()方法，可以将非线程安全的集合包装成线程安全的视图。

❓ 网友还关心：高频面试问答 (FAQ)

以下是网民在搜索“集合容器面试真题”时最关注的周边问题及深度解答：

Q1: 为什么HashMap的负载因子默认是0.75？

负载因子（load factor）决定了哈希表的满度。0.75是空间和时间成本的一个折中。如果负载因子太大（如1.0），虽然空间利用率高，但哈希冲突概率增加，链表/树变长，查找效率下降。如果负载因子太小（如0.5），虽然冲突少，但空间浪费严重，频繁扩容。0.75在泊松分布下，能在保证较低冲突率的同时，保持较高的空间利用率。

Q2: ArrayList和Vector的区别？

Vector是早期的线程安全集合，所有方法都加了synchronized关键字，性能较差。ArrayList是非线程安全的，性能高。在现代Java开发中，如果需要线程安全的List，推荐使用CopyOnWriteArrayList（适用于读多写少场景）或Collections.synchronizedList()。

Q3: 如何遍历HashMap并删除元素？

直接在使用for-each循环遍历HashMap时调用remove()会导致ConcurrentModificationException。正确做法是使用Iterator的remove()方法，或者在Java 8中使用Map.forEach()配合removeIf()，或者在遍历过程中收集需要删除的Key，遍历结束后统一删除。

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    if (entry.getKey().equals("target")) {
        iterator.remove(); // 安全删除
    }
}

Q4: ConcurrentHashMap如何保证可见性？

在JDK 1.8中，Node节点的value和next字段都被volatile修饰。这保证了当一个线程修改了value或next指针时，其他线程能立即看到最新值。同时，synchronized块内的操作也遵循Java内存模型的happens-before原则。