对于Java中的ArrayList，很多伙伴们都知道怎么用，像Kotlin中的MutableList，最终也是通过ArrayList来实现的，对于ArrayList，我想最基本的大家都知道，尤其是在面试中也经常会被问到。
首先ArrayList其实就是数组，它在内存中是连续的；对于添加和删除元素，速度是比较慢的，因为涉及到内存的移动，但是获取元素的速度很快，因为可以通过索引可以直接从内存中获取
从源码看ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
从ArrayList的源码中可以看到，ArrayList实现了几个接口，Serializable可序列化接口，代表ArrayList能够被序列化和反序列化，那么什么是序列化和反序列化
1 序列化和反序列化
序列化：将对象转换为有序的字节流，然后在网络上传输，或者保存数据到本地文件中，能够保持对象完整性
反序列化：就是将有序的字节流转换为对象
public class Person {
private String name;
private int age;
Person(){
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
其实这种场景在Android中也会经常见到，在Activity页面之间传递数据，如果按照下面的方式传递，是会报错的，因为Person不能序列化，需要Person实现Serializable接口
Person person = new Person();
person.setName("ming");
person.setAge(14);
Intent intent = new Intent();
intent.putExtra("person",person);
除了Serializable接口之外，Android还提供了另一个接口Parcelable，这是Android独有的，那么跟Serializable有什么区别呢？
首先Serializable的序列化和反序列化都是IO操作，需要在硬盘上做读写操作，如果数据需要做持久化存储，就用Serializable；Parcelable是在内存中做读写操作，因此效率上比Serializable高
2 深拷贝和浅拷贝
ArrayList实现了Cloneable接口，可以对其进行拷贝
public class Person implements Cloneable {
private String name;
private int age;
private Address address;
Person(){
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public Address getAddress() {
return address;
}
public void setAddress(Address address) {
this.address = address;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@NonNull
@Override
protected Person clone() throws CloneNotSupportedException {
Person person = (Person) super.clone();
Address address = (Address) this.address.clone();
person.setAddress(address);
return person;
}
}
像Person类中的name属性和age属性，属于常量池或者基本数据类型，它们的拷贝就是浅拷贝，也就是值传递；而像Address对象，如果浅拷贝，那么拷贝的只是这个对象的内存地址，也就是说拷贝之后的对象，如果address对象数据发生改变，之前的对象也会发生改变。
所以如果类中存在其他的对象引用，需要重写clone方法，进行深拷贝操作，这里可以写一个demo验证一下
Person person = new Person();
person.setName("ming");
person.setAge(12);
person.setAddress(new Address("123",0731));
Person person1 = null;
try {
person1 = (Person) person.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
System.out.println(person + " ---- "+person1);
if(person1 != null){
person1.setAge(25);
Address address = person1.getAddress();
address.setCode(123);
address.setPath("231414");
person1.setAddress(address);
}
System.out.println(person + " ---- "+person1);
正常来说，对于name和age来说，如果拷贝后的对象修改某个值，不会影响之前的对象，但是对于address来说，浅拷贝会有影响的，我们看结果之前的对象address值也是被修改了
Person{name='ming', age=12, address=Address{path='123', code=473}} ---- Person{name='ming', age=12, address=Address{path='123', code=473}}
Person{name='ming', age=12, address=Address{path='231414', code=123}} ---- Person{name='ming', age=25, address=Address{path='231414', code=123}}
但如果我们对Person做了深拷贝处理，就不一样了，因为是深拷贝，引用对象整体被放入一块新开辟的内存空间
Person{name='ming', age=12, address=Address{path='123', code=473}} ---- Person{name='ming', age=12, address=Address{path='123', code=473}}
Person{name='ming', age=12, address=Address{path='123', code=473}} ---- Person{name='ming', age=25, address=Address{path='231414', code=123}}
3 RandomAccess
ArrayList实现了RandomAccess接口，从字面意思来讲是随机访问接口
List<String> list = new ArrayList<>();
for (int i = 0; i < 10000000; i++) {
list.add("random"+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));
long startTime1 = System.currentTimeMillis();
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
iterator.next();
}
long endTime1 = System.currentTimeMillis();
System.out.println("顺序访问时间"+(endTime1 - startTime1));
最终得出的结果就是随机访问的时间，比顺序访问的时间更快，就是因为实现了这个RandomAccess接口
随机访问时间14
顺序访问时间20
4 ArrayList源码分析
//object数组
transient Object[] elementData;
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
首先，在ArrayList的空参构造方法中，初始化了一个Object数组，所以ArrayList底层就是数组实现的，这里并没有声明数组的长度，是一个空数组；
如果声明了数组的长度initialCapacity，那么就创建一个initialCapacity长度的数组
4.1 add添加元素 – 了解扩容机制
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
如果只是调用add方法，但是并没有声明该元素放置的位置，那么默认就是放在数组的尾部，然后ArrayList有一个扩容机制，就是从ensureCapacityInternal方法开始
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 逻辑1
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//逻辑2
ensureExplicitCapacity(minCapacity);
}
如果是新建的ArrayList，没有声明数组长度，那么
size = 0
elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}
minCapacity = 1
DEFAULT_CAPACITY = 10
max（10,1）
---------------
minCapacity = 10
调用ensureCapacityInternal，首先进逻辑1判断，那么minCapacity就是10，也就是说，如果创建一个ArrayList，当添加元素的时候，默认数组长度就是10，然后调用ensureExplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
这里有个参数modCount，每次调用add，代表ArrayList被修改了一次，modCount就会＋1，即便是删除也会＋1
modCount = 1
minCapacity = 10
elementData.length = 0
这里会判断，如果minCapacity比数组的长度还要长，那么就会扩容，扩容方法就是grow
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);
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;
}
oldCapacity = 0
newCapacity = 0 + 0 >> 1 = 0 + 0 / 2 = 0
minCapacity = 10
扩容的规则就是：新数组的长度为原数组长度的基础上 + 原数组长度 / 2（右移1位）
这里会判断，如果扩容后的数组容量比minCapacity还要小，那么新的数组的长度就以minCapacity为准；那么如果扩容后的数组长度比最大的数组商都还要大，需要再做一次判断：
如果minCapacity要比MAX_ARRAY_SIZE还要大，那么长度就是Integer.MAX_VALUE，否则就取MAX_ARRAY_SIZE
所以如果按照扩容规则扩容之后的数组长度比MAX_ARRAY_SIZE大，就需要按照minCapacity的大小来规定，最大为Integer.MAX_VALUE
最终是调用Arrays.copyOf，将elementData扩容为newCapacity数组的长度
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
还有一个方法，add(index,E)通过传入索引位置，在当前位置中插入一个元素，那么我们再跟一下这个逻辑，此时我们已经添加了一个元素
size = 1
------------ ensureCapacityInternal ----------- 走到逻辑2
minCapacity = 2
------------ ensureExplicitCapacity -----------
minCapacity = 2
elementData.length = 10
这里不会扩容
4.2 迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
iterator.next();
list.remove(5);
}
在ArrayList迭代的时候，我做了一个非常规的操作，在迭代的同时，移除了一个元素，这时候报错ConcurrentModificationException，那么可以去看下源码，为什么在迭代的时候，不能删除元素（添加元素也一样）
Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1043)
at java.base/java.util.ArrayList$Itr.next(ArrayList.java:997)
private class Itr implements Iterator<E> {
protected int limit = ArrayList.this.size;
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor < limit;
}
@SuppressWarnings("unchecked")
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
我们可以看到，在执行next方法的时候，会首先判断，如果 modCount != expectedModCount，就会抛出这个异常，modCount是什么？在之前扩容机制中介绍过，每次list添加或者删除元素，modCount + 1，所以当在迭代的时候，如果执行了添加和删除操作，modCount就会改变，因为expectedModCount就是最开始的modCount，这样就会抛出ConcurrentModificationException异常
所以如果想要在迭代的时候，删除元素，可以调用迭代器的remove来完成，我们从remove源码可以看到，在删除元素的时候，还是调用了ArrayList的remove方法，但是
expectedModCount = modCount;
调用remove方法之后，将expectedModCount的值做了一次更新，因此每次remove之前，expectedModCount和modCount都是一致的。
5 ArrayList优化
5.1 扩容优化
因为ArrayList在扩容时，如果没有声明初始值，那么就是从10开始，每次扩容1.5倍，假如我知道一定有100个数据，那么从10扩容到100，需要很多次才能到，所以这种情况下，直接传入确切的初始值，能够减少扩容次数
5.2 删除优化
因为ArrayList底层是数组实现的，那么只要涉及到数据删除，都需要移动内存，删除10次数据，就需要移动10次内存，那么这样应该怎么优化呢？
假设我在删除数据时，优先给删除的数据一个标志位，但是并没有删除这项数据，等到最后一个删除的数据打上标志位之后，统一删除，那么只需要移动一次内存，能够提高效率
