Java 集合框架

Java 集合框架 (Java Collections Framework) 详细学习笔记目录集合框架概述Collection 接口体系List (列表)Set (集合)Queue (队列)Map 接口体系工具类Collections Arrays并发集合 (JUC)核心面试题与总结1. 集合框架概述1.1 什么是集合框架Java 集合框架是java.util包下的一组类和接口用于存储和操作一组对象。它提供了统一的架构使得不同数据结构之间的操作更加一致和高效。1.2 体系结构图Collection (接口) ├── List (接口): 有序、可重复 │ ├── ArrayList │ ├── LinkedList │ ├── Vector (过时) │ └── Stack (过时推荐用 Deque) ├── Set (接口): 无序、不可重复 │ ├── HashSet │ ├── LinkedHashSet │ └── TreeSet └── Queue (接口): 队列 ├── PriorityQueue └── Deque (双端队列) - ArrayDeque, LinkedList Map (接口): 键值对 (Key-Value) ├── HashMap ├── LinkedHashMap ├── TreeMap ├── Hashtable (过时) └── ConcurrentHashMap1.3 核心区别Collection: 存储单个元素是 List, Set, Queue 的根接口。Map: 存储键值对不继承Collection 接口是独立的体系。2. Collection 接口体系2.1 List (列表)特点: 有序 (插入顺序)、元素可重复、允许 null、可通过索引访问。2.1.1 ArrayList底层: 动态数组 (Object[] elementData)。扩容机制:初始容量默认 0 (懒加载)第一次添加时扩容为 10。扩容规则newCapacity oldCapacity (oldCapacity 1)(即 1.5 倍)。性能扩容涉及数组复制 (Arrays.copyOf)代价高。时间复杂度:随机访问 (get):O ( 1 ) O(1)O(1)尾部添加 (add): 均摊O ( 1 ) O(1)O(1)中间插入/删除:O ( n ) O(n)O(n)(需移动元素)适用场景: 读多写少频繁随机访问。2.1.2 LinkedList底层: 双向链表 (Node类包含prev,next,item)。特点:非线程安全。实现了List和Deque接口可作栈或队列。时间复杂度:随机访问:O ( n ) O(n)O(n)头部/尾部插入删除:O ( 1 ) O(1)O(1)中间插入删除:O ( n ) O(n)O(n)(需先遍历找到位置)适用场景: 频繁在头部或中间进行插入/删除操作作为栈、队列、双端队列使用。2.1.3 Vector (了解)特点: 线程安全 (方法加synchronized)性能较差。扩容: 默认 2 倍扩容。建议: 现代开发中不推荐使用可用Collections.synchronizedList或CopyOnWriteArrayList替代。2.2 Set (集合)特点: 无序 (部分有序)、元素不可重复、最多允许一个 null。2.2.1 HashSet底层: 基于HashMap实现。Key: 存储的元素。Value: 一个固定的静态对象PRESENT。去重原理: 依赖元素的hashCode()和equals()方法。时间复杂度: 增删查O ( 1 ) O(1)O(1)(平均)。适用场景: 需要去重不关心顺序。2.2.2 LinkedHashSet底层:HashMap 双向链表。特点: 维护元素的插入顺序。适用场景: 需要去重且保持插入顺序 (如 LRU 缓存的基础)。2.2.3 TreeSet底层: 基于TreeMap(红黑树)。特点: 元素自然排序或自定义排序(Comparator)。时间复杂度: 增删查O ( log ⁡ n ) O(\log n)O(logn)。适用场景: 需要对集合元素进行排序。2.3 Queue (队列)特点: 遵循 FIFO (先进先出)部分支持优先级。2.3.1 PriorityQueue (优先队列)底层: 无界优先堆 (二叉堆数组实现)。特点:元素出队顺序由优先级决定 (默认自然排序可自定义 Comparator)。不允许 null 元素。非线程安全。时间复杂度: 入队/出队O ( log ⁡ n ) O(\log n)O(logn)。2.3.2 ArrayDeque底层: 循环数组。特点:比LinkedList更高效 (无节点对象开销缓存友好)。可作栈 (Stack) 或队列 (Queue)。不允许 null。建议: 替代Stack和LinkedList作为队列/栈的首选。3. Map 接口体系特点: 存储 Key-Value 对Key 不可重复Value 可重复。3.1 HashMap (核心重点)底层结构 (JDK 1.8): 数组 链表 红黑树。关键参数:initialCapacity: 初始容量 (默认 16必须是 2 的幂)。loadFactor: 负载因子 (默认 0.75)。threshold: 扩容阈值 容量 * 负载因子。put 流程:计算 Key 的 Hash 值 (扰动函数减少碰撞)。计算数组下标(n - 1) hash(要求 n 为 2 的幂)。若该位置为空直接插入。若发生碰撞 (Hash 冲突)若 Key 相同 (equals为 true)覆盖 Value。若不同插入链表尾部。树化: 若链表长度 8且数组长度 64链表转为红黑树。退化: 若红黑树节点数 6退化为链表。扩容 (Resize):触发元素个数 threshold。动作容量翻倍 (2 倍)重新计算元素位置 (Rehash)。优化JDK 1.8 扩容时元素要么在原位置要么在原位置 旧容量位置无需重新 Hash。线程安全:不安全。多线程下可能导致死循环 (JDK 1.7) 或数据覆盖 (JDK 1.8)。3.2 LinkedHashMap底层:HashMap 双向链表。特点:维护插入顺序(默认) 或访问顺序(构造时设置accessOrdertrue)。迭代顺序与插入顺序一致。应用: LRU 缓存 (配合removeEldestEntry方法)。3.3 TreeMap底层: 红黑树。特点: Key 有序 (自然排序或 Comparator)。时间复杂度:O ( log ⁡ n ) O(\log n)O(logn)。应用: 范围查询 (如subMap,headMap)。3.4 Hashtable (过时)特点: 线程安全 (全表锁synchronized)Key/Value 不能为 null。缺点: 性能差锁粒度粗。替代:ConcurrentHashMap。4. 工具类Collections Arrays4.1 Collections操作集合的工具类 (静态方法)。排序:Collections.sort(list)(底层归并排序/TimSort)。同步包装:Collections.synchronizedList(list)。不可变集合:Collections.unmodifiableList(list)。算法:binarySearch,reverse,shuffle,max,min。4.2 Arrays操作数组的工具类。排序:Arrays.sort(arr)(双轴快排)。查找:Arrays.binarySearch(arr, key)。转换:Arrays.asList(arr)(返回固定长度的 List 视图)。注意:asList返回的 List 不支持add/remove且底层直接引用原数组。5. 并发集合 (JUC - java.util.concurrent)5.1 ConcurrentHashMap目标: 线程安全的 HashMap高并发下性能优于Hashtable和Collections.synchronizedMap。JDK 1.7 实现:分段锁 (Segment)。将数据分成一段一段存储每段配一把锁 (ReentrantLock)。JDK 1.8 实现:Node CAS synchronized。摒弃 Segment直接采用Node数组 链表 红黑树。锁粒度更细只锁住当前桶 (Bucket) 的头节点 (synchronized)。利用 CAS 操作进行无锁插入 (空桶时)。特点: 允许 null 值吗Key 和 Value 均不允许为 null。5.2 CopyOnWriteArrayList原理:写时复制。读操作无锁直接读取数组。写操作 (add/set)复制一个新数组 - 修改新数组 - 将引用指向新数组。适用场景:读多写少(如监听器列表)。缺点: 内存占用大写操作开销大数据最终一致性 (非实时)。5.3 BlockingQueue (阻塞队列)特点: 队列空时取数据阻塞队列满时存数据阻塞。实现:ArrayBlockingQueue: 有界数组实现公平/非公平锁。LinkedBlockingQueue: 可选有界链表实现读写锁分离 (性能较好)。PriorityBlockingQueue: 无界优先队列。SynchronousQueue: 不存储元素每个 put 必须等待一个 take。应用: 线程池 (ThreadPoolExecutor) 的核心组件。6. 核心面试题与总结6.1 常见对比特性ArrayListLinkedListVector底层数组双向链表数组随机访问O ( 1 ) O(1)O(1)O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)插入/删除O ( n ) O(n)O(n)(尾部快)O ( 1 ) O(1)O(1)(头尾)O ( n ) O(n)O(n)线程安全否否是扩容1.5 倍无2 倍特性HashMapTreeMapLinkedHashMap底层数组链表红黑树红黑树HashMap链表Key 顺序无序排序插入/访问顺序性能O ( 1 ) O(1)O(1)O ( log ⁡ n ) O(\log n)O(logn)O ( 1 ) O(1)O(1)Null 支持Key/Value 可为 nullKey 不能为 nullKey/Value 可为 null6.2 经典问题HashMap 为什么线程不安全多线程扩容时可能导致链表成环 (JDK 1.7)。多线程 put 时可能覆盖数据 (JDK 1.8)。HashMap 为什么数组长度是 2 的幂为了使用(n-1) hash代替%取模运算提高效率。保证哈希分布均匀减少碰撞。为什么 JDK 1.8 引入红黑树解决哈希冲突严重时链表过长导致查询退化为O ( n ) O(n)O(n)的问题保证最坏情况O ( log ⁡ n ) O(\log n)O(logn)。ArrayList 和 LinkedList 如何选择随机访问多 - ArrayList。频繁增删 (特别是中间) - LinkedList。绝大多数场景推荐 ArrayList (缓存友好)。如何遍历 MapentrySet(): 推荐同时获取 Key 和 Value。keySet(): 只获取 Key需再getValue。forEach(Java 8 Lambda): 最简洁。6.3 最佳实践初始化容量: 如果预估数据量构造函数指定容量避免频繁扩容。Key 对象: 使用不可变类 (如 String) 作为 Map 的 Key并正确重写hashCode和equals。并发: 高并发场景优先使用ConcurrentHashMap读多写少用CopyOnWriteArrayList。迭代器: 遍历时不要直接修改集合结构 (使用iterator.remove())避免ConcurrentModificationException。附录常用代码片段快速创建不可变集合 (Java 9)ListStringlistList.of(A,B,C);// 不可变SetStringsetSet.of(X,Y);// 不可变MapString,IntegermapMap.of(k1,1,k2,2);// 不可变使用 Stream API 处理集合ListStringnameslist.stream().filter(s-s.startsWith(A)).map(String::toUpperCase).sorted().collect(Collectors.toList());自定义 Comparator 排序list.sort((a,b)-b.compareTo(a));// 降序