ArrayList源码解读
2017-10-23 本文已影响28人
西土城小羊
ArrayList特点总结
-
ArrayList实现List接口，底层是使用数组实现的，可以根据元素的个数进行动态扩容
-
ArrayList线程不安全而Vector是线程安全的，多线程环境下，可以考虑使用
List list = Collections.synchronizedList(new ArrayList(...)); -
元素可以是null
-
查询修改元素的时间复杂度O(1),而插入删除为O(n)
-
构造方法 有3种 一种是指定list的容量 一种是无参构造方法 还有一种是使用一个Collection为参数
-
扩容方法 见grow方法 int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容当前数组长度的一半 1.8之前是 newCapacity = (oldCapacity * 3)/2+1
源码分析
为了代码的简洁，将非核心的代码去掉了，这里还是想说英文的注释是最好的学习材料，有条件的还是应该多看源码中的英文注释
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//实现List接口
//实现RandomAccess接口，可以进行随机访问
//实现Cloneable接口，可以被clone
//实现序列化接口
private static final long serialVersionUID = 8683452581122892189L;
//默认的初始容量是10，也就是数组的大小默认是10，面试时会问问
private static final int DEFAULT_CAPACITY = 10;
//两个空的数组对应不同的构造方法
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储ArrayList元素的数组
//任何一个空的ArrayList(使用elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA进行初始化的，
//在第一个元素被add的时候都会自动扩容到DEFAULT_CAPACITY）
//使用transient时为了不被序列化
transient Object[] elementData;
//ArrayList中元素的个数
private int size;
//构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) { //初始化容量
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { //当初始化容量为0的时候 elementData = {}
this.elementData = EMPTY_ELEMENTDATA;
} else { //初始化容量<0时 抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//无参构造方法，elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 当第一个元素被添加的时候扩容到10
//jdk1.7的时候 好像是this(10)
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//构造方法 参数是一个Collection对象
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //将c转成数组对象
if ((size = elementData.length) != 0) {
// 判断elementData的类型 因为c.toArray不一定返回的Object[] 见
// http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 替换空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
//将数组中的元素剔除，这样可以使ArrayList实例占用的存储空间尽可能小
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//判断当前ArrayList的容量是否够用
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//minCapacity为默认大小10和参数指定大小的较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
//如果参数minCapacity比数组长度长就进行扩容
grow(minCapacity);
}
//用来扩容的函数
private void grow(int minCapacity) {
int oldCapacity = elementData.length; //获取当前数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容当前数组长度的一半 1.8之前是 newCapacity = (oldCapacity * 3)/2+1
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; //如果新容量还是比指定的minCapacity小就将容量扩充到minCapacity
if (newCapacity - MAX_ARRAY_SIZE > 0) //新容量超过了Integer.MAX_VALUE - 8 可能是Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
// minCapacity通常是接近size的
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; //Integer.MAX_VALUE - 8
}
//获取ArrayList中元素的个数
public int size() {
return size;
}
//判断是够为空
public boolean isEmpty() {
return size == 0;
}
//判断是否含有某个元素注意这种情况(o==null?e==null:o.equals(e))
//因为ArrayList可以塞进null，所以当o是null的时候只要ArrayList中元素e也是null就返回true
//如果o不是null的话，就是使用equals判断list中是否含有元素o
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回list中元素的下标（第一个），如果存在就返回该元素下标，如果不存在就返回-1
public int indexOf(Object o) {
if (o == null) { //如果元素指定的元素是null
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else { //指定的元素不为null
for (int i = 0; i < size; i++)
if (o.equals(elementData[i])) //循环遍历list 使用eqauls判断list中与指定元素相同的元素
return i;
}
return -1;
}
//获取最后一个元素o在list中的下标
public int lastIndexOf(Object o) {
if (o == null) {
//从后往前找
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
//使用equals方法判断相同
if (o.equals(elementData[i]))
return i;
}
//如果元素不存在返回-1
return -1;
}
//clone方法
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
//返回数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
//返回指定index的元素
public E get(int index) {
rangeCheck(index); //index合法性检查
return elementData(index);
}
//根据index对list元素进行赋值
public E set(int index, E element) {
rangeCheck(index); //index越界检查
E oldValue = elementData(index); //返回旧值
elementData[index] = element; //设置新值
return oldValue;
}
//添加指定的元素到list的末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保添加一个元素不会越界 如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次添加的时候list会扩容到默认的10
elementData[size++] = e;
return true;
}
//在指定index添加元素
public void add(int index, E element) {
rangeCheckForAdd(index); //index越界检测
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//删除指定index的元素并返回原先的元素
public E remove(int index) {
rangeCheck(index); //index下标检查
modCount++;
E oldValue = elementData(index); //获取原先的值
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // GC
//返回原先的值
return oldValue;
}
//删除list中出现的第一个元素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++)
//遍历使用equals判断相等
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//私有的删除方法，在remove中调用，在这个方法中不包含越界检查和返回原来值
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; //GC
}
//清空列表
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null; //GC
size = 0;
}
//添加Collection中所有的元素到当前的list中
public boolean addAll(Collection<? extends E> c) {
//collection转数组
Object[] a = c.toArray();
//获取数组的长度 即元素的个数
int numNew = a.length;
//确保list内部数组容量
ensureCapacityInternal(size + numNew); // Increments modCount
//复制数组
System.arraycopy(a, 0, elementData, size, numNew);
//修改list 元素个数
size += numNew;
return numNew != 0;
}
//指定index向list插入Collection的所有元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); //检查index
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
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;
}
//index越界检查，如果不合法抛出一个运行时异常，
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// add和addAll的越界检查
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//下标越界异常信息
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
//删除Collection中所有的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
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;
}
}
