集合框架

一、集合整体框架

Java 集合框架（Java Collection Framework）提供了一套设计优良的接口和类，用于存储和操作对象组。它位于 java.util 包中，是整个 Java 语言的核心组成部分。

1.1 顶层接口体系

集合框架主要分为两大体系：Collection 和 Map。

                    Iterable (接口)
                        │
                        ▼
                    Collection (接口)
                ┌───────┼───────────┐
                │       │           │
                ▼       ▼           ▼
              List     Set        Queue (接口)
           (接口)    (接口)       (接口)
                │       │           │
        ┌───────┼──┐ ┌──┼──┐       │
        ▼       ▼  ▼ ▼  ▼  ▼       ▼
    ArrayList LinkedList  HashSet TreeSet  LinkedList
                          │               (Deque)
                          ▼
                     LinkedHashSet


                    Map (接口)
                ┌───────┼───────────┐
                │       │           │
                ▼       ▼           ▼
            HashMap  TreeMap   LinkedHashMap
                │
                ▼
           ConcurrentHashMap

Collection：存储单一元素的集合，下有 List、Set、Queue 三个子接口。
Map：存储键值对（key-value）的集合，不继承 Collection。

1.2 接口说明

接口	描述	是否有序	是否允许重复
List	有序可重复集合	是	是
Set	不可重复集合	取决于实现	否
Queue	队列（FIFO）	通常是	是
Map	键值对，键不可重复	取决于实现	键不重复

二、Collection 接口通用方法

Collection 是所有单列集合的根接口，定义了以下通用方法：

方法	描述
`boolean add(E e)`	添加元素
`boolean remove(Object o)`	移除指定元素
`boolean contains(Object o)`	判断是否包含某元素
`int size()`	返回元素个数
`boolean isEmpty()`	判断是否为空
`void clear()`	清空集合
`Iterator<E> iterator()`	返回迭代器

代码示例

java

import java.util.*;

public class CollectionDemo {
    public static void main(String[] args) {
        // 使用多态：接口引用指向实现类
        Collection<String> coll = new ArrayList<>();

        // add —— 添加元素
        coll.add("Java");
        coll.add("Python");
        coll.add("Go");
        System.out.println("集合内容: " + coll); // [Java, Python, Go]

        // size —— 元素个数
        System.out.println("元素个数: " + coll.size()); // 3

        // contains —— 是否包含
        System.out.println("是否包含 Java: " + coll.contains("Java")); // true
        System.out.println("是否包含 C++: " + coll.contains("C++"));   // false

        // remove —— 移除元素
        coll.remove("Go");
        System.out.println("移除 Go 后: " + coll); // [Java, Python]

        // isEmpty —— 是否为空
        System.out.println("是否为空: " + coll.isEmpty()); // false

        // iterator —— 迭代器遍历
        System.out.print("迭代器遍历: ");
        Iterator<String> it = coll.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " "); // Java Python
        }

        // for-each 增强 for 循环（底层也是用迭代器）
        System.out.print("\n增强 for 遍历: ");
        for (String s : coll) {
            System.out.print(s + " "); // Java Python
        }

        // clear —— 清空
        coll.clear();
        System.out.println("\n清空后 size: " + coll.size()); // 0
    }
}

注意：Collection 的 remove() 方法只移除第一个匹配的元素。对于 Set 来说，因为没有重复元素，所以没有问题；对于 List，如果有多个相同元素，remove() 只移除第一个。

三、List 接口

List 是有序可重复集合，每个元素有索引。主要实现类有 ArrayList 和 LinkedList。

3.1 ArrayList

ArrayList 底层基于数组实现，支持快速随机访问。

3.1.1 底层结构

java

public class ArrayList<E> {
    // 底层就是一个 Object 数组
    transient Object[] elementData;

    // 默认初始容量为 10
    private static final int DEFAULT_CAPACITY = 10;

    // 实际元素个数
    private int size;
}

3.1.2 扩容机制

当数组容量不足时，ArrayList 会进行扩容，新容量 = 旧容量 × 1.5（右移一位实现）。

java

// JDK 源码核心逻辑（简化版）
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 右移一位相当于除以2，所以新容量 = 旧容量 + 旧容量/2 = 1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将旧数组元素拷贝到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容流程：

添加元素时检查容量是否足够
不够则调用 grow() 方法
新容量为旧容量的 1.5 倍
将旧数组元素通过 Arrays.copyOf() 复制到新数组
新数组替换旧数组

3.1.3 ArrayList 代码示例

