集合框架概述

集合框架概述

Java集合框架（Java Collections Framework, JCF）是Java语言中用于存储、操作和聚合一组对象的核心API。它提供了一套标准化的接口和类，简化了数据结构的实现，并支持高效的数据操作。集合框架是Java基础中最重要的组成部分之一，广泛应用于企业级开发、算法实现和数据处理场景。

核心设计目标

• 通用性：通过泛型支持不同类型元素的存储
• 高性能：针对不同场景优化数据结构的实现
• 可扩展：允许开发者自定义集合实现
• 互操作性：集合之间可以方便地转换

体系结构

Java集合框架主要由以下部分组成：

classDiagram Collection <|-- List Collection <|-- Set Collection <|-- Queue List <|-- ArrayList List <|-- LinkedList Set <|-- HashSet Set <|-- TreeSet Queue <|-- PriorityQueue Map <|-- HashMap Map <|-- TreeMap class Collection{ <<interface>> +add() +remove() +size() } class Map{ <<interface>> +put() +get() +keySet() }

主要接口层次

• Collection接口：所有集合类的根接口
• List接口：有序、可重复的集合
• Set接口：无序、不可重复的集合
• Queue接口：队列实现
• Map接口：键值对映射（严格来说不属于Collection体系）

核心实现类

以下是常用的具体实现类及其特性对比：

集合类特性比较

接口	实现类	特性	时间复杂度（平均）
ArrayList | 动态数组，随机访问快 | get/set: O(1) add/remove: O(n)
LinkedList | 双向链表，插入删除快 | get/set: O(n) add/remove: O(1)
HashSet | 哈希表实现，无序 | 基本操作: O(1)
TreeSet | 红黑树实现，有序 | 基本操作: O(log n)
HashMap | 哈希表实现 | 基本操作: O(1)
TreeMap | 红黑树实现，键有序 | 基本操作: O(log n)

基础代码示例

ArrayList基本操作

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

public class CollectionDemo {
    public static void main(String[] args) {
        // 创建ArrayList
        List<String> fruits = new ArrayList<>();
        
        // 添加元素
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        
        // 访问元素
        System.out.println("第二个水果: " + fruits.get(1)); // 输出: Banana
        
        // 遍历集合
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
        /* 输出:
           Apple
           Banana
           Orange
        */
    }
}

HashMap使用示例

import java.util.HashMap;
import java.util.Map;

public class MapDemo {
    public static void main(String[] args) {
        // 创建HashMap
        Map<String, Integer> studentScores = new HashMap<>();
        
        // 添加键值对
        studentScores.put("Alice", 95);
        studentScores.put("Bob", 88);
        studentScores.put("Charlie", 91);
        
        // 获取值
        System.out.println("Bob的分数: " + studentScores.get("Bob")); // 输出: 88
        
        // 遍历Map
        for (Map.Entry<String, Integer> entry : studentScores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        /* 可能输出:
           Alice: 95
           Bob: 88
           Charlie: 91
        */
    }
}

实际应用场景

场景1：数据去重

使用Set实现自动去重：

import java.util.HashSet;
import java.util.Set;

public class Deduplication {
    public static void main(String[] args) {
        String[] duplicates = {"A", "B", "A", "C", "B"};
        Set<String> unique = new HashSet<>();
        
        for (String item : duplicates) {
            unique.add(item);
        }
        
        System.out.println(unique); // 输出: [A, B, C]
    }
}

场景2：词频统计

使用Map实现词频统计：

import java.util.HashMap;
import java.util.Map;

public class WordFrequency {
    public static void main(String[] args) {
        String text = "hello world hello java world java";
        String[] words = text.split(" ");
        Map<String, Integer> frequency = new HashMap<>();
        
        for (String word : words) {
            frequency.put(word, frequency.getOrDefault(word, 0) + 1);
        }
        
        System.out.println(frequency); 
        // 输出: {world=2, java=2, hello=2}
    }
}

性能考量

选择集合类时应考虑以下因素：

• 访问模式：随机访问（ArrayList） vs 顺序访问（LinkedList）
• 数据规模：大数据量时考虑时间复杂度
• 线程安全：非线程安全类性能更好，多线程环境需使用并发集合
• 内存占用：不同实现有不同的内存开销

时间复杂度总结：

• ArrayList：随机访问O(1)，插入删除O(n)
• LinkedList：随机访问O(n)，插入删除O(1)
• HashSet/HashMap：基本操作O(1)
• TreeSet/TreeMap：基本操作O(log n)

最佳实践

1. 优先使用接口类型声明集合变量 2. 初始化时指定初始容量（特别对于大型集合） 3. 使用泛型确保类型安全 4. 遍历集合时考虑使用迭代器或forEach 5. 需要排序时考虑TreeSet/TreeMap 6. 多线程环境使用并发集合（如ConcurrentHashMap）

数学基础

集合框架的部分实现基于数学概念：

哈希表容量通常选择质数，因为当哈希表的大小为质数时，简单的取模哈希函数能更均匀地分布键。

哈希碰撞概率公式（生日问题）： $p(n;d)\approx 1-e^{-n(n-1)/(2d)}$ 其中：

• d = 哈希表大小
• n = 存储的元素数量

红黑树的高度保证（n个节点的红黑树）： $h\le 2{\log }_2(n+1)$

常见问题

Q: ArrayList和LinkedList如何选择？ A: 频繁随机访问用ArrayList，频繁插入删除用LinkedList

Q: HashMap的负载因子是什么？ A: 默认0.75，表示当哈希表填充到75%时会自动扩容

Q: 如何使自定义类可作为HashMap的键？ A: 必须正确重写hashCode()和equals()方法

Q: ConcurrentModificationException是什么？ A: 在迭代集合时直接修改集合（非通过迭代器）会抛出此异常

总结

Java集合框架提供了丰富的数据结构实现，理解各集合类的特性和适用场景对于编写高效、可维护的代码至关重要。初学者应从基本接口开始，逐步掌握各种实现类的特点，最终能够根据具体需求选择最合适的集合类型。