1. 为什么我要把 Collection 和 Map 单独拎出来做笔记刚入行那会儿我对集合框架的态度就是“能用就行”——ArrayList 装数据HashMap 做映射遇到要去重就 HashSet需要排序就 Collections.sort。直到有一次排查线上问题一个看似普通的“列表去重”操作在数据量上来之后直接把接口响应时间从 50ms 拉到了 2s我才意识到自己对这套东西的理解有多浅。后来花了整整两周时间把 Collection 和 Map 这两个体系从头到尾捋了一遍包括源码层面的扩容机制、哈希冲突处理、迭代器失效条件、线程安全边界等等才算真正把这块地基打牢。这篇笔记就是那次系统梳理的产物。它不是什么速查手册而是把散落在各处的知识点按照“为什么这样设计—怎么用—什么时候会踩坑”的逻辑重新组织了一遍。内容覆盖 List、Set、Queue 三大 Collection 分支以及 Map 体系的核心实现类重点讲清楚每个类的底层数据结构、适用场景、性能特征和常见陷阱。适合已经会用集合但想搞清楚底层原理的开发者也适合准备面试需要系统复习的朋友。如果你曾经被 ConcurrentModificationException 搞得莫名其妙或者好奇 HashMap 的扩容为什么是 2 倍那这篇笔记应该能帮到你。2. 集合框架的整体设计与选型逻辑2.1 两大顶层接口的分工与联系Java 集合框架从顶层看就是两条线Collection和Map。很多人初学时会疑惑为什么 Map 不继承 Collection其实从语义上就能理解——Collection 表示“一组单个元素”而 Map 表示“一组键值对映射”。前者你可以直接遍历元素后者你需要通过键来访问值。两者在数据结构层面有大量相通之处比如 HashMap 和 HashSet 底层共用数组链表红黑树但在接口抽象上刻意保持独立避免语义混淆。Collection 下面又分三个核心分支List有序可重复、Set不重复、Queue队列语义。Map 则是独立的键值对体系。实际选型时我习惯先问自己三个问题需不需要键值映射元素是否允许重复对顺序有没有要求这三个问题的答案基本就能锁定具体实现类。2.2 底层数据结构决定一切集合类的性能特征完全由底层数据结构决定这是选型的根本依据。数组结构ArrayList、HashMap 的桶数组支持 O(1) 随机访问但插入删除代价高链表结构LinkedList、HashMap 的链表桶插入删除 O(1) 但访问 O(n)哈希表结构HashMap、HashSet平均 O(1) 但依赖哈希函数质量树结构TreeMap、TreeSet保证 O(log n) 且有序。我见过不少项目里用 LinkedList 做频繁随机访问的容器结果性能比 ArrayList 差了一个数量级。也见过用 ArrayList 做大量头部插入的场景每次都要 System.arraycopy 搬移整个数组。这些问题的根源都是没搞清楚数据结构和操作模式的匹配关系。2.3 迭代器统一遍历的抽象层集合框架用 Iterator 统一了所有容器的遍历方式这是一个非常漂亮的设计。但迭代器也带来了一个经典问题fail-fast 机制。当你用迭代器遍历时如果通过集合自身的方法而不是迭代器的 remove修改了结构迭代器会立刻抛出 ConcurrentModificationException。这个机制的实现依赖一个 modCount 字段每次结构性修改都会递增迭代器在 next() 和 remove() 时检查这个值是否变化。理解这一点很重要因为它解释了为什么有些操作在单线程下也会“并发修改异常”——不是真的并发而是迭代过程中结构被改了。注意fail-fast 是一种检测机制而非保证机制它不能替代并发控制。在多线程环境下即使没有抛异常也不代表操作是安全的。3. List 家族有序集合的三种实现3.1 ArrayList 的扩容机制与性能特征ArrayList 底层就是一个 Object 数组默认初始容量是 10注意是第一次 add 时才分配不是 new 的时候就分配。扩容规则是newCapacity oldCapacity (oldCapacity 1)也就是 1.5 倍。这个 1.5 倍不是随便定的太小会导致频繁扩容太大则浪费内存1.5 是在时间和空间之间取的折中值。扩容时调用Arrays.copyOf做数组拷贝这是一个 O(n) 操作。所以如果你能预估数据量最好在创建时就指定初始容量。我实测过一个场景向 ArrayList 添加 100 万条数据不指定初始容量耗时约 45ms指定初始容量 100 万后耗时约 12ms差距接近 4 倍。// 推荐预估容量避免多次扩容 ListString list new ArrayList(1000000); // 不推荐默认容量触发多次扩容 ListString list new ArrayList();ArrayList 的随机访问是 O(1)因为数组支持下标直接定位。但中间插入和删除是 O(n)因为需要搬移后续元素。所以 ArrayList 适合读多写少、以尾部操作为主的场景。3.2 LinkedList 的真实适用场景LinkedList 底层是双向链表每个节点包含前驱、后继和数据三个部分。它的插入删除是 O(1)前提是已经定位到位置但随机访问是 O(n)。很多人以为 LinkedList 适合频繁插入删除但实际上如果你每次都是通过下标操作定位本身就要 O(n)综合下来并不比 ArrayList 快。LinkedList 真正适合的场景是频繁在头部插入删除如实现栈或队列或者你已经持有某个节点的引用需要在其前后操作。另外 LinkedList 实现了 Deque 接口可以作为双端队列使用。// LinkedList 作为栈使用 DequeInteger stack new LinkedList(); stack.push(1); stack.push(2); stack.pop(); // 返回 2 // LinkedList 作为队列使用 QueueInteger queue new LinkedList(); queue.offer(1); queue.offer(2); queue.poll(); // 返回 1实操心得在绝大多数业务场景下ArrayList 的综合性能都优于 LinkedList。除非你明确需要双端操作或频繁头部插入否则优先选 ArrayList。我做过一个基准测试同样是添加 10 万条数据ArrayList 比 LinkedList 快约 30%遍历速度快约 50 倍。3.3 Vector 与 CopyOnWriteArrayList 的取舍Vector 是早期 JDK 提供的线程安全 List所有方法都加了 synchronized。但它的锁粒度太大性能很差现在已经基本被淘汰。如果确实需要线程安全的 List优先考虑CopyOnWriteArrayList。CopyOnWriteArrayList 的核心思想是“写时复制”每次写操作都创建一个新数组写完后再替换引用。这样读操作完全无锁适合读多写极少的场景。但它的缺点也很明显——写操作代价高而且数据有延迟性读到的可能还是旧数组。// 适合读多写少的并发场景 ListString list new CopyOnWriteArrayList(); list.add(data); // 每次 add 都会复制整个数组如果写操作也比较频繁更好的方案是用Collections.synchronizedList包装一个普通 List或者直接用并发包里的其他结构。4. Set 家族去重背后的哈希与排序4.1 HashSet 的去重原理HashSet 底层就是一个 HashMap元素作为 keyvalue 是一个固定的 Object 常量。所以 HashSet 的去重能力完全依赖 HashMap 的 key 去重机制先比较 hashCode如果相同再比较 equals。这里有一个非常经典的坑如果你自定义的对象没有重写 hashCode 和 equalsHashSet 就无法正确去重。因为默认的 hashCode 是基于对象地址的两个内容相同的对象地址不同hashCode 就不同HashSet 会认为它们是两个不同的元素。class User { String name; // 没有重写 hashCode 和 equals } SetUser set new HashSet(); set.add(new User(张三)); set.add(new User(张三)); System.out.println(set.size()); // 输出 2而不是 1正确做法是同时重写 hashCode 和 equals且保证 equals 为 true 的两个对象 hashCode 一定相同。4.2 TreeSet 的排序规则与比较器TreeSet 底层是 TreeMap红黑树元素按自然顺序或指定的 Comparator 排序。它的去重逻辑不是靠 hashCode/equals而是靠 compareTo 或 compare 的返回值——返回 0 就认为是重复元素。// 自然排序 SetInteger set new TreeSet(); set.add(3); set.add(1); set.add(2); // 遍历顺序1, 2, 3 // 自定义排序 SetString set new TreeSet((a, b) - b.compareTo(a)); set.add(a); set.add(c); set.add(b); // 遍历顺序c, b, aTreeSet 的一个常见陷阱是如果 Comparator 返回 0 但 equals 返回 falseTreeSet 会认为它们是重复的而 HashSet 会认为它们不同。这种不一致性在混用两种 Set 时容易出问题。4.3 LinkedHashSet 的插入顺序保持LinkedHashSet 继承自 HashSet但内部额外维护了一个双向链表来记录插入顺序。它的去重逻辑和 HashSet 一样但遍历时按插入顺序输出。底层结构是数组链表红黑树双向链表内存开销比 HashSet 大一些。SetString set new LinkedHashSet(); set.add(banana); set.add(apple); set.add(cherry); // 遍历顺序banana, apple, cherry插入顺序三种 Set 的选型逻辑很清晰不需要顺序用 HashSet需要排序用 TreeSet需要保持插入顺序用 LinkedHashSet。Set 实现底层结构顺序时间复杂度适用场景HashSet哈希表无序O(1)快速去重TreeSet红黑树排序O(log n)需要有序遍历LinkedHashSet哈希表链表插入顺序O(1)去重且保持顺序5. Map 家族键值映射的核心实现5.1 HashMap 的哈希计算与索引定位HashMap 是集合框架里最精妙的设计之一。它的核心流程是对 key 的 hashCode 做扰动处理然后通过(n - 1) hash计算数组下标。这里的 n 是数组容量必须是 2 的幂这样(n - 1) hash等价于hash % n但效率更高。扰动函数是hash h ^ (h 16)目的是让高 16 位也参与运算减少哈希冲突。因为数组容量通常不会太大如果直接用 hashCode高位信息会被浪费。static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }当两个 key 计算出相同下标时就发生了哈希冲突。JDK 8 之前用链表解决JDK 8 之后当链表长度超过 8 且数组容量大于等于 64 时链表会转为红黑树查询复杂度从 O(n) 降到 O(log n)。5.2 扩容机制为什么是 2 倍HashMap 的扩容是 2 倍这个设计有两个原因。第一容量保持 2 的幂才能用位运算代替取模。第二2 倍扩容时元素的新位置只有两种可能要么在原位置要么在原位置旧容量。这是因为(2n - 1) hash相比(n - 1) hash只多了一个高位判断。// JDK 8 扩容时的元素迁移逻辑简化 if ((e.hash oldCap) 0) { // 留在原位置 } else { // 移动到 原位置 oldCap }这个设计避免了重新计算每个元素的哈希大大提升了扩容效率。默认负载因子是 0.75意思是当元素数量达到容量的 75% 时就触发扩容。0.75 是在空间利用率和冲突概率之间的折中——太高容易冲突太低浪费空间。注意如果你能预估数据量创建 HashMap 时指定初始容量可以避免多次扩容。计算公式是initialCapacity (expectedSize / 0.75) 1然后向上取最近的 2 的幂。5.3 TreeMap 与 LinkedHashMap 的差异化定位TreeMap 底层是红黑树按 key 排序支持范围查询如subMap、headMap、tailMap。它的 key 必须实现 Comparable 或传入 Comparator。时间复杂度是 O(log n)比 HashMap 慢但胜在有序。LinkedHashMap 继承自 HashMap额外维护了一个双向链表记录插入顺序或访问顺序。它最强大的功能是可以实现 LRU 缓存——构造时传入accessOrdertrue每次 get 会把访问的元素移到链表尾部当容量超限时淘汰链表头部的元素。// 用 LinkedHashMap 实现简单的 LRU 缓存 class LRUCacheK, V extends LinkedHashMapK, V { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrder true this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } }5.4 ConcurrentHashMap 的线程安全策略ConcurrentHashMap 是并发场景下的首选 Map。JDK 8 之前用分段锁SegmentJDK 8 之后改为 CAS synchronized 锁单个桶。锁粒度从段级别降到桶级别并发度大幅提升。它的 get 操作完全无锁因为 Node 的 val 和 next 都是 volatile 的。put 操作先用 CAS 尝试插入空桶如果桶非空则用 synchronized 锁住头节点再操作。ConcurrentHashMapString, Integer map new ConcurrentHashMap(); map.put(key, 1); map.computeIfAbsent(key2, k - 2); // 原子操作 map.merge(key, 1, Integer::sum); // 原子累加实操心得ConcurrentHashMap 不允许 null 键和 null 值这是为了避免并发场景下的歧义无法区分“不存在”和“值为 null”。另外它的 size() 返回的是近似值不是精确值因为并发插入时无法实时统计。Map 实现底层结构顺序线程安全适用场景HashMap数组链表红黑树无序否通用键值映射TreeMap红黑树按 key 排序否需要排序或范围查询LinkedHashMap哈希表双向链表插入/访问顺序否LRU 缓存、保持顺序ConcurrentHashMap数组链表红黑树无序是高并发场景Hashtable哈希表无序是全表锁已淘汰不推荐6. 遍历、删除与并发修改的实战避坑6.1 迭代器删除的正确姿势在遍历集合时删除元素是最容易踩坑的操作。直接调用集合的 remove 方法会触发 fail-fast正确做法是用迭代器的 remove。// 错误写法抛 ConcurrentModificationException ListString list new ArrayList(Arrays.asList(a, b, c)); for (String s : list) { if (b.equals(s)) { list.remove(s); // 抛异常 } } // 正确写法用迭代器 IteratorString it list.iterator(); while (it.hasNext()) { String s it.next(); if (b.equals(s)) { it.remove(); // 安全删除 } } // 更简洁的写法removeIfJDK 8 list.removeIf(s - b.equals(s));removeIf底层就是用迭代器实现的代码更简洁推荐优先使用。6.2 HashMap 遍历的三种方式对比HashMap 的遍历有 entrySet、keySet、values 三种方式。如果同时需要 key 和 value用 entrySet 效率最高因为 keySet 遍历时每次都要 get(key)多了一次查找。MapString, Integer map new HashMap(); // 方式一entrySet推荐 for (Map.EntryString, Integer entry : map.entrySet()) { System.out.println(entry.getKey() entry.getValue()); } // 方式二keySet需要 value 时不推荐 for (String key : map.keySet()) { System.out.println(key map.get(key)); // 多一次查找 } // 方式三forEachJDK 8简洁 map.forEach((k, v) - System.out.println(k v));6.3 常见问题速查表问题现象根本原因解决方案ConcurrentModificationException遍历时结构性修改用迭代器 remove 或 removeIfHashSet 去重失效未重写 hashCode/equals同时重写两个方法HashMap 死循环JDK 7并发扩容导致链表成环升级 JDK 8 或用 ConcurrentHashMapTreeSet 元素丢失Comparator 返回 0 但 equals 为 false保证比较器与 equals 一致ArrayList 性能差频繁扩容预估容量指定初始大小LinkedList 遍历慢随机访问 O(n)改用 ArrayList 或增强 for 循环7. 从源码到实战的几点个人体会集合框架这块内容我前后翻过好几遍源码每次都有新收获。最开始觉得 HashMap 的红黑树转换很复杂后来看懂了发现核心逻辑其实就那几行。最开始不理解为什么扩容是 2 倍后来自己推导了一遍位运算才恍然大悟。这些底层细节平时写业务代码可能用不上但一旦遇到性能问题或诡异 bug它们就是排查的关键线索。如果让我给初学者一个建议那就是不要只记 API要理解每个集合背后的数据结构。你知道了 ArrayList 是数组自然就明白为什么随机访问快、中间插入慢你知道了 HashMap 是哈希表自然就明白为什么 key 要重写 hashCode。数据结构决定了操作的时间复杂度时间复杂度决定了适用场景这条逻辑链是选型的根本依据。最后分享一个我常用的排查技巧当你怀疑集合相关代码有性能问题时先用jstack看线程栈确认是不是卡在扩容或哈希冲突上然后用 JMH 做基准测试对比不同实现的真实性能差异。不要凭感觉猜数据会告诉你答案。