Java的集合

⚡ Java集合体系全景概览

Java集合框架(Java Collections Framework, JCF)是Java标准库中最具设计智慧的部分之一,它为开发者提供了标准化的数据结构与算法实现,极大提升了开发效率与代码健壮性。该框架始于JDK 1.2,经过多次重构与增强,已形成层次清晰、职责分明、扩展性强的完整体系。其核心设计哲学遵循“接口与实现分离”,通过统一接口抽象共性行为,不同实现类针对特定场景做优化,这种设计既保障了API的稳定性,又为未来演进预留空间。

整个集合体系可划分为两大顶层接口:Collection与Map。前者用于存储单值元素集合,后者用于键值对映射。Collection下又细分为List(有序可重复)、Set(无序不可重复),而Map虽独立于Collection体系,但其视图(如keySet()、values()、entrySet())可与Collection无缝协作。值得注意的是,Queue与Deque作为特殊集合,虽实现Collection接口,但其语义更强调操作策略(如FIFO、LIFO),常被单独归类。

所有集合实现类均支持泛型(JDK 5引入),这不仅消除了显式类型转换的需要,更在编译期提供了类型安全检查,极大降低了ClassCastException风险。此外,集合类普遍实现了Cloneable与Serializable接口,支持对象复制与序列化传输,但需注意:浅拷贝(clone())仅复制引用,深拷贝需手动实现;序列化需显式声明serialVersionUID以保证版本兼容性。

集合类的线程安全性是另一个关键维度:大部分实现类(如ArrayList、HashMap)为非线程安全,适用于单线程或外部同步场景;而Vector、Hashtable等古老类虽线程安全,但因性能低下已被ConcurrentHashMap、CopyOnWriteArrayList等现代并发集合替代。JUC(java.util.concurrent)包的引入标志着Java集合进入高性能并发时代,其基于CAS与锁分离技术,实现了无锁或细粒度锁机制,显著提升吞吐量。

在内存管理层面,集合类的扩容策略直接影响性能表现。以ArrayList为例,其默认容量为10,扩容时按1.5倍增长(JDK 8起),若预知元素数量,建议通过构造器指定初始容量,避免多次扩容带来的数组复制开销。而HashMap的加载因子默认为0.75,是时间与空间成本的折中选择——过小导致频繁扩容,过大则哈希冲突增多。JDK 8起引入红黑树优化:当链表长度≥8且总容量≥64时,链表转为红黑树,将查询时间复杂度从O(n)降至O(log n),但插入/删除成本略增。

⚙️ List接口深度解析

List作为有序集合,严格维护元素插入顺序,支持通过索引(int)精确访问。其核心实现类包括ArrayList、LinkedList、Vector与Stack,各具鲜明特性,需结合场景选用。

〔ArrayList〕动态数组实现

  • 底层为Object[]数组,支持随机访问(get/set时间复杂度O(1))
  • 尾部插入/删除高效(均摊O(1)),但中间插入需移动后续元素(O(n))
  • 非线程安全,可通过Collections.synchronizedList()包装
  • 初始容量10,扩容1.5倍;建议预估容量避免扩容
  • JDK 8起支持Spliterator并行流处理,适合大数据集

〔LinkedList〕双向链表实现

  • 基于Node节点双向链表,每个节点含prev、item、next
  • 任意位置插入/删除O(1),但需先定位(索引访问O(n))
  • 可作为List、Queue、Deque三重角色使用
  • 内存开销大(每个节点额外存储两个引用)
  • 不支持随机访问,遍历应使用Iterator而非get(i)

〔Vector〕同步数组列表(已过时)

  • 与ArrayList结构相似,但方法均加synchronized
  • 扩容2倍增长,内存浪费严重
  • 仅遗留代码中可见,新项目应避免使用

〔Stack〕栈结构(不推荐)

  • 继承Vector,非栈专用设计
  • push/pop等操作同步但低效
  • JDK 6起推荐使用Deque实现栈(push/pop为O(1))

列表操作典型场景

