目录
- 一、集合框架层次结构
- 二、Collection集合
- 1.List集合
- 1.CopyOnWriteArrayList
- 2、ArrayList
- 3、LinkedList
- 4、Vector
Java 集合框架（Collections Framework）是 Java 中用于存储和操作数据组的重要架构。它提供了一组接口、实现类和算法。
一、集合框架层次结构
Collection (接口) ├── List (接口 - 有序，可重复) │ ├── ArrayList (实现类) │ ├── LinkedList (实现类) │ ├── Vector (线程安全，已过时) │ └── Stack (继承Vector) │ ├── Set (接口 - 无序，不可重复) │ ├── HashSet (实现类) │ │ └── LinkedHashSet (保持插入顺序) │ ├── SortedSet (接口) │ │ └── TreeSet (实现类) │ └── EnumSet (专用于枚举) │ └── Queue (接口 - 队列) ├── Deque (双端队列接口) │ ├── ArrayDeque (实现类) │ └── LinkedList (也实现了Deque) │ ├── PriorityQueue (优先队列) └── BlockingQueue (阻塞队列接口) ├── ArrayBlockingQueue ├── LinkedBlockingQueue └── PriorityBlockingQueue Map (接口 - 键值对) ├── HashMap (实现类) │ └── LinkedHashMap (保持插入顺序) ├── TreeMap (基于红黑树) ├── Hashtable (线程安全，已过时) ├── WeakHashMap (弱引用) └── ConcurrentHashMap (并发版)Java集合大致可以分为两大体系，一个是Collection，另一个是Map
Collection：主要由List、Set、Queue接口组成，List代表有序、重复的集合；其中Set代表无序、不可重复的集合；Queue体系集合，代表一种队列集合实现。Map：则代表具有映射关系的键值对集合。
java.util.Collection下的接口和继承类关系简易结构图：
java.util.Map下的接口和继承类关系简易结构图：
其中，Java 集合框架中主要封装的是典型的数据结构和算法，如动态数组、双向链表、队列、栈、Set、Map等。
二、Collection集合
通过集合的关系图我们可以知道Collection是集合的顶层父类，他定义了集合的基本方法如
基本操作方法
| 方法签名 | 功能描述 | 返回值 | 示例 | 时间复杂度 |
|---|---|---|---|---|
int size() | 返回集合中元素的数量 | 元素个数 | list.size()→3 | O(1) |
boolean isEmpty() | 判断集合是否为空 | true/false | list.isEmpty()→false | O(1) |
boolean contains(Object o) | 判断是否包含指定元素 | true/false | list.contains("A")→true | List: O(n) Set: O(1) TreeSet: O(log n) |
boolean add(E e) | 添加元素到集合 | 是否成功 | list.add("D")→true | ArrayList: 均摊O(1) LinkedList: O(1) TreeSet: O(log n) |
boolean remove(Object o) | 移除指定元素 | 是否成功 | list.remove("A")→true | ArrayList: O(n) LinkedList: O(n) HashSet: O(1) |
批量操作方法
| 方法签名 | 功能描述 | 返回值 | 示例 | 说明 |
|---|---|---|---|---|
boolean containsAll(Collection<?> c) | 是否包含集合c中所有元素 | true/false | list.containsAll(subList) | 检查子集关系 |
boolean addAll(Collection<? extends E> c) | 添加集合c中所有元素 | 是否改变 | list.addAll(anotherList) | 批量添加 |
boolean removeAll(Collection<?> c) | 移除集合c中所有元素 | 是否改变 | list.removeAll(toRemove) | 差集操作 |
boolean retainAll(Collection<?> c) | 仅保留集合c中元素 | 是否改变 | list.retainAll(common) | 交集操作 |
void clear() | 清空集合所有元素 | 无 | list.clear() | 集合变为空 |
转换和迭代方法
| 方法签名 | 功能描述 | 返回值 | 示例 | 说明 |
|---|---|---|---|---|
Object[] toArray() | 转换为Object数组 | Object数组 | list.toArray() | 返回新数组 |
<T> T[] toArray(T[] a) | 转换为指定类型数组 | 指定类型数组 | list.toArray(new String[0]) | 类型安全转换 |
Iterator<E> iterator() | 返回迭代器 | Iterator对象 | list.iterator() | 用于遍历集合 |
default boolean removeIf(Predicate<? super E> filter) | 条件删除 | 是否改变 | list.removeIf(s -> s.length() > 3) | Java 8+ |
default Spliterator<E> spliterator() | 返回分割迭代器 | Spliterator对象 | list.spliterator() | Java 8+，并行遍历 |
default Stream<E> stream() | 返回顺序流 | Stream对象 | list.stream() | Java 8+，流操作 |
default Stream<E> parallelStream() | 返回并行流 | Stream对象 | list.parallelStream() | Java 8+，并行流操作 |
集合运算方法
| 方法 | 数学运算 | 示意图 | 示例 |
|---|---|---|---|
addAll() | 并集 | A ∪ B | A.addAll(B) |
retainAll() | 交集 | A ∩ B | A.retainAll(B) |
removeAll() | 差集 | A - B | A.removeAll(B) |
常见操作示例
| 操作需求 | 代码示例 | 说明 |
|---|---|---|
| 遍历集合 | for (E e : collection) { ... } | 增强for循环 |
| 安全遍历并删除 | iterator.remove() | 使用迭代器删除 |
| 转换为数组 | String[] arr = coll.toArray(new String[0]) | 推荐写法 |
| 批量添加元素 | coll.addAll(Arrays.asList("A","B","C")) | 初始化集合 |
| 过滤集合 | coll.removeIf(e -> e.startsWith("A")) | Java 8+ |
| 集合判空 | if (!coll.isEmpty()) { ... } | 优于size() > 0 |
注意事项表格
| 方法 | 注意事项 | 推荐做法 |
|---|---|---|
| contains() | 依赖equals()和hashCode() | 正确实现这两个方法 |
| remove(Object) | 只删除第一个匹配项 | 使用removeIf()删除所有 |
| toArray() | 无参方法返回Object[] | 使用带参方法指定类型 |
| addAll() | 可能修改原集合 | 注意并发修改异常 |
| clear() | 不释放元素引用 | 大集合考虑设为null |
| iterator() | 遍历时不能修改集合 | 使用迭代器的remove() |
| 场景 | 建议 | 理由 |
|---|---|---|
| 频繁包含检查 | 使用HashSet | O(1)时间复杂度 |
| 频繁插入删除 | 使用LinkedList | 首尾操作O(1) |
| 随机访问 | 使用ArrayList | O(1)索引访问 |
| 需要排序 | 使用TreeSet | 自动维护顺序 |
| 线程安全 | 使用并发集合 | ConcurrentHashMap等 |
| 只读操作 | 使用不可变集合 | Collections.unmodifiableXXX() |
Collection集合中所包含的方法：
publicinterfaceCollection<E>extendsIterable<E>{// 基本操作方法intsize();booleanisEmpty();booleancontains(Objecto);booleanadd(Ee);booleanremove(Objecto);// 批量操作booleancontainsAll(Collection<?>c);booleanaddAll(Collection<?extendsE>c);booleanremoveAll(Collection<?>c);booleanretainAll(Collection<?>c);voidclear();// 数组转换Object[]toArray();<T>T[]toArray(T[]a);// 迭代器Iterator<E>iterator();// Java 8 新增方法defaultbooleanremoveIf(Predicate<?superE>filter){...}defaultSpliterator<E>spliterator(){...}defaultStream<E>stream(){...}defaultStream<E>parallelStream(){...}}1.List集合
List集合的特点就是存取有序，可以存储重复的元素，可以用下标进行元素的操作
该类适用于多线程下读多写少的并发场景,它在有写操作的时候会copy一份数据，然后写完再设置成新的数据,同时也进行了重入锁的处理保证了安全。
1.CopyOnWriteArrayList
CopyOnWriteArrayList是Java并发包中的线程安全List 实现，采用"写时复制"策略
读操作：
// 直接读取，无需加锁publicEget(intindex){returnget(getArray(),index);// 直接访问当前数组}写操作：
// 修改操作（add/set/remove）publicbooleanadd(Ee){synchronized(lock){// 写操作加锁Object[]elements=getArray();intlen=elements.length;// 1. 创建新数组（长度+1）Object[]newElements=Arrays.copyOf(elements,len+1);// 2. 在新数组上修改newElements[len]=e;// 3. 替换引用setArray(newElements);returntrue;}}2、ArrayList
它是一个标准的集合实现类,特点为有序,可重复,存储是连续的,因此查询较快,增删较为慢,使用Object数组进行存储。ArrayList是 Java 中最常用的动态数组实现，基于数组实现，支持动态扩容。
ArrayList底层实现：
publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{// 默认初始容量privatestaticfinalintDEFAULT_CAPACITY=10;// 存储元素的数组transientObject[]elementData;// non-private to simplify nested class access// 当前元素数量privateintsize;// 空数组实例（用于空列表）privatestaticfinalObject[]EMPTY_ELEMENTDATA={};privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};}核心特性
| 特性 | 说明 |
|---|---|
| 数据结构 | 基于数组 |
| 扩容机制 | 增长因子为 1.5 倍 |
| 随机访问 | O(1) 时间复杂度 |
| 插入/删除 | O(n) 时间复杂度（平均） |
| 线程安全 | 非线程安全 |
| 内存连续 | 连续内存分配 |
| 允许元素 | 允许 null 值，允许重复元素 |
构造方法
// 1. 默认构造（延迟初始化）ArrayList<String>list1=newArrayList<>();// 初始容量为0，第一次add时扩容到10// 2. 指定初始容量ArrayList<String>list2=newArrayList<>(100);// 初始容量100// 3. 从其他集合构造List<String>existingList=Arrays.asList("A","B","C");ArrayList<String>list3=newArrayList<>(existingList);扩容过程
// add() 方法中的扩容逻辑publicbooleanadd(Ee){ensureCapacityInternal(size+1);// 确保容量足够elementData[size++]=e;returntrue;}privatevoidensureCapacityInternal(intminCapacity){// 如果是空数组，使用默认容量10if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);}privatevoidensureExplicitCapacity(intminCapacity){modCount++;// 修改计数++// 需要扩容if(minCapacity-elementData.length>0)grow(minCapacity);}// 核心扩容方法privatevoidgrow(intminCapacity){intoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);// 增长1.5倍if(newCapacity-minCapacity<0)newCapacity=minCapacity;if(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);// 创建新数组并拷贝数据elementData=Arrays.copyOf(elementData,newCapacity);}常用方法详解
1. 添加元素
ArrayList<String>list=newArrayList<>();// 末尾添加list.add("A");// ["A"]list.add("B");// ["A", "B"]// 指定位置插入list.add(1,"C");// ["A", "C", "B"] O(n)操作// 批量添加list.addAll(Arrays.asList("D","E"));// ["A", "C", "B", "D", "E"]// 指定位置批量添加list.addAll(2,Arrays.asList("X","Y"));// ["A", "C", "X", "Y", "B", "D", "E"]2. 访问元素
ArrayList<String>list=newArrayList<>(Arrays.asList("A","B","C","D"));// 获取元素（随机访问 O(1)）Stringfirst=list.get(0);// "A"Stringlast=list.get(list.size()-1);// "D"// 遍历元素for(inti=0;i<list.size();i++){System.out.println(list.get(i));}// 增强for循环for(Stringitem:list){System.out.println(item);}// Java 8+ forEachlist.forEach(System.out::println);// 迭代器遍历Iterator<String>iterator=list.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}3. 修改元素
ArrayList<String>list=newArrayList<>(Arrays.asList("A","B","C"));// 设置元素（替换）list.set(1,"BB");// ["A", "BB", "C"]// 批量替换（Java 8+）list.replaceAll(s->s+"!");// ["A!", "BB!", "C!"]// 排序list.sort(String::compareTo);// 自然排序list.sort(Comparator.reverseOrder());// 逆序Collections.sort(list);// 传统方式// 洗牌（随机打乱）Collections.shuffle(list);4. 删除元素
ArrayList<String>list=newArrayList<>(Arrays.asList("A","B","C","D","E","B"));// 按索引删除（返回被删除元素）Stringremoved=list.remove(2);// 删除 "C"，返回 "C"// 按元素删除（删除第一个匹配项）booleansuccess=list.remove("B");// 删除第一个 "B"，返回 truelist.remove("X");// 元素不存在，返回 false// 批量删除list.removeAll(Arrays.asList("D","E"));// 删除所有匹配项// 条件删除（Java 8+）list.removeIf(s->s.startsWith("A"));// 删除所有以A开头的元素// 保留指定元素（交集）list.retainAll(Arrays.asList("B","C"));// 只保留 B 和 C// 清空list.clear();// 清空所有元素5. 查找元素
ArrayList<String>list=newArrayList<>(Arrays.asList("A","B","C","B","D"));// 查找索引intfirstIndex=list.indexOf("B");// 1intlastIndex=list.lastIndexOf("B");// 3intnotFound=list.indexOf("X");// -1// 判断包含booleancontainsB=list.contains("B");// truebooleancontainsAll=list.containsAll(Arrays.asList("A","C"));// true// 查找条件匹配（Java 8+）Optional<String>firstMatch=list.stream().filter(s->s.length()>1).findFirst();booleananyMatch=list.stream().anyMatch(s->s.equals("B"));booleanallMatch=list.stream().allMatch(s->s!=null);3、LinkedList
LinkedList是 Java 中基于双向链表实现的List，同时也实现了 Deque 接口，可以作为队列或栈使用。
与其他的实现类不同,他的底层是采用链接形式存储的,因此增删块,查询较慢如:
节点结构
privatestaticclassNode<E>{Eitem;// 存储的元素Node<E>next;// 后继节点Node<E>prev;// 前驱节点Node(Node<E>prev,Eelement,Node<E>next){this.item=element;this.next=next;this.prev=prev;}}链表结构
publicclassLinkedList<E>extendsAbstractSequentialList<E>implementsList<E>,Deque<E>,Cloneable,java.io.Serializable{transientintsize=0;// 链表大小transientNode<E>first;// 头节点transientNode<E>last;// 尾节点// 节点关系示意图：// first ←→ node1 ←→ node2 ←→ ... ←→ last// ↑ ↑ ↑ ↑// prev=null prev=first prev=node1 prev=...// next=node1 next=node2 next=node3 next=null}核心特性
| 特性 | 说明 |
|---|---|
| 数据结构 | 双向链表 |
| 内存分配 | 非连续内存 |
| 随机访问 | O(n) 时间复杂度 |
| 插入/删除 | O(1) 时间复杂度（已知节点位置） |
| 头尾操作 | O(1) 时间复杂度 |
| 线程安全 | 非线程安全 |
| 允许元素 | 允许 null 值，允许重复元素 |
| 额外空间 | 每个元素需要存储前后指针 |
构造方法
// 1. 默认构造（空链表）LinkedList<String>list1=newLinkedList<>();// 2. 从其他集合构造List<String>existingList=Arrays.asList("A","B","C");LinkedList<String>list2=newLinkedList<>(existingList);// 创建后结构：// first → Node("A") ↔ Node("B") ↔ Node("C") ← last// size = 31. 添加元素
LinkedList<String>list=newLinkedList<>();// 添加到末尾（List接口）list.add("A");// [A]list.add("B");// [A, B]// 指定位置插入list.add(1,"C");// [A, C, B]// 添加到末尾（等价于add）list.addLast("D");// [A, C, B, D]// 添加到开头list.addFirst("Z");// [Z, A, C, B, D]// 批量添加list.addAll(Arrays.asList("E","F"));// [Z, A, C, B, D, E, F]2. 访问元素
LinkedList<String>list=newLinkedList<>(Arrays.asList("A","B","C","D","E"));// 获取头尾元素Stringfirst=list.getFirst();// "A"Stringlast=list.getLast();// "E"// 按索引获取（需要遍历）Stringthird=list.get(2);// "C" - 从头开始遍历// 遍历方式for(inti=0;i<list.size();i++){// ❌ 低效：每次get都是O(n)System.out.println(list.get(i));}// ✅ 推荐：迭代器遍历for(Stringitem:list){// 使用迭代器，O(n)总体System.out.println(item);}// ✅ 推荐：列表迭代器（可双向遍历）ListIterator<String>iterator=list.listIterator();while(iterator.hasNext()){System.out.println(iterator.next());}// 反向遍历while(iterator.hasPrevious()){System.out.println(iterator.previous());}3. 查找元素
LinkedList<String>list=newLinkedList<>(Arrays.asList("A","B","C","B","D"));// 查找索引（从头开始遍历）intfirstIndex=list.indexOf("B");// 1intlastIndex=list.lastIndexOf("B");// 3// 判断包含booleanhasA=list.contains("A");// true// 查找条件匹配（Java 8+）Optional<String>result=list.stream().filter(s->s.startsWith("C")).findFirst();4. 删除元素
LinkedList<String>list=newLinkedList<>(Arrays.asList("A","B","C","D","E"));// 删除头节点StringremovedFirst=list.removeFirst();// "A"StringpolledFirst=list.pollFirst();// "B"（队列风格）// 删除尾节点StringremovedLast=list.removeLast();// "E"StringpolledLast=list.pollLast();// "D"// 按索引删除（需要遍历到该位置）Stringremoved=list.remove(0);// "C"// 按元素删除（删除第一个匹配项）booleansuccess=list.remove("B");// false（"B"已不存在）// 清空list.clear();// first = last = null, size = 04、Vector
该类于JDK1.1就出现了，特点为:线程安全但是效率较慢因为他的方法大多采用synchronized进行修饰,也是采用Object数组进行存储
底层数据结构
publicclassVector<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{// 存储元素的数组protectedObject[]elementData;// 元素数量protectedintelementCount;// 容量增长系数（扩容时使用）protectedintcapacityIncrement;// 默认初始容量privatestaticfinalintDEFAULT_CAPACITY=10;}核心特性
| 特性 | Vector | ArrayList | 说明 |
|---|---|---|---|
| 线程安全 | ✅ 是（synchronized） | ❌ 否 | Vector 的主要特点 |
| 数据结构 | 动态数组 | 动态数组 | 底层都是数组 |
| 扩容机制 | 可指定增长量，默认2倍 | 固定1.5倍 | Vector 更灵活 |
| 性能 | 较慢（锁开销） | 较快 | Vector 有同步开销 |
| 迭代器 | 快速失败 | 快速失败 | 都支持 fail-fast |
| 遗留类 | ✅ 是（JDK 1.0） | ❌ 否（JDK 1.2） | Vector 已过时 |
构造方法
// 1. 默认构造（容量10，满时容量翻倍）Vector<String>vec1=newVector<>();// 2. 指定初始容量Vector<String>vec2=newVector<>(100);// 3. 指定初始容量和容量增长量Vector<String>vec3=newVector<>(100,20);// 初始容量100，每次扩容增加20// 4. 从集合构造List<String>list=Arrays.asList("A","B","C");Vector<String>vec4=newVector<>(list);扩容逻辑
// Vector 的扩容方法privatevoidgrow(intminCapacity){intoldCapacity=elementData.length;// 关键：如果有 capacityIncrement，按增量增长；否则翻倍intnewCapacity=oldCapacity+((capacityIncrement>0)?capacityIncrement:oldCapacity);if(newCapacity-minCapacity<0)newCapacity=minCapacity;if(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);elementData=Arrays.copyOf(elementData,newCapacity);}扩容示例
// 示例1：默认扩容（翻倍）Vector<Integer>vec1=newVector<>(5);// 初始容量：5vec1.add(1);vec1.add(2);vec1.add(3);vec1.add(4);vec1.add(5);vec1.add(6);// 触发扩容：5 → 10（翻倍）// 示例2：指定增量扩容Vector<Integer>vec2=newVector<>(5,3);// 初始容量：5，增量：3vec2.add(1);vec2.add(2);vec2.add(3);vec2.add(4);vec2.add(5);vec2.add(6);// 触发扩容：5 → 8（5+3）vec2.add(7);vec2.add(8);vec2.add(9);// 触发扩容：8 → 11（8+3）同步机制
// Vector 的所有公共方法都加了 synchronizedpublicsynchronizedbooleanadd(Ee){modCount++;ensureCapacityHelper(elementCount+1);elementData[elementCount++]=e;returntrue;}publicsynchronizedEget(intindex){if(index>=elementCount)thrownewArrayIndexOutOfBoundsException(index);returnelementData(index);}publicsynchronizedEremove(intindex){modCount++;if(index>=elementCount)thrownewArrayIndexOutOfBoundsException(index);EoldValue=elementData(index);intnumMoved=elementCount-index-1;if(numMoved>0)System.arraycopy(elementData,index+1,elementData,index,numMoved);elementData[--elementCount]=null;// 帮助GCreturnoldValue;}复合操作的线程安全问题
// 即使单个方法是线程安全的，复合操作也可能有问题Vector<String>vector=newVector<>();// ❌ 线程不安全：check-then-act 模式if(!vector.isEmpty()){// 线程A检查Stringitem=vector.get(0);// 线程B可能在这里remove(0)// 可能抛出 IndexOutOfBoundsException}// ✅ 解决方案：对整个复合操作加锁synchronized(vector){if(!vector.isEmpty()){Stringitem=vector.get(0);// 安全操作}}// ❌ 另一个问题：迭代中的修改for(inti=0;i<vector.size();i++){Stringitem=vector.get(i);// size()和get()之间可能有其他线程修改process(item);}// ✅ 解决方案：迭代时加锁synchronized(vector){for(inti=0;i<vector.size();i++){Stringitem=vector.get(i);process(item);}}1. 容量管理方法
Vector<String>vec=newVector<>(10);// 获取/设置容量intcapacity=vec.capacity();// 当前容量：10vec.ensureCapacity(100);// 确保容量至少100vec.trimToSize();// 修剪容量到当前大小// 设置大小（可能截断或填充null）vec.setSize(15);// 如果原来小于15，填充nullvec.setSize(5);// 如果原来大于5，截断后面元素// 获取底层数组Object[]array=vec.toArray();2. 元素操作特有方法
Vector<String>vec=newVector<>(Arrays.asList("A","B","C","D"));// 添加元素（尾部）vec.addElement("E");// 同add()vec.insertElementAt("X",2);// 在索引2处插入// 设置元素vec.setElementAt("BB",1);// 设置索引1为"BB"// 删除元素vec.removeElement("B");// 删除第一个"B"vec.removeElementAt(0);// 删除索引0元素vec.removeAllElements();// 清空所有元素// 查找元素intindex=vec.indexOf("C");// 查找索引intlastIndex=vec.lastIndexOf("D");// 从后往前查找booleancontains=vec.contains("A");// 是否包含// 获取首尾元素Stringfirst=vec.firstElement();// 第一个元素Stringlast=vec.lastElement();// 最后一个元素3. 枚举器（Enumeration）
Vector<String>vec=newVector<>(Arrays.asList("A","B","C"));// 获取枚举器（旧版迭代器）Enumeration<String>enumeration=vec.elements();// 遍历while(enumeration.hasMoreElements()){Stringelement=enumeration.nextElement();System.out.println(element);}// 与Iterator对比Iterator<String>iterator=vec.iterator();while(iterator.hasNext()){Stringelement=iterator.next();System.out.println(element);iterator.remove();// Enumeration没有remove方法}
