集合框架与泛型

集合框架与泛型

目标：理解数组为什么装不下「动态增长」的数据；掌握集合框架两大体系——Collection（List/Set/Queue）与 Map；会用 ArrayList / HashSet / HashMap 完成增、删、查、遍历；理解泛型带来的类型安全与类型擦除机制。

一、为什么需要集合：数组的局限

• 长度固定：int[] a = new int[10]; 声明后大小就不能再变；要「装不下就扩容」只能自己新建更大的数组、逐个拷贝——繁琐且容易出错；
• 操作全靠手写：数组没有 add() / remove() / contains() / sort()，插入一个元素要手动移动后面所有元素，查找要自己写循环；
• 集合 = 自动管理的一组对象：java.util 包里的集合类替你管好扩容、增删查改、排序与遍历——你只管放东西、取东西。

一句话：数组是「定长容器」，集合是「动态容器」。数据量事先不知道、又要频繁增删时，用集合。

两者各有所长——点下面任意维度行，看具体表现与点评：

int[] scores = new int[3];   // 长度固定为 3
scores[0] = 88;
scores[1] = 76;
scores[2] = 95;
// 想再加第 4 个？
// 只能新建 int[4]，把旧值逐个拷过去……

List<Integer> scores = new ArrayList<>();
scores.add(88);
scores.add(76);
scores.add(95);
scores.add(92);                          // 直接加！自动扩容
System.out.println(scores.contains(76));  // true

二、集合框架继承树：两大体系

Java 集合分两大体系：

• Collection<E>（单元素集合）：装一组对象，统一提供 add / remove / contains / size / iterator；
  • List：有序、允许重复——按下标访问；
  • Set：无序、不重复——自动去重；
  • Queue：先进先出（FIFO）——排队语义；
• Map<K,V>（键值对映射）：每个 key 对应一个 value，key 唯一、value 可重复。注意：Map 不属于 Collection 体系（高频考点），它有自己的 put / get / remove / keySet / entrySet 一套方法。

下面的实验树把两大体系的常用接口与实现类都画出来了——点任意节点看它的族、继承链与关键方法，点上方标签可只看一族：

三、常用操作：增、删、查、遍历

三大最常用的集合各写一遍核心操作（ArrayList / HashSet / HashMap）：

// List —— ArrayList：按下标存取
List<String> names = new ArrayList<>();
names.add("Tom");              // 尾部添加
names.add("Jerry");
names.remove("Tom");           // 按值删除
System.out.println(names.get(0));   // 按下标取 → "Jerry"

// Set —— HashSet：自动去重，无序
Set<Integer> nums = new HashSet<>();
nums.add(1);
nums.add(2);
nums.add(2);                  // 重复元素被忽略（add 返回 false）
System.out.println(nums.size());    // 2

// Map —— HashMap：key→value
Map<String, Integer> scores = new HashMap<>();
scores.put("Tom", 88);
scores.put("Jerry", 76);
System.out.println(scores.get("Tom"));   // 按 key 取 value → 88

遍历对所有集合都统一——增强 for 循环（底层是 iterator()）：

for (String n : names) {
    System.out.println(n);
}
// Map 遍历用 entrySet()，一次拿到 key 和 value
for (Map.Entry<String, Integer> e : scores.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

HashMap 的底层：桶、链表与红黑树。 put(key, value) 并不是「随便放」——它先算 key.hashCode()，再对桶数取模 hashCode() % n 决定落进哪个桶；同一个桶里再来一个 key（哈希冲突）就挂成链表，当一条链长到 ≥8 时转成红黑树，把最坏查找从 O(n) 拉回 O(log n)。下面插入一组 key，看它们如何按 hashCode() % n 落桶、冲突时链表如何生长、以及「链长 ≥8 转红黑树」的阈值：

四、泛型：编译期类型安全

不用泛型（原始类型）——List 里什么都能放，取出来是 Object，必须强转；转错类型运行时才炸：

List list = new ArrayList();
list.add("字符串");
list.add(new Integer(10));
Date d = (Date) list.get(0);   // 编译通过！运行到这一行抛 ClassCastException

用泛型——List<String> 在声明时就把元素类型定死：只能放 String，取出来直接是 String，不用强转：

List<String> list = new ArrayList<String>();
list.add("Tom");
// list.add(123);             // 编译错误：int 不能放进 List<String>
String s = list.get(0);       // 无需强转，类型安全

类型擦除（type erasure）：泛型只存在于编译期——javac 编译后，字节码里的 List<String> 会被「擦除」成裸的 List，元素按 Object 处理；编译器在取出处自动插入强转。所以：

• 运行时无法区分 List<String> 和 List<Integer>（它们是同一个类）；
• 泛型检查只发生在编译期——这正是「类型安全」的来源，也是它的边界。

下面逐行对照「源码 vs 擦除后字节码」，并走查原始类型（raw type）为何危险：

List<String> strings = new ArrayList<>();
strings.add("Tom");

五、选型建议

经验法则：默认用 ArrayList + HashMap；有「去重」需求换 HashSet，有「排序」需求换 TreeSet / TreeMap。

六、总结

• 两大体系：Collection（List 有序可重复 / Set 无序不重复 / Queue 先进先出）+ Map（键值对，不属于 Collection）；
• 三大主力：ArrayList（按下标）、HashSet（去重）、HashMap（key→value），都基于哈希/数组、O(1) 操作；
• 泛型在编译期保证类型安全（List<String> 只能放 String、取出免强转）；类型擦除让运行时统一为裸类型——检查只在编译期。

思考题

1. Map 为什么不继承 Collection？两者在数据组织上有什么本质区别？
2. 什么场景下选 LinkedList 而不是 ArrayList？两者的 get(i) 代价各是多少？
3. 类型擦除后，运行时把 Integer 放进 List<String> 会发生什么？（提示：泛型检查只发生在编译期）

学习小测验