java

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        // 创建 ArrayList（默认容量 10）
        List<String> list = new ArrayList<>();

        // 添加元素
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");
        System.out.println("初始: " + list); // [A, B, C, D, E]

        // 指定位置插入
        list.add(2, "X");
        System.out.println("索引2插入 X: " + list); // [A, B, X, C, D, E]

        // 根据索引获取元素（随机访问，O(1)）
        System.out.println("索引3的元素: " + list.get(3)); // C

        // 修改元素
        list.set(0, "Z");
        System.out.println("索引0改为 Z: " + list); // [Z, B, X, C, D, E]

        // 根据索引删除
        list.remove(1);
        System.out.println("删除索引1: " + list); // [Z, X, C, D, E]

        // 根据元素删除
        list.remove("C");
        System.out.println("删除元素 C: " + list); // [Z, X, D, E]

        // 获取子列表（视图，与原列表共享数据）
        List<String> subList = list.subList(0, 2);
        System.out.println("子列表: " + subList); // [Z, X]

        // 遍历方式
        System.out.print("for 循环: ");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }

        System.out.print("\n增强 for: ");
        for (String s : list) {
            System.out.print(s + " ");
        }
    }
}

3.2 LinkedList

LinkedList 底层基于双向链表实现，插入和删除效率高。

3.2.1 底层结构

java

// 内部节点类
private static class Node<E> {
    E item;       // 当前元素
    Node<E> next; // 后继节点
    Node<E> prev; // 前驱节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

java

public class LinkedList<E> {
    // 链表头节点
    transient Node<E> first;
    // 链表尾节点
    transient Node<E> last;
    // 元素个数
    transient int size = 0;
}

3.2.2 LinkedList 代码示例

java

import java.util.*;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // 添加元素
        list.add("A");
        list.add("B");
        list.add("C");
        System.out.println("初始: " + list); // [A, B, C]

        // 在头部和尾部添加
        list.addFirst("First");
        list.addLast("Last");
        System.out.println("首尾添加: " + list); // [First, A, B, C, Last]

        // 获取首尾元素（不删除）
        System.out.println("第一个: " + list.getFirst()); // First
        System.out.println("最后一个: " + list.getLast()); // Last

        // 获取并删除首尾元素
        System.out.println("移除头部: " + list.removeFirst()); // First
        System.out.println("移除尾部: " + list.removeLast());  // Last
        System.out.println("移除后: " + list); // [A, B, C]

        // 队列操作（Deque）
        list.offer("D");       // 尾部添加
        System.out.println("offer: " + list); // [A, B, C, D]

        System.out.println("poll: " + list.poll());   // 移除头部 A
        System.out.println("peek: " + list.peek());   // 查看头部 B

        // 栈操作
        LinkedList<String> stack = new LinkedList<>();
        stack.push("A");  // 入栈（头插）
        stack.push("B");
        stack.push("C");
        System.out.println("栈: " + stack); // [C, B, A]
        System.out.println("pop: " + stack.pop()); // 出栈 C
        System.out.println("栈现在: " + stack); // [B, A]
    }
}

3.3 ArrayList vs LinkedList 对比

对比维度	ArrayList	LinkedList
底层结构	动态数组（Object[]）	双向链表（Node）
随机访问（get/set）	O(1)，直接索引访问	O(n)，需要从头/尾遍历
尾部插入（add）	O(1) 均摊（扩容时 O(n)）	O(1)
指定位置插入	O(n)，需要移动元素	O(n)，但只需修改指针
头部插入/删除	O(n)，所有元素后移	O(1)
内存占用	更紧凑，只存数据	更大，每个节点存 3 个引用（prev/item/next）
适合场景	查询多、尾部增删	频繁头尾操作、频繁插入删除

3.4 实战选择建议

读多写少：查询操作远多于插入/删除→ 选 ArrayList（如缓存数据、配置信息）
频繁头尾操作：如队列、栈 → 选 LinkedList（它同时实现了 Deque 接口）
数据量巨大且频繁在中间插入/删除：考虑 LinkedList，但需注意查找位置也是 O(n)

四、Set 接口

Set 是不包含重复元素的集合。主要实现类有 HashSet、TreeSet 和 LinkedHashSet。

4.1 HashSet

HashSet 底层基于 HashMap 实现，将元素作为 HashMap 的 key 存储。

4.1.1 底层原理

java

public class HashSet<E> {
    // 底层就是一个 HashMap
    private transient HashMap<E, Object> map;

    // 所有 key 共享同一个 value（一个 dummy 对象）
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        // 将元素作为 key 存入 HashMap
        return map.put(e, PRESENT) == null;
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }
}

HashSet 去重原理：

调用元素的 hashCode() 计算哈希值，确定存储位置
如果该位置没有元素，直接存储
如果有元素，通过 equals() 比较是否相同
如果 equals() 返回 true，则认为重复，不存储
如果 equals() 返回 false，则通过链表/红黑树处理哈希冲突

重要

HashSet 的去重依赖于 hashCode() 和 equals() 方法。如果两个对象 equals() 返回 true，它们的 hashCode() 必须相等。

4.2 hashCode() 和 equals() 的关系

4.2.1 约定规则

规则	说明
一致性	同一个对象多次调用 `hashCode()` 应返回相同值
equals 相等 → hashCode 相等	若 `a.equals(b)` 为 true，则 `a.hashCode() == b.hashCode()`
hashCode 相等 ≠ equals 相等	哈希碰撞是允许的
equals 用到的字段 → hashCode 也要用	保证逻辑一致性

