集合框架

集合概述

集合是用于保存和操作一组对象的容器。Java 集合类封装了数组、链表、哈希表、树等数据结构，并提供统一的接口。

与数组相比，集合通常具有以下特点：

集合长度可以动态变化。
集合只能直接保存引用类型，基本类型会通过自动装箱转换为包装类。
不同集合在查找、插入、删除、排序和去重方面各有特点。

选择集合时，应根据是否需要索引、是否允许重复、是否要求顺序、是否需要键值映射以及并发要求综合判断。

集合框架结构

Collection 是单列集合的顶层接口，常用方法包括 add()、addAll()、contains()、remove()、clear()、size() 和 iterator()。

List、Set 和 Queue 都属于 Collection 体系；Map 保存键值映射，不继承 Collection。

List 接口

List 表示有序、可重复的元素序列，并提供基于索引的操作。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add(1, "C");

System.out.println(list.get(0));
System.out.println(list.indexOf("C"));
list.set(0, "AA");
list.remove(1);

ArrayList

ArrayList 内部使用可扩容数组保存元素。

ArrayList 的特点

根据索引访问元素速度快，时间复杂度通常为 O(1)。
在尾部添加元素通常较快，但扩容时需要复制数组。
在中间插入或删除元素需要移动后续元素，时间复杂度通常为 O(n)。
不是线程安全集合。

简化版 ArrayList 的设计

实现简化版 ArrayList 时，可以使用以下字段：

private Object[] data;
private int size;

data.length 表示当前容量，size 表示实际元素数量。有效元素索引范围是 0 到 size - 1。

容量扩展

添加元素前，如果 size == data.length，需要创建更大的数组并复制元素。

private void ensureCapacity() {
    if (size < data.length) {
        return;
    }

    int newCapacity = data.length == 0 ? 10 : data.length + (data.length >> 1);
    data = Arrays.copyOf(data, newCapacity);
}

扩容比例需要在减少复制次数和控制空闲内存之间取得平衡。

添加元素

public boolean add(Object value) {
    ensureCapacity();
    data[size++] = value;
    return true;
}

在指定位置插入元素时，允许的索引范围是 0 到 size，其中 size 表示尾部插入。

public void add(int index, Object value) {
    checkPositionIndex(index);
    ensureCapacity();

    System.arraycopy(data, index, data, index + 1, size - index);
    data[index] = value;
    size++;
}

获取、修改和删除元素

public Object get(int index) {
    checkElementIndex(index);
    return data[index];
}

public Object set(int index, Object value) {
    checkElementIndex(index);
    Object oldValue = data[index];
    data[index] = value;
    return oldValue;
}

public Object remove(int index) {
    checkElementIndex(index);
    Object oldValue = data[index];

    int moved = size - index - 1;
    if (moved > 0) {
        System.arraycopy(data, index + 1, data, index, moved);
    }
    data[--size] = null;
    return oldValue;
}

删除后把空闲位置设置为 null，可以避免集合继续持有无用对象引用。

查找和清空

public int indexOf(Object value) {
    for (int i = 0; i < size; i++) {
        if (Objects.equals(value, data[i])) {
            return i;
        }
    }
    return -1;
}

public boolean contains(Object value) {
    return indexOf(value) >= 0;
}

public void clear() {
    Arrays.fill(data, 0, size, null);
    size = 0;
}

Objects.equals() 可以同时正确处理普通对象和 null。

LinkedList

LinkedList 内部使用双向链表保存元素，并实现了 List 和 Deque 接口。

每个节点通常保存当前数据、前一个节点引用和后一个节点引用。链表对象还保存头节点、尾节点和元素数量。

LinkedList 的特点

已知节点位置时，插入和删除只需要修改相邻节点引用。
按索引查找需要从头部或尾部逐个移动，时间复杂度通常为 O(n)。
每个节点需要额外保存前后引用，内存开销通常大于 ArrayList。
不是线程安全集合。

简化版节点结构

private static class Node {
    private Object data;
    private Node prev;
    private Node next;

