03-集合框架（Collection / List / Set / Map）

对应原始资料：JavaSE进阶_day04~day06

一、为什么要有集合

数组长度固定、类型单一、增删麻烦。集合提供动态长度、丰富 API、各种数据结构。

二、集合体系图

Collection（单列）
   ├── List（有序、有索引、可重复）
   │     ├── ArrayList      数组实现，查询快，增删慢
   │     ├── LinkedList     链表实现，查询慢，增删快
   │     └── Vector        旧版线程安全（基本不用）
   └── Set（无索引、不可重复）
         ├── HashSet        哈希表，无序（基于 hashCode + equals）
         ├── LinkedHashSet  哈希表 + 链表，存取顺序一致
         └── TreeSet        红黑树，自动排序

Map（双列，key-value）
   ├── HashMap             哈希表
   ├── LinkedHashMap       哈希表 + 链表，有序
   ├── TreeMap             红黑树，按 key 排序
   └── Hashtable           旧版线程安全（基本不用）

三、Collection 通用方法

java

boolean add(E e);
boolean remove(Object o);
boolean contains(Object o);
boolean isEmpty();
int size();
void clear();
Object[] toArray();       // 集合转数组
Iterator<E> iterator();   // 迭代器

示例：左边写 Collection 接口，右边随便换实现，代码不用改

java

Collection<String> c = new ArrayList<>();   // 换成 LinkedList 也一样
c.add("java"); c.add("python"); c.add("java");
c.contains("python");   // true
c.remove("python");     // true，remove 返回 boolean
c.size();               // 2（"java" 加了两次）
Object[] arr = c.toArray();

四、List 系列

1. 特点

有序（存取顺序一致）、有索引、可重复。

2. 特有方法（基于索引）

java

add(int index, E e);
remove(int index);
set(int index, E e);
get(int index);

3. ArrayList

底层：数组，初始容量 10，扩容为 1.5 倍。
查询快（O(1)），增删慢（可能移动元素）。
最常用的 List。

示例：增删改查一次看全

java

List<String> list = new ArrayList<>();
list.add("a"); list.add("b"); list.add("c");   // [a, b, c]
list.add(1, "x");                              // [a, x, b, c] 指定位置插入
list.set(0, "A");                              // [A, x, b, c] 替换
list.remove(2);                                // [A, x, c] 按索引删
list.remove("x");                              // [A, c] 按值删
String s = list.get(1);                        // "c"
System.out.println(list);                      // [A, c]

4. LinkedList

底层：双向链表。
查询慢（O(n)），首尾增删快（O(1)）。
特有方法：addFirst/addLast/removeFirst/removeLast/getFirst/getLast，适合做栈/队列。

5. 遍历方式

java

List<String> list = new ArrayList<>();
// 1. 普通 for
for (int i = 0; i < list.size(); i++) list.get(i);
// 2. 增强 for
for (String s : list) { }
// 3. 迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) it.next();
// 4. forEach + Lambda（JDK 8）
list.forEach(s -> System.out.println(s));

并发修改异常：遍历过程中用集合的 add/remove 会抛 ConcurrentModificationException。要用 Iterator.remove() 或 ListIterator。
示例：边遍历边删元素（经典坑）
java
// ❌ 报错：ConcurrentModificationException
for (String s : list) {
    if (s.equals("b")) list.remove("b");   // 修改了集合结构
}

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

五、Set 系列

1. 特点

无索引、不可重复。

2. HashSet（重点）

底层：哈希表（数组 + 链表 + 红黑树，JDK 8 链表长度 ≥ 8 且数组 ≥ 64 转红黑树）。
去重原理：先比较 hashCode，相同再用 equals。
存储自定义对象：必须重写 hashCode 和 equals。

示例：String 去重（自带 hashCode/equals，直接能去）
java
Set<String> set = new HashSet<>();
set.add("a"); set.add("a"); set.add("b");
System.out.println(set);   // [a, b]，重复的 "a" 只留一个

示例：自定义对象必须重写 hashCode + equals

java

public class Student {
    private String name;
    private int age;

    @Override
    public boolean equals(Object o) {          // 内容相同 → 相等
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student s = (Student) o;
        return age == s.age && Objects.equals(name, s.name);
    }

    @Override
    public int hashCode() {                    // 内容相同 → hash 也相同
        return Objects.hash(name, age);        // 必须和 equals 用同一批字段！
    }
}

Set<Student> set = new HashSet<>();
set.add(new Student("小明", 18));
set.add(new Student("小明", 18));   // 内容相同
System.out.println(set.size());     // 1  ✅ 重写了 → 去重成功

