ArrayList
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
实现的接口
Serializable
- 类的序列化由实现
java.io.Serializable接口的类启用。 不实现此接口的类将不会使任何状态 序列化 或 反序列化。 可序列化类的所有子类型都是可序列化的。 序列化接口没有方法或字段，仅用于标识可串行化的语义。 - 序列化:将对象的数据写入到文件(写对象)
- 反序列化:将文件中对象的数据读取出来(读对象)
RandomAccess
- 目的：可以 随机访问列表 或者 顺序访问列表的时候提供良好的性能
for (int i = 0; i < list.size(); i++) { list.get(i); } // -----随机访问
Iterator<String> it = list.iterator(); while (it.hasNext()){ it.next(); } // -----顺序访问
/*
ArrayList 中随机访问 更快
LinkedList 中 顺序访问 更快
-- 由于随机访问的时候源码底层每次都需要进行折半的动作，再经过判断是从头还是从尾部一个个寻找。
-- 而顺序访问只会在获取迭代器的时候进行一次折半的动作,以后每次都是在上一次的基础上获取下一个元素。
-- 因此顺序访问要比随机访问快得多
*/
总结： 对返回的集合进行判断,如果返回的集合实现了 RandomAccess 就使用 普通for ; 否则使用迭代器(增强for)
Cloneable
浅拷贝
1、 被克隆对象所在的类必须实现 Cloneable 接口
2、 必须重写 clone 方法
class Student implements Cloneable{
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
class clone_{
public static void main(String[] args) throws CloneNotSupportedException {
Student student = new Student();
Student student1 = (Student) student.clone();
System.out.println(student == student1); // fasle
}
}
存在的问题（局限性）: 基本数据类型可以完全复制，但是引用数据类型不可以，仅仅只会拷贝一分引用
深拷贝
class Skill implements Cloneable{
String skillname;
public Skill(String skillname) {
this.skillname = skillname;
}
public String getSkillName() {
return skillname;
}
public void setSkillName(String skillname) {
this.skillname = skillname;
}
@Override
protected Object clone() throws CloneNotSupportedException {
return super.clone();
}
@Override
public String toString() {
return "Skill{" +
"skillname='" + skillname + '\'' +
'}';
}
}
class Student implements Cloneable{
public Skill skill;
public int age;
public Student(int age,Skill skill) {
this.age = age;
this.skill = skill;
}
public Skill getSkill() {
return skill;
}
public void setSkill(Skill skill) {
this.skill = skill;
}
@Override
protected Object clone() throws CloneNotSupportedException {
// super.clone() 深拷贝不可以直接调用 super 的方法，浅拷贝 是可以的
//先 clone 一个学生对象
Student stu = (Student) super.clone();
//再clone 一个 Skill 对象
Skill skill = (Skill)this.skill.clone();
// 将 clone 出来的 skill_ 对象赋值给 stu 对象的成员变量
stu.setSkill(skill);
return stu;
}
@Override
public String toString() {
return "Student{" +
"skill=" + skill +
", age=" + age +
'}';
}
}
class Clone_{
public static void main(String[] args) throws CloneNotSupportedException {
Skill skill = new Skill("ry123");
Student student = new Student(23,skill);
Object student1 = student.clone();
System.out.println(student == student1); // fasle
System.out.println(student1);
System.out.println(student);
skill.setSkillName("ry");
System.out.println(student1);
System.out.println(student);
}
}
false
Student{skill=Skill{skillname='ry123'}, age=23}
Student{skill=Skill{skillname='ry123'}, age=23}
Student{skill=Skill{skillname='ry123'}, age=23}
Student{skill=Skill{skillname='ry'}, age=23}
源码分析
成员变量
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity. 默认初始容量。
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 创建一个大小为 0 的 list ，容量从 0 开始增加
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 创建一个 默认空参 的 list ，容量从10 开始增加
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
存储 ArrayList 元素的数组缓冲区。 ArrayList的容量就是该数组缓冲区的长度。
添加第一个元素时，任何具有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY。
*/
transient Object[] elementData; // non-private to simplify nested class access
/*
// 将ArrayList实例的状态保存到流中（即将其序列化）
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
// 写出元素计数以及任何隐藏的内容
int expectedModCount = modCount;
s.defaultWriteObject();
// 将大小写为与 clone() 行为兼容的容量
s.writeInt(size);
// 按正确的顺序写出所有元素。
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
*/
/**
* ArrayList 的大小（它包含的元素数量）
*/
private int size;
transient 作用：被修饰的属性不会序列化到硬盘
因为ArrayList 会扩容，其中元素可以删除但是集合不会缩容，所以不序列化到硬盘就可以减少占用的硬盘，减少大量删除之后出现的 null 值，可以优化磁盘
构造函数
/**
* 构造一个具有指定初始容量的空列表。
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
/**
* 构造一个初始容量为 10 的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 默认的空数组
}
/**
* 构造一个包含指定集合的元素的列表，按照集合迭代器返回这些元素的顺序排列。
*/
public ArrayList(Collection<? extends E> c) {
// 把集合变为数组，然后赋值给 ArrayList
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
//调用copy 进行赋值
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else { //a.length == 0 传入的是空的集合
// 那么赋值一个容量为 EMPTY_ELEMENTDATA 类型的空数组
elementData = EMPTY_ELEMENTDATA;
}
}
//将集合转数组的方法
public Object[] toArray() {
//调用数组工具类方法进行拷贝
return Arrays.copyOf(elementData, size);
}
添加方法
add(E e)
/*
该列表的结构被修改的次数，迭代时的修改会产生 ConcurrentModificationException来响应next 、 remove 、 previous 、 set或add操作，是快速失败行为，而不是在迭代过程中面对并发修改时的非确定性行为。
子类对该字段的使用是可选的。如果子类希望提供快速失败迭代器（和列表迭代器），那么它只需在其add(int, E)和remove(int)方法（以及它覆盖的导致结构性错误的任何其他方法）中增加此字段。列表的修改）。对add(int, E)或remove(int)单次调用必须向该字段添加不超过 1 个，否则迭代器（和列表迭代器）将抛出虚假的ConcurrentModificationExceptions 。如果实现不希望提供快速失败迭代器，则可以忽略该字段。
*/
protected transient int modCount = 0;
// 将指定元素追加到此列表的末尾。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; // 数组操作，后移 赋值
return true;
}
//扩容 + 数组拷贝 、数组容量判断、初始化数组
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算数组容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 要是 这里的条件是成立：elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
return Math.max(DEFAULT_CAPACITY, minCapacity); // 返回的就是 max （10 , minCapacity） 直接扩容到 10
}
// 要是 elementData == EMPTY_ELEMENTDATA 返回的就是 minCapacity，从 0 开始一步步扩容上去
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) { // minCapacity = size +1 ,加1：可以进行提前扩容，为下一次做准备
modCount++; // 记录修改次数
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 进行扩容
}
/**
* 要分配的数组的最大大小。一些虚拟机在数组中保留一些头字。尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超出 VM 限制
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容方法的具体实现
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 大约1.5 倍，源码的 原数组+原数组右移一位
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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); //移动旧的数组元素到新数组并返回新数组
}
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 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);
// 调用本地方法将旧数组元素移动到新数组中
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
// 原数组 原数组开始位置 目标数组 目标数组的起点 移动的长度
// 返回新数组
return copy;
}
add(int index, E element)
/**
* 在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加一）
*/
public void add(int index, E element) {
rangeCheckForAdd(index); // 检查下标
ensureCapacityInternal(size + 1); //扩容 、数组容量判断、初始化数组 指定位置之前的数组进行拷贝
System.arraycopy(elementData, index, elementData, index + 1, size - index); // 指定位置之后的数组进行拷贝
elementData[index] = element;
size++;
}
// 检查下标是否越界
private void rangeCheck(int index) {
if (index >= size) // size 是数组的实际容量 length 才是数组的长度
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//越界提示
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
addAll(Collection<? extends E> c)
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;
}
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); // Increments modCount
//移动的数量
int numMoved = size - index;
if (numMoved > 0)
//从 下标位置开始后移 numMoved 个位置
System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
// 要是移动的元素个数是0 ，就直接添加到后面
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
设置方法
set(int index, E element)
public E set(int index, E element) {
// 检查是否越界
rangeCheck(index);
// 获取原来位置的元素
E oldValue = elementData(index);
// 新值取代 旧值
elementData[index] = element;
// 返回旧值
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
获取方法
get(int index)
public E get(int index) {
rangeCheck(index); // 越界检查
return elementData(index); // 返回对应的 下标位置 的元素
}
删除方法
remove(int index)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 计算得到需要移除的元素的位置
int numMoved = size - index - 1;
// 删除 最后的一个元素 就 = 0,不用移动了
if (numMoved > 0)
// 开始移动元素 原数组 （源地址）删除元素的后一个位置为 目标数组 （目标位置）删除元素的位置 移动元素的个数(尺寸)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//将后面的元素置为 null 方便进行 gc 回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// 找到这个位置的元素
E elementData(int index) {
return (E) elementData[index];
}
remove(Object o)
只会移除
第一个匹配到的元素
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;
}
// 根据下标 移动（copy） 中的元素
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
}
removeAll(Collection<?> c)
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c); // 判空 空则抛出空指针
return batchRemove(c, false);
}
public static <T> T requireNonNull(T obj) {
if (obj == null)
throw new NullPointerException();
return obj;
}
// 批量删除
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
// 遍历
for (; r < size; r++)
// 数组中的元素，要是 elementData[r] 不在 要删除的元素集合中，
if (c.contains(elementData[r]) == complement)
// 将这个元素 覆盖到 elementData 中
elementData[w++] = elementData[r];
} finally {
// c.contains 出现 异常的时候 就会导致 r != size ，此时 w 只等于异常出现之前满足条件时记录的元素个数，
if (r != size) { // r != size判断是为了在出现异常的情况下也可以正常的进行元素移除
System.arraycopy(elementData, r, elementData, w, size - r); // elementData 没有全部删除完，只删除了一部分,没删除的部分要进行前移
w += size - r;
}
// 要是有元素被删除，就将 w 下标之后的元素 置为 null 方便进行 gc
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w; // 修改次数就是操作的次数
size = w;
modified = true;
}
}
// 都不满足就直接返回原数组
return modified;
}
removeRange(int fromIndex, int 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;
}
清空方法
clear()
public void clear() {
modCount++;
// 遍历置为 null 方便进行垃圾回收
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
// size 置为 0
size = 0;
}
是否包含
contains(Object o)
底层也是通过循环遍历集合,取出一个个的元素和要找的元素进行比较
/*
如果此列表包含指定元素，则返回true 。当且仅当此列表包含至少一个元素 e 且满足(o==null ? e==null : o.equals(e)) 时，才返回true
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/*
返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。更正式地说，返回满足(o==null ? get(i)==null : o.equals(get(i))) 的最低索引i ，如果没有这样的索引，则返回 -1 。
*/
public int indexOf(Object o) {
// 如果元素是null,也进行遍历操作 因为集合中有可能够会存储null
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
//如果没有走if,也没有走else,那么就说明o该元素在集合中不存在
return -1;
}
继承自 AbstractCollection 的 toString()
public String toString() {
Iterator<E> it = iterator();
//没有元素： 返回 "[]"
if (! it.hasNext())
return "[]";
// 创建 StringBuilder
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
//无限循环找到下一个元素
E e = it.next();
// sb添加元素 e == this防止自己引用自己
sb.append(e == this ? "(this Collection)" : e);
// 没有下一个元素了
if (! it.hasNext())
//结尾标记符，并在 将整个缓冲区转为 String
return sb.append(']').toString();
// sb添加 标记符号
sb.append(',').append(' ');
}
}
迭代器
public Iterator<E> iterator() {
return new Itr();
}
// 一个内部类
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回元素的索引。默认 0
int lastRet = -1; // 最后一个返回元素的索引
// 在迭代的过程中,只要实际修改次数和预期修改次数不一致就会产生并发修改异常,
// 由于expectedModCount是Itr的成员变量,那么只会被赋值一次!!!
int expectedModCount = modCount; //expectedModCount预期的修改次数 modCount实际的修改次数
Itr() {}
// 判断集合是不是 有元素
public boolean hasNext() {
return cursor != size; // 索引是否达到 数组长度
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
/*
有没有出现 ConcurrentModificationException 问题 ，就是根据 modCount != expectedModCount判断的
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
*/
int i = cursor; //下一个元素的索引赋值给i
if (i >= size) // 索引达到 数组长度,表示没有下一个元素了
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData; //集合底层存储数据的数组的地址 赋值 给 局部变量 []elementData
if (i >= elementData.length)
throw new ConcurrentModificationException(); // 下一个元素的索引 大于 集合底层存储元素的长度 并发修改异常
//索引后移
cursor = i + 1;
// 取出数组中的 元素 并 返回
return (E) elementData[lastRet = i];
}
// 迭代器的删除方法
public void remove() {
// 最后返回元素的索引是不是 < 0 ;满足条件就产生 非法状态异常
if (lastRet < 0)
throw new IllegalStateException();
// 检查 是否会产生并发修改异常
checkForComodification();
尝试执行 ArrayList 的 remove() 方法，将 lastRet 所指向的元素从 ArrayList 中移除。
try {
// 调用 ArrayList 的remove 进行删除
ArrayList.this.remove(lastRet);
// 下一个要返回元素的索引 就是 最后一个返回元素的索引
cursor = lastRet;
// 最后一个返回元素的索引 置为 -1
lastRet = -1;
// 赋值 ==> 此时 不管集合自身是否删除成功 ；实际修改次数和预期修改次数又一致了,所以并不会产生并发修改异常
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
//用于对ArrayList中的元素进行迭代操作，并将每个元素传递给指定的Consumer函数。
public void forEachRemaining(Consumer<? super E> consumer) {
//首先检查传入的consumer是否为null，如果是null则抛出NullPointerException
Objects.requireNonNull(consumer);
//获取ArrayList的大小和当前游标位置。
final int size = ArrayList.this.size;
int i = cursor;
//如果游标位置大于等于ArrayList的大小，表示已经迭代完所有元素，直接返回。
if (i >= size) {
return;
}
//获取ArrayList的元素数组elementData。
final Object[] elementData = ArrayList.this.elementData;
//如果游标位置大于等于elementData的长度，表示在迭代过程中ArrayList发生了结构性变化（比如增加或删除元素），抛出ConcurrentModificationException异常。
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
//当游标位置不等于ArrayList的大小 && modCount等于expectedModCount时
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]); // 将元素传递给consumer。
}
// update once at end of iteration to reduce heap write traffic
// 更新游标位置cursor和上一个返回的元素位置lastRet。
cursor = i;
lastRet = i - 1;
//调用checkForComodification方法检查是否发生了结构性变化，如果发生了则抛出ConcurrentModificationException异常。
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
特色
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer next = iterator.next();
System.out.println(next);
if (next == ArrayList中的元素值){
// 此处 会发生 并发修改异常，原因，就在于 底层判断 是否有并发修改异常 是根据 modCount != expectedModCount 判断的
// 但是这里执行了 ArrayList 的remove remove 的底层 会对 modCount++ 从而就导致了 modCount != expectedModCount
// 所以就有 有并发修改异常
list1.remove(ArrayList中的元素值);
}
}
//ArrayList中的元素值 不是 list 中的 倒数第二个值
注意：
结论：
只有当要删除的元素在集合的倒数第二个位置的时候，不会产生并发修改异常
原因：
是因为在调用hasNext()方法的时候，光标的值和集合的长度一样，那么就会返回false；因此就不会再去调用next()获取集合的元素，既然不会调用next()那么底层就不会产生并发修改异常
![反序列化 [网鼎杯 2020 朱雀组]phpweb 1](https://img-blog.csdnimg.cn/direct/8590d71bf0094336937f20db8d991c9b.png)