4.2.2 重写示例

java

class Student {
    private String id;   // 学号
    private String name; // 姓名

    public Student(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Student{id='" + id + "', name='" + name + "'}";
    }
}

public class HashSetEqualsDemo {
    public static void main(String[] args) {
        Set<Student> set = new HashSet<>();

        Student s1 = new Student("001", "张三");
        Student s2 = new Student("001", "李四"); // 学号相同，逻辑上是一个人
        Student s3 = new Student("002", "王五");

        set.add(s1);
        set.add(s2); // 因为 equals/hashCode 基于 id，不会被加入
        set.add(s3);

        System.out.println("集合大小: " + set.size()); // 2（s1 和 s2 被视为相同）
        System.out.println("集合内容: " + set);

        // 如果不重写 hashCode() 和 equals()，则 s1 和 s2 都会加入
    }
}

4.3 TreeSet

TreeSet 底层基于红黑树（Red-Black Tree）实现，元素自动排序。

java

import java.util.*;

public class TreeSetDemo {
    public static void main(String[] args) {
        // 自然排序（元素必须实现 Comparable 接口）
        Set<Integer> numbers = new TreeSet<>();
        numbers.add(5);
        numbers.add(1);
        numbers.add(9);
        numbers.add(3);
        numbers.add(7);
        System.out.println("排序后的数字: " + numbers); // [1, 3, 5, 7, 9]

        // String 也实现了 Comparable
        Set<String> words = new TreeSet<>();
        words.add("banana");
        words.add("apple");
        words.add("cherry");
        System.out.println("排序后的单词: " + words); // [apple, banana, cherry]

        // TreeSet 的常用方法
        TreeSet<Integer> ts = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
        System.out.println("第一个: " + ts.first());   // 10
        System.out.println("最后一个: " + ts.last());   // 50
        System.out.println("小于等于 25 的最大值: " + ts.floor(25)); // 20
        System.out.println("大于等于 25 的最小值: " + ts.ceiling(25)); // 30
        System.out.println("小于 25 的最大值: " + ts.lower(25));   // 20
        System.out.println("大于 25 的最小值: " + ts.higher(25));  // 30

        // 子集视图
        System.out.println("子集 [20, 40): " + ts.subSet(20, 40)); // [20, 30]
        System.out.println("头集 (<30): " + ts.headSet(30));    // [10, 20]
        System.out.println("尾集 (>=30): " + ts.tailSet(30));   // [30, 40, 50]
    }
}

4.4 LinkedHashSet

LinkedHashSet 继承自 HashSet，底层使用 LinkedHashMap，在哈希表基础上维护了一个双向链表来记录插入顺序。

java

import java.util.*;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> hashSet = new HashSet<>();
        hashSet.add("C");
        hashSet.add("A");
        hashSet.add("B");
        hashSet.add("D");
        System.out.println("HashSet（无序）: " + hashSet);

        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("C");
        linkedHashSet.add("A");
        linkedHashSet.add("B");
        linkedHashSet.add("D");
        System.out.println("LinkedHashSet（插入顺序）: " + linkedHashSet);
        // 输出示例: [C, A, B, D] —— 保持插入顺序
    }
}

4.5 Set 实现类对比

特性	HashSet	TreeSet	LinkedHashSet
底层结构	HashMap	红黑树	LinkedHashMap
元素顺序	无序	自然排序/定制排序	插入顺序
时间复杂度	O(1)	O(log n)	O(1)
是否允许 null	允许 1 个 null	不允许（需要比较）	允许 1 个 null
适用场景	快速查找、去重	需要排序的集合	需要保持顺序的去重集合

五、Comparable 和 Comparator

5.1 Comparable — 自然排序

Comparable 定义在元素类内部，实现自然排序。需要重写 compareTo() 方法。

java

// java.lang.Comparable
public interface Comparable<T> {
    public int compareTo(T o);
    // 返回负数 → this < o
    // 返回 0   → this == o
    // 返回正数 → this > o
}

java

import java.util.*;

class Person implements Comparable<Person> {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        // 按年龄升序排列
        return Integer.compare(this.age, other.age);
    }

    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

public class ComparableDemo {
    public static void main(String[] args) {
        List<Person> list = new ArrayList<>();
        list.add(new Person("张三", 25));
        list.add(new Person("李四", 20));
        list.add(new Person("王五", 30));

        Collections.sort(list); // 使用自然排序（Comparable）
        System.out.println("按年龄排序: " + list);
        // [李四(20), 张三(25), 王五(30)]
    }
}

5.2 Comparator — 定制排序

Comparator 定义在类外部，可以实现多种不同的排序规则。

java

import java.util.*;