当需要频繁随机访问(如读取第k个元素),ArrayList是首选;若插入/删除操作密集(如实现队列、双端队列),LinkedList更优。实际开发中,80%以上场景应优先考虑ArrayList——数组的缓存局部性优势在现代CPU架构下远超链表的理论O(1)优势。例如,遍历100万元素时,ArrayList耗时约8ms,LinkedList约25ms,差距显著。

以下为ArrayList扩容源码关键逻辑(JDK 11):

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

该设计平衡了内存效率与扩容频率:若扩容2倍,内存浪费严重;若1.25倍,则扩容过于频繁。实测表明,1.5倍在多数场景下综合性能最优。

〔Set〕无重复元素集合

Set继承自Collection,禁止重复元素(equals返回true即视为重复),底层由Map实现(元素作为key)。常见实现类包括HashSet、LinkedHashSet、TreeSet,各具独特特性。

〔HashSet〕哈希表实现

  • 基于HashMap,元素作为key,固定虚拟值PRESENT
  • 无序,允许null(仅一个)
  • 添加/查找/删除均摊O(1)
  • 初始容量16,加载因子0.75
  • JDK 8起链表转红黑树机制同HashMap

〔LinkedHashSet〕有序哈希集合

  • 继承HashSet,内部使用LinkedHashMap
  • 维护插入顺序(迭代顺序=插入顺序)
  • 性能略低于HashSet(多维护链表开销)
  • 适用于需去重且保序的场景

〔TreeSet〕有序树集合

  • 基于TreeMap,红黑树实现
  • 元素必须可比较(实现Comparable或传入Comparator)
  • 排序开销导致O(log n)时间复杂度
  • 支持范围查询(subSet、headSet、tailSet)
  • 不支持null(TreeMap禁止null键)

集合操作深度对比

特性HashSetLinkedHashSetTreeSet
顺序无序插入顺序自然/自定义排序
时间复杂度O(1)O(1)O(log n)
内存开销低中高
null支持允许1个允许1个禁止
适用场景快速去重去重+保序有序集合

自定义对象去重注意事项

当使用自定义类作为Set元素时,必须同时重写hashCode()与equals(),且二者需保持逻辑一致(hashCode相等则equals必须为true)。常见错误是仅重写equals而忽略hashCode,导致HashSet中出现重复元素。例如:

class Person {
    String name;
    int age;
    // 错误示例:仅重写equals
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
}

正确实现应补充hashCode:

@Override
public int hashCode() {
    return Objects.hash(name, age);
}

根据规范,若两个对象equals返回true,则其hashCode必须相同;反之则无需(不同对象可有相同hashCode)。违反此规则将导致HashSet失效——对象可能被存入错误的哈希桶,无法被正确检索。

〔Map〕键值对映射

Map提供键到值的映射关系,每个键最多映射一个值,且键不可重复。核心实现类包括HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap等,覆盖从单线程到高并发的全场景需求。

〔HashMap〕非线程安全映射

  • 基于数组+链表+红黑树(JDK 8)
  • 键/值可为null(null键存于索引0)
  • 初始容量16,加载因子0.75
  • 扩容时需重新哈希(rehash),成本高
  • 非线程安全,多线程用ConcurrentHashMap

〔LinkedHashMap〕有序映射

  • 继承HashMap,维护双向链表
  • 支持访问顺序(accessOrder=true)实现LRU缓存
  • 迭代顺序稳定(插入/访问顺序)
  • 内存开销略高于HashMap

〔TreeMap〕有序映射

  • 基于红黑树,键必须可比较
  • 支持范围查询(subMap、headMap、tailMap)
  • 时间复杂度O(log n)
  • 不支持null键

〔ConcurrentHashMap〕并发安全映射

  • JDK 7:分段锁(Segment),锁粒度粗
  • JDK 8:CAS + synchronized,锁粒度细
  • 支持高并发读写(读不加锁)
  • 线程安全,可替代Hashtable
  • 默认并发度16(CPU核心数)

Map遍历方式性能对比

