java集合

List 接口：有序可重复的

List 接口的核心定位是维护有序（插入顺序）、可重复的元素集合，就像生活里按顺序记录的 “待办清单”，新增元素会排在末尾（或指定位置），且允许内容相同的项重复出现。这种特性让它成为处理 “有先后顺序、需保留重复内容” 场景的首选，比如订单流程记录、用户操作日志等。

常用实现类对比（ArrayList、LinkedList、Vector）

实现类 底层结构 核心优势 典型适用场景 性能短板
ArrayList 动态数组 随机访问快（O (1)） 查询频繁、增删少（如配置列表） 中间增删慢（需移位 / O (n)）
LinkedList 双向链表 头尾增删快（O (1)） 增删频繁（如消息队列） 随机访问慢（需遍历 / O (n)）
Vector 动态数组（线程安全） 线程安全 老旧代码 / 强线程安全需求（极少用） 效率低（ synchronized 锁全表）

Vector 因性能问题已被逐步替代，JUC 包中的CopyOnWriteArrayList（写时复制，读无锁）是更优的线程安全 List 方案。

ArrayList vs LinkedList 性能差异验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void main(String[] args) {
        // 测试ArrayList：增+随机访问
        List<String> arrayList = new ArrayList<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < DATA_SIZE; i++) {
            arrayList.add("Item_" + i); // 尾部追加（ArrayList默认扩容策略）
        }
        for (int i = 0; i < DATA_SIZE; i++) {
            arrayList.get(i); // 随机访问，O(1)
        }

        long cost = System.currentTimeMillis() - start;
        System.out.println("ArrayList（增+随机访问）耗时：" + cost + "ms");

        // 测试LinkedList：增+随机访问
        List<String> linkedList = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < DATA_SIZE; i++) {
            linkedList.add("Item_" + i); // 尾部追加（链表修改指针，O(1)）
        }
        for (int i = 0; i < DATA_SIZE; i++) {
            linkedList.get(i); // 随机访问需遍历，O(n)
        }
        cost = System.currentTimeMillis() - start;
        System.out.println("LinkedList（增+随机访问）耗时：" + cost + "ms");

        // 测试LinkedList：头尾增删（模拟队列）
        LinkedList<String> queue = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < DATA_SIZE; i++) {
            queue.offer("QueueItem_" + i); // 队尾加，O(1)
        }
        for (int i = 0; i < DATA_SIZE; i++) {
            queue.poll(); // 队首删，O(1)
        }
        cost = System.currentTimeMillis() - start;
        System.out.println("LinkedList（队列增删）耗时：" + cost + "ms");
    }

运行结果

ArrayList（增+随机访问）耗时：16ms
LinkedList（增+随机访问）耗时：10671ms
LinkedList（队列增删）耗时：12ms

结论

根据场景选实现类，查询多就用 ArrayList，增删多（尤其头尾）选 LinkedList。

自己实现的动态数组和双向链表