⚠️ 反例：只重写 equals 不重写 hashCode，两个内容相同的对象 hashCode 不同 → 落在不同桶 → 去重失败，size() 输出 2。

3. LinkedHashSet

在 HashSet 基础上维护链表，保证存取顺序一致。

4. TreeSet

底层：红黑树。
自动排序：自然排序（Comparable）或比较器排序（Comparator）。

示例 1：整数默认升序 + 去重

java

TreeSet<Integer> ts = new TreeSet<>();
ts.add(3); ts.add(1); ts.add(3); ts.add(2);
System.out.println(ts);   // [1, 2, 3]  自动排序 + 去重

示例 2：对象按属性排序——方式一「自然排序 Comparable」（写进类里）

java

public class Student implements Comparable<Student> {
    private String name;
    private int age;

    @Override
    public int compareTo(Student o) {          // 返回负数 → this 排前面
        return this.age - o.age;              // 升序：按年龄
    }
}
TreeSet<Student> set = new TreeSet<>();

示例 3：对象按属性排序——方式二「比较器 Comparator」（外挂，不用改类）

java

// 按年龄升序，年龄相同再按姓名比（面试常考这种组合条件）
TreeSet<Student> set = new TreeSet<>((a, b) -> {
    if (a.getAge() != b.getAge()) return a.getAge() - b.getAge();
    return a.getName().compareTo(b.getName());
});

六、Collections 工具类

java

Collections.sort(list);                       // 排序（元素需实现 Comparable）
Collections.shuffle(list);                    // 打乱
Collections.reverse(list);                    // 反转
List<Integer> fixed = Collections.singletonList(1);  // 不可变单元素集合
Collections.addAll(list, 1, 2, 3);            // 批量添加

示例：一排操作看效果

java

List<Integer> list = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(list);              // [1, 2, 3]  升序
Collections.reverse(list);           // [3, 2, 1]  反转
Collections.shuffle(list);           // 每次运行结果随机，如 [2, 3, 1]
Collections.addAll(list, 9, 8);      // 批量追加（底层就是可变参数）

七、Map 系列（重点）

1. 特点

双列，key 不可重复、value 可重复，每个 key 对应一个 value。

2. 常用 API

java

V put(K key, V value);         // 添加/替换
V get(Object key);             // 根据 key 取 value
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
Set<K> keySet();               // 所有 key 的集合
Collection<V> values();        // 所有 value
Set<Map.Entry<K,V>> entrySet(); // 键值对集合

3. HashMap（最常用）

底层：哈希表（数组 + 链表 + 红黑树）。
key 的去重依赖 hashCode + equals。
自定义对象作 key，必须重写 hashCode 和 equals。

示例：增删查改看全

java

Map<String, Integer> map = new HashMap<>();
map.put("java", 3);            // key 不存在 → 返回 null
map.put("java", 5);            // key 已存在 → 覆盖，返回旧值 3
map.get("java");               // 5
map.getOrDefault("go", 0);     // 0（key 不存在给默认值，写统计很好用）
map.containsKey("java");       // true
map.remove("java");            // 5

示例：经典实战——统计字符串中每个字符出现次数（面试必背）

java

String s = "hello world";
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) {
    count.put(c, count.getOrDefault(c, 0) + 1);
}
System.out.println(count);   // { =1, r=1, d=1, e=1, w=1, h=1, l=3, o=2}

4. 遍历方式

java

Map<String, Integer> map = new HashMap<>();
// 1. 键找值
for (String key : map.keySet()) {
    map.get(key);
}
// 2. 键值对对象（推荐）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    entry.getKey();
    entry.getValue();
}
// 3. forEach + Lambda
map.forEach((k, v) -> System.out.println(k + "=" + v));

5. HashMap 底层原理（面试高频）

初始容量 16，负载因子 0.75，达到阈值 16 * 0.75 = 12 时扩容 2 倍。
JDK 8：数组 + 链表，链表长度 ≥ 8 且数组长度 ≥ 64 时转红黑树。
元素位置：(n - 1) & hash。

示例：手算元素落位（理解 (n-1) & hash）
java
// 容量 n = 16，则 n - 1 = 15 = 0b1111（末尾 4 位全 1）
// 位置 = hash & 15，只看 hash 的低 4 位 → 位置范围 0~15

// 例子：hash = 66
//   66   = 0b1000010
// & 15   = 0b0001111
//   结果 = 0b0000010 = 2   → 落在数组下标 2