遍历Map时,不同方式性能差异显著。实测100万元素HashMap遍历耗时:

最佳实践是使用entrySet()直接获取键值对:

for (Map.Entry entry : map.entrySet()) {
    K key = entry.getKey();
    V value = entry.getValue();
    // 处理逻辑
}

此方式避免了keySet()后二次调用get()的额外开销,是唯一线程安全的遍历方式(在单线程修改时)。若需并发修改,应使用ConcurrentHashMap的forEach方法。

HashMap扩容陷阱

HashMap扩容时,旧数组元素需重新哈希到新数组,此过程称为rehash。在多线程环境下,rehash可能导致链表成环(JDK 7),进而引发死循环。JDK 8通过尾插法改为头插法,但未彻底解决并发问题,因此仍需使用ConcurrentHashMap。

以下为扩容关键源码(JDK 8):

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = oldTab.length;
    int newCap = oldCap << 1; // 扩容2倍
    // ... 省略部分
    for (int j = 0; j < oldCap; ++j) {
        Node e = oldTab[j];
        if (e != null) {
            // 重新哈希到新位置
            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                ((TreeNode)e).split(...);
            else { // 链表处理
                Node loHead = null, loTail = null;
                Node hiHead = null, hiTail = null;
                Node next;
                do {
                    next = e.next;
                    if ((e.hash & oldCap) == 0) { // 保留在原索引
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    else { // 移动到新索引(原索引+oldCap)
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                // ... 设置新链表
            }
        }
    }
    return newTab;
}

该算法利用哈希值高位判断元素迁移位置,避免对所有元素重新计算hash,提升扩容效率。但多线程同时扩容仍会导致数据丢失,这是HashMap不适用于并发场景的根本原因。

♀ 线程安全集合详解

Java集合的线程安全实现历经三代演进:早期同步容器(Vector/Hashtable)、集合包装器(Collections.synchronizedXxx)、现代并发集合(JUC包)。选择不当将导致性能瓶颈或数据不一致。

〔Vector/Hashtable〕同步容器

  • 方法级synchronized,锁粒度粗
  • 迭代时需外部同步(ConcurrentModificationException)
  • 扩容时整表锁定,吞吐量极低
  • 已过时,仅用于兼容旧代码

〔Collections.synchronizedXxx〕包装器

  • 通过同步包装器返回线程安全集合
  • 迭代仍需手动同步(synchronized(map))
  • 仅适用于低并发场景

〔CopyOnWriteArrayList〕写时复制列表

  • 写操作复制新数组,读操作无锁
  • 适用于读多写少场景(如监听器列表)
  • 写时内存 spike,不适合大数据量
  • 迭代器快照机制,不抛ConcurrentModificationException

〔ConcurrentHashMap〕高并发映射

  • JDK 8:CAS + synchronized,锁分离
  • 读操作无锁(volatile保证可见性)
  • 支持高并发put/get/remove
  • 批量操作(forEach、search)支持并行

线程安全集合选择决策树

面对并发需求,应按以下逻辑选择:

  1. 是否需要Map?→ 是 → ConcurrentHashMap
  2. 是否需要List?→ 是 → CopyOnWriteArrayList(读多写少)或 Collections.synchronizedList(低并发)
  3. 是否需要Set?→ 是 → ConcurrentHashMap.newKeySet()或Collections.synchronizedSet(new HashSet<>())
  4. 是否需要Queue?→ 是 → ConcurrentLinkedQueue(无界)或 LinkedBlockingQueue(有界)

特别注意:ConcurrentHashMap的size()与isEmpty()在JDK 8中为估算值(非强一致),若需精确计数,应使用mappingCount()返回long类型。此外,批量操作(如putAll)并非原子,多线程下可能出现部分更新。

迭代器安全机制

非线程安全集合(如ArrayList)的迭代器采用fail-fast机制:当检测到结构修改(modCount != expectedModCount),立即抛出ConcurrentModificationException。此机制仅保证快速失败,非线程安全保证!

示例错误用法:

// 多线程环境下遍历ArrayList
new Thread(() -> {
    for (String s : list) {
        System.out.println(s);
    }
}).start();
new Thread(() -> {
    list.add("new"); // 可能触发ConcurrentModificationException
}).start();

正确做法:使用CopyOnWriteArrayList或外部同步:

new Thread(() -> {
    synchronized(list) {
        for (String s : list) {
            System.out.println(s);
        }
    }
}).start();

♂ 性能优化实战指南

集合操作性能瓶颈常源于不合理的容量预估、错误的遍历方式及忽略线程安全。以下为高频优化策略:

〔容量预估〕避免动态扩容

ArrayList初始容量10,HashMap初始容量16。若预知元素数量,应通过构造器指定初始容量:

// 错误:未预估容量
List list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    list.add("item" + i);
}
// 正确:预估容量
List list = new ArrayList<>(100000);

对于HashMap,初始容量应为预期元素数 / 加载因子 + 1,并确保是2的幂(内部自动处理)。例如100000元素,推荐初始容量=100000/0.75+1≈133334,向上取2的幂为131072。

〔遍历优化〕选择高效方式

遍历Map时,entrySet()比keySet()快40%以上;遍历List时,for-each与iterator()性能相当,但避免索引遍历(LinkedList为O(n²)):

// 高效:entrySet()
for (Map.Entry e : map.entrySet()) { ... }
// 低效:keySet() + get()
for (K k : map.keySet()) { V v = map.get(k); ... }

〔并发优化〕合理选择集合

多线程场景下,避免使用Vector/Hashtable。高并发读写推荐ConcurrentHashMap;读多写少用CopyOnWriteArrayList;队列操作用ConcurrentLinkedQueue。

〔内存优化〕避免装箱开销

使用基本类型数组(int[])替代包装类型(Integer[]),可减少70%内存占用。集合无法直接存储基本类型,但可通过第三方库(如Trove、FastUtil)实现高效原生类型集合:

// 标准库:Integer对象占用24字节(含对象头)
List list = new ArrayList<>();
// FastUtil:int[]数组仅需4字节/元素
IntArrayList list = new IntArrayList(100000);

〔面试高频考点〕

集合是Java面试必考内容,常结合源码、并发、性能综合考察。以下为核心高频问题:

HashMap与HashTable区别
HashMap线程安全
ConcurrentHashMap原理
ArrayList与LinkedList
HashSet去重原理

〔HashMap与HashTable区别〕

  • 线程安全:HashMap非线程安全,HashTable方法同步
  • null支持:HashMap允许1个null键、多个null值;HashTable禁止null
  • 性能:HashTable同步开销大,HashMap高效
  • 继承:HashTable继承Dictionary(过时),HashMap继承AbstractMap
  • 容量:HashMap初始16,HashTable初始11

现代开发应使用ConcurrentHashMap替代HashTable,而非Vector。

〔HashMap线程安全〕

  • 多线程读写必用ConcurrentHashMap
  • 单线程读、多线程写:用Collections.synchronizedMap
  • 高并发读多写少:CopyOnWriteArrayList替代List
  • 注意:fail-fast非线程安全保证!

〔ConcurrentHashMap原理〕

  • JDK 7:Segment分段锁(16个Segment)
  • JDK 8:CAS + synchronized,锁分离
  • 读操作无锁(volatile field)
  • 扩容时多线程协作(帮助迁移)
  • 计数器使用LongAdder避免竞争

〔ArrayList与LinkedList〕

  • 随机访问:ArrayList快(O(1)),LinkedList慢(O(n))
  • 插入/删除:LinkedList快(O(1)),ArrayList慢(O(n))
  • 内存:ArrayList紧凑,LinkedList节点额外开销
  • 实际性能:ArrayList通常更快(缓存局部性)

〔HashSet去重原理〕

  • 基于HashMap,元素作为key
  • 依赖equals()与hashCode()一致性
  • 添加时先查hashCode,再比equals
  • 重写对象时必须同时重写二者