动态数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public class MyDynamicArray<E> {
    private Object[] array;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;


    public MyDynamicArray() {
        this.size = 0;
        this.array = new Object[DEFAULT_CAPACITY];
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        checkIndex(index);
        return (E) array[index];
    }

    public void set(int index, E element) {
        checkIndex(index);
        array[index] = element;
    }

    public void add(E element) {
        ensureCapacity();
        array[size++] = element;
    }

    public void add(int index, E element) {
        checkIndex(index);
        ensureCapacity();
        System.arraycopy(array, index, array, index + 1, size - index);
        array[index] = element;
        size++;
    }

    public void remove(int index) {
        checkIndex(index);
        System.arraycopy(array, index + 1, array, index, size - index - 1);
        array[--size] = null;
    }


    private void checkIndex(int index) {
        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 扩容
     */
    private void ensureCapacity() {
        if (size == array.length) {
            int newCapacity = array.length + (array.length >> 1);
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }


    public static void main(String[] args) {
        MyDynamicArray<Integer> myDynamicArray = new MyDynamicArray<>();
        for (int i = 0; i < 10; i++) {
            myDynamicArray.add(i);
        }

        myDynamicArray.remove(0);

    }
}

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
public class MyLinkedList<E> {

    private static class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;

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

    private Node<E> first;
    private Node<E> last;
    private int size = 0;

    public int size() {
        return size;
    }

    public void addFirst(E e) {
        Node<E> newNode = new Node<>(null, e, first);
        // 把第一个的上一个替换成prev
        if (first != null) {
            first.prev = newNode;
        }
        first = newNode;

        if (last == null) {
            last = newNode;
        }

        size++;
    }

    public void addLast(E e) {
        Node<E> newNode = new Node<>(last, e, null);
        if (last != null) {
            last.next = newNode;
        }
        last = newNode;
        if (first == null) { // 空链表
            first = newNode;
        }
        size++;
    }

    public E removeLast() {
        if (last == null) throw new RuntimeException("List is empty");
        E item = last.item;
        last = last.prev;
        if (last != null) {
            last.next = null;
        } else {
            first = null;
        }

        size--;
        return item;
    }

    public E removeFirst() {
        if (first == null) throw new RuntimeException("List is empty");
        E item = first.item;
        first = first.next;
        if (first != null) {
            first.prev = null;
        }
        size--;

        return item;
    }

    public void add(int index, E e) {
        checkPositionIndex(index);
        if (index == size) {
            addLast(e);
        } else if (index == 0) {
            addFirst(e);
        } else {
            Node<E> target = getNode(index);
            Node<E> newNode = new Node<>(target.prev, e, target);
            target.prev.next = newNode;
            target.prev = newNode;
            size++;
        }
    }

    private Node<E> getNode(int index) {
        Node<E> node;
        if (index < (size >> 1)) {
            node = this.first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = this.last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }

        return node;
    }

    private void checkPositionIndex(int index) {
        if (!(index >= 0 && index <= size)) throw new IndexOutOfBoundsException();
    }

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.add(2, 2);
        //list.removeFirst();
				//list.addLast(3);
				//list.removeLast();

    }
}

Set 接口：无序不可重复的

Set 接口的核心使命是保证元素唯一性（不可重复）、不维护插入顺序（部分实现类如 LinkedHashSet 除外）。它通过equals()和hashCode()方法协同工作，判断元素是否重复：

  1. 先比较hashCode()：不同则认为元素不同，直接存入；
  2. 若hashCode()相同，再比较equals()：若返回true，则判定为重复元素，拒绝存入。

这种设计让 Set 成为 “去重场景” 的标配，比如存储用户唯一 ID、商品分类标签等。

常用实现类对比（HashSet、TreeSet、LinkedHashSet）

实现类 底层依赖 核心特性 元素顺序规则 典型适用场景
HashSet HashMap（存 key） 去重高效（O (1)） 无序（哈希散列） 纯去重、不关心顺序（如用户 ID 集合）
TreeSet 红黑树（自平衡） 自动排序（按 Comparable/Comparator） 自然顺序 / 自定义顺序 需排序的去重场景（如成绩排名）
LinkedHashSet HashSet + 链表 去重 + 维护插入顺序 与插入顺序一致 需去重且保留顺序（如订单状态流转）

HashSet

HashSet是一个底层基于HashMap实现的Set集合，内部维护一个 HashMap<E, Object>，添加的元素作为 HashMap 的 key，value 是一个空对象（PRESENT）。

特点：
插入和查询效率高。
非线程安全。
自动去重。

LinkedHashSet

LinkedHashSet是一个继承HashSet，底层基于LinkedHashMap实现的Set集合，利用 LinkedHashMap 的双向链表结构保持插入或访问顺序。
特点
保留插入顺序，同时支持高效的增删查。
自动去重。
严格维护FIFO顺序。

TreeSet

TreeSet是一个底层基于TreeMap实现的有序集合，存储的元素必须实现 Comparable 接口，或者构造时传入 Comparator（即元素必须可排序）

特点：

不允许 null 元素，非线程安全。

自动排序。

插入/删除效率较低。

有丰富的导航和范围查询方法。

选项

  • 需顺序 + 可重复 → 选 List（ArrayList/LinkedList 按需挑）；
  • 需去重 + 无序 → 选 HashSet；
  • 需去重 + 有序（插入顺序） → 选 LinkedHashSet；
  • 需去重 + 自定义排序 → 选 TreeSet。
java
#java
java集合
https://zhaops-hub.github.io/2025/11/05/java/java集合/
作者
赵培胜
发布于
2025年11月5日
许可协议