    Node(Object data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

尾部添加节点

public boolean add(Object value) {
    Node oldLast = last;
    Node newNode = new Node(value, oldLast, null);
    last = newNode;

    if (oldLast == null) {
        first = newNode;
    } else {
        oldLast.next = newNode;
    }

    size++;
    return true;
}

根据索引查找节点

可以比较索引与 size / 2，决定从头部还是尾部开始查找。

private Node getNode(int index) {
    checkElementIndex(index);

    if (index < (size >> 1)) {
        Node current = first;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    Node current = last;
    for (int i = size - 1; i > index; i--) {
        current = current.prev;
    }
    return current;
}

删除节点

private Object unlink(Node node) {
    Node previous = node.prev;
    Node next = node.next;

    if (previous == null) {
        first = next;
    } else {
        previous.next = next;
        node.prev = null;
    }

    if (next == null) {
        last = previous;
    } else {
        next.prev = previous;
        node.next = null;
    }

    Object oldValue = node.data;
    node.data = null;
    size--;
    return oldValue;
}

LinkedList 的队列和栈用法

Queue 队列

队列通常遵循先进先出规则。推荐使用 offer()、poll() 和 peek()，它们在操作失败或队列为空时使用返回值表示结果。

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");

System.out.println(queue.poll());
System.out.println(queue.peek());

Deque 双端队列

Deque 可以从两端添加和删除元素，也可以作为栈使用。

Deque<String> stack = new LinkedList<>();
stack.push("A");
stack.push("B");

System.out.println(stack.pop());
System.out.println(stack.peek());

新的代码通常使用 Deque 代替旧的 Stack 类。

ArrayList、LinkedList 和 Vector

集合	内部结构	主要特点
`ArrayList`	动态数组	索引访问快，中间插入删除需要移动元素
`LinkedList`	双向链表	按索引访问慢，可作为队列或双端队列
`Vector`	动态数组	旧式同步集合，单次方法调用带同步开销

不能简单认为 LinkedList 的所有插入删除都比 ArrayList 快。如果仍需先按索引查找位置，整体操作可能仍为 O(n)。

泛型

泛型把类型作为参数，使编译器能够在编译期检查类型，并减少强制转换。

类和接口泛型

public class Test<E, F> {
    public F method(E value) {
        return null;
    }
}

public interface ITest<PK> {
    void method(PK value);
}

泛型类型参数通常使用单个大写字母，例如 T、E、K 和 V。

泛型方法

泛型方法在返回类型前声明自己的类型参数。

public static <T> T first(T[] values) {
    return values.length == 0 ? null : values[0];
}

方法泛型与类泛型相互独立。

指定泛型类型

Test<String, Integer> test = new Test<>();

子类继承泛型父类或实现泛型接口时，可以指定具体类型。

public class SubTest extends Test<String, Integer>
        implements ITest<Person> {

    @Override
    public Integer method(String value) {
        return value.length();
    }

    @Override
    public void method(Person value) {
        System.out.println(value);
    }
}

使用原始类型会失去编译期类型检查，不应把“未指定泛型”简单理解为安全的 Object 泛型。

List rawList = new ArrayList(); // 不推荐

泛型不具备协变性

即使 Student 是 Person 的子类，List<Student> 也不是 List<Person> 的子类型。

// List<Person> people = new ArrayList<Student>(); // 编译错误

数组具有协变性，但错误可能延迟到运行时。

Person[] people = new Student[3];
// people[0] = new Person(); // 运行时抛出 ArrayStoreException

通配符

? 表示未知类型。

上界通配符

? extends Person 表示某个未知的 Person 子类型，适合读取数据。

public static void printPeople(List<? extends Person> people) {
    for (Person person : people) {
        System.out.println(person);
    }
}

除 null 外，通常不能向该集合安全添加具体对象，因为实际元素类型未知。

下界通配符

? super Student 表示 Student 或其父类型，适合写入 Student 对象。

public static void addStudent(List<? super Student> people) {
    people.add(new Student());
}

可以使用“生产者使用 extends，消费者使用 super”帮助记忆。

Collections 工具类

Collections 是集合算法工具类，Collection 是集合接口，两者含义不同。

批量添加和排序

List<String> values = new ArrayList<>();
Collections.addAll(values, "cac", "bcd", "abc");
Collections.sort(values);

元素实现 Comparable 时，可以提供自然顺序。

public class Person implements Comparable<Person> {
    private int age;
    private double height;

    @Override
    public int compareTo(Person other) {
        int ageResult = Integer.compare(age, other.age);
        if (ageResult != 0) {
            return ageResult;
        }
        return Double.compare(height, other.height);
    }
}

使用 Integer.compare() 等方法可以避免直接相减造成整数溢出。

需要临时改变比较规则时，可以传入 Comparator。

Collections.sort(people, new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getScore(), p2.getScore());
    }
});

compareTo() 和 compare() 都应返回负数、零或正数，不要求恰好返回 -1、0、1。

其他常用方法

binarySearch()：在有序列表中执行二分查找。
replaceAll()：替换所有相等元素。
shuffle()：随机打乱列表顺序。
swap()：交换两个索引位置的元素。
synchronizedList()：返回同步包装列表。

同步包装集合在遍历时仍需要按照文档要求进行外部同步，单个方法同步不代表一组复合操作自动具备原子性。

Map 接口

Map 使用键和值保存映射关系。键不能重复，重复调用 put() 会替换旧值；值可以重复。

Map<String, Integer> map = new HashMap<>();
map.put("001", 100);
map.put("002", 200);
map.put("002", 300);

System.out.println(map.get("001"));
System.out.println(map.containsKey("002"));
System.out.println(map.containsValue(300));
map.remove("002");

不同 Map 实现对顺序、空键、排序和线程安全的规定不同。

HashMap

HashMap 使用哈希表保存键值映射。理想情况下，查找、添加和删除的平均时间复杂度接近 O(1)，但最坏情况和实际性能取决于哈希分布、冲突和容量。

基本结构

Java 8 的 HashMap 主要由数组、链表和红黑树组成。

