ArrayList源码解析
实现的接口
本文基于Oracle JDK1.8展开讨论
ArrayList位于java.util包下
ArrayList类的声明：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.SerializableArrayList继承了AbstractList，看AbstractList源码，实现了List接口
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
而ArrayList再次实现了List接口，不觉得多余吗？实际上，这么设计是有原因的：
List接口里面包含了很多方法，实现了List接口的类要重新全部的方法，而且各自的实现类具体的方法实现是不一样的，比如ArrayList和LinkedList对于add的具体实现肯定是不一样的。
但是ArrayList和LinkedList对于某些方法的实现是一模一样的，比如size()方法
这时候，如果每增加一个List的实现类，都要重复的写一些方法体一模一样的方法，无法复用代码
这时候就利用了设计模式里的模板方法模式，把List的实现类的共有方法抽象到AbstractList里，并提供默认的实现，这样下层的实现类继承了AbstractList，直接继承共有的方法，而不需要重复的写一些代码
RandomAccess
此接口为一个空接口，目的是加快ArrayList随机访问的速度
public interface RandomAccess {}Cloneable
此接口为一个空接口，实现了后可以重写clone方法实现深拷贝
public interface Cloneable {}java.io.Serializable
此接口为一个空接口，目的是方便序列化
public interface Serializable {}成员变量
/** * 序列化ID */ private static final long serialVersionUID = 8683452581122892189L; /** * 默认初始化容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 创建一个空ArrayList时，赋值使用 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 默认空的数组，在初始化时使用 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 实际存放数据的数组 */ transient Object[] elementData; // non-private to simplify nested class access /** * 数组内存放的实际元素个数 */ private int size;构造函数
共三个构造函数
无参构造函数
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //elementData 为存放数据的数组 transient Object[] elementData; //无参初始化时，赋值为一个空的数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};根据容量初始化构造函数
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { //根据容量生成一个Object数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //参数等于0 则赋值一个空数组 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }根据现有List初始化构造函数
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { //如果返回的不是Object[]类型 则进行复制操作，Arrays.copyOf底层调用的System.arraycopy() if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }clone方法
public Object clone() { try { //先调用父类的clone克隆 ArrayList<?> v = (ArrayList<?>) super.clone(); //底层还是调用System.arraycopy(); v.elementData = Arrays.copyOf(elementData, size); //修改次数设置为0 v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }get方法
```java
public E get(int index) {//首先检查index是否合法 rangeCheck(index); return elementData(index);
}
/**检查index是否合法
/
private void rangeCheck(int index) {if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
/**
*返回index 位置的元素
*/
E elementData(int index) {
return (E) elementData[index];
}
### set方法
```java
public E set(int index, E element) {
//检查index是否合法
rangeCheck(index);
//取出旧元素
E oldValue = elementData(index);
//把index位置的元素替换为新元素
elementData[index] = element;
return oldValue;
}add方法：此处会产生扩容
public boolean add(E e) {
//确定容量是否足够 不够则扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果数组为空数组 即第一次add元素 取一个最大的Capacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//修改次数+1
modCount++;
//如果需要的Capacity 大于当前elementData的长度 则需要扩容
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
} 扩容机制 grow(minCapacity);
private void grow(int minCapacity) {
// 记录旧容量
int oldCapacity = elementData.length;
//新容量为 旧容量+ 旧容量的1/2
//这里使用了移位运算 右移一位相当于除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//取一个最大值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量超过Integer.MAX_VALUE - 8 则把newCapacity赋值为Integer.MAX_VALUE
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;
} remove方法
public E remove(int index) {
//检查下标是否合法
rangeCheck(index);
//修改次数+1
modCount++;
//保存旧值
E oldValue = elementData(index);
//删除元素后 数组需要移动的元素数量
int numMoved = size - index - 1;
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;
} clear方法
public void clear() {
//修改次数+1
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
} addAll方法
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;
//此处的移动是把index之后的元素后移numMoved个 目的是给下面插入的元素腾出位置
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//把数据插入index处
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
} 迭代器
public Iterator<E> iterator() {
//平时使用的迭代器 实际上是ArrayList的一个内部类Itr
return new Itr();
} 迭代器解析
private class Itr implements Iterator<E> { //指向下一个元素的游标 int cursor; // index of next element to return //上一个返回的元素 int lastRet = -1; // index of last element returned; -1 if no such //此处注意！！！ 在获取迭代器的时候，expectedModCount只会被赋值一次 // 所以当外部的modCount改变之后，内部类的expectedModCount并不会改变 int expectedModCount = modCount; /** *判断是否有下一个元素 */ public boolean hasNext() { //直接判断游标是否==size return cursor != size; } @SuppressWarnings("unchecked") public E next() { //判断修改版本是否一致 checkForComodification(); int i = cursor; //下标大于size 抛出异常 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]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; //此处会更新修改的版本 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } //内外修改次数不一致时 此处会引起并发修改异常 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
其他方法
/**
* 获取元素数量
*/
public int size() {
return size;
}
/**
* 判断是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 判断是否包含元素o 这里就是调用indexOf 看一下元素的索引是不是>0
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
//如果对象为空 则取数组里查找第一个对象为空的索引
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
//不为空 则遍历数组 使用equals判断
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
} #java#
