Java 学习网站

主题

集合框架入门 ​

Java 初级 · 进阶基础

数组长度固定，难以应对「数量不确定」的场景。Java 集合框架提供了一套可动态伸缩、类型安全的容器。本节不只列 API，更深入 ArrayList 如何扩容（数组拷贝）、LinkedList 节点如何串联、HashMap 底层数组+链表/红黑树如何工作——这些是面试与性能调优的核心，也是集合「为什么这么快/这么慢」的底层答案。

一、集合框架总览 ​

集合框架两大根接口：

  • List：有序、可重复，按索引访问。常用 ArrayList（数组）、LinkedList（链表）。
  • Set：不可重复。常用 HashSet（哈希）、TreeSet（红黑树，自动排序）。
  • Map：键值对，key 不可重复。常用 HashMap、TreeMap、LinkedHashMap。

二、ArrayList：动态数组与扩容拷贝 ​

ArrayList 底层是一个普通 Object[] 数组。它「可变长」的秘密是：数组不够就换更大的数组，把旧元素整体拷贝过去。

扩容机制（JDK 8/21） ​

  • 默认构造 new ArrayList<>() 时，底层数组初始是空数组（懒初始化），首次 add 才扩到容量 10。
  • 当 size == 容量 时触发扩容：新容量 = 旧容量 + 旧容量>>1，即约 1.5 倍。
  • 扩容靠 Arrays.copyOf（底层 System.arraycopy，native 实现，批量内存拷贝）把旧数组内容搬到新数组。
java
// 伪代码：add 时的扩容逻辑
if (size == elementData.length) {
    int newCap = oldCap + (oldCap >> 1);   // 1.5 倍
    elementData = Arrays.copyOf(elementData, newCap);  // 拷贝
}
elementData[size++] = e;

启示 ​

  • 扩容有代价（要拷贝全部元素）。已知大概数量时，用 new ArrayList<>(initialCapacity) 指定初始容量，避免反复扩容。例如要放 1000 条，new ArrayList<>(1000) 一次到位。
  • 随机访问 get(i) 是 O(1)（直接下标）；但中间插入/删除要搬移后续元素，平均 O(n)，频繁这种操作不适合 ArrayList。

三、LinkedList：双向链表节点 ​

LinkedList 每个元素是一个节点（Node），节点里存「数据 + 前驱指针 + 后继指针」：

java
// JDK 中节点结构（示意）
class Node<E> {
    E item;          // 数据
    Node<E> next;    // 后继
    Node<E> prev;    // 前驱
}
  • 头尾插入/删除是 O(1)（只改几个指针），这是它对比 ArrayList 的优势场景。
  • 但按索引访问要沿链表从头/尾走，平均 O(n)，远慢于 ArrayList 的 O(1)。
  • 现代 JVM 下，链表节点分散在堆里、缓存不友好，ArrayList 的连续内存反而更快。所以默认用 ArrayList，只有在确实频繁头插/头删、且数据量大时才考虑 LinkedList。

四、HashSet / HashMap：哈希桶与冲突 ​

HashSet 内部就是用一个 HashMap（元素作 key，value 是个固定占位对象）。所以弄懂 HashMap 就懂了 HashSet。

底层结构：数组 + 链表 + 红黑树 ​

HashMap 底层是一个桶数组 Node[] table。每个元素通过 key.hashCode() 算哈希，再映射到某个桶下标：

java
// 定位桶下标（简化）：容量 n 为 2 的幂时
int index = (n - 1) & hash;   // 等价于 hash % n，但位运算更快
  • 哈希冲突：不同 key 算到同一桶，就在该桶形成链表（JDK 7 及之前纯链表）。
  • 树化（JDK 8 优化）：当某桶链表长度 ≥ 8 且数组容量 ≥ 64 时，链表转成红黑树，查找从 O(n) 降到 O(log n)；当树节点 ≤ 6 时退化回链表（防止频繁转换抖动）。

