ArrayList源码解析
2020-04-25 本文已影响0人
jyhnp
一定要耐心看完，会有收获的！
**ArrayList底层属性**
//默认容量10
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的数组对象
private static final Object[] EMPTY_ELEMENTDATA = {};
//初始化默认大小的数组对象，和空数组实例区分开来
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储ArrayList元素的数组
transient Object[] elementData;
//ArrayList的大小（它包含元素的数量）
private int size;
//数组分配最大的容量，因为虚拟机在数组中保留一些头信息，尝试分配最大的数组长度，可能会导致OutOfMemoryError：
//请求的数组大小超过VM的限制
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
**ArrayList初始化（3种方式）**
/**
* （1）构造指定初始化容量的空列表
* initialCapacity（初始化数组容量）
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果初始化容量大于0，就对elementData进行初始化，并指定数组长度
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//若果初始化容量等于0，就表示是一个长度为0的空数组，用空数组对象EMPTY_ELEMENTDATA来初始化
this.elementData = EMPTY_ELEMENTDATA;
} else {
//小于0的话就报错
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* （2）初始化数组，不指定长度，用默认的数组对象DEFAULTCAPACITY_EMPTY_ELEMENTDATA来初始化
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* （3）构造一个包含指定元素的数组
*/
public ArrayList(Collection<? extends E> c) {
//初始化elementData
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
//size等于elementData的长度，如果不等于0并且elementData的类型不是Object类型，
//Arrays.copyOf扩容操作生成新的数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//size等于0时，用空数组EMPTY_ELEMENTDATA初始化对象
this.elementData = EMPTY_ELEMENTDATA;
}
}
**ArrayList底层数组扩容**
/**
* 将元素添加到列表末尾
*/
public boolean add(E e) {
//扩容操作，调用ensureCapacityInternal方法传参当前数组大小加1，表示新增一个元素，数组需要的最小容量
ensureCapacityInternal(size + 1); // Increments modCount!!
//扩容之后将新增元素追加到集合末尾
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 计算数组需要的容量
* elementData（元素数组），minCapacity（数组需要的最小容量）
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果数组等于默认数组实例，表示数组第一次添加元素，需要进行初始化数组长度
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//默认的数组长度DEFAULT_CAPACITY（10）和最小需要的数组长度作比较，谁大取谁，保证数组容量足够容纳元素
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//否则返回数组需要最小的长度
return minCapacity;
}
/**
* 判断数组是否需要扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果数组需要最小的长度大于存储元素的数组的长度，就调用扩容方法
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 数组扩容
* minCapacity（数组需要最小的长度），MAX_ARRAY_SIZE（数组能分配最大的容量）
* oldCapacity（添加新元素之前的数组长度）
*/
private void grow(int minCapacity) {
// 老数组的长度（添加元素之前数组的长度）
int oldCapacity = elementData.length;
// 老数组的长度*1.5，生成新数组的长度（老数组长度的*二进制右移1位再转成10进制，相当于老数组的0.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//如果扩容后的新数组长度小于数组需要最小的长度，那么新数组长度就等于数组需要最小的长度
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果新数组的长度大于数组分配最大的容量，调用hugeCapacity方法
newCapacity = hugeCapacity(minCapacity);
//最后拿数组和扩容后的长度生成新的数组，就是数组扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 数组能分配的最大容量
* minCapacit（数组需要最小的长度），MAX_ARRAY_SIZE（数组能分配最大的容量）
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
//若果数组需要最小的长度小于0，就抛异常
throw new OutOfMemoryError();
//如果数组需要最小的长度大于数组能分配的最大容量，就返回Integer最大值，否则返回MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 判断索引是否在数组范围内，如果没有就抛异常
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
** 移除指定下标的元素 **
public E remove(int index) {
//先判断下标是否在数组范围内
rangeCheck(index);
modCount++;
//保存要移除的元素，当做remove的返回值
E oldValue = elementData(index);
//要移除的元素后边剩余元素的长度
int numMoved = size - index - 1;
//如果大于0说明要移除元素不是最后一个元素
if (numMoved > 0)
//将要移除元素后边剩余的元素，从要移除元素的位置开始，依次向前移位，相当于把要移除的元素给覆盖了从而达到删除效果
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//移除完元素后，数组的长度减1
elementData[--size] = null;
//返回移除的元素对象
return oldValue;
}
** 根据下标获取元素 **
public E get(int index) {
//判断下标是否在正确的范围内
rangeCheck(index);
return elementData(index);
}
//索引元素返回指定下标的值
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
System.arraycopy是一个静态的本地方法，由虚拟机实现，效率比用java一个一个复制高
底层方法：public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
从原数组src取元素，范围为srcPos开始到srcPos+length-1，取出length个元素，存放到目标数组中，
存放的下标为destPos到destPos+length-1；
Arrays.copyOf底层还是System.arraycopy，只是把原数组从下标0开始移到新数组中，并且指定长度，底层方法如下：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
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;
}
从上面移除、获取元素可以看出，ArrayList移除元素时需要对数组元素进行移位remove(Object obj)时间复杂度为O(n)，
获取元素根据其下标索引元素get(int i)时间复杂度为O(1)；
结束语：如果有写的不好或者不太懂得地方可以在下方评论