public class ComparatorDemo {
    public static void main(String[] args) {
        List<Person> list = new ArrayList<>();
        list.add(new Person("张三", 25));
        list.add(new Person("李四", 20));
        list.add(new Person("王五", 30));

        // 方式一：匿名内部类 —— 按姓名排序
        list.sort(new Comparator<Person>() {
            @Override
            public int compare(Person a, Person b) {
                return a.name.compareTo(b.name);
            }
        });
        System.out.println("按姓名排序: " + list);

        // 方式二：Lambda 表达式 —— 按年龄降序
        list.sort((a, b) -> Integer.compare(b.age, a.age));
        System.out.println("按年龄降序: " + list);

        // 方式三：Comparator 工具方法
        list.sort(Comparator.comparingInt(p -> p.age));
        System.out.println("按年龄升序（方法引用）: " + list);

        // 方式四：多级排序（先按年龄，再按姓名）
        list.sort(Comparator.comparingInt((Person p) -> p.age)
                .thenComparing(p -> p.name));
        System.out.println("多级排序: " + list);
    }
}

5.3 Comparable vs Comparator

对比	Comparable	Comparator
包位置	`java.lang.Comparable`	`java.util.Comparator`
核心方法	`compareTo(T o)`	`compare(T o1, T o2)`
排序策略	自然排序（内部）	定制排序（外部）
修改类	需要修改元素类	无需修改元素类
灵活性	一个类只能有一种自然排序	可定义多种比较器
使用场景	类有默认排序规则，如 String、Integer	多种排序需求，无法修改源码的类

六、Map 接口

Map 用于存储键值对（key-value），key 不可重复，每个 key 映射一个 value。

6.1 HashMap

HashMap 是最常用的 Map 实现，底层结构为 数组 + 链表 + 红黑树。

6.1.1 底层数据结构

JDK 8 中的 HashMap 结构：

        数组（table）
    ┌─────┬─────┬─────┬─────┬─────┐
    │  0  │  1  │  2  │ ... │  n  │
    ├─────┼─────┼─────┼─────┼─────┤
    │ null│  →  │ null│     │  →  │
    └─────┘──┬──┘─────┴─────┴──┬──┘
             │                  │
          Node(key,v)       Node(key,v)
             │                  │
          Node(key,v)       Node(key,v)
         (链表)         (链表)
                            │
                         Node(key,v)
                         (链表长度>8且数组长度≥64 → 转红黑树)

重要字段：

java

public class HashMap<K,V> {
    // 默认初始容量：16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

    // 最大容量：2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 负载因子：0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 链表转红黑树的阈值：8
    static final int TREEIFY_THRESHOLD = 8;

    // 红黑树转链表的阈值：6
    static final int UNTREEIFY_THRESHOLD = 6;

    // 转红黑树的最小数组容量（若数组不够大，即使链表>8也会先扩容）
    static final int MIN_TREEIFY_CAPACITY = 64;

    // 核心数组
    transient Node<K,V>[] table;

    // 实际键值对数量
    transient int size;

    // 扩容阈值 = capacity * loadFactor
    int threshold;

    // 负载因子
    final float loadFactor;
}

6.1.2 Hash 算法

java

// JDK 8 的 hash 算法：高 16 位与低 16 位异或，减少哈希碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 计算数组下标：(n - 1) & hash，其中 n 为数组长度（2 的幂）
// 等价于 hash % n，但位运算更快
int index = (table.length - 1) & hash(key);

为什么用 (n-1) & hash 而不是 hash % n？

当 n 是 2 的幂时，两者等价，但位运算速度远快于取模运算。
这也是 HashMap 容量必须为 2 的幂的原因。

6.1.3 Put 流程

put(key, value) 流程：
  1. 计算 key 的 hash 值：hash = key.hashCode() ^ (h >>> 16)
  2. 计算数组下标：index = (table.length - 1) & hash
  3. 如果 table[index] == null，直接插入
  4. 如果 table[index] != null（发生哈希碰撞）：
     a. 检查 key 是否相同（== 或 equals），相同则覆盖 value
     b. 如果是红黑树节点，调用红黑树的插入方法
     c. 否则遍历链表：
        - 找到相同的 key → 覆盖 value
        - 没找到相同的 key → 尾插法插入链表尾部
        - 如果链表长度 ≥ 8，转为红黑树
  5. 检查 size 是否超过 threshold（capacity * 0.75），超过则扩容

java

import java.util.*;

