集合性能分析
集合性能取决于底层数据结构和操作类型，选择合适的集合对性能至关重要。
List 性能对比
时间复杂度
| 操作 | ArrayList | LinkedList |
|---|---|---|
| get(index) | O(1) | O(n) |
| add(末尾) | O(1) | O(1) |
| add(头部) | O(n) | O(1) |
| add(中间) | O(n) | O(n) |
| remove(末尾) | O(1) | O(1) |
| remove(头部) | O(n) | O(1) |
| remove(中间) | O(n) | O(n) |
| contains | O(n) | O(n) |
ArrayList 性能分析
Java
// 查询快：索引直接定位
list.get(1000); // O(1)，无需遍历
// 中间插入慢：需移动后续元素
list.add(500, "new"); // O(n)，移动 500 个元素
// 扩容开销
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add(i); // 默认容量 10，多次扩容
}
// 优化：预设容量
List<Integer> list = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
list.add(i); // 无扩容，性能提升
}
LinkedList 性能分析
Java
// 头部操作快
list.addFirst("head"); // O(1)
list.removeFirst(); // O(1)
// 中间操作慢：需遍历定位
list.add(500, "new"); // O(n)，先遍历到位置 500
// 随机访问慢
list.get(50000); // O(n)，遍历 50000 次
Set 性能对比
时间复杂度
| 操作 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| add | O(1) | O(1) | O(log n) |
| remove | O(1) | O(1) | O(log n) |
| contains | O(1) | O(1) | O(log n) |
HashSet 性能分析
Java
Set<Integer> set = new HashSet<>();
set.add(100); // O(1)，哈希定位
set.contains(100); // O(1)，哈希定位
set.remove(100); // O(1)，哈希定位
// 哈希冲突影响性能
Set<String> set = new HashSet<>();
for (int i = 0; i < 100000; i++) {
set.add("key" + i); // 理想 O(1)，冲突时略有下降
}
HashSet 性能影响因素：hashCode 质量、哈希冲突程度、容量和负载因子。
TreeSet 性能分析
Java
TreeSet<Integer> set = new TreeSet<>();
set.add(100); // O(log n)，红黑树插入
set.contains(100); // O(log n)，红黑树查找
// 排序功能有代价
// 10 万元素：HashSet 约 10ms，TreeSet 约 50ms
Map 性能对比
时间复杂度
| 操作 | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| get | O(1) | O(1) | O(log n) |
| put | O(1) | O(1) | O(log n) |
| remove | O(1) | O(1) | O(log n) |
HashMap 性能优化
Java
// 默认：容量 16，负载因子 0.75
Map<String, Integer> map = new HashMap<>();
// 预设容量避免扩容（推荐）
int expectedSize = 10000;
Map<String, Integer> map = new HashMap<>(expectedSize);
// 实际容量公式：(expectedSize / 0.75) + 1
Map<String, Integer> map = new HashMap<>((int)(10000 / 0.75) + 1);
// 大量数据测试
// 10 万次 put：预设容量约 20ms，默认容量约 50ms（多次扩容）
扩容开销：每次扩容需重新计算所有元素位置，性能下降明显。
HashMap JDK 8 优化
- 链表长度 > 8 且容量 > 64 → 转红黑树
- 红黑树查找 O(log n)，链表查找 O(n)
- 哈希冲突严重时性能提升
集合选择原则
List 选择
| 场景 | 推荐 | 原因 |
|---|---|---|
| 频繁随机访问 | ArrayList | O(1) 查询 |
| 频繁头部插入删除 | LinkedList | O(1) 头部操作 |
| 预知元素数量 | ArrayList(预设容量) | 避免扩容 |
| 线程安全需求 | CopyOnWriteArrayList | 读多写少 |
Set 选择
| 场景 | 推荐 | 原因 |
|---|---|---|
| 一般去重 | HashSet | O(1) 性能最高 |
| 去重+保持顺序 | LinkedHashSet | 插入顺序 |
| 去重+排序 | TreeSet | 自然排序 |
| 高并发去重 | ConcurrentHashMap.keySet() | 并发安全 |
Map 选择
| 场景 | 推荐 | 原因 |
|---|---|---|
| 一般键值存储 | HashMap | O(1) 性能最高 |
| 有序键值存储 | LinkedHashMap | 插入/访问顺序 |
| 排序键值存储 | TreeMap | 自然排序 |
| 高并发键值存储 | ConcurrentHashMap | 并发安全 |
性能优化建议
- 预设容量：ArrayList/HashMap 预知元素数量时设置初始容量
- 选择合适实现：根据操作特点选择 ArrayList/LinkedList、HashSet/TreeSet
- 避免频繁扩容：HashMap 扩容开销大，预设容量
- 使用并发集合：多线程环境用 ConcurrentHashMap 替代 synchronizedMap
- hashCode 质量：自定义对象实现好的 hashCode 减少冲突
要点总结
- ArrayList 查询 O(1)，插入删除 O(n)
- LinkedList 头部操作 O(1)，查询 O(n)
- HashSet/HashMap O(1)，TreeSet/TreeMap O(log n)
- ArrayList/HashMap 预设容量避免扩容
- 频繁随机访问用 ArrayList，频繁头部操作用 LinkedList
- 一般场景用 HashSet/HashMap，排序用 TreeSet/TreeMap
- 高并发用 ConcurrentHashMap
📝 发现内容有误？点击此处直接编辑