集合

一、为什么需要集合框架？

数组是 Java 唯一的原生容器，但数组长度固定、类型单一、没有现成的增删改查方法。集合框架提供了可变长度、丰富数据结构、高性能算法，是 Java 最常用的 API 之一。

二、集合框架全景

Collection
├── List（有序、可重复）
│   ├── ArrayList（数组实现，查快改慢）
│   ├── LinkedList（链表实现，增删快）
│   └── Vector（线程安全，已淘汰）
│       └── Stack（LIFO）
├── Set（无序、不可重复）
│   ├── HashSet（HashMap 实现，O(1)）
│   │   └── LinkedHashSet（链表维护插入顺序）
│   ├── TreeSet（红黑树，O(log n)，有序）
│   └── EnumSet（位向量，枚举专用）
└── Queue（队列）
    ├── PriorityQueue（二叉堆，优先级队列）
    └── Deque（双端队列）
        ├── ArrayDeque（循环数组）
        └── LinkedList（同时实现了 List 和 Deque）

Map（键值对，独立接口）
├── HashMap（数组+链表+红黑树，O(1)）
│   └── LinkedHashMap（链表维护插入顺序/访问顺序）
├── TreeMap（红黑树，O(log n)，键有序）
├── Hashtable（线程安全，已淘汰）
└── ConcurrentHashMap（分段锁/CAS，高并发场景）

三、ArrayList vs LinkedList

3.1 底层原理

ArrayList： 底层是 Object[] 数组，默认容量 10，每次扩容 1.5 倍。通过 System.arraycopy()（native 方法）进行元素移动。

// 扩容核心逻辑（简化）
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5 倍
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList： 底层是双向链表，每个节点持有前后指针。插入/删除只需修改指针，不需要移动元素。

3.2 为什么 ArrayList 查询 O(1)？

原理： 数组元素在内存中连续存储。访问 arr[i] 时，JVM 计算 首地址 + i × 元素大小，直接定位。这是 CPU 缓存友好的——连续内存使得 CPU 可以预取相邻元素到缓存行。

3.3 选择指南

场景	选择	原因
频繁随机访问	ArrayList	O(1) 查询
频繁头尾增删	LinkedList	O(1) 增删，无需移动
频繁中间增删	ArrayList	数据量大时 LinkedList 遍历慢，抵消了增删优势
遍历	ArrayList	内存连续，CPU 缓存友好
内存敏感	ArrayList	LinkedList 每个节点额外存储前后指针

四、HashMap

4.1 底层原理

JDK 8 中 HashMap 由数组 + 链表 + 红黑树组成：

数组（Node[] table）
  │
  ├── [0] → Node(hash, key, value, next) → Node → Node（链表）
  ├── [1] → null
  ├── [2] → TreeNode（红黑树，链表长度≥8 且 table≥64 时树化）
  ├── ...
  └── [15] → Node → Node

put 流程：

1. 计算 key 的 hashCode，再通过 (n-1) & hash 计算桶下标
2. 桶为空 → 直接放入
3. 桶不为空 → 遍历链表/树，equals 比较
4. 找到相同 key → 覆盖 value
5. 没找到 → 尾插到链表/树
6. 链表长度 ≥ 8 且 table 长度 ≥ 64 → 树化（链表转红黑树）
7. size > threshold → 扩容

4.2 为什么链表长度 ≥ 8 才树化？

原理： 根据泊松分布，在负载因子 0.75 且 hash 均匀的条件下，链表长度达到 8 的概率约为 0.00000006（千万分之六）。树化是处理极端情况（hash 碰撞严重）的兜底方案，且树化后退化为链表（长度 ≤ 6）以减少树维护开销。

4.3 扩容机制

为什么扩容？ 负载因子 0.75 是空间和时间的平衡点。太高 → 碰撞严重 → 链表变长 → 查询变慢；太低 → 频繁扩容 → 浪费内存。

