ArrayList源码解析
一直以来都是看别人的博客,所以从来都是输入,没有输出。所以决心自己搞一个博客输出一下学习的东西。
既然决定要写,就先从集合类开始。集合类最常用到的肯定是list,map,和set等。因此决定先从list的ArrayList写起。ArrayList的源码还是很容易理解的不算很绕。
注:虽然是源码解析,但是并不是所有的源码都会涉及到,只涉及到经常使用的那些。
源码基于1.8。
首先看看ArrayList的类关系图,了解一下它的继承关系和实现的接口。
从图中可以看出,ArrayList继承自AbstractList,同时实现了克隆,序列化,随机访问这几个接口。这里不多说。
那么再来看看ArrayList拥有的变量。
// 默认的初始化容量。
private static final int DEFAULT_CAPACITY = 10;
// 一个共享的空数组,用于空实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
// 也是共享的空数组实例,用于默认大小的空实例。
// 与上面的那个区别是知道添加第一个元素时会膨胀多少。
// 在空的构造函数中使用了。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正存放元素的数组。
transient Object[] elementData; // non-private to simplify nested class access
// ArrayList的大小。
private int size;
// 分配给数组的最大容量。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
从上面的变量可以看出,该ArrayList基于数组实现的(不过这应该众所周知吧),该数组是一个动态数组。
下面看看ArrayList的构造方法:
// 用户使用带参的构造函数,指定该数组的容量。
public ArrayList(int initialCapacity) {
// 参数大于0时, 构造该大小的数组
// 注意这里并没有修改size, 因为此时数组中还没有任何元素。
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果容量为0, 直接将EMPTY_ELEMENTDATA赋值给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 容量小于0, 抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 默认的构造方法,将DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个空数组赋给了elementData
// 其实看后面代码可以知道,如果数组是这个类型的,添加第一个元素时,ArrayList的大小会设为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 使用其他集合类来构造ArrayList
*/
public ArrayList(Collection<? extends E> c) {
// 使用Collection.toArray()
elementData = c.toArray();
// 如果该Collection的大小不为0
if ((size = elementData.length) != 0) {
// c.toArray 可能不是Object[],因此使用Arrays.copyOf复制
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 否则,collection 的大小为0,那么使用EMPTY_ELEMENTDATA赋给elementData
this.elementData = EMPTY_ELEMENTDATA;
}
}
根据上面的构造函数可以看出,ArrayList提供了三种构造函数给提供给我们使用。
1.第一个是无参的,它会创建一个空数组。其实这样是默认大小为10的,看后面的代码可以知道。
2.第二个是用户指定参数的,会创建相应大小的数组,如果指定的参数是负数,那么抛出参数异常的错误。
3.第三个是Collection的类型,因为ArrayList继承自AbstractList,而AbstractList实现的是Collection的接口。
而Collection接口中提供了toArray(),因此只要是实现了Collection或其子接口的就能转换成数组。
下面继续看其他的代码:
// 该方法用来修剪大小的,因为不是所有数组中的空间都能用到。
public void trimToSize() {
modCount++;
// 如果当前ArrayList拥有的元素小于elementData的大小。
if (size < elementData.length) {
// 如果size是0,则将EMPTY_ELEMENTDATA赋给elementData,否则使用Arrays.copyOf复制
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);
}
}
// 如果elementData是默认的数组,那么判断默认的初始化大小(10)和参数minCapacity哪个大,然后返回。
// 否则直接返回minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果该值大于当前数组的大小,那么扩容,grow()方法就是扩容,等会再讲。
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
这里引出了一个新的变量,modCount,该变量是AbstractList中protected类型的变量,ArrayList继承了这个变量。该变量的作用是:记录该ArrayList结构的变化次数,常用于迭代判断fail-fast的,一旦触发fail-fast就会抛出ConcurrentModificationException异常。关于fail-fast我这里不赘述,想了解的自行百度,可能以后也会写关于这个的文章。
常用API
增加
// 增加一个元素。
public boolean add(E e) {
// 添加元素的时候判断,这里方法是上面的那个方法套方法,没写注释的那个
// 这里就可以知道,如果用户使用的是无参构造函数,那么默认的初始化大小是10
// 这里会使用到扩容,因此就放在一块写了。PS:这里的官方注释好可爱,我就没删了。
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 扩容的方法。
private void grow(int minCapacity) {
// 获取当前数组的大小。
int oldCapacity = elementData.length;
// 新的大小,为旧的大小的1.5倍。
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新的大小还是小于传来的参数,那么新的大小设为传来的参数。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新的大小大于MAX_ARRAY_SIZE(变量那块有,值为Integer.MAX_VALUE - 8)
if (newCapacity - MAX_ARRAY_SIZE > 0)
//下面贴出该方法。注意此时传的参数是minCapacity。
newCapacity = hugeCapacity(minCapacity);
// 将之前数组中的元素复制到新数组中去。
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity 小于零,抛出OOM错误。
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果minCapacity 大于MAX_ARRAY_SIZE就将数组大小设为Integer.MAX_VALUE,
// 否则设为MAX_ARRAY_SIZE。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
这里其实还是比较好理解的。添加一个元素到ArrayList数组的末尾。当然在添加之前会判断是否需要扩容,因此,如果使用的是无参的构造函数创建对象,会默认扩展为大小为10的数组。同时可得,ArrayList扩容是扩容至原数组大小的1.5倍。
删除
// 根据位置移除元素,返回删除的那个元素值,会抛出IndexOutOfBoundsException
public E remove(int index) {
// 这个方法是检查index是否大于size,如果大于就会抛异常。
rangeCheck(index);
modCount++;
// 拿到index位置上的元素
E oldValue = elementData(index);
// 下面的操作就是将这个位置后面的元素向前移动。
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 设为null帮助GC(垃圾回收)
return oldValue;
}
// 根据元素移除元素
public boolean remove(Object o) {
// 如果该元素为null,那么删除list中为null元素。
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 不为 null,则遍历数组,查找出与该元素相等的元素。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
// 如果该元素在数组中找不到则返回false.
return false;
}
// 这是私有方法,跳过了边界检查,而且也不用返回被删除的元素
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; // 设为null帮助GC
}
// 清除所有的元素。
public void clear() {
modCount++;
// 帮助GC
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
从这里可以看出, ArrayList是支持插入null数据的。删除元素一般根据index或者根据元素来删除,但是**需要注意的是:**根据元素来删除只会删除第一次出现的位置,之后即使还有这个元素,也还是不会删除的。
查
public E get(int index) {
// 越界检查
rangeCheck(index);
// 根据下标取出数据
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
改
public E set(int index, E element) {
rangeCheck(index);
// 根据index拿到之前旧数据。
E oldValue = elementData(index);
// 将改位置上的数据设为你传入的数据。
elementData[index] = element;
return oldValue;
}
查和改都很一目了然,就不多说了。
还有一个也比较常用,判断该元素在ArrayList中是否存在:
// 判断元素在ArrayList中是否存在。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// 如果元素在ArrayList中,那么返回该元素第一次出现的位置。否则返回-1。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// 与之相对应的是lastIndexOf,这样会从后面开始查找元素,返回元素最后一次出现的位置,否则返回-1
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--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
indexOf和lastIndexOf在String类中也有。
这里我踩过一个很小的坑,也说一下吧,不过只是我想当然的原因。当时需要做判断,如果字符串中有=,就截取部分字符串然后跳转,没有就跳另外一个。于是使用indexOf来查找=,返回=在字符串中的位置,由于并不是每个传来的字符串都会有=,因此就会返回-1。但是我没判断这个-1,直接就截取了,因此不管怎样都是跳一个页面。
总结一下:
- 首先,ArrayList基于动态数组。因此在增删改查的操作中,增和删的效率都比较低,因为增可以会导致扩容,而删需要移动元素,除非移动的是最后一个元素,同时也会修改modCount这个值。查和改效率都是比较高的,因为直接定位修改和取出。
- ArrayList是线程不安全的,多个线程同时的操作的话,建议使用Collections.synchronizedList()封装,或者在外部使用锁,如果读操作远高于写操作的话,那么建议使用CopyOnWriteArrayList。
- 这里再提一下,ArrayList和Vector的区别,因为不会写Vector相关的文章,因此这里就直接说了吧。Vector也是基于数组的,与ArrayList不同,Vector是线程安全的,但是是因为它每个方法都使用sychronized修饰,每次只允许一个线程进行操作,因此效率很低。然后,Vector每次都是两倍扩容,ArrayList则是1.5倍扩容的,也是不一样的区别之处。
最后,以上是关于ArrayList的全部内容。
谢谢各位的观看。本人才疏学浅,如有错误之处,欢迎指正,共同进步。