Java 集合框架详解笔记

1. HashMap

基本特性

• 实现方式：数组 + 链表/红黑树（JDK8+）
• 线程安全：非线程安全
• 键值对：允许null键和null值
• 顺序：不保证插入顺序

核心源码结构

// JDK 8+ 节点结构
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

应用场景

• 缓存系统：快速键值查找
• 数据索引：建立对象间的映射关系
• 配置存储：存储应用配置参数
• 统计计数：使用merge()方法进行频次统计

代码示例

// 基本使用
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

// 统计词频
String text = "apple banana apple";
String[] words = text.split(" ");
HashMap<String, Integer> wordCount = new HashMap<>();
for (String word : words) {
    wordCount.merge(word, 1, Integer::sum);
}

注意事项

• 初始容量：根据预估数据量设置合理初始容量
• 负载因子：默认0.75，影响扩容时机
• 并发修改：多线程环境下需要使用ConcurrentHashMap
• 键对象：必须正确实现hashCode()和equals()方法

2. HashTable

基本特性

• 线程安全：所有方法使用synchronized修饰
• 键值对：不允许null键和null值
• 性能：由于同步开销，性能较低
• 遗留类：已被ConcurrentHashMap取代

应用场景

• 遗留系统：维护老代码兼容性
• 简单同步：不需要高性能的简单同步场景

代码示例

Hashtable<String, String> table = new Hashtable<>();
table.put("key1", "value1");
table.put("key2", "value2");

// 同步遍历
synchronized(table) {
    for (String key : table.keySet()) {
        System.out.println(key + ": " + table.get(key));
    }
}

注意事项

• 性能问题：同步粒度太粗，影响性能
• 过时类：新代码推荐使用ConcurrentHashMap
• null限制：插入null会抛出NullPointerException

3. Queue

队列体系结构

Queue接口
├── LinkedList (双向队列)
├── PriorityQueue (优先级队列)
├── ArrayDeque (数组双端队列)
└── BlockingQueue接口
    ├── ArrayBlockingQueue
    ├── LinkedBlockingQueue
    └── PriorityBlockingQueue

主要实现对比

LinkedList

• 特性：基于链表，可作队列、双端队列、栈
• 应用：通用队列场景，需要频繁在两端操作

ArrayDeque

• 特性：基于循环数组，性能优于LinkedList
• 应用：栈和队列操作，高性能要求场景

PriorityQueue

• 特性：基于堆，元素按优先级排序
• 应用：任务调度，需要按优先级处理的场景

代码示例

// 队列操作
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);  // 入队
queue.poll();    // 出队

// 优先级队列
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // 输出: 1, 3, 5
}

// 双端队列
Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);  // 头部添加
deque.offerLast(2);   // 尾部添加

应用场景

• 任务队列：线程池任务调度
• 消息队列：生产者-消费者模式
• 缓存淘汰：LRU缓存实现
• 广度优先搜索：图算法中的节点遍历

注意事项

• 队列选择：根据具体需求选择合适的队列实现
• 边界处理：注意队列为空时的操作行为
• 线程安全：普通队列非线程安全，并发场景使用阻塞队列

4. ArrayList vs LinkedList

核心区别对比

源码结构对比

ArrayList

// 内部数组
transient Object[] elementData;
// 扩容机制
private void grow(int minCapacity) {
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
}

LinkedList

// 节点结构
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}
// 头尾指针
transient Node<E> first;
transient Node<E> last;

应用场景

ArrayList 适用场景

• 频繁查询：需要大量随机访问操作
• 数据遍历：顺序访问大量数据
• 内存敏感：对内存使用有严格要求
• 数值计算：存储基本数据类型（配合包装类）

LinkedList 适用场景

• 频繁插入删除：在列表中间频繁添加删除元素
• 队列操作：实现队列、双端队列、栈
• 不确定大小：数据量动态变化较大
• 实现算法：某些特定算法如LRU缓存

代码示例

// ArrayList - 适合随机访问
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    arrayList.add(i); // 快速尾部插入
}
int value = arrayList.get(500000); // 快速随机访问

// LinkedList - 适合频繁修改
LinkedList<Integer> linkedList = new LinkedList<>();
ListIterator<Integer> it = linkedList.listIterator();
while (it.hasNext()) {
    if (someCondition) {
        it.add(newElement); // 在迭代中高效插入
    }
}

性能测试示例

// 插入性能对比
long start = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    list.add(0, i); // 头部插入
}
long end = System.nanoTime();
System.out.println("Time: " + (end - start) + " ns");

注意事项

ArrayList 注意事项

• 初始容量：预估数据量设置合理初始大小
• 扩容成本：扩容时涉及数组拷贝，影响性能
• 删除操作：删除元素可能导致大量数据移动
• 内存浪费：trimToSize()可释放多余空间

LinkedList 注意事项

• 内存开销：每个元素有额外节点开销
• 访问性能：避免使用get(index)随机访问
• 迭代器：使用ListIterator进行高效遍历和修改
• 缓存不友好：数据不连续，缓存命中率低

总结与选择指南

集合选择决策树

需要存储键值对？
├── 需要线程安全？ → ConcurrentHashMap
├── 需要排序？ → TreeMap
└── 普通映射 → HashMap

需要列表？
├── 频繁随机访问？ → ArrayList
├── 频繁插入删除？ → LinkedList
└── 需要线程安全？ → CopyOnWriteArrayList

需要队列？
├── 优先级排序？ → PriorityQueue
├── 高性能双端操作？ → ArrayDeque
├── 线程安全阻塞？ → BlockingQueue实现
└── 通用队列 → LinkedList

最佳实践

1. 预估容量：初始化时设置合理容量避免扩容
2. 选择接口：编程时面向接口而非实现
3. 线程安全：明确并发需求，选择合适的同步集合
4. 性能测试：关键路径进行性能测试验证选择
5. 代码可读性：选择最能表达意图的集合类型

常见陷阱

• 在LinkedList中使用get(index)进行随机访问
• 在多线程环境中使用非同步集合
• 忽略集合的初始容量设置导致频繁扩容
• 在频繁修改的场景使用CopyOnWriteArrayList

这份笔记涵盖了主要集合类的核心特性、区别和应用场景，可以作为日常开发和面试准备的参考资料。