扩容时容量翻倍，每个元素重新计算桶下标（oldCap & hash == 0 则下标不变，否则下标 = 原下标 + oldCap）。JDK 8 的优化避免了 JDK 7 中头插法导致的死循环问题。

4.4 hashCode 与 equals 的契约

为什么重写 equals 必须重写 hashCode？

// 只重写 equals 不重写 hashCode 的 Bug
class User {
    String name;
    @Override public boolean equals(Object o) { return name.equals(((User)o).name); }
}
Map<User, String> map = new HashMap<>();
map.put(new User("张三"), "北京");
map.get(new User("张三"));  // null！因为 hashCode 不同，定位到了不同桶

HashMap 的工作流程：hashCode 定位桶 → equals 在桶内精确匹配。equals 相等但 hashCode 不同 → 放在不同桶 → get 找不到。

五、ConcurrentHashMap

5.1 为什么不用 Hashtable？

Hashtable 用 synchronized 锁住整个表，同一时间只有一个线程能操作，并发度极低。

5.2 JDK 7 vs JDK 8 的实现演进

JDK 7（分段锁 Segment）： 默认 16 个 Segment，每个 Segment 独立加锁。写操作只锁相关 Segment，读操作不加锁（volatile 保证可见性）。并发度 = Segment 数量。

JDK 8（CAS + synchronized）： 抛弃 Segment，直接用 Node 数组 + CAS + synchronized。锁粒度降到单个桶（bin）级别：

• 桶为空 → CAS 写入，无锁
• 桶不为空 → synchronized 锁住桶的头节点
• 扩容时支持多线程并发扩容（transferIndex 分配迁移区间）

为什么 JDK 8 改用了 synchronized？ synchronized 在 JDK 6+ 后经过了大量优化（偏向锁、轻量级锁、锁升级），性能已经不输 ReentrantLock。且粒度更细、代码更简洁。

六、TreeMap vs LinkedHashMap

	TreeMap	LinkedHashMap
数据结构	红黑树	HashMap + 双向链表
有序性	按 key 的自然顺序或 Comparator	插入顺序或访问顺序（LRU）
时间复杂度	O(log n)	O(1)
适用场景	需要排序的 key	需要保持顺序，LRU 缓存

LinkedHashMap 实现 LRU 缓存：

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

    public 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;  // 超过容量时自动删除最老的
    }
}

七、fail-fast 机制

原理： 集合内部维护一个 modCount 计数器，每次结构性修改（增/删）都会自增。迭代器创建时记录 expectedModCount = modCount，每次 next() 前检查两者是否相等，不等则抛出 ConcurrentModificationException。

// 反例：迭代时删除，触发 fail-fast
for (String s : list) {
    if (s.equals("a")) list.remove(s);  // 抛出 ConcurrentModificationException
}

// 正例：用 Iterator 的 remove
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("a")) it.remove();  // 安全
}

八、面试要点

Q：HashMap 的底层原理？

数组 + 链表 + 红黑树。通过 hashCode 定位桶，桶内用链表或红黑树解决冲突。链表长度 ≥ 8 且 table ≥ 64 时树化，长度 ≤ 6 时退化为链表。负载因子 0.75，容量翻倍扩容。

Q：HashMap 和 ConcurrentHashMap 的区别？

HashMap 线程不安全，多线程 put 可能死循环（JDK 7）或数据丢失；ConcurrentHashMap 线程安全，JDK 7 用分段锁，JDK 8 用 CAS + synchronized 锁住单个桶，并发度更高。

Q：ArrayList 和 LinkedList 的区别？

ArrayList 底层是数组，O(1) 查询，增删需要移动元素（O(n)），内存连续；LinkedList 底层是双向链表，O(1) 头尾增删，查询需要遍历（O(n)），额外内存开销大。

Q：HashSet 底层是什么？

HashSet 底层是 HashMap，元素作为 key 存入，value 是一个固定的 Object 常量（PRESENT）。add() 调用 map.put()，contains() 调用 map.containsKey()。