一、简介
ArrayList非常常用，就看看它的部分源码，主要还是关注get、add、remove方法。它的内部用于存储数据的字段是：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
就是个Obejct数组。
二、get方法
get方法源码如下：
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
rangeCheck就是检查一下index是否大于等于size，如果大于等于，就抛出IndexOutOfBoundsException。没抛异常就直接返回elementData[index]。
三、add方法
add方法有两个重载：
public boolean add(E e) {
add(size(), e);
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
add(E e）将元素插在数组末尾，add(int index, E element)可以指定插入的位置。
就这么几行，一行一行来：
1.rangeCheckForAdd(index);
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
检查index是否合法，>size或小于0的index不能插入元素因此不合法。
2.ensureCapacityInternal(size + 1);
确保增加了一个元素之后没有超过数组的容量capacity。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
可以看到，主要就是判断当前数组的长度是否小于size+1，小于则增加数组的长度保证当前数组长度大于等于size+1。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;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
一般情况下，新的capacity的旧capacity加上旧capacity右移一位（即除以二）。再判断newCapacity <要保证的最小capacity（minCapacity）的情况以及大于MAX_ARRAY_SIZE的情况。
得到新的capacity后，调用
elementData = Arrays.copyOf(elementData, newCapacity);
这是将原本的elementData拷贝一份到newCapacity长度的数组里。Arrays.copyOf方法为：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
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;
}
就是新建一个T类型的copy数组，长度为newCapacity，再调用System.arraycopy将原数组的min(original.length, newLength)个元素拷贝到copy数组里。
Systen.arraycopy是一个native方法：
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
* @exception IndexOutOfBoundsException if copying would cause
* access of data outside array bounds.
* @exception ArrayStoreException if an element in the <code>src</code>
* array could not be stored into the <code>dest</code> array
* because of a type mismatch.
* @exception NullPointerException if either <code>src</code> or
* <code>dest</code> is <code>null</code>.
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
3.Systen.arraycopy(elementData, index, elementData, index + 1, size - index)
将elementData中的index以后的元素拷贝到elementData的index+1后面，得以把index处空出来。
4.elementData[index] = element;
index处的元素等于要插入的元素。
++size。改变size，即数组元素个数的统计。
四、remove方法
remove方法有两个重载，一个是移除对象，一个是移除某个index处的元素。
public E remove(int index) {
rangeCheck(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; // clear to let GC do its work
return oldValue;
}
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++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
remove(int index)方法就是index+1后面的元素拷到index处，这样index处的元素就被删除了，再将elementData末尾元素置为null，改变数组元素的个数。
remove(Object o)方法，就是找到和对象o相等的元素的位置index，再调用fastRemove(index);fastRemove的实现和remove(int index)类似：
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; // clear to let GC do its work
}
网友评论