📦 集合框架

1. Java 集合框架的整体结构

集合分两大体系：

• Collection（单列集合）：
  • List：有序、可重复 — ArrayList / LinkedList / Vector
  • Set：无序（多数实现）、不可重复 — HashSet（底层 HashMap）/ LinkedHashSet / TreeSet（底层 TreeMap）
  • Queue/Deque：队列，FIFO — ArrayDeque / PriorityQueue（二叉堆）
• Map（双列集合，键值对）：HashMap / LinkedHashMap / TreeMap / ConcurrentHashMap / Hashtable

2. ArrayList 和 LinkedList 的区别？

ArrayList：底层动态数组（Object[] elementData）。

• 随机访问 O(1)，get(i) 直接按下标寻址
• 尾部增删 O(1)（均摊）；中间插入/删除 O(n)（元素搬移）
• 扩容：默认容量 10，每次扩容 1.5 倍（old + old >> 1），拷贝数组，所以预先指定容量可避免扩容

LinkedList：底层双向链表（Node prev/data/next，且实现 Deque）。

• 随机访问 O(n)（从头部或尾部折半找）
• 任意位置插入/删除 O(1)（找到节点后只需改指针）——但找节点本身 O(n)
• 占用内存更大：每个元素多存两个指针

结论：99% 场景用 ArrayList（局部性原理，缓存友好）。LinkedList 的"插入快"在随机插入时并不成立，因为要先遍历找位置。

3. HashMap 底层原理？（面试必问中的必问）

数据结构（JDK8）：数组 + 链表 + 红黑树。数组默认容量 16，每个槽位是链表头，链表长度 >= 8 且数组长度 >= 64 时转红黑树。

put 流程：

1. 计算 key 的 hash：h = key.hashCode() ^ (h >>> 16)（高 16 位与低 16 位异或，让高位也参与寻址，降低碰撞）
2. 定位桶：index = (n - 1) & hash（等价于 hash % n，因为 n 是 2 的幂）
3. 桶为空 → 直接放；不为空 → 遍历链表比较 equals；key 已存在 → 覆盖 value；否则尾插法（JDK7 是头插，会形成死链）
4. 链表长度达到 8 → 转红黑树（前提数组长度 ≥ 64，否则先扩容）
5. size 超过 阈值 = 容量 × 加载因子 0.75 → 扩容 2 倍并 rehash 重排

为什么 JDK7 → JDK8 变化大：

• 头插法 → 尾插法：修复并发下扩容成环死循环的问题（但 HashMap 仍非线程安全）
• 链表 → 链表+红黑树：优化哈希碰撞严重时的查找性能 O(n) → O(log n)
• 扩容时利用"高位是否有 1"判断新位置（原位置 or 原位置+oldCap），无需重新计算 hash

// 定位桶：hash % n 可用位运算替代，前提 n 是 2 的幂
int index = (n - 1) & hash;

// n=16:   n-1 = 0000 1111（二进制）
// 结果只保留 hash 的低 4 位 → 均匀分布在 0~15
// 若 n=15（非 2 的幂）: n-1 = 0000 1110，最后一位恒为 0
// → 奇数下标永远空着，浪费一半桶且碰撞加剧

4. ConcurrentHashMap 如何保证线程安全？

JDK7：分段锁（Segment 数组）。默认 16 个 Segment，每个 Segment 是一把小锁（继承 ReentrantLock），锁粒度是"段"。并发度 = 段数。

JDK8：抛弃分段锁，改为 CAS + synchronized 锁桶头节点：

• put 时桶为空 → CAS 无锁插入（自旋重试）
• 桶不为空 → synchronized 锁住桶的头节点再操作（锁粒度细化到单个桶）
• 并发度大幅提升：不同桶互不阻塞；读操作完全无锁（volatile 保证可见性）
• size() 用累加器（CounterCell）分散计数，避免全局计数竞争

JDK8 的改进思路：锁粒度从"段"细化为"桶"，且空桶用 CAS 避免加锁开销，读读、读写并行度都更高。

5. TreeMap 和 LinkedHashMap 的特点？

TreeMap：底层红黑树，键有序。支持自然排序（Comparable）和自定义排序（Comparator）。操作 O(log n)。用于需要按 key 排序或范围查询的场景（如区间统计）。

LinkedHashMap：HashMap + 双向链表维护插入顺序。构造时可开启 accessOrder=true，链表按"访问顺序"维护 → 被访问的节点移到尾部。**这正好是实现 LRU 缓存的底层机制**（LinkedHashMap 设计目的之一）。

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LRUCache(int capacity) {
        super(capacity, 0.75f, true);   // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > capacity;   // 超过容量时淘汰最久未访问的
    }
}

6. 什么是 fail-fast 和 fail-safe？

fail-fast（快速失败）：迭代器遍历时若集合被结构性修改（增/删，不包括 set 修改值），立即抛 ConcurrentModificationException。实现原理：迭代器持有 modCount（修改次数），每次 next() 检查 modCount 是否被改动。

fail-safe（安全失败）：遍历的是拷贝，修改原集合不影响遍历，不抛异常。代表：CopyOnWriteArrayList / ConcurrentHashMap 的迭代器。代价是遍历期间读不到最新数据。

List<String> list = new ArrayList<>();
list.add("a"); list.add("b"); list.add("c");

// ❌ 抛 ConcurrentModificationException
for (String s : list) {
    if (s.equals("b")) list.remove(s);
}

// ✅ 正确：使用迭代器的 remove
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();
}