java 集合

深入理解集合体系 · 掌握核心源码机制 · 解决工程实战问题

一、java 集合框架全景概览

java 集合框架(Java Collections Framework,JCF)是Java标准库中最具工程价值的设计之一,它以统一的接口体系、丰富的实现类和高效的算法支撑了现代Java应用的数据处理能力。整个框架以Collection和Map为根接口,向下派生出List、Set、Queue、Deque等子接口,并通过ArrayList、LinkedList、HashMap、HashSet等实现类提供具体功能。

框架设计遵循三大核心原则:

值得注意的是,自JDK 8起,java 集合框架引入了大量函数式编程支持:通过forEachRemaining、removeIf、replaceAll等默认方法,结合Lambda表达式显著提升开发效率;JDK 9更进一步增强集合不可变性(List.of()、Map.ofEntries()),从语言层面规避并发修改风险。

下图展示了完整的集合类层次结构(简化版):

java 集合核心结构图

Collection(单列集合)
├── List(有序可重复)
│   ├── ArrayList(动态数组)
│   ├── LinkedList(双向链表)
│   └── Vector(线程安全,已过时)
├── Set(无序不可重复)
│   ├── HashSet(哈希表)
│   ├── LinkedHashSet(哈希+链表)
│   └── TreeSet(红黑树)
└── Queue(队列)
    ├── PriorityQueue(堆)
    └── Deque(双端队列)
        └── ArrayDeque(动态数组实现)
Map(双列集合)
├── HashMap(哈希表,JDK8红黑树优化)
├── LinkedHashMap(哈希+链表)
├── ConcurrentHashMap(分段锁→CAS+synchronized)
├── TreeMap(红黑树)
└── Hashtable(线程安全,已过时)

从实现角度看,java 集合框架的本质是数据结构的工程化封装。例如ArrayList背后是动态扩容数组,HashMap是哈希表+红黑树的混合结构,TreeMap则是自平衡二叉搜索树(红黑树)。理解这些底层机制,才能在实际开发中做出最优选择。

二、核心接口深度解析

2.1 Collection接口

Collection是所有单列集合的顶级接口,定义了add、remove、size等基础操作。其子接口Set和List分别强调元素唯一性和顺序性,而Queue则专注队列语义(FIFO/LIFO)。

关键设计点在于:集合操作的失败快速机制(fail-fast)。当遍历过程中集合被结构性修改(如添加/删除元素),Iterator会抛出ConcurrentModificationException,避免产生不可预测的遍历结果。例如:

失败快速示例

List list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
// 遍历时直接修改集合
for (String s : list) {
    if ("B".equals(s)) {
        list.remove(s); // 抛出ConcurrentModificationException
    }
}

正确做法是使用Iterator的remove方法:

安全删除方式

Iterator it = list.iterator();
while (it.hasNext()) {
    if ("B".equals(it.next())) {
        it.remove(); // 安全删除
    }
}

2.2 Map接口

Map存储键值对(key-value),通过put(K,V)、get(Object)等方法管理映射关系。其核心特性包括:

以HashMap为例,其put操作流程如下:

  1. 计算键的哈希值(hashCode)并进行扰动处理(h ^ (h >>> 16))
  2. 通过(n-1) & hash定位桶(bucket)索引
  3. 若桶为空,直接插入;若发生哈希冲突,则遍历链表/红黑树
  4. 当链表长度≥8且桶数≥64时,转为红黑树;否则扩容

这一机制解释了为何HashMap在JDK8中引入红黑树——当哈希分布不均导致链表过长时,O(n)查找退化为O(log n),显著提升性能。

三、列表实现类详解

3.1 ArrayList:动态数组的智慧

ArrayList底层是可变长数组,其扩容策略为:新容量 = 旧容量 × 1.5(通过oldCapacity + (oldCapacity >> 1)实现)。扩容操作涉及数组拷贝(System.arraycopy),代价高昂,因此建议在已知元素数量时预设初始容量:

容量预设对比

// 未预设:10次添加触发3次扩容(10→15→22→33)
List list1 = new ArrayList<>();
for (int i = 0; i < 33; i++) list1.add(i);
// 预设容量:0次扩容
List list2 = new ArrayList<>(33);
for (int i = 0; i < 33; i++) list2.add(i);

此外,ArrayList的remove(int index)操作时间复杂度为O(n)(需移动后续元素),而add(E)摊还复杂度为O(1)。在频繁删除场景中,可考虑使用LinkedList。

3.2 LinkedList:双向链表的灵活

LinkedList同时实现List和Deque接口,其节点结构为双向链表(JDK8起废弃了Entry类,改用Node内部类):

节点定义(简化版)

private static class Node {
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

关键优势在于:

典型应用场景包括:

但需注意:LinkedList的内存开销远高于ArrayList(每个节点需存储前后指针),在随机访问频繁的场景中性能较差。

3.3 Vector:历史的遗珠

Vector是JDK1.0时代的线程安全集合,其所有方法均被synchronized修饰,导致并发性能低下。现代开发中应避免使用,可替换为:

四、映射实现类深度剖析

4.1 HashMap:哈希表的艺术

HashMap的实现演进是JDK优化的缩影:

核心参数说明:

参数默认值说明
初始容量16必须为2的幂
负载因子0.75空间与时间的平衡点
树化阈值8链表转红黑树长度
去树化阈值6红黑树退化为链表长度
最小树化容量64桶数不足时不树化,仅扩容

扩容机制详解:

  1. 当size ≥ capacity × loadFactor时触发扩容
  2. 新容量 = 旧容量 × 2,旧元素需重新哈希(rehash)
  3. JDK8优化:利用(e.hash & oldCap) == 0判断元素是否迁移(避免重新计算哈希)

扩容性能对比(100万数据)

// JDK7:每次扩容需全量rehash
// JDK8:约50%元素无需迁移,性能提升约30%

4.2 LinkedHashMap:有序映射

LinkedHashMap通过维护双向链表实现访问顺序或插入顺序:

典型应用:缓存实现(removeEldestEntry重写可控制缓存大小)

LRU缓存示例

Map cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100; // 仅保留最近100条
    }
};

4.3 TreeMap:红黑树的严谨

TreeMap基于红黑树实现,所有操作时间复杂度为O(log n),支持自然排序或自定义比较器:

自定义排序

TreeMap map = new TreeMap<>((a, b) -> {
    int lenCompare = Integer.compare(a.length(), b.length());
    return lenCompare != 0 ? lenCompare : a.compareTo(b);
});

注意:TreeMap的键必须实现Comparable或传入Comparator,否则抛出ClassCastException。

五、集合实现类对比

5.1 HashSet:哈希表的极致

HashSet底层是HashMap的键集合(值统一为PRESENT常量),其特性完全继承自HashMap:

常见陷阱:未重写hashCode导致重复元素插入

错误示例

class Person {
    String name;
    Person(String n) { name = n; }
}
Set set = new HashSet<>();
set.add(new Person("Alice"));
set.add(new Person("Alice")); // 实际存储2个对象!

5.2 LinkedHashSet:有序集合

继承LinkedHashMap的有序特性,同时保持HashSet的哈希效率,适用于需保持插入顺序的去重场景。

5.3 TreeSet:有序去重

TreeSet基于TreeMap实现,元素必须可比较:

自然排序要求

class Student implements Comparable {
    String name;
    int score;
    public int compareTo(Student other) {
        return Integer.compare(this.score, other.score); // 按分数升序
    }
}

六、线程安全集合方案

6.1 传统方案:同步包装器

Collections.synchronizedList(new ArrayList<>())通过包装器模式添加synchronized锁,但遍历时仍需手动加锁:

安全遍历示例

List syncList = Collections.synchronizedList(new ArrayList<>());
synchronized (syncList) {
    for (String s : syncList) {
        System.out.println(s);
    }
}

6.2 并发集合:分而治之

ConcurrentHashMap的演进:

关键优化点:

  1. 〈减少锁粒度〉:从段锁→桶锁→无锁(CAS)
  2. 〈优化扩容〉:支持多线程并发扩容
  3. 〈计数器改进〉:用BaseCount+CounterCell数组避免竞争

ConcurrentHashMap vs HashMap性能对比

// 10线程写入100万数据
HashMap: 280ms(需外部同步)
ConcurrentHashMap: 190ms(内置并发支持)

6.3 新型选择:CopyOnWriteArrayList

写时复制机制:每次修改创建新数组,适用于读多写少场景(如监听器列表):

适用场景

// 1000次读 + 1次写:CopyOnWriteArrayList快3倍
// 1000次写 + 1次读:CopyOnWriteArrayList慢10倍(频繁拷贝)

七、性能优化实战策略

7.1 遍历方式对比

方式ArrayListLinkedList适用场景
for循环O(1)访问O(n)定位顺序访问
增强for同for循环同for循环通用
Iterator同for循环高效定位删除操作
Stream API并行流快并行流慢复杂计算

7.2 内存优化技巧

内存占用对比(100万整数)

ArrayList: ~40MB(对象头+引用+装箱)
int[]: ~4MB

7.3 高频陷阱规避

八、高频面试题精讲

Q1:HashMap的哈希冲突如何解决?

A:JDK8采用链地址法+红黑树优化。当链表长度≥8且桶数≥64时转为红黑树;扩容时若红黑树节点≤6则退化为链表。扰动函数将高位参与计算,降低冲突概率。

Q2:ConcurrentHashMap如何保证线程安全?

A:JDK8通过CAS操作更新baseCount计数器,桶操作用synchronized锁定头节点,扩容时支持多线程分段迁移。整个过程无全局锁,显著提升并发性能。

Q3:ArrayList和LinkedList选择依据?

A:
• 随机访问频繁→ArrayList
• 头尾操作频繁→LinkedList
• 中间插入/删除频繁→LinkedList
• 内存敏感→ArrayList
• 线程安全需求→用同步包装器或并发集合

Q4:如何实现线程安全的LRU缓存?

A:推荐方案:
1. LinkedHashMap(accessOrder=true)+ synchronized包装
2. ConcurrentHashMap + 自定义LRU逻辑
3. Guava Cache(生产级方案)