// 两个 key 的 hash 低 4 位相同（如 hash=2 和 hash=18）→ 落在同一格 → 用链表挂起来
⚠️ JDK 8 优化：key 的 hash 先做 hash ^ (hash >>> 16) 高低 16 位扰动，让高位也参与运算，减少"低 4 位相同"的冲突概率。

八、可变参数

java

public static int sum(int... nums) {   // nums 本质是数组
    int sum = 0;
    for (int n : nums) sum += n;
    return sum;
}

一个方法只能有一个可变参数，且必须是最后一个。
Collections.addAll(list, 1, 2, 3) 底层就是可变参数。

九、集合嵌套

集合元素本身可以是集合，例如：

java

List<List<String>> grades = new ArrayList<>();   // 年级 → 班级 → 学生
Map<String, List<String>> provinceCities = new HashMap<>();  // 省 → 城市

综合实战：斗地主（洗牌 → 发牌 → 排序看牌）

java

// 造牌：每张牌 → 权重（3→0 ... 2→12，小王13 大王14），TreeSet 按权重排
String[] colors = {"♠", "♥", "♣", "♦"};
String[] nums = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2"};
List<String> poker = new ArrayList<>();
for (String num : nums)
    for (String color : colors) poker.add(color + num);
poker.add("小王"); poker.add("大王");

// 洗牌 + 发牌：3 人轮流各 17 张，剩下 3 张做底牌
Collections.shuffle(poker);
List<String> player1 = new ArrayList<>();
List<String> player2 = new ArrayList<>();
List<String> player3 = new ArrayList<>();
List<String> bottom = new ArrayList<>();
for (int i = 0; i < poker.size(); i++) {
    List<String> target = i < 51 ? (i % 3 == 0 ? player1 : i % 3 == 1 ? player2 : player3) : bottom;
    target.add(poker.get(i));
}

// 看牌：放进按权重排序的 TreeSet 自动排好
System.out.println("玩家1：" + sort(player1));
System.out.println("底牌 ：" + bottom);

（sort() 就是把 List 放进一个按权重比较的 TreeSet，权重用 Map 存： Map<String, Integer> weight：3→0 ... 2→12、小王→13、大王→14）

十、集合选择指南

存储单元素？
├── 查询多、要索引、可重复        → ArrayList
├── 频繁首尾增删、做栈/队列        → LinkedList
├── 去重、不关心顺序              → HashSet
├── 去重、保留存取顺序            → LinkedHashSet
└── 去重 + 自动排序              → TreeSet

存储 key-value？
├── 一般场景                    → HashMap
├── 保留存取顺序                → LinkedHashMap
└── 按 key 自动排序             → TreeMap

不知道选什么？→ ArrayList / HashMap。

练习建议

ArrayList 去重（重写 equals，或用 contains 判断）。
HashMap 统计字符串中每个字符出现次数。
模拟斗地主：洗牌、发牌、看牌（Collections.shuffle + TreeMap 排序）。
用 LinkedList 模拟栈和队列。
TreeSet 按"年龄 + 姓名"自定义排序。

03-集合框架（Collection / List / Set / Map） ​

一、为什么要有集合 ​

二、集合体系图 ​

三、Collection 通用方法 ​

四、List 系列 ​

1. 特点 ​

2. 特有方法（基于索引） ​

3. ArrayList ​

4. LinkedList ​

5. 遍历方式 ​

五、Set 系列 ​

1. 特点 ​

2. HashSet（重点） ​

3. LinkedHashSet ​

4. TreeSet ​

六、Collections 工具类 ​

七、Map 系列（重点） ​

1. 特点 ​

2. 常用 API ​

3. HashMap（最常用） ​

4. 遍历方式 ​

5. HashMap 底层原理（面试高频） ​

八、可变参数 ​

九、集合嵌套 ​

十、集合选择指南 ​

练习建议 ​

03-集合框架（Collection / List / Set / Map）

一、为什么要有集合

二、集合体系图

三、Collection 通用方法

四、List 系列

1. 特点

2. 特有方法（基于索引）

3. ArrayList

4. LinkedList

5. 遍历方式

五、Set 系列

1. 特点

2. HashSet（重点）

3. LinkedHashSet

4. TreeSet

六、Collections 工具类

七、Map 系列（重点）

1. 特点

2. 常用 API

3. HashMap（最常用）

4. 遍历方式

5. HashMap 底层原理（面试高频）

八、可变参数

九、集合嵌套

十、集合选择指南

练习建议