public class HashMapPutDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();

        // put —— 插入键值对
        map.put("苹果", 5);
        map.put("香蕉", 3);
        map.put("橘子", 8);
        System.out.println(map); // {橘子=8, 苹果=5, 香蕉=3}

        // key 相同时，覆盖 value 并返回旧值
        Integer oldValue = map.put("苹果", 10);
        System.out.println("旧值: " + oldValue); // 5
        System.out.println("覆盖后: " + map);    // {橘子=8, 苹果=10, 香蕉=3}

        // get —— 获取
        System.out.println("香蕉数量: " + map.get("香蕉"));     // 3
        System.out.println("不存在的 key: " + map.get("西瓜")); // null

        // getOrDefault —— 获取，不存在则返回默认值
        System.out.println("西瓜: " + map.getOrDefault("西瓜", 0)); // 0

        // containsKey / containsValue
        System.out.println("是否包含苹果: " + map.containsKey("苹果")); // true
        System.out.println("是否有值 10: " + map.containsValue(10));   // true

        // 遍历方式
        // 方式一：entrySet 遍历（推荐）
        System.out.println("--- entrySet 遍历 ---");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }

        // 方式二：keySet + get（效率较低，多了一次查找）
        System.out.println("--- keySet 遍历 ---");
        for (String key : map.keySet()) {
            System.out.println(key + " = " + map.get(key));
        }

        // 方式三：values 遍历（只遍历值）
        System.out.println("--- values 遍历 ---");
        for (Integer value : map.values()) {
            System.out.println(value);
        }

        // 方式四：forEach（JDK 8 Lambda）
        System.out.println("--- forEach Lambda ---");
        map.forEach((k, v) -> System.out.println(k + " -> " + v));

        // remove —— 移除
        map.remove("橘子");
        System.out.println("移除橘子: " + map); // {苹果=10, 香蕉=3}
    }
}

6.1.4 Get 流程

get(key) 流程：
  1. 计算 key 的 hash 值
  2. 计算数组下标 index = (n-1) & hash
  3. 如果 table[index] == null → 返回 null
  4. 如果 table[index] != null：
     a. 检查第一个节点 key 是否相同 → 是则返回 value
     b. 如果是红黑树 → 在红黑树中查找
     c. 否则遍历链表 → 查找相同的 key
     d. 没找到 → 返回 null

6.1.5 扩容机制

java

final Node<K,V>[] resize() {
    // 1. 容量翻倍（左移一位）
    int newCap = oldCap << 1;  // 新容量 = 旧容量 × 2

    // 2. 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];

    // 3. 重新分配元素位置
    //    要么在原位置，要么在原位置 + oldCap（由 hash 的新一位决定）
    //    比如：容量从 16 扩到 32，则 hash 的低 5 位决定位置
}

扩容要点：

触发条件：size > threshold（threshold = capacity × loadFactor）
容量翻倍（2 的幂保持不变）
元素在新数组的位置 = 原位置 或 原位置 + 旧容量
负载因子 0.75 是时间与空间的折中方案

6.1.6 负载因子 0.75 的意义

太高（如 1.0）：空间利用率高，但哈希碰撞概率增大，链表变长，查询效率降低
太低（如 0.5）：碰撞少、查询快，但浪费大量内存空间
0.75 是经过大量测试得出的平衡点

6.2 HashMap 默认初始化容量

java

import java.util.*;

public class HashMapInitDemo {
    public static void main(String[] args) {
        // 默认：容量 16，负载因子 0.75
        Map<String, String> map1 = new HashMap<>();

        // 指定初始容量（实际会调整为最近的 2 的幂）
        Map<String, String> map2 = new HashMap<>(100);
        // 实际容量：128（大于 100 的最小的 2 的幂）
        // 注意：不是 100！HashMap 会调用 tableSizeFor() 计算

        // 指定容量和负载因子
        Map<String, String> map3 = new HashMap<>(32, 0.8f);
    }
}

6.3 LinkedHashMap

LinkedHashMap 继承自 HashMap，额外维护一个双向链表来记录元素顺序。

java

import java.util.*;

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        // 默认：保持插入顺序
        Map<String, Integer> linkedMap = new LinkedHashMap<>();
        linkedMap.put("C", 3);
        linkedMap.put("A", 1);
        linkedMap.put("B", 2);
        System.out.println("LinkedHashMap（插入顺序）: " + linkedMap);
        // {C=3, A=1, B=2}

        // HashMap 对比
        Map<String, Integer> hashMap = new HashMap<>();
        hashMap.put("C", 3);
        hashMap.put("A", 1);
        hashMap.put("B", 2);
        System.out.println("HashMap（无序）: " + hashMap);
        // 结果不确定，例如 {A=1, B=2, C=3}

        // 访问顺序模式（accessOrder = true）
        // 用于实现 LRU（最近最少使用）缓存
        Map<String, Integer> lruMap = new LinkedHashMap<>(16, 0.75f, true);
        lruMap.put("A", 1);
        lruMap.put("B", 2);
        lruMap.put("C", 3);
        System.out.println("初始: " + lruMap); // {A=1, B=2, C=3}

        // 访问 B
        lruMap.get("B");
        System.out.println("访问 B 后: " + lruMap); // {A=1, C=3, B=2}
        // B 被移到了末尾
    }
}

6.4 TreeMap

TreeMap 底层基于红黑树，key 按自然顺序或定制顺序排列。

java

import java.util.*;

