两大根接口一张关系网，复杂度速查表存好
很多人学集合框架，是从List、Map、Set三个单词开始背的，背完还是串不起来：它们之间到底什么关系？为什么HashMap既有"哈希"又有"映射"？Collections和Collection是同一个东西吗？今天我们用一张"关系网"把整个集合框架捋顺，让你之后看任何一篇源码解析都像看地图一样清晰。
一、集合框架为什么要分层？
Java 集合框架（Java Collections Framework，JCF）的设计哲学是：接口定义行为，抽象类提供骨架，具体类给实现。三层各司其职：
- 接口（Interface）：规定"能做什么"，比如
Collection说"我是一个装元素的容器"，List说"我是有序可重复的"，Map说"我是键值对"。 - 抽象类（AbstractXxx）：实现接口里大部分通用方法，具体类只需补全差异逻辑，避免重复造轮子。
- 具体类（Concrete）：
ArrayList、HashMap、TreeSet等，提供真正的存储结构和算法。
这种设计让你写业务代码时面向接口编程：List<User> list = new ArrayList<>()，哪天想换LinkedList，改一行就行。
二、两大根接口：Collection 与 Map
整个框架有两个互不继承的根，这是初学者最容易迷糊的地方：
Collection（单个元素的容器） ├── List（有序、可重复） │ ├── ArrayList 数组实现，查快改慢 │ ├── LinkedList 双向链表，增删快 │ ├── Vector 线程安全但老旧的数组 │ └── Stack 继承 Vector 的栈（已不推荐） ├── Set（无序、不可重复） │ ├── HashSet 哈希表，最快 │ ├── LinkedHashSet 哈希 + 双向链表，保插入序 │ └── TreeSet 红黑树，按 key 排序 └── Queue / Deque（队列 / 双端队列） ├── ArrayDeque 数组双端队列 ├── PriorityQueue 堆实现的优先队列 └── 各阻塞队列（BlockingQueue 家族） Map（键值对容器，不属于 Collection） ├── HashMap 哈希表，最常用 ├── LinkedHashMap 哈希 + 链表，保插入/访问序 ├── TreeMap 红黑树，按键排序 ├── Hashtable 线程安全但老旧的哈希表 └── ConcurrentHashMap 高并发哈希表关键点：Map不是Collection的子接口。它的根就是Map<K,V>自己。所以Map没有add()，只有put()；它没有继承Collection的任何方法。但Map提供了keySet()、values()、entrySet()三个视图，它们返回的就是Collection/Set，于是两条线在这里交汇。
一个高频面试题：
Collection和Collections的区别？前者是接口（根），后者是一个工具类，里面全是静态方法（sort、synchronizedList、emptyList等），用来操作集合。同理Arrays是操作数组的工具类。名字只差一个s，含义天差地别。
三、List / Set / Queue 的行为契约
面试常让你对比三兄弟，记住它们的"契约"就够了：
| 接口 | 元素顺序 | 重复 | 索引访问 | 典型实现 |
|---|---|---|---|---|
| List | 有序（插入序） | 允许 | 支持get(i) | ArrayList、LinkedList |
| Set | 无序（HashSet） | 禁止 | 不支持 | HashSet、TreeSet |
| Queue | 按排队规则 | 看实现 | 一般不支持 | ArrayDeque、PriorityQueue |
“有序"在List里指插入顺序可复现、可用下标访问；Set的HashSet不保证顺序，TreeSet按比较器排但也不是"插入序”。这点极易混淆。
四、时间复杂度速查表（背下来）
这是集合框架最实用的"性能地图"，建议存下来：
| 操作 | ArrayList | LinkedList | HashMap | TreeMap | HashSet |
|---|---|---|---|---|---|
| 按索引查 get(i) | O(1) | O(n) | — | — | — |
| 末尾增 add | O(1)* | O(1) | O(1)* | O(log n) | O(1)* |
| 中间插/删 | O(n) | O(1)** | — | — | — |
| 查 contain | O(n) | O(n) | O(1)* | O(log n) | O(1)* |
| 取最小/最大 | O(n) | O(n) | — | O(log n) | — |
* 均摊复杂度，扩容/哈希冲突时退化为更高
** 已知节点引用时 O(1)，若要先遍历定位则是 O(n)
一句话总结性能直觉：随机访问多用 ArrayList，头尾增删多用 ArrayDeque/LinkedList，查重/映射多用 HashMap，要排序用 TreeMap/TreeSet。
五、迭代器：统一的遍历方式
不管底层是数组还是链表，Collection都用同一个Iterator遍历：
List<String>list=newArrayList<>(List.of("a","b","c"));Iterator<String>it=list.iterator();while(it.hasNext()){Strings=it.next();if("b".equals(s))it.remove();// 安全删除}注意：遍历时用集合自身的remove()会抛ConcurrentModificationException，必须用迭代器的remove()，或用for-each+ 提前收集再删，或用Iterator。这正是后面调优篇要细讲的fail-fast机制。
Map没有Iterator，但entrySet()返回Set<Map.Entry<K,V>>，一样能迭代：
for(Map.Entry<String,Integer>e:map.entrySet()){System.out.println(e.getKey()+"="+e.getValue());}六、Java 8 之后的函数式增强
集合框架在 Java 8 吃到了大红利：
Collection.removeIf(Predicate)：一行替代"迭代 + 判断 + 删除"。List.replaceAll(UnaryOperator)、sort(Comparator)。Map.forEach、compute、merge、getOrDefault等，写统计逻辑极爽。StreamAPI 让集合进入"流水线"时代：list.stream().filter(...).map(...).collect(...)。
例子，按城市统计人数：
Map<String,Long>cnt=users.stream().collect(Collectors.groupingBy(User::getCity,Collectors.counting()));但parallelStream()不是银弹——共享可变状态、线程不安全集合、小数据量都会让它反而不如串行的，调优篇会专门拆。
七、为什么"面向接口编程"这么重要？
回到开头那句List<User> list = new ArrayList<>()。当你把方法参数写成List<T>而不是ArrayList<T>，调用方可以传LinkedList、CopyOnWriteArrayList、Collections.emptyList()，你的方法完全不用改。这是集合框架分层带来的最大红利：解耦"使用方式"和"底层实现"。
同理，返回Map的方法，内部想换成ConcurrentHashMap提升并发，对外签名不变。写 SDK、写业务分层时，这个习惯能少写无数适配代码。
总结
集合框架 = 两大根（Collection / Map）+ 三层结构（接口 / 抽象类 / 实现）+ 一套统一迭代器。记住"List 有序可重复、Set 不可重复、Map 是键值对且不属于 Collection"，再配合复杂度速查表，你就拿到了整个框架的地图。后续源码篇都是在给这张地图填充细节。
