ArrayList详解

前面介绍Java集合三大热门之二——HashMap和ConcurrentHashMap，那么剩下的一个就是ArrayList了，在使用列表时，除非特殊情况，一般都会用ArrayList。

一、简介

List允许有重复元素、且存储有序，实现主要有ArrayList、CopyOnWriteArrayList、Vector和LinkedList：

• ArrayList：底层是数组，查询快，增删慢，线程不安全。

• CopyOnWriteArrayList：底层是数组，读写分离，线程安全，效率较Vector高效，不过内存消耗较大。（add和remove等操作都加了ReentrantLock锁，当写的时候COW会先从原数组拷贝一份，然后在新的数组上做些操作，写完之后再将原数组引用指向新数组，读操作没有锁）

• Vector：底层是数组，线程安全，但效率低，扩容时为原来的2倍。（所有方法都加了Synchronized锁）

• LinkedList：底层是链表，查询慢，增删快，线程不安全。

二、源码解析

2.1 基础属性

//默认初始容量为10
private static final int DEFAULT_CAPACITY = 10;
//空实例数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认的空实例数组，在第一次调用ensureCapacityInternal时会初始化长度为10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
//数组当前元素的数量
private int size;
//数组允许的最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2.2 构造方法

//指定初始容量的有参构造
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);}
}
​
//使用默认容量的无参构造
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2.3 替换指定位置元素

//用指定元素替换指定位置的元素
public E set(int index, E element) {//检验是否数组越界rangeCheck(index);//根据index获取原元素E oldValue = elementData(index);//替换为新元素elementData[index] = element;//返回原元素return oldValue;
}
//ps：下方多处用到
private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

2.4删除元素

2.4.1 根据索引删除

//删除指定索引位置的元素
public E remove(int index) {//检查是否越界rangeCheck(index);modCount++;//获取要被删除的元素E oldValue = elementData(index);//计算需要移动的元素个数，int numMoved = size - index - 1;//判断是否需要移动。解释：如果size为5，index为4，那么5-4-1=0，因为index=4刚好是最后一个元素，无需移动。if (numMoved > 0){//将index+1之后的元素向左移动一位System.arraycopy(elementData, index+1, elementData, index,numMoved);}//将元素个数-1，并将size-1位置置空（因为上面将元素左移了，所以size-1位置的元素是重复的；或者本身就是尾元素，直接置空）elementData[--size] = null; // clear to let GC do its work//返回删除元素的值return oldValue;
}

2.4.2 根据元素值删除

//删除与指定值相同的元素，如果匹配到删除第一个与之匹配的元素，返回true，反之返回false
public boolean remove(Object o) {if (o == null) {//入参为null，遍历数组找到第一个为null的元素for (int index = 0; index < size; index++)if (elementData[index] == null) {//调用fastRemove将改元素移除fastRemove(index);return true;}} else {//同理，遍历数据找到第一个值为o的元素for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;
}
​
//删除指定index位置的元素
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
}

2.5 添加元素

2.5.1 添加到数组尾部

//在数组尾部增加一个元素
public boolean add(E e) {//将modCount+1，并校验添加元素后是否需要扩容，确保能存下size+1个元素ensureCapacityInternal(size + 1);  // Increments modCount!!//在数组尾部添加元素，并将size+1elementData[size++] = e;return true;
}

2.5.2 添加到指定位置

public void add(int index, E element) {//检查是否越界rangeCheckForAdd(index);//将modCount+1，并校验添加元素后是否需要扩容，确保能存下size+1个元素ensureCapacityInternal(size + 1);  // Increments modCount!!//将index之后的元素向右移动1位System.arraycopy(elementData, index, elementData, index + 1,size - index);//index位置设置为要添加的元素elementData[index] = element;//元素个数+1size++;
}
​
private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

举个例子：

2.6 扩容

2.5小节在add方法添加元素之前会先调用ensureCapacityInternal方法，该方法有两个作用，一个是如果没初始化就先初始化，二是检验添加元素后是否需要扩容：

private void ensureCapacityInternal(int minCapacity) {//判断ArrayList是否是无参构造创建的if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//是无参构造，主要是给DEFAULTCAPACITY_EMPTY_ELEMENTDATA设置初始容量minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);
}
​
private void ensureExplicitCapacity(int minCapacity) {modCount++;// 判断添加元素后的大小是否超过数组大小if (minCapacity - elementData.length > 0){//超过，进行扩容grow(minCapacity);}
}
​
//扩容
private void grow(int minCapacity) {// overflow-conscious code//原来的容量int oldCapacity = elementData.length;//新容量=老容量+老容量/2，也就是原来的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);
​if (newCapacity - minCapacity < 0){//说明新容量比需要的最小容量还小，把最小容量作为新容量newCapacity = minCapacity;}
​if (newCapacity - MAX_ARRAY_SIZE > 0){//说明超过数组最大大小阈值，调用hugeCapacity方法设置一个合适的容量newCapacity = hugeCapacity(minCapacity);}
​// minCapacity is usually close to size, so this is a win://将原数组元素拷贝到容量为newCapacity的新数组elementData = Arrays.copyOf(elementData, newCapacity);
}
​
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();//这就不用解释了吧。。。return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

三、如何实现序列化

大家可能没注意到，elementData数组使用transizent关键字修饰的，这就意味着序列化ArrayList时会忽略elementData，反序列化时会给其分配默认值，这肯定不行，那么它是如何实现序列化和反序列化的呢？

//存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access

这有个知识点。

ps：在序列化过程中，如果序列化类中定义了writeObject和readObject方法，JVM会调用对象类里的writeObject和readObject方法完成序列化和反序列化。如果没有这俩方法，会默认调用ObjectOutputStream的defaultWriteObject方法和ObjectInputStream的defaultReadObject方法。

所以ArrayList重写了writeObject和readObject方法来完成对elementData的序列化：

private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount = modCount;s.defaultWriteObject();// Write out size as capacity for behavioural compatibility with clone()s.writeInt(size);// Write out all elements in the proper order.//注意：是sizefor (int i=0; i<size; i++) {s.writeObject(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}
}
​
private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData = EMPTY_ELEMENTDATA;// Read in size, and any hidden stuffs.defaultReadObject();// Read in capacitys.readInt(); // ignoredif (size > 0) {// be like clone(), allocate array based upon size not capacityint capacity = calculateCapacity(elementData, size);SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);ensureCapacityInternal(size);Object[] a = elementData;// Read in all elements in the proper order.for (int i=0; i<size; i++) {a[i] = s.readObject();}}
}

为什么要用transient？

ArrayList实际上是动态数组，每次放满后自动扩容，假如10个容量满了，这是又来一个元素要add，那么这时候就会扩容为15容量，但实际是11个元素，那么就会有4个null（容量越大，null值越多），而null值是没有意义的（除了add的null）。

使用Java自带的序列化机制会把没有意义的null值也序列化了，会造成空间浪费，所以ArrayList把元素数组设置为transient，并自己重写writeObject和readObject来实现序列化操作。

End：希望对大家有所帮助，如果有纰漏或者更好的想法，请您一定不要吝啬你的赐教🙋。