public class TreeMapDemo {
    public static void main(String[] args) {
        // 自然排序（key 需实现 Comparable）
        Map<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "C");
        treeMap.put(1, "A");
        treeMap.put(2, "B");
        System.out.println("TreeMap（按 key 排序）: " + treeMap);
        // {1=A, 2=B, 3=C}

        // 定制排序：按姓名长度排序
        Map<String, Integer> custom = new TreeMap<>(
            (a, b) -> Integer.compare(a.length(), b.length())
        );
        custom.put("banana", 1);
        custom.put("apple", 2);
        custom.put("pear", 3);
        System.out.println("按长度排序: " + custom);
        // {pear=3, apple=2, banana=1}

        // TreeMap 的导航方法
        TreeMap<Integer, String> tm = new TreeMap<>();
        tm.put(10, "Ten");
        tm.put(20, "Twenty");
        tm.put(30, "Thirty");
        tm.put(40, "Forty");
        tm.put(50, "Fifty");

        System.out.println("第一个 entry: " + tm.firstEntry());     // 10=Ten
        System.out.println("最后一个 key: " + tm.lastKey());        // 50
        System.out.println(">=25 的最小 key: " + tm.ceilingKey(25)); // 30
        System.out.println("<=42 的最大 key: " + tm.floorKey(42));   // 40
        System.out.println("subMap(20, 40): " + tm.subMap(20, 40)); // {20=Twenty, 30=Thirty}
    }
}

6.5 Map 实现类对比

特性	HashMap	LinkedHashMap	TreeMap
底层结构	数组+链表+红黑树	HashMap + 双向链表	红黑树
key 顺序	无序	插入顺序/访问顺序	自然顺序/定制顺序
时间复杂度	O(1)	O(1)	O(log n)
是否允许 null key	允许 1 个	允许 1 个	不允许
是否允许 null value	允许	允许	允许
适用场景	快速存取	LRU 缓存、需要顺序	排序需求

七、HashMap 多线程问题

7.1 HashMap 线程不安全

HashMap 不是线程安全的。多线程并发操作会导致以下问题：

7.1.1 数据覆盖

两个线程同时 put，可能只有一个线程的数据被保存，另一个被覆盖。

java

// 多线程并发 put 可能丢失数据
Map<String, Integer> map = new HashMap<>();
// 线程1: put("A", 1)
// 线程2: put("A", 2)
// 结果可能既不是 1 也不是 2，而是 null（数据错乱）

7.1.2 Java 7 的死循环问题

JDK 7 中，HashMap 采用头插法（每次将新节点插入链表头部），多线程扩容时可能产生环形链表，导致 get() 操作陷入死循环。

java

// JDK 7 模拟死循环（仅供理解原理，不要在生产环境运行）
Map<Integer, String> map = new HashMap<>(2, 1.5f); // 容量小，容易触发扩容
map.put(3, "A");
map.put(7, "B");
map.put(5, "C");

// 多线程并发扩容时，transfer() 方法头插法可能导致环链
// 扩容时两个线程同时 rehash：
// 线程1 执行到一半被挂起，线程2 完成扩容
// 线程1 恢复后继续执行，此时链表方向反转，形成环
// 之后 get() 遍历链表会陷入无限循环！

JDK 8 的改进：改用尾插法（插入到链表尾部），且扩容时保持原有顺序，解决了死循环问题。但并发问题仍然存在（数据覆盖、size 计数不准确等）。

7.2 线程安全的方案

方案	说明	使用场景
`Hashtable`	全表加 synchronized 锁（性能差）	不推荐使用
`Collections.synchronizedMap()`	包装类，也是全表加锁	简单场景
`ConcurrentHashMap`	分段锁/红黑树+CAS，性能最优	推荐使用

7.3 ConcurrentHashMap 简介

JDK 8 的 ConcurrentHashMap 摒弃了 JDK 7 的分段锁（Segment）机制，采用 CAS + synchronized 实现线程安全。

核心原理：

CAS（比较并交换）：插入时没有哈希碰撞，直接用 CAS 操作，无锁
synchronized：发生哈希碰撞时，对链表/红黑树的头节点加锁
并发度远高于 Hashtable 的全表锁

java

import java.util.concurrent.*;

public class ConcurrentHashMapDemo {
    public static void main(String[] args) {
        // 线程安全的 HashMap
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

        // 使用方法与 HashMap 完全一致
        map.put("A", 1);
        map.put("B", 2);
        map.put("C", 3);

        // JDK 8 新增原子方法
        map.computeIfAbsent("D", key -> key.length()); // D=1
        map.merge("A", 10, Integer::sum);              // A=11

        System.out.println(map);

        // 多线程场景
        ExecutorService pool = Executors.newFixedThreadPool(10);
        for (int i = 0; i < 1000; i++) {
            int key = i;
            pool.submit(() -> map.put("key" + key, key));
        }
        pool.shutdown();
        System.out.println("最终大小: " + map.size()); // 1000
    }
}

八、Collections 工具类

java.util.Collections 提供了大量操作集合的静态方法。

8.1 常用方法一览

