前言
ArrayList也叫数组列表,底层使用的数组实现的,严格来说是动态数组。为了简化,我将从以下几个方面对ArrayList进行分析
常用操作的源码分析
使用场景与小结
ArrayList工作原理
ArrayList工作原理其实很简单,底层是动态数组,每次创建一个ArrayList实例时会分配一个初始容量(如果指定了初始容量的话),以add方法为例,如果没有指定初始容量,当执行add方法,先判断当前数组是否为空,如果为空则给保存对象的数组分配一个最小容量,这里为10。当添加大容量元素额时候,会先增加数组的大小,以提高添加的效率。
把ArrayList理解为一个数组就好了
源码分析
由于ArrayList方法较多,对源码的分析不能一一到位,所以选取了我们平时最常用的add、get和remove方法来分析。
add方法
add方法重载了多个实现,包括add(E e)和add(int index,E e),由于没有指定插入的位置,每次插入操作会把元素放到数组的末尾,而这个过程只需要保证容量够用就行,先来看看add(E e)方法:
public boolean add(E e) {
//保证数组的容量始终够用
ensureCapacityInternal(size + 1);
//size是elementData数组中元组的个数,初始为0
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果数组没有元素,给数组一个默认大小,会选择实例化时的值与默认大小中较大值
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//保证容量够用
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//modCount是数组发生size更改的次数
modCount++;
// 如果数组长度小于默认的容量10,则调用扩大数组大小的方法
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
下面看看add(int index,E e):
public void add(int index, E element) {
//判断index的值是否合法,如果大于size或者小于0则将抛出异常
rangeCheckForAdd(index);
//保证容量够用,并修改modCount的值
ensureCapacityInternal(size + 1);
//从第index位置开始,将元素往后移动一个位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//把要插入的元素e放在第index位置
elementData[index] = element;
//数组元素的个数增加1
size++;
}
get方法
get方法最简单,首先判断该位置是否合法,如果合法则直接返回该位置的元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
remove方法
由于删除操作会改变size,所以每次删除都需要把元素向前移动一个位置,然后把原来最后一个位置的元素设置为null,一次删除操作完成。下面看看源码:
public E remove(int index) {
//判断index是否合法
rangeCheck(index);
//remove操作会改变size,所以modCount加1
modCount++;
//保存待删除位置的元素
E oldValue = elementData(index);
//要移动的元素个数
int numMoved = size - index - 1;
//如果index不是最后一个元素,则从第index+1到最后一个位置,依次向前移动一个位置
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//元素的size减少1,并把原来末尾位置元素的值设置为null
elementData[--size] = null;
//返回index位置的值
return oldValue;
}
可以注意到源码调用了System.arraycopy方法,该方法是native的,即该代码是其他语言编写,但Java允许与其进行交互(详情请搜索JNI),那么该方法是如何让实现的呢?
//add方法的System.arraycopy()
//把从第i位置的元素开始到最后一个元素,都往后移动一个位置
for(int j = size - 1; j > i; j--){
elements[j] = elements[j-1];
}
//把第i位置的值改为e
elements[i] = e;
//remove方法的System.arraycopy()方法
//把从第i位置到最后一个位置,都向前移动一个位置
for (int j = i; j < size - 1; j++) {
elements[j] = elements[j + 1];
}
//把数组的元素个数减少1
elements[--size] = null;
ArrayList小结
ArrayList是基于数组实现的,是一个动态数组,其容量能够自动增长 ArrayList不是线程安全的,只能用在单线程环境下,多线程环境需要使用Collections同步方法。Collections.synchronizedList(List l)返回一个线程安全的ArrayList。如果是读写比例比较大的话,则可以考虑CopyOnwriteArrayList。
- 默认容量是10
- ArrayList每次增加元素的时候,都需要调用ensureCapacity方法来确保足够的容量。当容量不足的时候,就设置新的容量为旧的的容量的1.5倍加1,如果设置的容量仍然不够,那么直接设置为传入的参数,而后用Arrays.copyOf方法将元素拷贝到新的数组。建议:在能够实现确定元素数量的情况下使用ArrayList,否则使用LinkedList。
- Arrays.copy()方法在方法的内部又创建了一个长度等长的数组,调用System.arraycopy方法完成新数组元素的复制。该方法的实际上调用native方法中C的memmove函数,在复制大数组的时候强烈建议使用该方法进行数组的复制。效率高。
- ArrayList是基于数组实现的,支持随机访问,查找效率高,但是插入删除效率低。
- ArrayList一般应用于查询较多但插入以及删除较少情况,如果插入以及从删除较多则建议使用LinkedList.