show Diagram
从上图可以看出我们的老朋友ArrayList实现了Cloneable、RandomAccess、Serializable3个接口,并且继承了AbstractList抽象类。
1. Cloneable
Cloneable接口是Java中的一个标记接口，它没有任何方法定义，只是作为一个标志，表示实现该接口的类可以进行克隆操作。
说到克隆，就不得不抛出面试题中经常出现的深克隆和浅克隆。
浅克隆
是指创建一个新对象，并将原始对象的值直接复制到新对象中。新对象和原始对象共享相同的引用类型字段，即它们引用相同的对象。
深克隆
是指创建一个新对象，并将原始对象所有引用类型字段指向的对象也进行克隆，从而实现整个对象及其关联对象的完全复制。
那问题来了，为什么不自己直接new一个，要使用克隆呢？
-
保持一致性和完整性： 克隆通常会复制对象的所有属性和状态，包括私有字段。这样可以确保新对象与原始对象在创建时的状态一致，而直接使用
new可能会导致某些状态不一致或丢失。 -
封装和隐藏细节： 对象可能有私有字段或复杂的构造逻辑，直接通过
new创建新对象可能需要了解和重复构造逻辑。通过克隆，可以隐藏对象的实现细节，提供一个更简洁的接口来创建新对象。 -
性能考虑： 在某些情况下，克隆可以比实例化对象更高效。特别是对于大对象或对象构造开销较大的情况，克隆可以通过避免重复创建和初始化过程来提高性能。
-
灵活性和可定制性： 克隆操作通常可以通过实现
Cloneable接口或类似的机制来定制克隆行为。这使得可以在对象被克隆时进行某些自定义操作，而直接使用new则无法提供这种灵活性。import java.util.ArrayList; import java.util.List; class Person implements Cloneable { private String name; private List<String> hobbies; public Person(String name, List<String> hobbies) { this.name = name; this.hobbies = hobbies; } public String getName() { return name; } public List<String> getHobbies() { return hobbies; } @Override protected Object clone() throws CloneNotSupportedException { // 浅克隆 // return super.clone(); // 深克隆 Person clonedPerson = (Person) super.clone(); clonedPerson.hobbies = new ArrayList<>(hobbies); return clonedPerson; } } public class Main { public static void main(String[] args) throws CloneNotSupportedException { List<String> originalHobbies = new ArrayList<>(); originalHobbies.add("Reading"); originalHobbies.add("Traveling"); Person originalPerson = new Person("Alice", originalHobbies); // 浅克隆 Person shallowClone = (Person) originalPerson.clone(); System.out.println("Original Person: " + originalPerson.getName() + ", Hobbies: " + originalPerson.getHobbies()); System.out.println("Shallow Clone: " + shallowClone.getName() + ", Hobbies: " + shallowClone.getHobbies()); // 修改原始对象的爱好列表 originalPerson.getHobbies().add("Cooking"); // 验证浅克隆后，引用类型字段共享同一对象 System.out.println("Original Person: " + originalPerson.getName() + ", Hobbies: " + originalPerson.getHobbies()); System.out.println("Shallow Clone: " + shallowClone.getName() + ", Hobbies: " + shallowClone.getHobbies()); System.out.println("------------------------"); // 深克隆 Person deepClone = (Person) originalPerson.clone(); System.out.println("Original Person: " + originalPerson.getName() + ", Hobbies: " + originalPerson.getHobbies()); System.out.println("Deep Clone: " + deepClone.getName() + ", Hobbies: " + deepClone.getHobbies()); // 修改原始对象的爱好列表 originalPerson.getHobbies().add("Gardening"); // 验证深克隆后，引用类型字段具有独立的副本 System.out.println("Original Person: " + originalPerson.getName() + ", Hobbies: " + originalPerson.getHobbies()); System.out.println("Deep Clone: " + deepClone.getName() + ", Hobbies: " + deepClone.getHobbies()); } }
2. RandomAccess
RandomAccess接口是Java集合框架中的一个标记接口，位于 java.util 包下。它并不包含任何方法，仅用于标识实现该接口的集合是否支持高效的随机访问。
如果一个集合没有实现 RandomAccess 接口，则表示使用索引进行访问的性能可能较差。
并不是所有实现了List接口的集合都实现了RandomAccess接口。例如，ArrayList 实现了 RandomAccess 接口，因为它底层基于数组实现，支持通过索引快速访问元素。但是， LinkedList 并没有实现 RandomAccess 接口，因为它是基于链表实现的，对于随机访问需要遍历链表。
public class RandomAccessDemo02 {
public static void main(String[] args) {
// 创建LinkedList集合
List<String> list = new LinkedList<>();
//添加10W条数据
for (int i = 0; i < 100000; i++) {
list.add(i + "");
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
// 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问: " + (endTime - startTime)); // 5104
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
//仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问: " + (endTime - startTime)); // 3
}
}
LinkedList使用迭代器访问比get方法要快很多，主要是由于LinkedList的底层结构是链表，所以LinkedList无法支持索引访问，也就没有实现RandomAccess 接口，而LinkedList使用get访问，每次访问都需要从头节点开始遍历，这样每次都需要遍历一次十分浪费时间，而迭代器访问下一层遍历可以直接接着上一次的位置往下访问，所以只需要遍历一遍即可。
在开发中我们都是直接使用多态机制，我们无论是创建ArrayList或者LinkedList都是使用List类型，所以不确定的话同时我们想要遍历，我们最好使用迭代器遍历。当然不嫌麻烦，也可以直接使用 instaceof 关键字进行判断，如果当前 List 对象实现了RandomAccess接口就选择使用索引遍历，否则就使用迭代器遍历。
3. Serializable
Serializable接口是Java中的一个标记接口，它没有任何方法定义，只是作为一个标志，用于表示类的对象可以被序列化。序列化是将对象转换为字节序列的过程，使得对象可以被存储到文件、数据库中，或者通过网络进行传输。
如果一个类的某一个属性我们不想进行序列化,或者无法进行序列化可以使用transient关键字来修饰某些字段，以排除它们不被序列化
序列化和反序列化
-
序列化（Serialization）：是指将对象转换为字节序列的过程，使得对象可以被存储到文件、数据库中或者通过网络进行传输
-
反序列化（Deserialization）：是指将字节序列转换回对象的过程，恢复对象的状态。序列化是将对象转换为字节序列的过程，而反序列化是将字节序列转换回对象的过程，通过序列化和反序列化可以实现对象的持久化、网络传输和分布式计算等功能。
import java.io.IOException;
import java.util.Arrays;
import java.util.List;
public class ArrayList {
public static void main(String[] args) {
java.util.ArrayList<Object> arrayList = new java.util.ArrayList<>();
List<String> stringList = Arrays.asList("Apple", "Banana", "Orange", "Pear");
serializeArrayList(stringList);
deserializeArrayList();
}
private static void serializeArrayList(List<String> list) {
java.io.FileOutputStream fileOutputStream =null;
java.io.ObjectOutputStream objectOutputStream = null;
try {
fileOutputStream = new java.io.FileOutputStream(ListConstants.fileName);
objectOutputStream = new java.io.ObjectOutputStream(fileOutputStream);
objectOutputStream.writeObject(list);
} catch (java.io.IOException e) {
e.printStackTrace();
}finally {
try {
assert objectOutputStream != null;
objectOutputStream.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
try {
fileOutputStream.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
private static void deserializeArrayList() {
java.io.FileInputStream fileInputStream = null;
java.io.ObjectInputStream objectInputStream = null;
try {
fileInputStream = new java.io.FileInputStream(ListConstants.fileName);
objectInputStream = new java.io.ObjectInputStream(fileInputStream);
List<String> list = (List<String>) objectInputStream.readObject();
System.out.println(list);
} catch (java.io.IOException | ClassNotFoundException e) {
e.printStackTrace();
}
}
}
interface ListConstants {
String fileName = "list.txt";
}
无参构造
public class ArrayList<E> {
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默认容量的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 集合真正存储数组元素的数组
*/
transient Object[] elementData;
/**
* 集合的大小
*/
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}
可以看到通过空参构造方法创建集合对象并未构造一个初始容量为10的空数组，仅仅将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址赋值给elementData
new ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {
//判断初始容量initialCapacity是否大于0
if (initialCapacity > 0) {
// 创建一个数组,且指定长度为initialCapacity
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果initialCapacity容量为0，把EMPTY_ELEMENTDATA的地址赋值给elementData
// 相当于是无参构造
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 以上两个条件都不满足报错
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
new ArrayList(Collection<? extends E> c)
public class ArrayList<E> {
public ArrayList(Collection<? extends E> c) {
// 将集合构造中的集合对象转成数组,且将数组的地址赋值给elementData
elementData = c.toArray();
// 将elementData的长度赋值给 集合长度size,且判断是否不等于 0
if ((size = elementData.length) != 0) {
// 判断 elementData 和 Object[] 是否为不一样的类型
if (elementData.getClass() != Object[].class)
// 如果不一样,使用Arrays的copyOf方法进行元素的拷贝
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 用空数组代替
this.elementData = EMPTY_ELEMENTDATA;
}
}
// 将集合转数组
public Object[] toArray() {
// 调用数组工具类方法进行拷贝
return Arrays.copyOf(elementData, size);
}
}
数组工具类源码
// 数组工具类源码
public class Arrays {
public static <T> T[] copyOf(T[] original, int newLength) {
// 再次调用方法进行拷贝
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T, U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// 用三元运算符进行判断,不管结果如何都是创建一个新数组
T[] copy = ((Object) newType == (Object) Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 将数组的内容拷贝到 copy 该数组中
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
// 返回拷贝元素成功后的数组
return copy;
}
}
add(E e)方法解析
/**
* 往ArrayList添加元素
*
* @param e 待添加的元素
* @return
*/
public boolean add(E e) {
// 调用方法对内部容量进行校验，判断ArrayList现有容量能否添加一个元素
ensureCapacityInternal(size + 1);
// 扩容完毕后直接在已有元素后面添加
elementData[size++] = e;
return true;
}
/**
* 确保ArrayList容量充足
*
* @param minCapacity 当前所需最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
// 判断当前数组是否已被初始化（即 elementData 是否为 null）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 通过最小容量和默认容量求出较大值 (用于第一次扩容)
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 将if中计算出来的容量传递给下一个方法，继续校验
ensureExplicitCapacity(minCapacity);
}
/**
* 确保ArrayList扩容后的容量充足
*
* @param minCapacity 当前所需最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
// 集合修改次数+1（在扩容的过程中没用，主要是用于迭代器中，确保线程安全)
// modCount这个字段主要用于实现 ArrayList 的快速失败机制 fail-fast
modCount++;
// 判断最小容量 - 数组长度是否大于 0（也就是判断当前数组容量是否满足最小容量，避免溢出）
if (minCapacity - elementData.length > 0)
// 当前数组容量不满足所需最小容量，则将第一次计算出来的容量传递给 核心扩容方法
grow(minCapacity);
}
/**
* 扩容 elementData 数组
*
* @param minCapacity 当前所需最小容量
*/
private void grow(int minCapacity) {
// 记录数组的实际长度,此时由于木有存储元素，长度为0
int oldCapacity = elementData.length;
// 核心扩容算法 原容量的 1.5 倍（位运算效率更高）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断新容量 - 最小容量 是否小于 0（判断扩容后的容量是否足够）
if (newCapacity - minCapacity < 0)
// 当前容量不够，将最小容量赋值给新容量（确保新容量不会比最小容量小）
newCapacity = minCapacity;
// 判断新容量-最大数组大小（也就是 Integer.MAX_VALUE - 8） 是否>0（判断扩容后的容量是否足够）
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 新容量已超过了当前数组的最大容量，需要重新计算出一个超大的容量（其实就是Integer.MAX_VALUE）
newCapacity = hugeCapacity(minCapacity);
// 调用数组工具类方法，浅拷贝出一个新数组(新数组的大小就是前面计算的newCapacity)
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 获取一个超大容量
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow（健壮性代码）
throw new OutOfMemoryError();
// 如果当前超过了 MAX_ARRAY_SIZE（Integer.MAX_VALUE-8）就返回Integer.MAX_VALUE
// 否则返回 MAX_ARRAY_SIZE（Integer.MAX_VALUE-8）
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add(int index, E element) 方法解析
/**
* 往指定索引位置添加元素
*
* @param index 指定索引
* @param element 待添加的元素
*/
public void add(int index, E element) {
// 判断索引是否越界
rangeCheckForAdd(index);
// 检验是否要扩容
ensureCapacityInternal(size + 1);
// 浅拷贝 elementData 中 index 后面的所有元素
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 覆盖原来索引的位置
elementData[index] = element;
size++;
}
/**
* 判断索引是否越界
*
* @param index
*/
private void rangeCheckForAdd(int index) {
// 超出指定范围就报 IndexOutOfBoundsException 异常（相信对于之前刚学Javad的同学这个异常很常见吧(●ˇ∀ˇ●)）
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
addAll(Collection<? extends E> c)
/**
* 往ArrayList中添加若干给元素
*
* @param c 待添加的元素集合
* @return
*/
public boolean addAll(Collection<? extends E> c) {
// 把集合的元素转存到Object类型的数组中
Object[] a = c.toArray();
// 新增元素的数量
int numNew = a.length;
// 调用方法检验是否要扩容
ensureCapacityInternal(size + numNew);
// 调用方法将a数组的元素拷贝到elementData数组中
System.arraycopy(a, 0, elementData, size, numNew);
// 集合的长度+=a数组的长度
size += numNew;
// 只要a数组的长度不等于0,即说明添加成功
return numNew != 0;
}
addAll(int index, Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c) {
// 判断是否索引越界
rangeCheckForAdd(index);
// 将数据源转成数组
Object[] a = c.toArray();
// 记录数据源的长度
int numNew = a.length;
// 目的就是为了给集合存储数据的数组进行扩容
ensureCapacityInternal(size + numNew);
// 计算元素要后移的长度
int numMoved = size - index;
// 判断需要移动的个数是否大于0（健壮性判断）
if (numMoved > 0)
// 将 [index, size] 这个闭区间的所有元素往后移动 numMoved 位
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
// 将要添加的元素浅拷贝到 elementData的[index, size]区间，覆盖原来的值
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
// 判断当前有没有新增成功，如果 numNew == 0 说明没有新增元素，也就是新增失败
// 这里使用 !=0 来判断，简化了判断逻辑，实际上 numNew 要么大于0，要么小于0，不可能是负数
return numNew != 0;
}
remove(int index)
/**
* 移除指定索引位置的元素
*
* @param index 指定索引
* @return E 移除的元素
*/
public E remove(int index) {
// 判断索引是否越界
rangeCheck(index);
// 修改次数加一
modCount++;
// 将index对应的元素赋值给 oldValue，用于返回
E oldValue = elementData(index);
// 计算集合需要移动元素个数
int numMoved = size - index - 1;
// 判断numMoved是否大于0（健壮性判断）
if (numMoved > 0)
// 将elementData这个 [index+1, size] 闭区间中的所有元素往前移动一位
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
// 将源集合最后一个元素置为null
elementData[--size] = null;
// 返回被删除的元素
return oldValue;
}
remove(Object o)
/**
* 移除指定元素
* @param o 要移除的元素
* @return
*/
public boolean remove(Object o) {
// 判断要删除的元素是否为null
if (o == null) {
// 遍历集合，寻找为null的元素
for (int index = 0; index < size; index++)
// 判断集合的元素是否为null
if (elementData[index] == null) {
// 如果相等，调用fastRemove方法快速删除
fastRemove(index);
return true;
}
} else {
// 遍历集合，寻找要删除的元素
for (int index = 0; index < size; index++)
// 用o对象的equals方法和集合每一个元素进行比较
// 注意这里是直接调用Object的equals方法进行比较，比较的是地址
if (o.equals(elementData[index])) {
// 如果相等,调用fastRemove方法快速删除
fastRemove(index);
return true;
}
}
// 如果集合没有o该元素,那么就会返回false
return false;
}
/**
* 移除指定索引位置的元素
* @param index
*/
private void fastRemove(int index) {
// 修改次数+1
modCount++;
// 计算集合需要移动元素的个数
int numMoved = size - index - 1;
// 判断numMoved是否大于0（健壮性判断）
if (numMoved > 0)
// 将elementData这个 [index+1, size] 闭区间中的所有元素往前移动一位
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
// 将集合最后一个元素置为null
elementData[--size] = null;
}
get(int index)和set(int index, E element)
/**
* 根据指定索引获取元素
* @param index 指定的索引
* @return
*/
public E {
// 判断是否发生索引越界
rangeCheck(index);
// 直接根据索引取出集合元素
return elementData(index);
}
/**
* 修改指定索引位置的元素值
* @param index 指定索引
* @param element 修改后的值
* @return
*/
public E set(int index, E element) {
// 判断索引是否越界
rangeCheck(index);
// 获取要修改的值，用于返回
E oldValue = elementData(index);
// 将element直接覆盖index对应的元素
elementData[index] = element;
// 返回被覆盖的元素
return oldValue;
}
iterator
/**
* 将ArrayList转成Iterator
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* ArrayList集合内部类
*/
private class Itr implements Iterator<E> {
// 游标，用于遍历集合。它表示当前迭代器所指向的元素的索引
int cursor;
// 记录上一个访问的元素的索引。默认值为-1，表示还没有进行过迭代
int lastRet = -1;
// 用于检测并发修改的计数器。它保存了创建迭代器时集合的modCount值，用于后续比较是否发生了并发修改
int expectedModCount = modCount;
/**
* 判断集合中是否还有元素
*/
public boolean hasNext() {
// cursor要么小于，要么等于，小于的时候不等式成立，说明集合中还有元素
// 等于的时候不等成不成立，说明游标已经遍历到集合最后一个元素了，已经没有最后一个元素了
return cursor != size;
}
/**
* 移动游标到下一个位置，获取游标上一个位置的值
*/
public E next() {
// 检测集合是否发生了并发修改
checkForComodification();
// 将当前游标的值赋值给i
int i = cursor;
// 健壮性判断
if (i >= size)
// 如果i大于size，此时已经发生了越界，没有元素，抛一个NoSuchElementException异常
throw new NoSuchElementException();
// 将ArrayList中的成员变量 elementData 赋值给局部变量 elementData
Object[] elementData = ArrayList.this.elementData;
// 健壮性判断
if (i >= elementData.length)
// 如果i大于数组的最大元素，此时已经发生了越界，没有元素，抛一个NoSuchElementException异常
throw new ConcurrentModificationException();
// 游标值+1
cursor = i + 1;
// 返回 lastRet 对应位置的元素（也就是游标上一个位置的值）
return (E) elementData[lastRet = i];
}
/**
* 检查 modCount 变量是否发生修改
*/
final void checkForComodification() {
// 创建迭代器的时候 就将初始的 modCount 赋值给了 expectedModCount
// 如果在迭代器遍历的过程中对ArrayList进行了修改就会抛ConcurrentModificationException异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
注意事项：如果使用迭代器的方式遍历ArrayList集合时，不要一边遍历ArrayList一边修改ArrayList集合。
若在遍历的同时对ArrayList进行修改，可以使用迭代器提供的修改方法remove()，但是这个方法好像只能删除符合指定条件的一个元素，不能重复调用。
迭代器-remove()
/**
* 删除 lastRet 位置的元素
*/
public void remove() {
// 判断游标上一个位置是否小于0（健壮性判断）
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 删除ArrayList中位于 lastRet 位置的元素
ArrayList.this.remove(lastRet);
// 将游标后移一位
cursor = lastRet;
// 将 lastRet 置为-1，恢复为迭代前的状态（也就是还未被迭代）
lastRet = -1;
// 重置expectedModCount，防止出现并发修改异常的发生（这个是核心操作）
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer value = iterator.next();
// 移动一个删除一个
iterator.remove();
System.out.println(value); // 打印 1 2 3
}
// 由于迭代器的remove方法一遍迭代一遍删除，所以最后list中的元素都被删除了
System.out.println(list); // []
}
使用迭代器遍历 ArrayList 的同时，调用 ArrayList 的方法进行修改（比如：add、remove、set方法）
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer value = iterator.next();
System.out.println(value);
list.add(5); // ConcurrentModificationException
}
}
clear() 和 isEmpty()
/**
* 清空ArrayList
*/
public void clear() {
// 修改次数+1
modCount++;
// 遍历集合，将集合每一个索引对应位置上的元素都置为null
for (int i = 0; i < size; i++)
elementData[i] = null;
// 集合长度更改为0
size = 0;
}
/**
* 判断集合是否为null
*/
public boolean isEmpty() {
// 只需要判断size是否为0即可，size表示当前集合中的元素个数
return size == 0;
}
contains(Object o)
/**
* 判断集合中是否含有元素 o
* @param o
* @return
*/
public boolean contains(Object o) {
// 调用indexOf方法进行查找
// 如果结果为-1，也就是小于0，就说明ArrayList中没有o，反之则说明有
return indexOf(o) >= 0;
}
/**
* 获取元素第一次出现的索引位置
*
* @param o
* @return -1表示集合中不存在该元素，>=0的时候表示该元素在集合中最先出现的索引
*/
public int indexOf(Object o) {
// 判断 o 是否为null，为null和不为null都需要进行遍历，判断方式不同
if (o == null) {
// 如果元素是null，也进行遍历操作，因为集合中有可能够会存储null
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
// o非null，则直接调用equal方法进行判断，注意Object的equals方法判断是是地址
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
// 如果if、else两者都没有从ArrayList中找到o，则说明集合中压根不存在这个元素，直接返回-1
return -1;
}
核心源码总结
扩容算法
int newCapacity = oldCapacity + (oldCapacity >> 1);
这里通过>>（算术右移）计算出当前容量的一半
-
先由ensureCapacityInternal方法获取当前集合所需最小容量。也就是计算当前最小容量，也就是判断当前较大值是DEFAULT_CAPACITY（默认容量10）还是minCapacity，较大值为当前最小容量
-
然后再由ensureExplicitCapacity判断是否需要扩容，也就是判断minCapacity和elementData.length的大小，如果minCapacity大于elementData.length，就直接调用grow方法进行扩容
-
最后由grow方法进行扩容，先按照核心扩容算法进行扩容（也也就扩容为原来的1.5倍，具体的扩容是利用Arrays.copyOf方法进行浅拷贝），然后判断扩容后的容量是否充足，如果容量不足，再调用hugeCapacity方法得到一个更大的容量（这个最大容量Integer.MAX_VALUE）
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组（用于空实例）。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小空实例的共享空数组实例。
//我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList 所包含的元素个数
*/
private int size;
/**
* 带初始容量参数的构造函数。（用户自己指定容量）
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//创建initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
*/
public ArrayList(Collection<? extends E> c) {
//
elementData = c.toArray();
//如果指定集合元素个数不为0
if ((size = elementData.length) != 0) {
// c.toArray 可能返回的不是Object类型的数组所以加上下面的语句用于判断，
//这里用到了反射里面的getClass()方法
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 用空数组代替
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//下面是ArrayList的扩容机制
//ArrayList的扩容机制提高了性能，如果每次只扩充一个，
//那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
/**
* 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取默认的容量和传入参数的较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
}
/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
// oldCapacity为旧容量，newCapacity为新容量
int oldCapacity = elementData.length;
//将oldCapacity 右移一位，其效果相当于oldCapacity /2，
//我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//再检查新容量是否超出了ArrayList所定义的最大容量，
//若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
//如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
//比较minCapacity和 MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
*返回此列表中的元素数。
*/
public int size() {
return size;
}
/**
* 如果此列表不包含元素，则返回 true 。
*/
public boolean isEmpty() {
//注意=和==的区别
return size == 0;
}
/**
* 如果此列表包含指定的元素，则返回true 。
*/
public boolean contains(Object o) {
//indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
return indexOf(o) >= 0;
}
/**
*返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
//equals()方法比较
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 返回此ArrayList实例的浅拷贝。 （元素本身不被复制。）
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
//Arrays.copyOf功能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// 这不应该发生，因为我们是可以克隆的
throw new InternalError(e);
}
}
/**
*以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
*返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
*因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）;
*返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组，则返回其中。
*否则，将为指定数组的运行时类型和此列表的大小分配一个新数组。
*如果列表适用于指定的数组，其余空间（即数组的列表数量多于此元素），则紧跟在集合结束后的数组中的元素设置为null 。
*（这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。）
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 新建一个运行时类型的数组，但是ArrayList数组的内容
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//调用System提供的arraycopy()方法实现数组之间的复制
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* 返回此列表中指定位置的元素。
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* 用指定的元素替换此列表中指定位置的元素。
*/
public E set(int index, E element) {
//对index进行界限检查
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
//返回原来在这个位置的元素
return oldValue;
}
/**
* 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//这里看到ArrayList添加元素的实质就相当于为数组赋值
elementData[size++] = e;
return true;
}
/**
* 在此列表中的指定位置插入指定的元素。
*先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
*再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
//从列表中删除的元素
return oldValue;
}
/**
* 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。
*返回true，如果此列表包含指定的元素
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
/**
* 从列表中删除所有元素。
*/
public void clear() {
modCount++;
// 把数组中所有的元素的值设为null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 将指定集合中的所有元素插入到此列表中，从指定的位置开始。
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* 从此列表中删除所有索引为fromIndex （含）和toIndex之间的元素。
*将任何后续元素移动到左侧（减少其索引）。
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* 检查给定的索引是否在范围内。
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* add和addAll使用的rangeCheck的一个版本
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 返回IndexOutOfBoundsException细节信息
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 从此列表中删除指定集合中包含的所有元素。
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
//如果此列表被修改则返回true
return batchRemove(c, false);
}
/**
* 仅保留此列表中包含在指定集合中的元素。
*换句话说，从此列表中删除其中不包含在指定集合中的所有元素。
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* 从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。
*指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。
*返回的列表迭代器是fail-fast 。
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
*返回列表中的列表迭代器（按适当的顺序）。
*返回的列表迭代器是fail-fast 。
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
*以正确的顺序返回该列表中的元素的迭代器。
*返回的迭代器是fail-fast 。
*/
public Iterator<E> iterator() {
return new Itr();
}
System.arraycopy()和Arrays.copyOf()的区别
看二者源代码可以发现copyOf()内部调用了System.arraycopy()方法，两者都是浅拷贝
-
参数传递方式不同：
-
System.arraycopy()方法需要提供源数组、源数组的起始位置、目标数组、目标数组的起始位置以及要复制的元素个数作为参数。
-
Arrays.copyOf()方法只需要提供源数组和要复制的长度作为参数。
-
-
返回结果不同：
-
System.arraycopy()方法没有返回值，直接将源数组的元素复制到目标数组中。
-
Arrays.copyOf()方法会返回一个新的数组，其中包含了源数组的指定长度部分。
-
-
目标数组长度不足时的处理不同：
-
System.arraycopy()方法会将源数组尽可能多的元素复制到目标数组中，如果目标数组长度不足，则只复制部分元素。
-
Arrays.copyOf()方法在目标数组长度不足时，会自动扩展目标数组的长度，并将剩余位置填充默认值（例如，对于整型数组，默认值为0）。
-
-
参数介绍
- System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
- src: 源数组对象，表示要复制元素的源数组。
- srcPos: 源数组的起始位置，表示从源数组的哪个索引位置开始复制元素。
- dest: 目标数组对象，表示将要复制元素到目标数组中。
- destPos: 目标数组的起始位置，表示从目标数组的哪个索引位置开始存放复制的元素。
- length: 要复制的元素个数，表示从源数组复制多少个元素到目标数组中。
-
Arrays.copyOf(T[] original, int newLength)
- original: 源数组对象，表示要进行复制的源数组。
- newLength: 新数组的长度，表示复制后的数组应该具有的长度。
int[] sourceArray = {1, 2, 3, 4, 5};
// 使用 System.arraycopy() 方法复制数组
int[] targetArray1 = new int[5];
System.arraycopy(sourceArray, 0, targetArray1, 0, sourceArray.length);
System.out.println(Arrays.toString(targetArray1)); // 输出 [1, 2, 3, 4, 5]
// 使用 Arrays.copyOf() 方法复制数组
int[] targetArray2 = Arrays.copyOf(sourceArray, sourceArray.length);
System.out.println(Arrays.toString(targetArray2)); // 输出 [1, 2, 3, 4, 5]
ArrayList频繁扩容导致添加性能急剧下降，如何处理？
如果在容量大概确定的情况下，可以在创建ArrayList对象的时候就指定一个大致的初始容量，减少扩容的次数
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
// 不指定初始容量 新增10w条数据
List<String> list = new ArrayList<>();
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
list.add(i + "");
}
long endTime = System.currentTimeMillis();
System.out.println("未指定容量: " + (endTime - startTime)); // 22
// 指定初始容量 新增10w条数据
List<String> list1 = new ArrayList<>(100000);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
list1.add(i + "");
}
endTime = System.currentTimeMillis();
System.out.println("指定容量: " + (endTime - startTime)); // 10
}
}
注意：这种优化方式只针对特定的场景，如果添加的元素是少量的、未知的，不推荐使用
ArrayList插入或删除元素一定比LinkedList慢么？
不一定，如果ArrayList每次插入或删除的元素是集合最后一个元素，则ArrayList要比LinkedList要比LinkedList要快。
但是一般情况下ArrayList插入或删除元素比LinkedList要慢，这是因为数组插入或删除元素后，需要新建数组和数据拷贝；而LinkedList只需要修改指针的引用即可。
比较ArrayList和LinkedList按照顺序插入50w条数据，谁更快？
import java.util.ArrayList;
import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
// 测试 ArrayList 插入和删除元素的耗时
ArrayList<String> arrayList = new ArrayList<>();
long startTime = System.currentTimeMillis();
for (int i = 0; i < 5000000; i++) {
arrayList.add(i+"XXX");
}
long endTime = System.currentTimeMillis();
System.out.println("ArrayList按顺序插入500w条数据: "+(endTime-startTime)); // 3740
startTime = System.currentTimeMillis();
arrayList.remove("5000XXX");
endTime = System.currentTimeMillis();
System.out.println("ArrayList集合删除元素的时间: "+(endTime-startTime)); // 3
// 测试 LinkedList 插入和删除元素的耗时
LinkedList<String> linkedList = new LinkedList<>();
startTime = System.currentTimeMillis();
for (int i = 0; i < 5000000; i++) {
linkedList.add(i+"XXX");
}
endTime = System.currentTimeMillis();
System.out.println("LinkedList按顺序插入500w条数据: "+(endTime-startTime)); // 2646
startTime = System.currentTimeMillis();
linkedList.remove("5000XXX");
endTime = System.currentTimeMillis();
System.out.println("LinkedList集合删除元素的时间: "+(endTime-startTime)); // 0
}
}
从上面代码执行之后，可以得出：
新增LinkedList要比ArrayList要快，删除LinkedList也比ArrayList也要快，删除的元素是中间的，这个LinkedList快没什么争议，但是为什么按照顺序添加为什么还是LinkedList要快，这是什么原因？这是由于ArrayList没有指定初始容量大小，导致在新增的过程中进行了多次扩容，从而降低了效率
解决措施：在创建ArrayList的时候指定初始容量
现在我们为ArrayList指定初始容量为 5000000 ，然后再来测试，可以看到此时ArrayList新增耗时 2998ms，而 LinkedList 耗时2509ms，为什么还是 LinkedList 要快？其实这个已经相差不大了
ArrayList 非线程安全
ArrayList是线程不安全的。如果想要线程安全该怎么办？
通过Collections工具类把List变成一个线程安全的集合
使用线程安全类Vector
使用CopyOnWriteArrayList
```java
import java.util.ArrayList;
import java.util.List;
class Task implements Runnable {
private List<String> list;
public Task(List<String> list) {
this.list = list;
}
@Override
public void run() {
// 每次执行任务前都休眠1s
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
list.add(Thread.currentThread().getName());
}
}
public class Test {
public static void main(String[] args) throws InterruptedException {
List<String> list = new ArrayList<String>();
Task task = new Task(list);
// 开启50个线程
for (int i = 0; i < 50; i++) {
new Thread(task).start();
}
Thread.sleep(1000);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println("集合长度: " + list.size());
}
}
通过Collections.synchronizedList()方法将 ArrayList 转成SynchronizedRandomAccessList
List<String> list = new ArrayList<>();
list = Collections.synchronizedList(list);
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
复制ArrayList到另一个ArrayList中
- 使用clone方法
- 使用ArrayList构造方法
- 使用addAll方法
- 使用System.arraycopy()
场景显现
提问：已知成员变量集合存储N个用户名称,在多线程的环境下，使用迭代器在读取集合数据的同时，如何保证还可以正常的写入数据到集合？
使用 读写分离集合 CopyOnWriteArrayList。
CopyOnWriteArrayList开始迭代后，就会以最初始的集合进行遍历，如果中间发生了修改操作，会创建应该副本，
遍历中间的所有修改操作都发生在这个副本上，等到遍历完毕后再将原来的数组引用指向这个副本。
import java.util.ArrayList;
class Task implements Runnable {
private static List<String> list = new ArrayList<>();
static {
list.add("Jack");
list.add("Lucy");
list.add("Jimmy");
}
@Override
public void run() {
for (String value : list) {
System.out.println(value);
// 在读取数据的同时又向集合写入数据
list.add("coco");
}
}
}
public class Test {
public static void main(String[] args) {
// 创建线程任务
Task task = new Task();
// 开启10条线程
for (int i = 0; i < 10; i++) {
new Thread(task).start();
}
}
}
更换代码：
private static List<String> list = new CopyOnWriteArrayList<>();