知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# Java 集合框架深度解析 > 面向面试与生产实践的完整指南 --- ## 目录 1. [集合框架总览](#1-集合框架总览) 2. [List:ArrayList vs LinkedList](#2-list) 3. [HashMap 深度解析](#3-hashmap-深度解析) 4. [Map 家族对比](#4-map-家族对比) 5. [Set 家族](#5-set-家族) 6. [Queue / Deque](#6-queue--deque) 7. [Collections 工具类](#7-collections-工具类) 8. [Fail-fast vs Fail-safe 迭代器](#8-fail-fast-vs-fail-safe-迭代器) 9. [如何选择合适的集合](#9-如何选择合适的集合) 10. [面试高频 Q&A](#10-面试高频-qa) --- ## 1. 集合框架总览  *图:Collection 与 Map 两大体系的继承关系* ``` java.lang.Iterable └── java.util.Collection ├── List(有序、可重复) │ ├── ArrayList │ ├── LinkedList │ └── Vector(线程安全,已过时) ├── Set(无序、不可重复) │ ├── HashSet │ │ └── LinkedHashSet │ └── SortedSet │ └── TreeSet └── Queue(队列) ├── LinkedList ├── PriorityQueue └── Deque ├── ArrayDeque └── LinkedList java.util.Map(键值对,独立体系) ├── HashMap │ └── LinkedHashMap ├── SortedMap │ └── TreeMap └── Hashtable(线程安全,已过时) ``` --- ## 2. List ### ArrayList **底层:动态数组(Object[])** ```java // 核心字段 transient Object[] elementData; // 存储元素的数组 private int size; // 实际元素个数 // 默认初始容量 10,首次 add 时才分配 ``` **扩容机制:** - 触发条件:`size == elementData.length` - 扩容倍数:**1.5 倍**(`oldCapacity + (oldCapacity >> 1)`) - 扩容操作:`Arrays.copyOf()` 复制到新数组 **时间复杂度:** | 操作 | 复杂度 | 说明 | |------|--------|------| | `get(index)` | O(1) | 随机访问,直接寻址 | | `add(E)` 末尾 | O(1) 均摊 | 偶尔触发扩容 O(n) | | `add(index, E)` | O(n) | 需要移动后续元素 | | `remove(index)` | O(n) | 需要移动后续元素 | | `contains(E)` | O(n) | 线性扫描 | ### LinkedList **底层:双向链表** ```java static class Node<E> { E item; Node<E> next; Node<E> prev; } ``` | 操作 | 复杂度 | |------|--------| | `get(index)` | O(n) | | `add(E)` 末尾 | O(1) | | `addFirst(E)` | O(1) | | `removeFirst/Last` | O(1) | ### ArrayList vs LinkedList | 维度 | ArrayList | LinkedList | |------|-----------|------------| | 底层结构 | 动态数组 | 双向链表 | | 随机访问 | O(1) ✅ | O(n) ❌ | | 头部插入/删除 | O(n) ❌ | O(1) ✅ | | 内存占用 | 紧凑,有预留空间 | 每节点额外两个指针 | | 缓存友好性 | ✅ 连续内存 | ❌ 节点分散 | **结论:90% 的场景用 ArrayList,LinkedList 仅在明确需要 O(1) 头部操作时使用。** --- ## 3. HashMap 深度解析 ### 底层数据结构 **JDK 8:数组 + 链表 + 红黑树** ```java // 核心字段 transient Node<K,V>[] table; // 哈希桶数组 transient int size; // 键值对数量 int threshold; // 扩容阈值 = capacity * loadFactor final float loadFactor; // 负载因子,默认 0.75 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16 static final int TREEIFY_THRESHOLD = 8; // 链表转红黑树阈值 static final int UNTREEIFY_THRESHOLD = 6; // 红黑树退化为链表阈值 static final int MIN_TREEIFY_CAPACITY = 64; // 树化最小数组容量 ``` ### hash() 计算 ```java static final int hash(Object key) { int h; // 高16位与低16位异或:扰动函数,减少碰撞 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 计算数组下标(n 为数组长度,必须是2的幂次) int index = (n - 1) & hash; // 等价于 hash % n,但位运算更快 ``` **为什么高16位与低16位异或?** 数组长度通常较小,`(n-1) & hash` 只用到 hash 的低位。通过将高16位混入低16位,让高位信息也参与寻址,降低哈希碰撞概率。 ### put() 流程  *图:HashMap put 的定位、插入与扩容判断流程* ``` put(key, value) ↓ 计算 hash(key) ↓ table 为空? → resize() 初始化 ↓ 计算 index = (n-1) & hash ↓ table[index] 为空? → 直接插入 Node ↓ table[index] 不为空: ├── key 相同? → 覆盖 value ├── 是 TreeNode? → 红黑树插入 └── 是链表? → 遍历尾插,长度≥8且容量≥64则树化 ↓ size > threshold? → resize() 扩容 ``` ### 扩容机制 **触发条件:** `size > capacity * 0.75`(默认:`size > 16 * 0.75 = 12`) **JDK 8 的优化——不需要重新计算 hash:** ``` 旧容量 = 16,新容量 = 32 元素的新位置只有两种情况: - hash & 旧容量 == 0 → 位置不变(仍在原 index) - hash & 旧容量 != 0 → 新位置 = 原 index + 旧容量 ``` ### 负载因子为什么是 0.75? - 负载因子过小(如0.5):内存浪费,扩容频繁 - 负载因子过大(如1.0):哈希冲突增多,链表变长 - 0.75:根据泊松分布,链表长度超过8的概率约为 0.00000006,极低 ### 链表转红黑树条件 **同时满足两个条件才树化:** 1. 链表长度 ≥ 8(`TREEIFY_THRESHOLD = 8`) 2. 数组长度 ≥ 64(`MIN_TREEIFY_CAPACITY = 64`) 若数组长度 < 64,优先扩容而非树化。 ### JDK 7 vs JDK 8 核心差异 | 对比项 | JDK 7 | JDK 8 | |--------|-------|-------| | 底层结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 | | 插入方式 | **头插法** | **尾插法** | | 树化 | 无 | 链表长度≥8且数组≥64时树化 | | 并发死链 | **头插法导致死循环** ⚠️ | 尾插法避免死循环 | --- ## 4. Map 家族对比 | 特性 | HashMap | LinkedHashMap | TreeMap | |------|---------|---------------|---------| | 底层结构 | 数组+链表+红黑树 | HashMap + 双向链表 | 红黑树 | | 顺序 | 无序 | 插入顺序/访问顺序 | 按key排序 | | null key | 允许(1个) | 允许(1个) | **不允许** | | get/put | O(1) 均摊 | O(1) 均摊 | O(log n) | ```java // LinkedHashMap 实现 LRU 缓存 public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrder = true this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; } } // TreeMap 导航方法 TreeMap<Integer, String> map = new TreeMap<>(); map.floorKey(5); // ≤5 的最大 key map.ceilingKey(5); // ≥5 的最小 key map.subMap(1, 10); // [1, 10) 子视图 ``` ### IdentityHashMap ```java String a = new String("x"); String b = new String("x"); Map<String, Integer> map = new IdentityHashMap<>(); map.put(a, 1); map.put(b, 2); System.out.println(map.size()); // 2 ``` ``` IdentityHashMap 比较 key 时不用 equals(),而是直接用 == 比较“是不是同一个对象”。 所以: - 内容一样,但不是同一个对象 → 视为两个 key - 适合区分“对象身份”而不是“对象内容”的场景 常见场景: 1. 对象图遍历 2. 序列化 / 反序列化框架 3. 循环引用检测 ``` ### WeakHashMap ```java Map<Object, String> map = new WeakHashMap<>(); Object key = new Object(); map.put(key, "value"); key = null; System.gc(); // 之后 entry 可能被回收 ``` ``` WeakHashMap 的 key 是弱引用。 如果外部已经没有强引用指向这个 key,那么 GC 后这条 entry 就可能被自动清掉。 适合: 1. 生命周期跟随 key 的缓存 2. 一些辅助索引、元数据映射 不适合: 1. 强一致业务缓存 2. 不能接受数据被 GC 随机回收的核心流程 ``` --- ## 5. Set 家族 **Set 本质是基于 Map 实现的:** - `HashSet` → 内部持有 `HashMap`,元素作为 key,value 是固定的 `PRESENT` 对象 - `LinkedHashSet` → 内部持有 `LinkedHashMap` - `TreeSet` → 内部持有 `TreeMap` | 特性 | HashSet | LinkedHashSet | TreeSet | |------|---------|---------------|---------| | 底层 | HashMap | LinkedHashMap | TreeMap | | 顺序 | 无序 | 插入顺序 | 自然序/Comparator | | null 元素 | 允许(1个) | 允许(1个) | **不允许** | | add/contains | O(1) 均摊 | O(1) 均摊 | O(log n) | **自定义对象放入 HashSet 必须同时重写 `hashCode()` 和 `equals()`!** ### equals() 和 hashCode() 为什么要一起重写 ``` HashSet / HashMap 的去重与定位分两步: 1. 先看 hashCode(),决定元素落到哪个桶 2. 桶里冲突了,再用 equals() 判断是不是同一个对象语义 ``` ``` 如果只重写 equals() 不重写 hashCode(): 逻辑相等的两个对象可能落到不同桶 → 去重失效 如果只重写 hashCode() 不重写 equals(): 即使落到同一个桶,也可能判不出“内容相等” → 去重仍然不可靠 ``` ``` 结论: 只要对象要放进 HashMap / HashSet,且你希望按“业务字段相等”来判断, 就必须同时重写 equals() 和 hashCode()。 ``` --- ## 6. Queue / Deque ### Queue 接口方法 | 操作 | 抛异常版本 | 返回特殊值版本(推荐) | |------|-----------|----------------------| | 入队 | `add(e)` | `offer(e)` → false | | 出队 | `remove()` | `poll()` → null | | 查看队头 | `element()` | `peek()` → null | ### ArrayDeque vs LinkedList | 特性 | ArrayDeque | LinkedList | |------|------------|------------| | 底层结构 | 循环数组 | 双向链表 | | null 元素 | **不允许** | 允许 | | 性能 | 通常更快 | 略慢 | **用作栈或队列时,优先选 `ArrayDeque`。** ```java // ArrayDeque 当栈用(替代过时的 Stack 类) Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); // addFirst stack.pop(); // removeFirst stack.peek(); // peekFirst ``` ### Comparable vs Comparator ```java // Comparable:类自己定义“默认怎么比” class User implements Comparable<User> { int age; @Override public int compareTo(User other) { return Integer.compare(this.age, other.age); } } // Comparator:外部临时指定“这次怎么比” users.sort(Comparator.comparingInt(User::getAge)); ``` ``` Comparable 和 Comparator 的区别: 1. Comparable 是“对象自身定义默认顺序” 2. Comparator 是“外部传入比较规则” TreeMap / TreeSet / PriorityQueue 排序时都可能用到它们: - 没传 Comparator → 用元素自身的 Comparable - 传了 Comparator → 以外部比较器为准 ``` --- ## 7. Collections 工具类 ```java List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5)); Collections.sort(list); // 升序 Collections.sort(list, Comparator.reverseOrder()); // 降序 Collections.reverse(list); // 反转 Collections.shuffle(list); // 随机打乱 Collections.max(list); // 最大值 Collections.frequency(list, 1); // 元素出现次数 // 线程安全包装(每个方法加 synchronized,迭代时仍需手动加锁) List<String> syncList = Collections.synchronizedList(new ArrayList<>()); // 不可变集合(JDK 9+,推荐) List<String> immutable = List.of("a", "b", "c"); Map<String, Integer> immutableMap = Map.of("a", 1, "b", 2); ``` --- ## 8. Fail-fast vs Fail-safe 迭代器 ### Fail-fast(快速失败) 迭代过程中若集合结构被修改,立即抛出 `ConcurrentModificationException`。 **原理:** 通过 `modCount` 字段记录结构修改次数,迭代器每次 `next()` 检查是否变化。 ```java // ❌ 错误:增强for循环中直接 remove for (String s : list) { if (s.equals("b")) list.remove(s); // ConcurrentModificationException } // ✅ 正确方式1:Iterator.remove() Iterator<String> it = list.iterator(); while (it.hasNext()) { if (it.next().equals("b")) it.remove(); } // ✅ 正确方式2:JDK 8+ removeIf(推荐) list.removeIf(s -> s.equals("b")); ``` ### Fail-safe(安全失败) 迭代时操作集合的副本,不抛异常,但可能读到旧数据。 ```java // CopyOnWriteArrayList:写时复制,迭代器基于快照 List<String> cowList = new CopyOnWriteArrayList<>(Arrays.asList("a", "b", "c")); Iterator<String> it = cowList.iterator(); cowList.add("d"); // 不影响已有迭代器 while (it.hasNext()) { System.out.print(it.next()); // 输出:a b c(看不到"d") } ``` --- ## 9. 如何选择合适的集合  *图:按存储需求选择 Map、Set、List 的具体实现类* ``` 需要存储什么? │ ├── 键值对(Map) │ ├── 需要按 key 排序? → TreeMap │ ├── 需要保持插入顺序? → LinkedHashMap │ ├── 需要线程安全? → ConcurrentHashMap │ └── 其他(最常用)→ HashMap │ ├── 唯一元素集合(Set) │ ├── 需要排序? → TreeSet │ ├── 需要保持插入顺序? → LinkedHashSet │ └── 其他(最常用)→ HashSet │ └── 有序序列(List / Queue) ├── 需要队列/栈? │ ├── 优先级队列? → PriorityQueue │ ├── 线程安全队列? → LinkedBlockingQueue │ └── 普通栈/队列 → ArrayDeque(首选) └── 需要列表? ├── 频繁随机访问? → ArrayList(首选) └── 线程安全列表? → CopyOnWriteArrayList(读多写少) ``` **常见误区:** ```java // ❌ 用过时的 Stack、Vector、Hashtable // ✅ 用 ArrayDeque、ArrayList、ConcurrentHashMap // ❌ 遍历 Map 时用 keySet() 再 get()(两次查找) for (String key : map.keySet()) { map.get(key); } // ✅ 用 entrySet() for (Map.Entry<String, Integer> entry : map.entrySet()) { ... } // ✅ JDK 8+ map.forEach((key, val) -> System.out.println(key + "=" + val)); // ❌ Arrays.asList() 返回的 List 不支持 add/remove List<String> fixed = Arrays.asList("a", "b"); fixed.add("c"); // UnsupportedOperationException! // ✅ 包装一层 List<String> mutable = new ArrayList<>(Arrays.asList("a", "b")); ``` --- ## 10. 面试高频 Q&A **Q:HashMap 的底层原理?** A:JDK 8 采用数组+链表+红黑树。put 时计算 hash(高16位异或低16位),用 `(n-1)&hash` 定位桶,桶为空直接插入,否则处理冲突(覆盖/链表尾插/树插入),链表长度≥8且数组≥64时树化。size > capacity*0.75 时扩容,容量翻倍。 **Q:HashMap 为什么线程不安全?** A:JDK 7 并发扩容时头插法导致链表成环,get() 死循环;JDK 8 并发 put 时可能数据丢失(两线程同时写同一个空桶,后者覆盖前者)。解决:用 ConcurrentHashMap。 **Q:ConcurrentHashMap 的实现原理?** A:JDK 7 用分段锁(16个Segment);JDK 8 改用 CAS+synchronized,桶为空时 CAS 插入(无锁),桶不为空时 synchronized 锁住单个桶的头节点,并发度大幅提升。 **Q:HashMap 的负载因子为什么是 0.75?** A:时间与空间的权衡。过小内存浪费扩容频繁,过大冲突增多性能下降。根据泊松分布,0.75 时链表长度超过8的概率约为 0.00000006,极低。 **Q:HashSet 如何保证元素不重复?** A:内部持有 HashMap,元素作为 key。add 时调用 map.put,HashMap 通过 hash 和 equals 判断 key 是否已存在。因此自定义对象必须同时重写 hashCode() 和 equals()。 **Q:fail-fast 和 fail-safe 的区别?** A:fail-fast 迭代中集合被修改立即抛 ConcurrentModificationException(通过 modCount 实现),适用于 java.util 包集合;fail-safe 操作副本不抛异常但可能读旧数据,适用于 java.util.concurrent 包集合。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入