Java 集合框架核心知识手册

1. 集合框架体系核心区别

1.1 List 接口（有序、可重复）

ArrayList

底层：动态数组（Object[]），默认初始容量 10

性能：
- 随机访问（get(index)）：O(1)（直接通过索引定位）
- 中间增删（add(index,e)/remove(index)）：O(n)（需移动元素）

场景：频繁查询、尾端增删（如用户列表展示）

LinkedList

底层：双向链表（节点含prev/next指针），实现Deque接口

性能：
- 随机访问：O(n)（需遍历链表）
- 中间增删：O(1)（仅改指针，定位节点后）

场景：频繁中间增删、队列 / 栈操作（如消息队列）

1.2 Set 接口（无序 / 有序、不可重复）

HashSet

底层：基于HashMap（元素存key，value为固定空对象）

核心：
- 去重：依赖hashCode()+equals()（需同时重写）

性能：查找 / 增删平均O(1)，支持 1 个null

场景：快速去重、无需排序（如过滤重复标签）

TreeSet

底层：基于TreeMap（红黑树结构）

核心：
- 去重排序：依赖Comparable（自然排序）或Comparator（自定义排序）

性能：查找 / 增删O(log n)，不支持null

场景：去重 + 排序（如成绩排行榜）

1.3 Map 接口（键值对、key 不可重复）

HashMap

底层：数组 + 链表 / 红黑树（JDK8+），默认容量 16，负载因子 0.75

性能：查找 / 增删平均O(1)，支持 1 个null键，key无序

场景：快速键值查询（如缓存用户信息）

TreeMap

底层：红黑树

核心：
- key有序：支持自然排序 / 自定义排序

功能：支持范围查询（subMap()）、首尾key获取

场景：键值排序 + 范围查询（如日期 - 数据映射）

1.4 三大接口对比表

维度	List	Set	Map
存储形式	单个元素	单个元素（去重）	key-value键值对
有序性	插入顺序有序	HashSet 无序 / TreeSet 有序	HashMap 无序 / TreeMap 有序
重复性	允许重复	不允许重复	key不重复，value可重复

2. 集合选型场景分析

需求类型	推荐集合	理由
频繁查询	ArrayList	索引访问效率最高
频繁中间增删	LinkedList	仅修改指针，无需移动元素
快速去重	HashSet	哈希查找效率优于 List
去重 + 排序	TreeSet	红黑树自动维护有序性
键值快速查询	HashMap	平均O(1)效率，比 TreeMap 快
键值 + 排序 / 范围查询	TreeMap	支持key排序与范围查询

3. 实操任务实现

3.1 手写 ArrayList 扩容逻辑（模拟 grow () 方法）

import java.util.Arrays;
public class CustomArrayList {

    private Object[] elementData; // 存储数组
    private int size; // 元素数量
    private static final int DEFAULT_CAPACITY = 10; // 默认容量

    // 无参构造
    public CustomArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    // 扩容核心方法
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;

        // 新容量 = 旧容量的1.5倍（位运算：oldCapacity >> 1 = 旧容量/2）
        int newCapacity = oldCapacity + (oldCapacity >> 1);

        // 若新容量仍不足，用最小需求容量
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }

        // 数组拷贝（核心步骤）
        elementData = Arrays.copyOf(elementData, newCapacity);

        System.out.println("扩容：" + oldCapacity + "→" + newCapacity);
    }

    // 添加元素（触发扩容）

    public void add(Object e) {

        if (size >= elementData.length) {
            grow(size + 1); // 至少需要size+1的容量
        }

        elementData[size++] = e;
    }

    // 测试

    public static void main(String[] args) {

        CustomArrayList list = new CustomArrayList();
        for (int i = 0; i < 15; i++) { // 超过默认容量10，触发扩容
            list.add("元素" + i);
        }
    }
}

3.2 ArrayList 与 LinkedList 性能对比测试

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PerformanceTest {

    private static final int LOOP = 10000; // 测试次数

    public static void main(String[] args) {

        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 1. 中间添加性能
        long arrayAddTime = testAddMiddle(arrayList);
        long linkedAddTime = testAddMiddle(linkedList);
        System.out.println("中间添加耗时：ArrayList=" + arrayAddTime + "ms，LinkedList=" + linkedAddTime + "ms");

        // 2. 随机访问性能
        fillData(arrayList);
        fillData(linkedList);
        long arrayGetTime = testGet(arrayList);
        long linkedGetTime = testGet(linkedList);
        System.out.println("随机访问耗时：ArrayList=" + arrayGetTime + "ms，LinkedList=" + linkedGetTime + "ms");
    }

    // 中间位置添加

    private static long testAddMiddle(List<Integer> list) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < LOOP; i++) {
            list.add(list.size() / 2, i);
        }

        return System.currentTimeMillis() - start;
    }

    // 随机访问

    private static long testGet(List<Integer> list) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < LOOP; i++) {
            list.get(i % list.size());
        }

        return System.currentTimeMillis() - start;
    }

    // 填充测试数据

    private static void fillData(List<Integer> list) {

        list.clear();

        for (int i = 0; i < LOOP; i++) {
            list.add(i);
        }
    }

}

测试结果说明：

中间添加：LinkedList 耗时远低于 ArrayList（无需移动元素）

随机访问：ArrayList 耗时远低于 LinkedList（直接索引定位）

4. 集合选型速查表

集合类	底层结构	增删效率（中间）	查询效率	核心场景
ArrayList	动态数组	O(n)	O(1)	频繁查询、尾端增删
LinkedList	双向链表	O(1)	O(n)	频繁中间增删、队列 / 栈
HashSet	HashMap（哈希表）	O(1)	O(1)	快速去重、无需排序
TreeSet	TreeMap（红黑树）	O(log n)	O(log n)	去重 + 排序
HashMap	数组 + 链表 / 红黑树	O(1)	O(1)	键值快速查询
TreeMap	红黑树	O(log n)	O(log n)	键值排序 + 范围查询

备注：

所有集合均线程不安全，多线程场景需用Collections.synchronizedXXX()或ConcurrentHashMap

自定义对象作 HashSet/HashMap 的元素 /key 时，必须重写hashCode()和equals()