java.util.ArrayList是Java开发最常用的类之一，但是对具体的实现不太了解，通过源码来分析下ArrayList的具体实现。
初始化
ArrayList提供2个初始化方法不带参数的和带参数的ArrayList(int initialCapacity)，其中capacity 是ArrayList的默认大小。
源码如下：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//创建指定大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//默认数组，空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
下面我们先看一下ArrayList 的 add方法。
add方法有2个 分别是插入到末尾和插入到指定位置对应的方法是
1.add(E e)
- add(int index, E element)
首先我们先看一下插入到末尾的方法
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//size是当前的list 容量
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
首先是调用ensureCapacityInternal()方法把arraylist做扩容处理。进入方法
/**
* 确定list容量
* minCapacity = size + 1
*/
private void ensureCapacityInternal(int minCapacity) {
//计算得到新的容量
int newCapacity = calculateCapacity(elementData, minCapacity);
//确定新的容量
ensureExplicitCapacity(newCapacity);
}
//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果list中没有数据，则获取list默认容量和计算容量(size+1)中较大的作为list新的容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//记录修改次数
modCount++;
// overflow-conscious code
//如果计算出的新容量 大于原容量，则执行扩容操作
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
具体的操作逻辑可以看上面注释，已经标记的很明白了。
下面我们看一下grow 方法
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
//记录旧的容量
int oldCapacity = elementData.length;
//重点！！ 计算实际的扩容之后的容量
// 每次扩容最小扩容为原容量的 1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//扩容之后的容量不超过最大容量(虚拟机限制)，超过之后会有OOM
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);
}
我们再看一下copyOf方法Arrays.copyOf(elementData, newCapacity),这个方法接收2个参数
/**
* Copies the specified array, truncating or padding with nulls (if necessary)
* so the copy has the specified length. For all indices that are
* valid in both the original array and the copy, the two arrays will
* contain identical values. For any indices that are valid in the
* copy but not the original, the copy will contain <tt>null</tt>.
* Such indices will exist if and only if the specified length
* is greater than that of the original array.
* The resulting array is of exactly the same class as the original array.
*
* @param <T> the class of the objects in the array
* @param original the array to be copied 原始数组
* @param newLength the length of the copy to be returned 扩容之后的容量
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @since 1.6
*/
@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
举个栗子：
/**
* 测试调用array list 的 add(index,element)方法
*/
private static void testAddArrayCopy() {
Object[] src = new Object[]{1,2,3,4};
Object[] newSrc = Arrays.copyOf(src,5);
for (Object i : newSrc) {
System.out.print(i+ ",");
}
}
这个方法的运行结果：1,2,3,4,null,
回到add()方法中
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//size是当前的list 容量
ensureCapacityInternal(size + 1); // Increments modCount!!
//执行到了这里，此时的elementData是已经扩容之后的数组了。
//将要添加的元素放到数组的末尾
elementData[size++] = e;
return true;
}
我们看到扩容完成之后
elementData[size++] = e;
这行代码中 size 为数组扩容前的容量，size + 1就是把要添加的元素放到数组的最后一个。
网友评论