默认负载因子为 0.75，扩容阈值通常为容量乘以负载因子。

键值对被封装为节点对象，节点实现 Map.Entry 接口。

默认构造器不会立即创建长度为 16 的数组，存储表通常在首次插入时延迟初始化为默认容量。

添加元素的过程

向 HashMap 添加键值对时，主要过程如下：

计算键的哈希值并进行扰动处理。
使用数组长度和哈希值计算桶索引。容量为二的幂时通常使用位运算，而不是普通取余。
桶为空时直接创建节点。
桶不为空时，通过哈希值和 equals() 判断是否存在相同键。
键已存在时替换值；否则把新节点加入链表或红黑树。
元素数量超过阈值时扩容。

Java 8 中，单个桶的链表节点数达到树化阈值时，还要检查数组容量。容量不足时通常优先扩容；容量达到要求后才转换为红黑树。不能简单表述为“链表达到某个长度一定树化”。

HashMap 允许一个 null 键和多个 null 值，但不是线程安全集合。

键对象的要求

作为键的对象如果重写 equals()，必须同时正确重写 hashCode()。键存入 HashMap 后，不应修改会参与 equals() 或 hashCode() 计算的字段，否则可能无法再次找到该键。

常见 Map 实现

Hashtable

Hashtable 是旧式同步映射，不允许 null 键或 null 值。新代码通常根据场景选择 HashMap、同步包装或 ConcurrentHashMap。

TreeMap

TreeMap 基于红黑树，根据键的自然顺序或指定比较器排序。

TreeMap<Integer, String> map = new TreeMap<>(
        Comparator.reverseOrder()
);
map.put(100, "100");
map.put(80, "80");
map.put(120, "120");
System.out.println(map);

比较器判断两个键相等时，TreeMap 会把它们视为同一个键，因此比较规则应与业务相等语义保持一致。

LinkedHashMap

LinkedHashMap 在哈希表基础上维护双向链表。默认按插入顺序迭代，也可以通过构造器配置为访问顺序，常用于实现简单的 LRU 缓存。

Map<String, Integer> map = new LinkedHashMap<>();
map.put("b", 10);
map.put("a", 11);
map.put("c", 12);
System.out.println(map);

Set 接口

Set 不允许重复元素。是否保持顺序或排序由具体实现决定，不能把所有 Set 都概括为无序。

HashSet

HashSet 内部使用 HashMap 保存元素，集合元素作为键，值使用内部固定对象。

Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("a");
set.add("c");
System.out.println(set);

元素是否重复主要由 hashCode() 和 equals() 共同决定。

LinkedHashSet

LinkedHashSet 在去重的同时维护插入顺序。

Set<String> set = new LinkedHashSet<>();
Collections.addAll(set, "b", "a", "c", "a");
System.out.println(set);

TreeSet

TreeSet 根据自然顺序或比较器排序，并使用比较结果是否为零判断元素是否重复。

Set<String> set = new TreeSet<>(
        Comparator.comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder())
);
set.add("baaaa");
set.add("a");
set.add("ccc");
set.add("bbb");
System.out.println(set);

如果比较器只比较字符串长度，长度相同的不同字符串会被视为重复元素，因此需要增加次级比较规则。

Iterator 迭代器

Iterable 接口提供 iterator() 方法，Iterator 接口统一了不同集合的遍历方式。

常用方法如下：

hasNext()：判断是否还有下一个元素。
next()：返回下一个元素；没有元素时抛出 NoSuchElementException。
remove()：删除最近一次由 next() 返回的元素，是否支持由具体迭代器决定。

遍历 List

List<String> list = new ArrayList<>();
Collections.addAll(list, "a", "b", "c");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String value = iterator.next();
    if ("c".equals(value)) {
        iterator.remove();
    }
}

遍历期间直接调用集合的结构性修改方法，通常会触发快速失败检查并抛出 ConcurrentModificationException。应使用迭代器自己的 remove()，或者在遍历结束后统一修改。

遍历 Set

Set<String> set = new HashSet<>();
Collections.addAll(set, "a", "b", "c");

Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

遍历 Map

Map 本身不实现 Iterable，通常通过 entrySet()、keySet() 或 values() 获取可迭代视图。

Map<String, String> map = new HashMap<>();
map.put("101", "a");
map.put("102", "b");
map.put("103", "c");

for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "," + entry.getValue());
}

只需要键时可以遍历 keySet()，只需要值时可以遍历 values()。

增强 for 循环

增强 for 循环可以遍历数组和实现 Iterable 的对象。

for (String value : list) {
    System.out.println(value);
}

遍历集合时，增强 for 循环底层使用迭代器，因此不能在循环中直接对集合进行不受支持的结构性修改。

遍历数组时，编译器按数组索引生成循环逻辑，并不是使用 Iterator。

String[][] values = {
    {"a", "b"},
    {"c", "d"}
};

for (String[] row : values) {
    for (String value : row) {
        System.out.println(value);
    }
}

需要根据索引修改 List 元素时，可以使用普通 for 循环或 ListIterator。