方法	描述
`sort(List)`	排序（自然排序）
`sort(List, Comparator)`	定制排序
`reverse(List)`	反转
`shuffle(List)`	随机打乱
`binarySearch(List, key)`	二分查找（必须先排序）
`max(Collection)`	返回最大元素
`min(Collection)`	返回最小元素
`fill(List, obj)`	用指定元素填充列表
`copy(List dest, List src)`	复制列表
`swap(List, i, j)`	交换两个位置
`frequency(Collection, obj)`	返回元素出现次数
`disjoint(Collection a, Collection b)`	判断两个集合无交集
`unmodifiableList(List)`	返回不可修改的列表
`synchronizedList(List)`	返回线程安全的列表

8.2 排序与查找

java

import java.util.*;

public class CollectionsSortDemo {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 3, 9, 1, 7, 3));

        // 排序（自然排序）
        Collections.sort(numbers);
        System.out.println("升序: " + numbers); // [1, 3, 3, 5, 7, 9]

        // 定制排序：降序
        Collections.sort(numbers, Comparator.reverseOrder());
        System.out.println("降序: " + numbers); // [9, 7, 5, 3, 3, 1]

        // 反转
        Collections.reverse(numbers);
        System.out.println("反转: " + numbers); // [1, 3, 3, 5, 7, 9]

        // 打乱
        List<Integer> deck = new ArrayList<>();
        for (int i = 1; i <= 10; i++) deck.add(i);
        Collections.shuffle(deck);
        System.out.println("打乱: " + deck);

        // 二分查找（必须先升序排列！）
        Collections.sort(numbers);
        int index = Collections.binarySearch(numbers, 5);
        System.out.println("数字 5 的索引: " + index);

        // 没找到返回负数（-(insertion point) - 1）
        int notFound = Collections.binarySearch(numbers, 100);
        System.out.println("100 的查找结果: " + notFound); // 负数

        // 最大最小值
        System.out.println("最大值: " + Collections.max(numbers)); // 9
        System.out.println("最小值: " + Collections.min(numbers)); // 1

        // 频率
        System.out.println("3 出现的次数: " + Collections.frequency(numbers, 3)); // 2

        // 填充
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
        Collections.fill(list, "X");
        System.out.println("填充后: " + list); // [X, X, X]

        // 替换
        Collections.replaceAll(list, "X", "Y");
        System.out.println("替换后: " + list); // [Y, Y, Y]
    }
}

8.3 不可变集合

java

import java.util.*;

public class UnmodifiableDemo {
    public static void main(String[] args) {
        List<String> original = new ArrayList<>(Arrays.asList("A", "B", "C"));

        // 创建不可修改的视图（数据变化时视图也会变）
        List<String> unmodifiable = Collections.unmodifiableList(original);
        System.out.println("不可修改视图: " + unmodifiable);

        // 以下操作会抛出 UnsupportedOperationException
        // unmodifiable.add("D");       // 异常！
        // unmodifiable.remove(0);      // 异常！
        // unmodifiable.set(0, "Z");    // 异常！

        // 注意：视图本身不可修改，但原始列表仍可修改
        original.add("D");
        System.out.println("原始列表修改后，视图也跟着变了: " + unmodifiable);
        // [A, B, C, D]

        // JDK 9+ 创建不可变集合的简便方式
        // List.of("A", "B", "C");      // 完全不可变
        // Set.of("A", "B", "C");       // 完全不可变
        // Map.of("A", 1, "B", 2);      // 完全不可变
    }
}

8.4 线程安全包装

java

import java.util.*;

public class SynchronizedDemo {
    public static void main(String[] args) throws InterruptedException {
        // 普通 ArrayList 线程不安全
        List<Integer> unsafe = new ArrayList<>();

        // 用 Collections.synchronizedList 包装成线程安全
        List<Integer> safe = Collections.synchronizedList(new ArrayList<>());

        // 多线程并发添加
        Runnable task = () -> {
            for (int i = 0; i < 1000; i++) {
                safe.add(i); // 安全的
                // unsafe.add(i); // 不安全的 —— 可能报错或数据丢失
            }
        };

        Thread t1 = new Thread(task);
        Thread t2 = new Thread(task);
        t1.start();
        t2.start();
        t1.join();
        t2.join();

        System.out.println("线程安全集合大小: " + safe.size()); // 2000
    }
}

九、小结

9.1 核心要点回顾

集合框架两大体系：Collection（单列）和 Map（键值对），Collection 下有 List、Set、Queue。
List：有序可重复
- ArrayList：数组实现，查询快（O(1)），增删慢（O(n)），1.5倍扩容
- LinkedList：双向链表，头尾操作快（O(1)），中间操作慢
Set：不可重复
- HashSet：基于 HashMap，O(1)，无序，依赖 hashCode() 和 equals() 去重
- TreeSet：基于红黑树，O(log n)，自动排序
- LinkedHashSet：基于 LinkedHashMap，保持插入顺序
Map：键值对
- HashMap：数组+链表+红黑树，O(1)，负载因子 0.75，扩容翻倍
- TreeMap：红黑树，O(log n)，key 排序
- LinkedHashMap：维护插入/访问顺序
- ConcurrentHashMap：线程安全，CAS+synchronized
排序：
- Comparable：类内部实现自然排序
- Comparator：外部定制排序，lambda 可简化
Collections 工具类：排序、查找、反转、不可变包装、线程安全包装

