【Java入门指南 Day12:Java集合框架】
一、集合框架整体设计
Java集合框架像一个精心设计的工具箱,为不同的数据存储需求提供了专门的工具。
主要接口体系
// Collection接口体系
Collection
├── List(有序、可重复)
│ ├── ArrayList // 动态数组实现
│ ├── LinkedList // 双向链表实现
│ └── Vector // 线程安全的动态数组(已过时)
├── Set(无序、不可重复)
│ ├── HashSet // 基于HashMap实现
│ ├── TreeSet // 基于TreeMap实现
│ └── LinkedHashSet // 维护插入顺序
└── Queue(队列)
├── PriorityQueue // 优先队列
└── Deque // 双端队列
// Map接口体系(键值对映射)
Map
├── HashMap // 哈希表实现
├── TreeMap // 红黑树实现
└── LinkedHashMap // 维护插入顺序
二、ArrayList与LinkedList详解
ArrayList工作原理
public class ArrayList<E> {
// 底层使用数组存储
private Object[] elementData;
private int size;
// 动态扩容机制
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
// 扩容实现
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
LinkedList工作原理
public class LinkedList<E> {
// 节点定义
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
// 头尾节点
transient Node<E> first;
transient Node<E> last;
// 添加元素
public boolean add(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
return true;
}
}
性能对比
public class ListPerformanceTest {
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// 添加性能对比
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
System.out.println("ArrayList添加用时:" + (System.nanoTime() - startTime));
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
System.out.println("LinkedList添加用时:" + (System.nanoTime() - startTime));
// 随机访问性能对比
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
arrayList.get(i);
}
System.out.println("ArrayList访问用时:" + (System.nanoTime() - startTime));
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
linkedList.get(i);
}
System.out.println("LinkedList访问用时:" + (System.nanoTime() - startTime));
}
}
三、HashMap实现原理
基本结构
public class HashMap<K,V> {
// Node节点定义
static class Node<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
// 哈希桶数组
transient Node<K,V>[] table;
// 键值对数量
transient int size;
// 扩容阈值
int threshold;
// 负载因子
final float loadFactor;
}
工作原理
// 1. 计算key的哈希值
int hash = Objects.hashCode(key);
// 2. 定位桶位置
int index = (table.length - 1) & hash;
// 3. 处理哈希冲突
if (table[index] != null) {
// 链表形式存储
// 当链表长度超过8时,转换为红黑树
}
// 4. 自动扩容
if (size > threshold) {
resize();
}
四、TreeMap的红黑树结构
基本特性
public class TreeMapDemo {
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<>();
// 自动排序
map.put(3, "Three");
map.put(1, "One");
map.put(2, "Two");
// 输出是有序的
System.out.println(map); // {1=One, 2=Two, 3=Three}
// 范围操作
System.out.println(map.firstKey()); // 1
System.out.println(map.lastKey()); // 3
System.out.println(map.subMap(1, 3)); // {1=One, 2=Two}
}
}
五、并发集合类
ConcurrentHashMap
public class ConcurrentMapExample {
public static void main(String[] args) {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
// 线程安全的操作
map.put("count", 0);
// 原子操作
map.computeIfPresent("count", (k, v) -> v + 1);
// 批量操作
map.forEach(1, (k, v) ->
System.out.println(k + "=" + v));
}
}
CopyOnWriteArrayList
public class CopyOnWriteExample {
public static void main(String[] args) {
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
// 写时复制,适合读多写少的场景
list.add("A");
// 迭代时可以修改列表
for (String item : list) {
list.add("B"); // 不会抛出ConcurrentModificationException
}
}
}
最佳实践建议 💡
- 集合选择
- 频繁随机访问用ArrayList
- 频繁插入删除用LinkedList
- 需要排序用TreeMap/TreeSet
- 并发场景使用并发集合类
- 安全性
- 使用不可变集合
- 注意线程安全
- 防止内存泄漏
常见陷阱提醒 ⚠️
- 并发修改
// 错误:遍历时修改集合
for (String item : list) {
list.remove(item); // ConcurrentModificationException
}
// 正确:使用迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String item = it.next();
it.remove();
}
- 性能陷阱
// 不好的实践:频繁扩容
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10000000; i++) {
list.add(i);
}
// 好的实践:指定初始容量
ArrayList<Integer> list = new ArrayList<>(10000000);
for (int i = 0; i < 10000000; i++) {
list.add(i);
}
- 内存泄漏
// 可能导致内存泄漏
class Cache {
private Map<String, Object> map = new HashMap<>();
public void add(String key, Object value) {
map.put(key, value);
}
// 忘记实现删除方法
}
Java集合框架是日常编程中最常用的工具之一。理解每种集合的特点和适用场景,能够帮助我们写出更高效的代码。