Java集合框架

概述

Java集合框架（Java Collections Framework）是Java中用于存储和操作对象集合的统一架构。它提供了一套设计良好的接口和实现类，用于处理不同类型的数据集合。

集合框架层次结构

Collection接口层次

Collection
├── List（有序，可重复）
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector
├── Set（无序，不可重复）
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
└── Queue（队列）
    ├── PriorityQueue
    └── Deque
        └── ArrayDeque

Map接口层次

Map（键值对）
├── HashMap
├── LinkedHashMap
├── TreeMap
└── Hashtable

List接口及实现

ArrayList

底层实现：动态数组
特点：
- 随机访问速度快（O(1)）
- 插入和删除操作较慢（O(n)）
- 线程不安全
- 默认初始容量为10

java

List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");
arrayList.get(0); // 快速随机访问

List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");
arrayList.get(0); // 快速随机访问

LinkedList

底层实现：双向链表
特点：
- 插入和删除操作快（O(1)）
- 随机访问较慢（O(n)）
- 线程不安全
- 实现了List和Deque接口

java

List<String> linkedList = new LinkedList<>();
linkedList.add("Java");
linkedList.addFirst("Python"); // 头部插入
linkedList.addLast("C++");     // 尾部插入

List<String> linkedList = new LinkedList<>();
linkedList.add("Java");
linkedList.addFirst("Python"); // 头部插入
linkedList.addLast("C++");     // 尾部插入

Vector

底层实现：动态数组
特点：
- 线程安全（方法使用synchronized修饰）
- 性能较ArrayList差
- 扩容时容量翻倍

Set接口及实现

HashSet

底层实现：HashMap
特点：
- 无序，不可重复
- 允许null值
- 线程不安全
- 查找速度快（O(1)）

java

Set<String> hashSet = new HashSet<>();
hashSet.add("Java");
hashSet.add("Python");
hashSet.add("Java"); // 重复元素不会被添加

Set<String> hashSet = new HashSet<>();
hashSet.add("Java");
hashSet.add("Python");
hashSet.add("Java"); // 重复元素不会被添加

LinkedHashSet

底层实现：HashMap + 双向链表
特点：
- 保持插入顺序
- 其他特性与HashSet相同

TreeSet

底层实现：红黑树
特点：
- 有序（自然排序或自定义排序）
- 不允许null值
- 查找、插入、删除时间复杂度为O(log n)

java

Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);
// 输出：[1, 2, 3] 自动排序

Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);
// 输出：[1, 2, 3] 自动排序

Map接口及实现

HashMap

底层实现：数组 + 链表 + 红黑树（JDK 1.8+）
特点：
- 键值对存储
- 允许null键和null值
- 线程不安全
- 查找速度快（平均O(1)）

java

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Java", 25);
hashMap.put("Python", 30);
hashMap.get("Java"); // 返回25

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Java", 25);
hashMap.put("Python", 30);
hashMap.get("Java"); // 返回25

LinkedHashMap

底层实现：HashMap + 双向链表
特点：
- 保持插入顺序或访问顺序
- 可用于实现LRU缓存

TreeMap

底层实现：红黑树
特点：
- 按键排序
- 不允许null键
- 时间复杂度为O(log n)

Hashtable

底层实现：数组 + 链表
特点：
- 线程安全
- 不允许null键和null值
- 性能较HashMap差

集合工具类

Collections类

提供了许多静态方法来操作集合：

java

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5);

// 排序
Collections.sort(list);

// 反转
Collections.reverse(list);

// 查找
int index = Collections.binarySearch(list, 4);

// 创建不可变集合
List<Integer> unmodifiableList = Collections.unmodifiableList(list);

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5);

// 排序
Collections.sort(list);

// 反转
Collections.reverse(list);

// 查找
int index = Collections.binarySearch(list, 4);

// 创建不可变集合
List<Integer> unmodifiableList = Collections.unmodifiableList(list);

Arrays类

提供了数组操作的工具方法：

java

int[] array = {3, 1, 4, 1, 5};

// 排序
Arrays.sort(array);

// 转换为List
List<Integer> list = Arrays.asList(1, 2, 3);

// 填充
Arrays.fill(array, 0);

int[] array = {3, 1, 4, 1, 5};

// 排序
Arrays.sort(array);

// 转换为List
List<Integer> list = Arrays.asList(1, 2, 3);

// 填充
Arrays.fill(array, 0);

性能比较

操作	ArrayList	LinkedList	HashMap	TreeMap
随机访问	O(1)	O(n)	O(1)	O(log n)
插入/删除（头部）	O(n)	O(1)	O(1)	O(log n)
插入/删除（尾部）	O(1)	O(1)	O(1)	O(log n)
查找	O(n)	O(n)	O(1)	O(log n)

选择建议

需要快速随机访问：选择ArrayList
频繁插入删除：选择LinkedList
需要去重且不关心顺序：选择HashSet
需要排序：选择TreeSet或TreeMap
需要键值对存储：选择HashMap
线程安全要求：使用Collections.synchronizedXxx()或ConcurrentHashMap

总结

Java集合框架提供了丰富的数据结构实现，理解各种集合的特点和适用场景对于编写高效的Java程序至关重要。在实际开发中，应根据具体需求选择合适的集合类型。