9.2 选型速查表

需求	推荐实现	原因
按索引随机访问	ArrayList	随机访问 O(1)
频繁头尾插入删除	LinkedList	头尾操作 O(1)
去重（无需顺序）	HashSet	O(1) 去重
去重 + 排序	TreeSet	自动排序
去重 + 保持插入顺序	LinkedHashSet	双向链表维护顺序
快速存取键值对	HashMap	性能之王
键值对 + 排序	TreeMap	按 key 排序
键值对 + 保持顺序	LinkedHashMap	LRU 缓存
多线程环境（高性能）	ConcurrentHashMap	CAS+分段
多线程环境（简单）	Collections.synchronizedXxx	简单包装
只读集合	Collections.unmodifiableXxx	安全共享

集合框架 ​

一、集合整体框架 ​

1.1 顶层接口体系 ​

1.2 接口说明 ​

二、Collection 接口通用方法 ​

代码示例 ​

三、List 接口 ​

3.1 ArrayList ​

3.1.1 底层结构 ​

3.1.2 扩容机制 ​

3.1.3 ArrayList 代码示例 ​

3.2 LinkedList ​

3.2.1 底层结构 ​

3.2.2 LinkedList 代码示例 ​

3.3 ArrayList vs LinkedList 对比 ​

3.4 实战选择建议 ​

四、Set 接口 ​

4.1 HashSet ​

4.1.1 底层原理 ​

4.2 hashCode() 和 equals() 的关系 ​

4.2.1 约定规则 ​

4.2.2 重写示例 ​

4.3 TreeSet ​

4.4 LinkedHashSet ​

4.5 Set 实现类对比 ​

五、Comparable 和 Comparator ​

5.1 Comparable — 自然排序 ​

5.2 Comparator — 定制排序 ​

5.3 Comparable vs Comparator ​

六、Map 接口 ​

6.1 HashMap ​

6.1.1 底层数据结构 ​

6.1.2 Hash 算法 ​

6.1.3 Put 流程 ​

6.1.4 Get 流程 ​

6.1.5 扩容机制 ​

6.1.6 负载因子 0.75 的意义 ​

6.2 HashMap 默认初始化容量 ​

6.3 LinkedHashMap ​

6.4 TreeMap ​

6.5 Map 实现类对比 ​

七、HashMap 多线程问题 ​

7.1 HashMap 线程不安全 ​

7.1.1 数据覆盖 ​

7.1.2 Java 7 的死循环问题 ​

7.2 线程安全的方案 ​

7.3 ConcurrentHashMap 简介 ​

八、Collections 工具类 ​

8.1 常用方法一览 ​

8.2 排序与查找 ​

8.3 不可变集合 ​

8.4 线程安全包装 ​

九、小结 ​

9.1 核心要点回顾 ​

9.2 选型速查表 ​

集合框架

一、集合整体框架

1.1 顶层接口体系

1.2 接口说明

二、Collection 接口通用方法

代码示例

三、List 接口

3.1 ArrayList

3.1.1 底层结构

3.1.2 扩容机制

3.1.3 ArrayList 代码示例

3.2 LinkedList

3.2.1 底层结构

3.2.2 LinkedList 代码示例

3.3 ArrayList vs LinkedList 对比

3.4 实战选择建议

四、Set 接口

4.1 HashSet

4.1.1 底层原理

4.2 hashCode() 和 equals() 的关系

4.2.1 约定规则

4.2.2 重写示例

4.3 TreeSet

4.4 LinkedHashSet

4.5 Set 实现类对比

五、Comparable 和 Comparator

5.1 Comparable — 自然排序

5.2 Comparator — 定制排序

5.3 Comparable vs Comparator

六、Map 接口

6.1 HashMap

6.1.1 底层数据结构

6.1.2 Hash 算法

6.1.3 Put 流程

6.1.4 Get 流程

6.1.5 扩容机制

6.1.6 负载因子 0.75 的意义

6.2 HashMap 默认初始化容量

6.3 LinkedHashMap

6.4 TreeMap

6.5 Map 实现类对比

七、HashMap 多线程问题

7.1 HashMap 线程不安全

7.1.1 数据覆盖

7.1.2 Java 7 的死循环问题

7.2 线程安全的方案

7.3 ConcurrentHashMap 简介

八、Collections 工具类

8.1 常用方法一览

8.2 排序与查找

8.3 不可变集合

8.4 线程安全包装

九、小结

9.1 核心要点回顾

9.2 选型速查表