集合框架（Collections）深度解析
本模块面试重点
- 集合体系结构：熟悉
Collection/Map两大体系，知道List、Set、Map及它们常见实现类的大致特点和使用场景。 - 常见实现类对比：
ArrayListvsLinkedList、HashMapvsHashtablevsConcurrentHashMap，增删改查的时间复杂度和线程安全差异。 - 典型坑点：
HashMap扩容/负载因子、遍历时修改集合导致的ConcurrentModificationException、Arrays.asList的不可变列表等。
❓ 面试官：Java 集合框架有哪些顶层接口？你能画一下大概的结构图吗？
频率：🔥🔥🔥🔥
💡 一句话总结（先抛结论）： Java 集合框架主要分为两大派系：Collection（单列集合） 和 Map（双列键值对集合）。它们之下又派生出了 List、Set 和具体的 HashMap 等实现类。
📝 核心脉络梳理：
- Collection（单列存取）
- List：有序、可重复、有索引。（代表：
ArrayList、LinkedList） - Set：无序、不可重复、无索引。（代表：
HashSet、TreeSet）
- List：有序、可重复、有索引。（代表：
- Map（键值对存取）
- 存储
Key-Value，其中 Key 不可重复，Value 可重复。（代表：HashMap、TreeMap、ConcurrentHashMap）
- 存储
❓ 面试官：ArrayList 和 LinkedList 有什么区别？平时开发中怎么选？
频率：🔥🔥🔥🔥🔥
💡 一句话总结（先抛结论）：ArrayList 底层是动态数组，适合多读少写（或尾部追加）的场景；LinkedList 底层是双向链表，适合频繁在头部或中间进行插入/删除的场景。实际开发中，99% 的情况都用 ArrayList。
📝 详细原理解析：
- 数据结构：
ArrayList：一块连续的内存空间。支持通过下标O(1)极速随机访问。但如果要在中间插入或删除元素，需要移动后面所有的元素，时间复杂度O(N)。LinkedList：内存不连续，靠指针连接。不支持随机访问，查第 N 个元素必须从头遍历O(N)。但在已知节点位置的情况下，插入和删除只需修改指针，非常快。
- 空间占用：
ArrayList会预留一定的容量空间（尾部可能有空闲），但总体紧凑。LinkedList每个节点都要额外存储两个指针（前驱和后继），消耗内存更大。
🌟 面试加分项（实战坑点）： 面试官常追问：“你说 LinkedList 插入快，那如果我在末尾追加 1 万个元素，谁快？” 绝杀回答： "依然是 ArrayList 快！ 很多人以为 LinkedList 插入一定快，其实是误区。LinkedList 每次 add 都要去堆内存里 new 一个 Node 对象，海量数据下会触发频繁的垃圾回收（GC），非常慢。而 ArrayList 只要没有触发扩容，尾部追加只是简单地给数组赋值，极其迅速。即使触发扩容（系统级的 System.arraycopy），整体性能依然秒杀 LinkedList。"
❓ 面试官：能详细讲讲 HashMap 的底层原理吗？（JDK 8 之后的结构）【中高级】
频率：🔥🔥🔥🔥🔥
💡 一句话总结（先抛结论）： JDK 8 中，HashMap 的底层数据结构是 “数组 + 链表 + 红黑树”。这种设计既保证了极快的通过哈希计算找桶的速度，又通过红黑树解决了极端情况下哈希冲突导致的链表过长、查询变慢的问题。
📝 详细原理解析：
- put(Key, Value) 核心流程：
- 第一步：对 Key 调用
hashCode()，并经过一次扰动函数（高低 16 位异或），算出最终的hash值。 - 第二步：根据
(n - 1) & hash算出在数组中的索引位置。 - 第三步：如果该位置为空，直接存入。
- 第四步：如果发生哈希冲突（该位置已经有元素了），则用
equals()判断 Key 是否一样。一样就覆盖 Value；不一样就在此节点后挂一个新节点（尾插法）。 - 第五步（树化）：如果当前链表长度大于等于 8，且数组总长度大于等于 64，就会把链表转化为红黑树，把
O(N)的查询时间优化为O(log N)。
- 第一步：对 Key 调用
- 扩容机制（Resize）：
- 默认初始容量是 16，加载因子是 0.75。
- 当
size > 16 * 0.75 = 12时，触发扩容，数组容量翻倍（变成 32）。 - 扩容时极其巧妙：因为容量是 2 的幂次方，原来在链表上的元素重新计算位置时，只有两种结果：要么留在原位置，要么移动到（原位置 + 旧容量）的位置。
🌟 面试加分项（连环追问）：
- 问：为什么加载因子是 0.75 而不是 1 或 0.5？ 答：这是时间和空间的折中。如果是 1，空间利用率高，但哈希冲突极其严重，链表会很长导致查询极慢；如果是 0.5，冲突少了，但内存浪费一半，且频繁触发扩容影响性能。0.75 是经过泊松分布概率计算得出的最优解。
- 问：为什么链表转红黑树的阈值是 8？ 答：根据泊松分布，在加载因子为 0.75 的理想哈希情况下，一个桶里挂 8 个节点的概率不到千万分之一。如果真的到了 8，说明哈希算法极差或者遭遇了恶意的哈希碰撞攻击，这时候才逼不得已转为红黑树保命（因为红黑树每个节点占空间比普通节点大一倍）。
❓ 面试官：HashMap 是线程安全的吗？多线程下会出什么问题？应该用什么代替？【中级】
频率：🔥🔥🔥🔥
💡 一句话总结（先抛结论）：HashMap 是绝对线程不安全的。在多线程并发 put 时，会导致数据覆盖丢失；如果是 JDK 7 版本，还会引发死循环（环形链表）导致 CPU 100%。必须用 ConcurrentHashMap 来代替。
📝 ConcurrentHashMap 怎么保证线程安全的？
- JDK 7：采用了 “分段锁（Segment）” 机制。把整个大数组切分成 16 个小数组（Segment）。每次加锁只锁一个小数组，其他小数组的读写不受影响。
- JDK 8 终极优化： 摒弃了臃肿的分段锁，直接采用和 HashMap 一样的 “数组+链表+红黑树” 结构。 线程安全靠的是
CAS（乐观锁） +synchronized（悲观锁）。 在put时：- 如果发现该桶的位置是空的，直接使用无锁的
CAS操作尝试把新节点塞进去。 - 如果发现桶里已经有元素了发生冲突，只使用
synchronized锁住这一个头节点（链表首节点或树根）。锁的粒度变得极其细小，并发度达到了理论最大值（有多少个桶，就允许多少个线程同时并发写）。
- 如果发现该桶的位置是空的，直接使用无锁的