#32
Java八股
集合 基础用法掌握 速通
小林 不是很全
老韩 详细底层 byd课程质量一般
八股文听书
算法题
不会写byd
密码的还没开始看
双指针技巧秒杀七道链表题目 | labuladong 的算法笔记
等等熬夜看
笔记
实现底层代码
后面非常长
但是也只写到了list完 map 和set明天写
collection
这段代码展示了Java集合框架的核心接口层次结构。`Collection` 是整个集合框架的根接口，定义了集合操作的基本契约。以下是对 `Collection` 接口及其主要方法的详细讲解：
### **一、`Collection` 接口概述**
`Collection` 是Java集合框架的顶级接口之一（另一个是 `Map`），它代表一组对象（元素）的集合。所有具体集合类（如 `ArrayList`、`HashSet`）都直接或间接实现了这个接口。
`Collection` 接口定义了集合的基本操作，包括添加、删除、查询、遍历等。它不关心元素的顺序或存储方式，具体行为由子接口（如 `List`、`Set`）和实现类决定。
### **二、主要方法分类解析**
#### 1. **添加元素**
```java
boolean add(E e);
boolean addAll(Collection<? extends E> c);
```
- **`add(E e)`**：将元素 `e` 添加到集合中。如果集合因添加操作发生变化，则返回 `true`；如果集合不允许重复且元素已存在，则返回 `false`。
- **`addAll(Collection<? extends E> c)`**：将指定集合 `c` 中的所有元素添加到当前集合中。如果集合因添加操作发生变化，则返回 `true`。
#### 2. **删除元素**
```java
boolean remove(Object o);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
```
- **`remove(Object o)`**：移除集合中首次出现的指定元素 `o`（如果存在）。如果集合因移除操作发生变化，则返回 `true`。
- **`removeAll(Collection<?> c)`**：移除当前集合中所有包含在指定集合 `c` 中的元素（即差集操作）。
- **`retainAll(Collection<?> c)`**：仅保留当前集合中同时存在于指定集合 `c` 中的元素（即交集操作）。
- **`clear()`**：清空集合中的所有元素。
#### 3. **查询元素**
```java
boolean contains(Object o);
boolean containsAll(Collection<?> c);
int size();
boolean isEmpty();
```
- **`contains(Object o)`**：判断集合是否包含指定元素 `o`。
- **`containsAll(Collection<?> c)`**：判断集合是否包含指定集合 `c` 中的所有元素。
- **`size()`**：返回集合中的元素数量。
- **`isEmpty()`**：判断集合是否为空（元素数量为0）。
#### 4. **遍历元素**
```java
Iterator<E> iterator();
default void forEach(Consumer<? super E> action) {
// ...
}
```
- **`iterator()`**：返回一个迭代器，用于遍历集合中的元素。这是最基本的遍历方式，所有集合类都必须实现。
- **`forEach(Consumer<? super E> action)`**：Java 8引入的默认方法，使用Lambda表达式遍历集合元素（函数式编程风格）。
#### 5. **集合转换**
```java
Object[] toArray();
<T> T[] toArray(T[] a);
```
- **`toArray()`**：将集合转换为数组（返回 `Object[]` 类型）。
- **`toArray(T[] a)`**：将集合转换为指定类型的数组。如果数组 `a` 的长度足够，则元素直接存入 `a`；否则，创建一个新数组并返回。
#### 6. **其他方法**
```java
default boolean removeIf(Predicate<? super E> filter) {
// ...
}
```
- **`removeIf(Predicate<? super E> filter)`**：Java 8引入的默认方法，移除满足给定条件的所有元素。
### **三、子接口与实现类**
`Collection` 接口的主要子接口包括：
1. **`List`**：有序集合，允许重复元素，支持索引访问（如 `ArrayList`、`LinkedList`）。
2. **`Set`**：不允许重复元素的集合（如 `HashSet`、`TreeSet`）。
3. **`Queue`**：队列，遵循FIFO（先进先出）原则（如 `LinkedList`、`PriorityQueue`）。
`Map` 虽然不直接继承 `Collection`，但也是集合框架的核心接口，用于存储键值对映射关系（如 `HashMap`、`TreeMap`）。
### **四、示例代码**
以下是 `Collection` 常用方法的示例：
```java
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class CollectionExample {
public static void main(String[] args) {
// 创建一个ArrayList实例（实现了Collection接口）
Collection<String> fruits = new ArrayList<>();
// 添加元素
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
System.out.println(fruits); // 输出: [Apple, Banana, Cherry]
// 查询元素
System.out.println(fruits.contains("Banana")); // 输出: true
System.out.println(fruits.size()); // 输出: 3
// 删除元素
fruits.remove("Banana");
System.out.println(fruits); // 输出: [Apple, Cherry]
// 遍历元素（使用迭代器）
Iterator<String> iterator = fruits.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
// 遍历元素（使用forEach和Lambda）
fruits.forEach(fruit -> System.out.println(fruit.toUpperCase()));
// 转换为数组
String[] array = fruits.toArray(new String[0]);
System.out.println(java.util.Arrays.toString(array)); // 输出: [Apple, Cherry]
}
}
```
### **五、注意事项**
1. **线程安全**：`Collection` 的默认实现（如 `ArrayList`、`HashSet`）是非线程安全的。如需线程安全，可使用 `Collections.synchronizedList()` 或并发集合类（如 `CopyOnWriteArrayList`）。
2. **空元素处理**：大多数实现允许 `null` 元素（如 `ArrayList`），但 `Set` 的实现（如 `HashSet`）通常不允许重复的 `null`。
3. **迭代器修改**：在使用迭代器遍历集合时，若通过集合本身的方法（而非迭代器的 `remove()`）修改集合结构，会抛出 `ConcurrentModificationException`。
### **总结**
`Collection` 接口是Java集合框架的基础，定义了集合操作的通用契约。通过子接口和实现类，它提供了灵活多样的数据结构选择，适用于各种场景。理解 `Collection` 的核心方法是掌握Java集合框架的关键。
自己实现：
_collection
package _Collection;
/**
* 集合层次结构中的根接口。集合表示一组对象，称为其元素。
* 某些集合允许重复元素，而其他集合则不允许。某些集合是有序的，而其他集合是无序的。
* JDK 不提供此接口的直接实现：它提供了更具体的子接口（如 Set 和 List）的实现。
* 此接口通常用于传递集合，并在需要最大通用性的地方操作它们。
*
* @param <E> 此集合中元素的类型
* @see Set_
* @see List_
* @see Map_
* @see SortedSet_
* @see SortedList_
* @see HashSet_
* @see ArrayList_
* @see LinkedList_
*/
public interface Collection_<E> extends Iterable<E> {
/**
* 返回此集合中的元素数。
* 如果此集合包含超过 Integer.MAX_VALUE 个元素，则返回 Integer.MAX_VALUE。
*
* @return 此集合中的元素数
*/
int size();
/**
* 如果此集合不包含任何元素，则返回 true。
*
* @return 如果此集合不包含任何元素，则返回 true
*/
boolean isEmpty();
/**
* 如果此集合包含指定的元素，则返回 true。
* 更正式地说，当且仅当此集合包含至少一个元素 e 时返回 true
* (o==null ? e==null : o.equals(e))。
*
* @param o 要检查是否包含在此集合中的元素
* @return 如果此集合包含指定的元素，则返回 true
* @throws ClassCastException 如果指定元素的类型与此集合不兼容
* （可选）
* @throws NullPointerException 如果指定的元素为 null 并且此集合不允许 null 元素
* （可选）
*/
boolean contains(Object o);
/**
* 返回包含此集合中所有元素的数组。
* 如果此集合对其迭代器返回元素的顺序做出任何保证，则此方法必须以相同的顺序返回元素。
*
* 返回的数组将是 "安全的"，因为此集合不维护对它的引用。
* （换句话说，即使此集合由数组支持，此方法也必须分配一个新数组）。
* 因此，调用者可以自由修改返回的数组。
*
* 此方法充当基于数组的 API 与基于集合的 API 之间的桥梁。
*
* @return 包含此集合中所有元素的数组
*/
Object[] toArray();
/**
* 返回包含此集合中所有元素的数组；
* 返回数组的运行时类型是指定数组的运行时类型。
* 如果集合适合指定的数组，则返回其中。
* 否则，将为指定数组的运行时类型和此集合的大小分配一个新数组。
*
* 如果此集合适合指定的数组并有剩余空间（即数组的元素比此集合多），
* 则紧跟在集合末尾的数组元素被设置为 null。
* （这仅在调用者知道此集合不包含任何 null 元素时才能确定此集合的长度。）
*
* 如果此集合对其迭代器返回元素的顺序做出任何保证，则此方法必须以相同的顺序返回元素。
*
* 像 toArray() 方法一样，此方法充当基于数组的 API 与基于集合的 API 之间的桥梁。
* 此外，此方法允许精确控制输出数组的运行时类型，并且在某些情况下可以用于节省分配成本。
*
* 假设 x 是一个已知只包含字符串的集合。
* 以下代码可用于将集合转储到新分配的 String 数组中：
*
* String[] y = x.toArray(new String[0]);
*
* 注意 toArray(new Object[0]) 和 toArray() 在功能上是相同的。
*
* @param <T> 包含集合的数组的运行时类型
* @param a 要存储此集合元素的数组（如果它足够大）；
* 否则，将为此目的分配相同运行时类型的新数组
* @return 包含此集合元素的数组
* @throws ArrayStoreException 如果指定数组的运行时类型不是此集合每个元素的运行时类型的超类型
* @throws NullPointerException 如果指定的数组为 null
*/
<T> T[] toArray(T[] a);
/**
* 确保此集合包含指定的元素（可选操作）。
* 如果此集合因调用而更改，则返回 true。
* （如果此集合不允许重复且已包含指定的元素，则返回 false。）
*
* 支持此操作的集合可能会限制可以添加到此集合的元素。
* 特别是，某些集合将拒绝添加 null 元素，而其他集合将对可能添加的元素类型强加限制。
* 集合类应在其文档中明确指定对可以添加哪些元素的任何限制。
*
* 如果集合拒绝添加特定元素（null 元素除外），
* 则它必须抛出异常（而不是返回 false）。
* 这保留了在此调用返回后此集合始终包含指定元素的不变量。
*
* @param e 要确保在此集合中存在的元素
* @return 如果此集合因调用而更改，则返回 true
* @throws UnsupportedOperationException 如果此集合不支持 add 操作
* @throws ClassCastException 如果指定元素的类阻止将其添加到此集合
* @throws NullPointerException 如果指定的元素为 null 并且此集合不允许 null 元素
* @throws IllegalArgumentException 如果此元素的某些属性阻止将其添加到此集合
*/
boolean add(E e);
/**
* 从此集合中移除指定元素的单个实例（如果存在）（可选操作）。
* 更正式地说，移除元素 e 使得
* (o==null ? e==null : o.equals(e))，
* 如果此集合包含一个或多个这样的元素。
* 如果此集合包含指定的元素（或者等效地，如果此集合因调用而更改），则返回 true。
*
* @param o 要从此集合中移除的元素（如果存在）
* @return 如果此集合包含指定的元素，则返回 true
* @throws ClassCastException 如果指定元素的类型与此集合不兼容
* （可选）
* @throws NullPointerException 如果指定的元素为 null 并且此集合不允许 null 元素
* （可选）
* @throws UnsupportedOperationException 如果此集合不支持 remove 操作
*/
boolean remove(Object o);
/**
* 如果此集合包含指定集合中的所有元素，则返回 true。
*
* @param c 要在此集合中检查包含的集合
* @return 如果此集合包含指定集合中的所有元素，则返回 true
* @throws ClassCastException 如果指定集合的元素的类型与此集合不兼容
* （可选）
* @throws NullPointerException 如果指定的集合包含一个或多个 null 元素
* 并且此集合不允许 null 元素
* （可选）
* 或者如果指定的集合为 null
* @see #contains(Object)
*/
boolean containsAll(Collection_<?> c);
/**
* 将指定集合中的所有元素添加到此集合（可选操作）。
* 如果在操作进行中修改了指定的集合，则此操作的行为未定义。
* （这意味着如果指定的集合是此集合，并且此集合是非空的，则此调用的行为未定义。）
*
* @param c 包含要添加到此集合的元素的集合
* @return 如果此集合因调用而更改，则返回 true
* @throws UnsupportedOperationException 如果此集合不支持 addAll 操作
* @throws ClassCastException 如果指定集合的元素的类阻止将其添加到此集合
* @throws NullPointerException 如果指定的集合包含一个或多个 null 元素
* 并且此集合不允许 null 元素，
* 或者如果指定的集合为 null
* @throws IllegalArgumentException 如果指定集合的元素的某些属性阻止将其添加到此集合
* @see #add(Object)
*/
boolean addAll(Collection_<? extends E> c);
/**
* 从此集合中移除指定集合中包含的所有元素（可选操作）。
* 此调用返回后，此集合将不包含与指定集合相同的元素。
*
* @param c 包含要从此集合中移除的元素的集合
* @return 如果此集合因调用而更改，则返回 true
* @throws UnsupportedOperationException 如果此集合不支持 removeAll 操作
* @throws ClassCastException 如果此集合的元素的类型与指定的集合不兼容
* （可选）
* @throws NullPointerException 如果此集合包含 null 元素并且指定的集合不允许 null 元素
* （可选）
* 或者如果指定的集合为 null
* @see #remove(Object)
* @see #contains(Object)
*/
boolean removeAll(Collection_<?> c);
/**
* 仅保留此集合中包含在指定集合中的元素（可选操作）。
* 换句话说，从此集合中移除所有未包含在指定集合中的元素。
*
* @param c 包含要保留在此集合中的元素的集合
* @return 如果此集合因调用而更改，则返回 true
* @throws UnsupportedOperationException 如果此集合不支持 retainAll 操作
* @throws ClassCastException 如果此集合的元素的类型与指定的集合不兼容
* （可选）
* @throws NullPointerException 如果此集合包含 null 元素并且指定的集合不允许 null 元素
* （可选）
* 或者如果指定的集合为 null
* @see #remove(Object)
* @see #contains(Object)
*/
boolean retainAll(Collection_<?> c);
/**
* 从此集合中移除所有元素（可选操作）。
* 此方法返回后，集合将为空，除非抛出异常。
*
* @throws UnsupportedOperationException 如果此集合不支持 clear 操作
*/
void clear();
/**
* 比较指定对象与此集合是否相等。
*
* 虽然 Collection 接口本身不添加任何超出 Object 类的规定的合同
* 但直接实现 Collection 的程序员（换句话说，创建一个 Collection 但它不是 Set 或 List 的类）
* 必须小心重写 Object.equals 方法。
* 不这样做将导致违反 Object.equals 方法的通用合同，
* 并且该行为将是未定义的。
*
* 所有通用的 Collection 实现类都应该重写 Object.equals 方法，
* 而不是使用 Object 的默认实现，后者仅测试对象引用是否相等。
* 集合的 equals 方法必须实现元素的相等性，而不是引用的相等性。
* 然而，Collection 接口不强制执行此操作。
* （Set 和 List 接口确实强制执行此操作。）
*
* @param o 要与此集合进行相等性比较的对象
* @return 如果指定对象等于此集合，则返回 true
* @see Object#equals(Object)
* @see Set#equals(Object)
* @see List#equals(Object)
*/
boolean equals(Object o);
/**
* 返回此集合的哈希码值。
* 当 Collection 接口不添加任何超出 Object 类的规定的合同
* 时，程序员应该注意，任何重写 equals 方法的类也必须重写 hashCode 方法，
* 以满足 Object.hashCode 方法的通用合同。
* 特别是，c1.equals(c2) 意味着 c1.hashCode()==c2.hashCode()。
*
* @return 此集合的哈希码值
* @see Object#hashCode()
* @see Object#equals(Object)
*/
int hashCode();
}
Itr
package _Collection;
public interface Iterator_<E> {
boolean hasNext();
E next();
default void remove(){
throw new UnsupportedOperationException("remove");
}
}
List_
package _Collection;
/**
* 有序集合（也称为序列）。此接口的用户可以精确控制列表中每个元素的插入位置。
* 用户可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。
*
* 与集合不同，列表通常允许重复元素。更正式地说，列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2，
* 并且如果它们允许 null 元素，它们通常允许多个 null 元素。
* 如果实现者选择不允许重复元素，他们应该在文档中说明这一点。
*
* List 接口在迭代器、add、remove、equals 和 hashCode 方法的协定上添加了其他规定，
* 以便在列表实现之间可以有明确定义的行为。
*
* 列表的用户可以通过索引操作列表的每个元素，可以搜索列表中的元素。
* 列表接口提供了 4 种位置（索引）访问列表元素的方法。
* 列表（像 Java 数组一样）是基于 0 的。
* 注意，对于某些实现（例如 LinkedList 类），这些操作可能执行时间过长。
* 每个列表的文档都应该指出其每个位置访问操作的性能特征。
*
* 列表接口提供了一个特殊的迭代器，称为 ListIterator，它允许元素插入和替换，
* 以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。
*
* List 接口提供了两种搜索指定对象的方法。
* 从性能的角度来看，应该谨慎使用这些方法。
* 在许多实现中，它们将执行代价高昂的线性搜索。
*
* List 接口提供了两种在列表中插入和移除多个元素的方法。
*
* 注意：虽然列表允许将自身作为元素包含，但建议格外小心：
* 相等和哈希码方法在这样的列表中不再是定义良好的。
*
* 某些列表实现对它们可能包含的元素有限制。
* 例如，某些实现禁止 null 元素，而某些实现对元素的类型有限制。
* 尝试添加不合格的元素会抛出未经检查的异常，通常是 NullPointerException 或 ClassCastException。
* 尝试查询不合格元素的存在可能会抛出异常，或者它可能只是返回 false；
* 某些实现会表现出前一种行为，而某些实现会表现出后一种。
* 更一般地，尝试对不合格元素执行操作，其完成不会导致将不合格元素插入到列表中，
* 可能会抛出异常，也可能会成功，这取决于实现的选择。
* 在此接口的规范中，此类异常被标记为 "可选"。
*
* @param <E> 此列表中元素的类型
* @author 豆包编程助手
* @see Collection_
* @see Set_
* @see ArrayList_
* @see LinkedList_
* @see Vector_
*/
public interface List_<E> extends Collection_<E> {
/**
* 返回此列表中指定位置的元素。
*
* @param index 要返回的元素的索引
* @return 此列表中指定位置的元素
* @throws IndexOutOfBoundsException 如果索引超出范围 (index < 0 || index >= size())
*/
E get(int index);
/**
* 用指定的元素替换此列表中指定位置的元素（可选操作）。
*
* @param index 要替换的元素的索引
* @param element 要存储在指定位置的元素
* @return 以前在指定位置的元素
* @throws UnsupportedOperationException 如果此列表不支持 set 操作
* @throws ClassCastException 如果指定元素的类阻止将其添加到此列表
* @throws NullPointerException 如果指定的元素为 null 并且此列表不允许 null 元素
* @throws IllegalArgumentException 如果指定元素的某些属性阻止将其添加到此列表
* @throws IndexOutOfBoundsException 如果索引超出范围 (index < 0 || index >= size())
*/
E set(int index, E element);
/**
* 在此列表中的指定位置插入指定的元素（可选操作）。
* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加 1）。
*
* @param index 要插入指定元素的索引
* @param element 要插入的元素
* @throws UnsupportedOperationException 如果此列表不支持 add 操作
* @throws ClassCastException 如果指定元素的类阻止将其添加到此列表
* @throws NullPointerException 如果指定的元素为 null 并且此列表不允许 null 元素
* @throws IllegalArgumentException 如果指定元素的某些属性阻止将其添加到此列表
* @throws IndexOutOfBoundsException 如果索引超出范围 (index < 0 || index > size())
*/
void add(int index, E element);
/**
* 移除并返回此列表中指定位置的元素（可选操作）。
* 将任何后续元素向左移动（从它们的索引中减去 1）。
* 返回此列表中先前位于指定位置的元素。
*
* @param index 要移除的元素的索引
* @return 以前在指定位置的元素
* @throws UnsupportedOperationException 如果此列表不支持 remove 操作
* @throws IndexOutOfBoundsException 如果索引超出范围 (index < 0 || index >= size())
*/
E remove(int index);
/**
* 返回此列表中首次出现的指定元素的索引，
* 如果此列表不包含该元素，则返回 -1。
* 更正式地说，返回最低索引 i，使得
* (o==null ? get(i)==null : o.equals(get(i)))，
* 如果没有这样的索引，则返回 -1。
*
* @param o 要搜索的元素
* @return 此列表中首次出现的指定元素的索引，或 -1（如果此列表不包含该元素）
* @throws ClassCastException 如果指定元素的类型与此列表不兼容
* （可选）
* @throws NullPointerException 如果指定的元素为 null 并且此列表不允许 null 元素
* （可选）
*/
int indexof(Object o);
/**
* 返回此列表中最后一次出现的指定元素的索引，
* 如果此列表不包含该元素，则返回 -1。
* 更正式地说，返回最高索引 i，使得
* (o==null ? get(i)==null : o.equals(get(i)))，
* 如果没有这样的索引，则返回 -1。
*
* @param o 要搜索的元素
* @return 此列表中最后一次出现的指定元素的索引，或 -1（如果此列表不包含该元素）
* @throws ClassCastException 如果指定元素的类型与此列表不兼容
* （可选）
* @throws NullPointerException 如果指定的元素为 null 并且此列表不允许 null 元素
* （可选）
*/
int lastIndexOf(Object o);
}
ArrayList_
package _Collection;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 自定义实现的动态数组类，模拟Java标准库中的ArrayList。
* 支持泛型，提供动态扩容、增删改查等基本集合操作。
* 使用modCount记录结构修改次数，支持fail-fast机制。
*/
public class ArrayList_<E> implements Collection_<E> {
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 存储元素的数组
private Object[] elementData;
// 当前元素数量
private int size;
// 记录结构修改次数，用于实现fail-fast机制
private int modCount = 0;
/**
* 无参构造函数，初始化默认容量数组
*/
public ArrayList_() {
this.elementData = new Object[DEFAULT_CAPACITY];
}
/**
* 指定初始容量的构造函数
* @param initialCapacity 初始容量
* @throws IllegalArgumentException 如果初始容量为负数
*/
public ArrayList_(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = new Object[0];
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
/**
* 返回集合中的元素数量
* @return 元素数量
*/
@Override
public int size() {
return size;
}
/**
* 判断集合是否为空
* @return 如果集合为空返回true，否则返回false
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 判断集合是否包含指定元素
* @param o 指定元素
* @return 如果包含返回true，否则返回false
*/
@Override
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 返回指定元素首次出现的索引
* @param o 指定元素
* @return 元素索引，如果不存在返回-1
*/
private int indexOf(Object o) {
// 处理null元素
if (o == null) {
for (int i = 0; i < size; i++) {
if (elementData[i] == null) return i;
}
} else {
// 处理非null元素，使用equals方法比较
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) return i;
}
}
return -1;
}
/**
* 将集合转换为数组
* @return 包含所有元素的数组
*/
@Override
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 将集合转换为指定类型的数组
* @param a 指定类型的数组
* @return 包含所有元素的数组
*/
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
// 如果传入数组长度小于集合大小，创建新数组
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
}
// 将元素复制到传入数组
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size) {
// 标记数组末尾
a[size] = null;
}
return a;
}
/**
* 在集合末尾添加元素
* @param e 要添加的元素
* @return 总是返回true
*/
@Override
public boolean add(E e) {
// 确保数组容量足够
ensureCapacityInternal(size + 1);
elementData[size++] = e;
modCount++; // 记录结构修改
return true;
}
/**
* 确保内部容量足够
* @param minCapacity 最小需要的容量
*/
private void ensureCapacityInternal(int minCapacity) {
if (minCapacity - elementData.length > 0) {
// 容量不足时进行扩容
grow(minCapacity);
}
}
/**
* 数组扩容方法
* @param minCapacity 最小需要的容量
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 扩容为原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) {
// 如果新容量仍然不够，直接使用最小需要的容量
newCapacity = minCapacity;
}
// 复制元素到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 移除集合中首次出现的指定元素
* @param o 指定元素
* @return 如果移除成功返回true，否则返回false
*/
@Override
public boolean remove(Object o) {
// 处理null元素
if (o == null) {
for (int index = 0; index < size; index++) {
if (elementData[index] == null) {
fastRemove(index);
return true;
}
}
} else {
// 处理非null元素
for (int index = 0; index < size; index++) {
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
}
return false;
}
/**
* 快速移除指定位置的元素（不做边界检查）
* @param index 要移除元素的索引
*/
private void fastRemove(int index) {
modCount++; // 记录结构修改
int numMoved = size - index - 1;
if (numMoved > 0) {
// 将后续元素前移
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
// 置空最后一个位置帮助GC
elementData[--size] = null;
}
/**
* 判断集合是否包含另一个集合的所有元素
* @param c 另一个集合
* @return 如果包含返回true，否则返回false
*/
@Override
public boolean containsAll(Collection_<?> c) {
// 遍历另一个集合的所有元素
for (Object e : c) {
if (!contains(e)) return false;
}
return true;
}
/**
* 将另一个集合的所有元素添加到当前集合
* @param c 另一个集合
* @return 如果集合发生变化返回true，否则返回false
*/
@Override
public boolean addAll(Collection_<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
// 复制元素到当前集合
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
modCount++; // 记录结构修改
return numNew != 0;
}
/**
* 移除当前集合中所有也存在于另一个集合的元素
* @param c 另一个集合
* @return 如果集合发生变化返回true，否则返回false
*/
@Override
public boolean removeAll(Collection_<?> c) {
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove(); // 使用迭代器的remove方法保证fail-fast
modified = true;
}
}
return modified;
}
/**
* 仅保留当前集合中也存在于另一个集合的元素
* @param c 另一个集合
* @return 如果集合发生变化返回true，否则返回false
*/
@Override
public boolean retainAll(Collection_<?> c) {
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove(); // 使用迭代器的remove方法保证fail-fast
modified = true;
}
}
return modified;
}
/**
* 清空集合中的所有元素
*/
@Override
public void clear() {
modCount++; // 记录结构修改
// 置空所有元素帮助GC
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}
/**
* 判断集合是否与另一个对象相等
* @param o 另一个对象
* @return 如果相等返回true，否则返回false
*/
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof Collection_)) return false;
Collection_<?> c = (Collection_<?>) o;
if (c.size() != size()) return false;
try {
Iterator<E> e1 = iterator();
Iterator<?> e2 = c.iterator();
// 逐个比较元素
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1 == null ? o2 == null : o1.equals(o2))) {
return false;
}
}
return !(e1.hasNext() || e2.hasNext());
} catch (ClassCastException | NullPointerException unused) {
return false;
}
}
/**
* 计算集合的哈希值
* @return 哈希值
*/
@Override
public int hashCode() {
int hashCode = 1;
// 计算每个元素的哈希值
for (E e : this) {
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
/**
* 返回集合的迭代器
* @return 迭代器对象
*/
@Override
public Iterator<E> iterator() {
return new Itr();
}
/**
* 迭代器实现类，支持fail-fast机制
*/
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回的元素索引
int lastRet = -1; // 上一次返回的元素索引，-1表示没有
int expectedModCount = modCount; // 期望的修改次数，用于fail-fast
/**
* 判断是否还有下一个元素
* @return 如果有返回true，否则返回false
*/
public boolean hasNext() {
return cursor != size;
}
/**
* 返回下一个元素
* @return 下一个元素
* @throws NoSuchElementException 如果没有下一个元素
* @throws ConcurrentModificationException 如果检测到并发修改
*/
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); // 检查并发修改
int i = cursor;
if (i >= size) {
throw new NoSuchElementException();
}
Object[] elementData = ArrayList_.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
cursor = i + 1;
return (E) elementData[lastRet = i];
}
/**
* 移除上一次返回的元素
* @throws IllegalStateException 如果没有调用next()或者已经调用了remove()
* @throws ConcurrentModificationException 如果检测到并发修改
*/
public void remove() {
if (lastRet < 0) {
throw new IllegalStateException();
}
checkForComodification();
try {
ArrayList_.this.remove(lastRet);
cursor = lastRet; // 重置cursor，因为元素被移除
lastRet = -1; // 防止重复调用remove
expectedModCount = modCount; // 更新期望的修改次数
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 检查是否有并发修改
* @throws ConcurrentModificationException 如果检测到并发修改
*/
final void checkForComodification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
}
LinkedList_
package _Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 基于双向链表实现的 {@link Collection_} 接口。
* 该类支持所有可选的集合操作，并允许存储包括 null 在内的所有元素。
*
* <p>所有操作的实现都遵循双向链表的典型操作模式。
* 索引操作会从链表头部或尾部开始遍历，具体取决于哪个方向距离目标位置更近。
*
* <p>注意，此实现不是线程安全的。
* 如果多个线程同时访问一个链表，并且至少有一个线程从结构上修改了链表，
* 则必须在外部进行同步。
* （结构修改是指添加或删除一个或多个元素的操作；仅设置元素的值不是结构修改。）
* 这通常通过对自然封装该集合的对象进行同步来完成。
* 如果不存在这样的对象，则应该使用 {@link java.util.Collections#synchronizedList}
* 方法来 "包装" 该列表。
* 最好在创建时完成这一操作，以防止意外的非同步访问：
* <pre>
* Collection_ list = Collections.synchronizedList(new LinkedList_());
* </pre>
*
* <p>该类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：
* 如果在迭代器创建后的任意时间从结构上修改了列表，
* 除非通过迭代器自身的 remove 或 add 方法，
* 否则迭代器将抛出 {@link ConcurrentModificationException}。
* 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是冒着在未来某个不确定时间发生任意的、不确定的行为的风险。
*
* <p>注意，迭代器的快速失败行为无法得到保证，
* 因为一般来说，不可能对非同步的并发修改做出任何硬性保证。
* 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。
* 因此，编写依赖于此异常的程序来保证其正确性是错误的：
* 迭代器的快速失败行为应该仅用于检测错误。
*
* @param <E> 此列表中元素的类型
* @author 豆包编程助手
* @see Collection_
* @see List_
* @see ArrayList_
* @since 1.0
*/
public class LinkedList_<E> implements Collection_<E> {
/**
* 链表的头节点。
* 当链表为空时，first 和 last 都为 null。
*/
private Node<E> first;
/**
* 链表的尾节点。
* 当链表为空时，first 和 last 都为 null。
*/
private Node<E> last;
/**
* 链表中的元素数量。
*/
private int size = 0;
/**
* 记录链表结构修改次数的计数器。
* 用于迭代器的快速失败机制。
*/
private int modCount = 0;
/**
* 链表的节点结构，包含元素值、前驱节点和后继节点。
*/
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
* 返回此链表中的元素数量。
*
* @return 链表中的元素数量
*/
@Override
public int size() {
return size;
}
/**
* 如果此链表不包含任何元素，则返回 true。
*
* @return 如果此链表不包含任何元素，则返回 true
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 如果此链表包含指定的元素，则返回 true。
*
* @param o 要检查是否包含在此链表中的元素
* @return 如果此链表包含指定的元素，则返回 true
* @throws ClassCastException 如果指定元素的类型与此链表不兼容
* @throws NullPointerException 如果指定的元素为 null 并且此链表不允许 null 元素
*/
@Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* 返回指定元素在此链表中首次出现的索引，
* 如果此链表不包含该元素，则返回 -1。
*
* @param o 要搜索的元素
* @return 指定元素在此链表中首次出现的索引，或 -1（如果此链表不包含该元素）
*/
private int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
return index;
}
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
}
return -1;
}
/**
* 返回包含此链表中所有元素的数组，
* 数组元素的顺序与链表迭代器返回的顺序相同。
*
* @return 包含此链表中所有元素的数组
*/
@Override
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next) {
result[i++] = x.item;
}
return result;
}
/**
* 返回包含此链表中所有元素的数组，
* 返回数组的运行时类型是指定数组的类型。
* 如果链表元素数量小于指定数组的长度，则在返回的数组中，
* 紧跟在链表元素后的元素被设置为 null。
*
* @param <T> 包含链表元素的数组的运行时类型
* @param a 要存储链表元素的数组（如果它足够大）；
* 否则，将为此目的分配相同运行时类型的新数组
* @return 包含此链表元素的数组
* @throws ArrayStoreException 如果指定数组的运行时类型不是此链表每个元素的运行时类型的超类型
* @throws NullPointerException 如果指定的数组为 null
*/
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
}
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next) {
result[i++] = x.item;
}
if (a.length > size) {
a[size] = null;
}
return a;
}
/**
* 将指定元素添加到此链表的尾部。
*
* @param e 要添加到此链表的元素
* @return true（根据 Collection.add 的规范）
* @throws NullPointerException 如果指定的元素为 null 并且此链表不允许 null 元素
*/
@Override
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 将指定元素作为最后一个元素链接到链表。
*/
private void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
modCount++;
}
/**
* 从此链表中移除首次出现的指定元素（如果存在）。
*
* @param o 要从此链表中移除的元素（如果存在）
* @return 如果此链表包含指定的元素，则返回 true
* @throws ClassCastException 如果指定元素的类型与此链表不兼容
* @throws NullPointerException 如果指定的元素为 null 并且此链表不允许 null 元素
*/
@Override
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* 从此链表中移除指定节点。
*
* @param x 要移除的节点
* @return 被移除节点的元素值
*/
private E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
/**
* 如果此链表包含指定集合中的所有元素，则返回 true。
*
* @param c 要检查是否包含在此链表中的集合
* @return 如果此链表包含指定集合中的所有元素，则返回 true
* @throws ClassCastException 如果指定集合中的某个元素的类型与此链表不兼容
* @throws NullPointerException 如果指定的集合包含 null 元素并且此链表不允许 null 元素，
* 或者如果指定的集合为 null
*/
@Override
public boolean containsAll(Collection_<?> c) {
for (Object e : c) {
if (!contains(e)) return false;
}
return true;
}
/**
* 将指定集合中的所有元素添加到此链表的尾部，
* 按照指定集合的迭代器返回的顺序。
*
* @param c 包含要添加到此链表的元素的集合
* @return 如果此链表因调用而更改，则返回 true
* @throws UnsupportedOperationException 如果此链表不支持 addAll 操作
* @throws ClassCastException 如果指定集合中的某个元素的类阻止将其添加到此链表
* @throws NullPointerException 如果指定的集合包含 null 元素并且此链表不允许 null 元素，
* 或者如果指定的集合为 null
* @throws IllegalArgumentException 如果指定集合的元素的某些属性阻止将其添加到此链表
*/
@Override
public boolean addAll(Collection_<? extends E> c) {
return addAll(size, c);
}
/**
* 将指定集合中的所有元素插入到此链表中的指定位置。
* 将当前位于该位置的元素（如果有）和任何后续元素向右移动（增加其索引）。
* 新元素将按照指定集合的迭代器返回的顺序出现在链表中。
*
* @param index 要插入第一个元素的位置索引
* @param c 包含要添加到此链表的元素的集合
* @return 如果此链表因调用而更改，则返回 true
* @throws IndexOutOfBoundsException 如果索引超出范围 (index < 0 || index > size)
* @throws UnsupportedOperationException 如果此链表不支持 addAll 操作
* @throws ClassCastException 如果指定集合中的某个元素的类阻止将其添加到此链表
* @throws NullPointerException 如果指定的集合包含 null 元素并且此链表不允许 null 元素，
* 或者如果指定的集合为 null
* @throws IllegalArgumentException 如果指定集合的元素的某些属性阻止将其添加到此链表
*/
public boolean addAll(int index, Collection_<?> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0) return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) {
first = newNode;
} else {
pred.next = newNode;
}
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
/**
* 返回指定索引处的（非 null）节点。
* 根据索引位置选择从头节点或尾节点开始遍历，以优化查找效率。
*/
private Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
/**
* 检查给定的索引是否为迭代或添加操作的有效位置索引。
*/
private void checkPositionIndex(int index) {
if (!isPositionIndex(index)) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
/**
* 判断给定的索引是否为迭代或添加操作的有效位置索引。
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/**
* 从此链表中移除包含在指定集合中的所有元素。
*
* @param c 包含要从此链表中移除的元素的集合
* @return 如果此链表因调用而更改，则返回 true
* @throws UnsupportedOperationException 如果此链表不支持 removeAll 操作
* @throws ClassCastException 如果此链表中的某个元素的类型与指定的集合不兼容
* @throws NullPointerException 如果此链表包含 null 元素并且指定的集合不允许 null 元素，
* 或者如果指定的集合为 null
*/
@Override
public boolean removeAll(Collection_<?> c) {
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
/**
* 仅保留此链表中包含在指定集合中的元素。
* 换句话说，从此链表中移除所有不包含在指定集合中的元素。
*
* @param c 包含要保留在此链表中的元素的集合
* @return 如果此链表因调用而更改，则返回 true
* @throws UnsupportedOperationException 如果此链表不支持 retainAll 操作
* @throws ClassCastException 如果此链表中的某个元素的类型与指定的集合不兼容
* @throws NullPointerException 如果此链表包含 null 元素并且指定的集合不允许 null 元素，
* 或者如果指定的集合为 null
*/
@Override
public boolean retainAll(Collection_<?> c) {
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
/**
* 从此链表中移除所有元素。
* 调用此方法后，链表将为空。
*/
@Override
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
/**
* 比较指定对象与此链表是否相等。
* 如果给定对象也是一个集合，并且两个集合具有相同的大小，
* 并且指定集合的迭代器返回的每个元素与此链表的迭代器返回的相应元素相等，
* 则返回 true。
* 换句话说，如果两个集合以相同的顺序包含相同的元素，则它们相等。
*
* @param o 要与此链表进行相等性比较的对象
* @return 如果指定对象等于此链表，则返回 true
*/
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof Collection_)) return false;
Collection_<?> c = (Collection_<?>) o;
if (c.size() != size()) return false;
try {
Iterator<E> e1 = iterator();
Iterator<?> e2 = c.iterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1 == null ? o2 == null : o1.equals(o2))) {
return false;
}
}
return !(e1.hasNext() || e2.hasNext());
} catch (ClassCastException | NullPointerException unused) {
return false;
}
}
/**
* 返回此链表的哈希码值。
* 哈希码值由链表中每个元素的哈希码累加计算得出，
* 遵循 Collection 接口的规范。
*
* @return 此链表的哈希码值
*/
@Override
public int hashCode() {
int hashCode = 1;
for (E e : this) {
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
/**
* 返回以适当顺序遍历此链表中元素的迭代器。
*
* @return 以适当顺序遍历此链表中元素的迭代器
*/
@Override
public Iterator<E> iterator() {
return new Itr();
}
/**
* 链表迭代器的实现类，支持快速失败机制。
*/
private class Itr implements Iterator<E> {
/**
* 最后一次返回的节点。
*/
private Node<E> lastReturned;
/**
* 下一个要返回的节点。
*/
private Node<E> next;
/**
* 下一个节点的索引。
*/
private int nextIndex;
/**
* 期望的修改次数，用于快速失败检查。
*/
private int expectedModCount = modCount;
Itr() {
next = (size == 0) ? null : first;
nextIndex = 0;
}
/**
* 如果迭代器有更多元素，则返回 true。
*
* @return 如果迭代器有更多元素，则返回 true
*/
public boolean hasNext() {
return nextIndex < size;
}
/**
* 返回迭代器中的下一个元素。
*
* @return 迭代器中的下一个元素
* @throws NoSuchElementException 如果迭代器没有更多元素
* @throws ConcurrentModificationException 如果在迭代过程中链表结构被修改
*/
public E next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException();
}
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
/**
* 移除迭代器最后返回的元素。
* 每次调用 next 方法后只能调用一次此方法。
*
* @throws IllegalStateException 如果尚未调用 next 方法，
* 或者在上一次调用 next 方法后已经调用了 remove 方法
* @throws ConcurrentModificationException 如果在迭代过程中链表结构被修改
*/
public void remove() {
checkForComodification();
if (lastReturned == null) {
throw new IllegalStateException();
}
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned) {
next = lastNext;
} else {
nextIndex--;
}
lastReturned = null;
expectedModCount++;
}
/**
* 检查链表的修改次数是否与迭代器创建时的次数一致。
* 如果不一致，则抛出 ConcurrentModificationException。
*/
final void checkForComodification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
}
Vector_
package _Collection;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 基于动态数组实现的线程安全集合类，支持自动扩容。
* 与 ArrayList 类似，但所有操作都通过 synchronized 保证线程安全。
*
* <p>Vector_ 的容量会在元素添加时自动增长，增长策略由 capacityIncrement 控制：
* - 若 capacityIncrement > 0，每次扩容增加该固定值
* - 若 capacityIncrement <= 0，每次扩容翻倍
*
* <p>注意：
* 1. 由于同步开销，建议在非并发环境下使用 ArrayList
* 2. 迭代器支持快速失败机制，但遍历时仍需外部同步
* 3. 允许存储 null 元素
*
* @param <E> 集合中元素的类型
* @author 豆包编程助手
* @see Collection_
* @see ArrayList_
* @since 1.0
*/
public class Vector_<E> implements Collection_<E> {
/** 存储元素的数组缓冲区 */
protected Object[] elementData;
/** 实际存储的元素数量 */
protected int elementCount;
/** 扩容时的增量值，若为 0 则每次扩容翻倍 */
protected int capacityIncrement;
/** 记录集合结构修改次数，用于快速失败机制 */
protected transient int modCount = 0;
/**
* 构造一个初始容量为 10 的空 Vector
*/
public Vector_() {
this(10);
}
/**
* 构造一个具有指定初始容量的空 Vector
*
* @param initialCapacity 初始容量
* @throws IllegalArgumentException 若初始容量为负数
*/
public Vector_(int initialCapacity) {
this(initialCapacity, 0);
}
/**
* 构造一个具有指定初始容量和扩容增量的空 Vector
*
* @param initialCapacity 初始容量
* @param capacityIncrement 扩容增量，若为 0 则每次扩容翻倍
* @throws IllegalArgumentException 若初始容量为负数
*/
public Vector_(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
/**
* 返回 Vector 中的元素数量
*
* @return 元素数量
*/
@Override
public synchronized int size() {
return elementCount;
}
/**
* 判断 Vector 是否为空
*
* @return 若 Vector 不包含任何元素则返回 true
*/
@Override
public synchronized boolean isEmpty() {
return elementCount == 0;
}
/**
* 判断 Vector 是否包含指定元素
*
* @param o 要查找的元素
* @return 若包含则返回 true
*/
@Override
public boolean contains(Object o) {
return indexOf(o, 0) >= 0;
}
/**
* 返回指定元素在 Vector 中首次出现的索引
*
* @param o 要查找的元素
* @return 元素首次出现的索引，若不存在则返回 -1
*/
public synchronized int indexOf(Object o) {
return indexOf(o, 0);
}
/**
* 从指定位置开始搜索，返回指定元素在 Vector 中首次出现的索引
*
* @param o 要查找的元素
* @param index 开始搜索的索引位置
* @return 元素首次出现的索引，若不存在则返回 -1
* @throws IndexOutOfBoundsException 若 index 为负数
*/
public synchronized int indexOf(Object o, int index) {
if (index < 0) {
throw new IndexOutOfBoundsException("Index: " + index);
}
if (o == null) {
for (int i = index; i < elementCount; i++) {
if (elementData[i] == null) {
return i;
}
}
} else {
for (int i = index; i < elementCount; i++) {
if (o.equals(elementData[i])) {
return i;
}
}
}
return -1;
}
/**
* 返回包含 Vector 中所有元素的数组
*
* @return 包含 Vector 中所有元素的数组
*/
@Override
public synchronized Object[] toArray() {
return Arrays.copyOf(elementData, elementCount);
}
/**
* 返回包含 Vector 中所有元素的数组，数组类型与指定数组相同
*
* @param <T> 数组元素的类型
* @param a 目标数组，若长度不足则会创建新数组
* @return 包含 Vector 中所有元素的数组
* @throws ArrayStoreException 若指定数组的类型不是元素类型的超类型
*/
@Override
@SuppressWarnings("unchecked")
public synchronized <T> T[] toArray(T[] a) {
if (a.length < elementCount) {
return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());
}
System.arraycopy(elementData, 0, a, 0, elementCount);
if (a.length > elementCount) {
a[elementCount] = null;
}
return a;
}
/**
* 将指定元素添加到 Vector 的末尾
*
* @param obj 要添加的元素
*/
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
/**
* 将指定元素添加到 Vector 的末尾
*
* @param e 要添加的元素
* @return true（根据 Collection 接口规范）
*/
@Override
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
/**
* 确保 Vector 的容量至少能容纳指定的最小容量
*
* @param minCapacity 所需的最小容量
*/
private void ensureCapacityHelper(int minCapacity) {
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
/**
* 扩容 Vector 以容纳至少指定的最小容量
*
* @param minCapacity 所需的最小容量
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 计算新容量：若 capacityIncrement > 0 则增加该值，否则翻倍
int newCapacity = 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);
}
/**
* 数组的最大容量，某些 VM 会保留一些头部字
* 尝试分配更大的数组可能导致 OutOfMemoryError
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 处理超大容量需求
*
* @param minCapacity 所需的最小容量
* @return 合理的最大容量
* @throws OutOfMemoryError 若所需容量为负数
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
/**
* 移除 Vector 中首次出现的指定元素
*
* @param o 要移除的元素
* @return 若 Vector 包含该元素则返回 true
*/
@Override
public synchronized boolean remove(Object o) {
modCount++;
int i = indexOf(o);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
/**
* 移除指定索引位置的元素
*
* @param index 要移除元素的索引
* @throws ArrayIndexOutOfBoundsException 若索引越界
*/
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
} else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
// 计算需要移动的元素数量
int j = elementCount - index - 1;
if (j > 0) {
// 将后续元素前移一位
System.arraycopy(elementData, index + 1, elementData, index, j);
}
// 清空末尾引用，帮助垃圾回收
elementData[--elementCount] = null;
}
/**
* 判断 Vector 是否包含指定集合中的所有元素
*
* @param c 要检查的集合
* @return 若包含所有元素则返回 true
*/
@Override
public synchronized boolean containsAll(Collection_<?> c) {
for (Object e : c) {
if (!contains(e)) {
return false;
}
}
return true;
}
/**
* 将指定集合中的所有元素添加到 Vector 的末尾
*
* @param c 包含要添加元素的集合
* @return 若 Vector 因调用而改变则返回 true
*/
@Override
public synchronized boolean addAll(Collection_<? extends E> c) {
modCount++;
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityHelper(elementCount + numNew);
System.arraycopy(a, 0, elementData, elementCount, numNew);
elementCount += numNew;
return numNew != 0;
}
/**
* 移除 Vector 中所有包含在指定集合中的元素
*
* @param c 包含要移除元素的集合
* @return 若 Vector 因调用而改变则返回 true
*/
@Override
public synchronized boolean removeAll(Collection_<?> c) {
modCount++;
boolean modified = false;
Iterator<?> e = iterator();
while (e.hasNext()) {
if (c.contains(e.next())) {
e.remove();
modified = true;
}
}
return modified;
}
/**
* 仅保留 Vector 中包含在指定集合中的元素
*
* @param c 包含要保留元素的集合
* @return 若 Vector 因调用而改变则返回 true
*/
@Override
public synchronized boolean retainAll(Collection_<?> c) {
modCount++;
boolean modified = false;
Iterator<E> e = iterator();
while (e.hasNext()) {
if (!c.contains(e.next())) {
e.remove();
modified = true;
}
}
return modified;
}
/**
* 清空 Vector 中的所有元素
*/
@Override
public synchronized void clear() {
modCount++;
// 将所有元素置为 null，帮助垃圾回收
for (int i = 0; i < elementCount; i++) {
elementData[i] = null;
}
elementCount = 0;
}
/**
* 判断 Vector 与指定对象是否相等
*
* @param o 要比较的对象
* @return 若对象是 Collection 且元素相同则返回 true
*/
@Override
public synchronized boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Collection_)) {
return false;
}
Collection_<?> c = (Collection_<?>) o;
if (c.size() != size()) {
return false;
}
try {
Iterator<E> e1 = iterator();
Iterator<?> e2 = c.iterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1 == null ? o2 == null : o1.equals(o2))) {
return false;
}
}
return !(e1.hasNext() || e2.hasNext());
} catch (ClassCastException | NullPointerException unused) {
return false;
}
}
/**
* 返回 Vector 的哈希码值
*
* @return 哈希码值
*/
@Override
public synchronized int hashCode() {
int hashCode = 1;
for (E e : this) {
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
/**
* 返回以适当顺序遍历 Vector 中元素的迭代器
*
* @return 迭代器
*/
@Override
public synchronized Iterator<E> iterator() {
return new Itr();
}
/**
* Vector 的迭代器实现，支持快速失败机制
*/
private class Itr implements Iterator<E> {
/** 下一个要返回的元素索引 */
int cursor;
/** 最后一次返回的元素索引，-1 表示尚未返回任何元素 */
int lastRet = -1;
/** 期望的修改计数，用于快速失败检查 */
int expectedModCount = modCount;
/**
* 判断是否还有下一个元素
*
* @return 若有下一个元素则返回 true
*/
public boolean hasNext() {
synchronized (Vector_.this) {
return cursor != elementCount;
}
}
/**
* 返回下一个元素
*
* @return 下一个元素
* @throws NoSuchElementException 若无更多元素
* @throws ConcurrentModificationException 若检测到并发修改
*/
public E next() {
synchronized (Vector_.this) {
checkForComodification();
int i = cursor;
if (i >= elementCount) {
throw new NoSuchElementException();
}
cursor = i + 1;
return elementData(lastRet = i);
}
}
/**
* 移除最后一次返回的元素
*
* @throws IllegalStateException 若尚未调用 next() 或已调用 remove()
* @throws ConcurrentModificationException 若检测到并发修改
*/
public void remove() {
if (lastRet == -1) {
throw new IllegalStateException();
}
synchronized (Vector_.this) {
checkForComodification();
Vector_.this.remove(lastRet);
expectedModCount = modCount;
}
// 重置 cursor，因为元素被移除后索引会变化
cursor = lastRet;
lastRet = -1;
}
/**
* 获取指定索引位置的元素
*
* @param index 元素索引
* @return 指定位置的元素
*/
@SuppressWarnings("unchecked")
private E elementData(int index) {
return (E) elementData[index];
}
/**
* 检查迭代期间是否发生了并发修改
*
* @throws ConcurrentModificationException 若检测到并发修改
*/
final void checkForComodification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
}