put / get 流程 ​

  • 定位桶靠 hashCode（快）；桶内确认靠 equals（准）。这正是「equals/hashCode 契约」的意义（见常用类一节）。
  • 负载因子（load factor）默认 0.75：当 元素数 > 容量 × 0.75 时，整个数组扩容为 2 倍并重新哈希（rehash）。0.75 是「空间」与「冲突概率」的折中：太小浪费空间，太大冲突多、链表长。

把可变对象当 HashMap 的 key

若 key 对象放进 Map 后，其内容（参与 hashCode 的字段）被修改，hashCode 就变了，原来算出的桶再也找不到了——get(key) 返回 null，元素「丢了但还在内存里」。HashMap 的 key 必须不可变（用 String、基本类型包装类等）。

五、TreeMap / TreeSet：红黑树有序 ​

TreeMap 用红黑树（一种自平衡二叉搜索树）存键值，按 key 的「自然顺序」或 Comparator 排序。put/get/remove 都是 O(log n)，且能轻松拿「区间」「前驱/后继」。代价是不如 HashMap 的 O(1) 平均查找。需要排序/范围查询用 Tree，只求快速查找用 HashMap*。

六、常见误区与注意点 ​

WARNING

  • ArrayList/LinkedList 乱选：随机访问多用 ArrayList；只有频繁头插/删才考虑 LinkedList（且多数情况 ArrayList 仍更快）。
  • 遍历 Map 用 keySet 再 get：多一次哈希查找；直接遍历 entrySet 拿到键值对最高效。
  • 把可变对象当 HashMap 的 key：key 哈希变化后永远找不到，key 必须不可变。
  • ConcurrentModificationException：for-each 遍历时直接 list.remove(x) 会报错（迭代器 fail-fast 检测），用迭代器 it.remove() 或 removeIf。
  • new ArrayList<>(100) 是容量不是大小：size() 仍是 0，它只是预留空间，不是预填 100 个元素。

七、最佳实践 ​

  1. 默认用 ArrayList（综合性能最好）和 HashMap（最常用）。
  2. 已知元素数量时指定初始容量，避免反复扩容拷贝。
  3. 需要去重用 HashSet；需要排序/范围用 TreeSet/TreeMap。
  4. 变量声明为接口类型（List/Map），面向接口编程，便于换实现。
  5. 遍历并删除用 list.removeIf(...) 或迭代器，避免并发修改异常。
  6. HashMap 的 key 用不可变类型；自定义 key 务必正确实现 equals/hashCode。

📚 官方文档与参考资料 ​

✏️ 练习与自测 ​

  1. 用 ArrayList 存入 5 个字符串，用 for-each 打印，并用 removeIf 删除其中一个；思考若用 for-i 正向遍历时 remove 会有什么下标错位问题。
  2. 用 HashSet 统计一个 List 中有多少不重复的单词；若把其中字符串改为可变对象（如自定义类 equals 看名字但名字可改）当 key，演示「改了 key 后 contains 找不到」的现象。
  3. 用 HashMap 实现「姓名→分数」登记本，分别用 keySet 遍历和 entrySet 遍历，体会后者少一次 get 查找。
  4. 解释：向一个初始容量为 0 的 ArrayList 连续 add 1000 次，底层数组容量会经历怎样的扩张序列（10 → 15 → 22 → ... → ≥1000）？为什么指定 new ArrayList<>(1000) 更好？

本节小结

集合分 Collection（List 有序可重复、Set 不可重复）和 Map（键值对）。ArrayList 底层数组，满了按 1.5 倍扩容并 System.arraycopy 整体拷贝，随机访问 O(1)、中间增删 O(n)，指定初始容量可避免反复扩容；LinkedList 是双向节点链表，头尾增删 O(1) 但随机访问 O(n)，多数场景不如 ArrayList。HashMap 底层桶数组 + 链表/红黑树：(n-1)&hash 定位桶，冲突挂链表，链表≥8 且容量≥64 转红黑树（查找 O(log n)），负载因子 0.75 触发 2 倍扩容 rehash；key 必须不可变且正确实现 equals/hashCode。有序/范围用 Tree*，快速查找用 HashMap。