Android ArrayList源码分析
2016-05-09 本文已影响247人
Reiya
/**
* ArrayList is an implementation of {@linkList}, backed by an array.
* All optional operations including adding, removing, and replacing elements are supported.
*
*
All elements are permitted, including null.
*
*
This class is a good choice as your default {@codeList} implementation.
* {@linkVector} synchronizes all operations, but not necessarily in a way that's
* meaningful to your application: synchronizing each call to {@codeget}, for example, is not
* equivalent to synchronizing the list and iterating over it (which is probably what you intended).
* {@linkjava.util.concurrent.CopyOnWriteArrayList} is intended for the special case of very high
* concurrency, frequent traversals, and very rare mutations.
*
*@paramThe element type of this list.
*@since1.2
*/
以上是ArrayList的类前注释。大致意思如下：
ArrayList是底层用数组实现的List。支持增删改等操作。支持包括null的任意类型元素。Vector使用synchronized来进行线程同步；CopyOnWriteArrayList适合确保高并发场景下的线程安全；在一般情况下使用ArrayList效率较高。
下面从代码里的几个主要属性和方法入手。
/**
* The minimum amount by which the capacity of an ArrayList will increase.
* This tuning parameter controls a time-space tradeoff. This value (12)
* gives empirically good results and is arguably consistent with the
* RI's specified default initial capacity of 10: instead of 10, we start
* with 0 (sans allocation) and jump to 12.
*/
private static final int MIN_CAPACITY_INCREMENT = 12;
与JDK源码不同，JDK初始容量是10，而Android下是初始0再跳到12。不不不你说12好一般人也看不出妙在哪啊难道是8派和16派僵持不下最后折中成12吗。
/**
* The elements in this list, followed by nulls.
*/
transient Object[] array;
Object数组array用来存储元素。值得注意的是修饰符transient。transient的作用是使可序列化对象中的指定属性不被序列化。而在这里使用transient的目的，是因为直接序列化array的话array里可能存在一定数量的空值导致浪费资源。
/**
* Adds the specified object at the end of this {@code ArrayList}.
*
* @param object
* the object to add.
* @return always true
*/
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
/**
* Inserts the specified object into this {@code ArrayList} at the specified
* location. The object is inserted before any previous element at the
* specified location. If the location is equal to the size of this
* {@code ArrayList}, the object is added at the end.
*
* @param index
* the index at which to insert the object.
* @param object
* the object to add.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location > size()}
*/
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
/**
* This method controls the growth of ArrayList capacities. It represents
* a time-space tradeoff: we don't want to grow lists too frequently
* (which wastes time and fragments storage), but we don't want to waste
* too much space in unused excess capacity.
*
* NOTE: This method is inlined into {@link #add(Object)} for performance.
* If you change the method, change it there too!
*/
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
增。如果数组已满则进行扩容。扩容方式为：若容量小于6则增加12，否则1.5倍扩容。
/**
* Adds the objects in the specified collection to this {@code ArrayList}.
*
* @param collection
* the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
*/
@Override public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
}
批量增。又与JDK实现不同：JDK是扩容为新容量与1.5倍容量的较大者；此处为 以新容量为基准1.5倍扩容。如newCapacity方法的注释所写：这是时间空间权衡，既不想频繁扩容（数组复制），又不想浪费过多冗余空间。就这种扩容方式而言，容量比JDK的方式要大，减少了扩容次数，想必思路倾向于以空间换时间。
@SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
查。直接返回array里对应位置的对象。
/**
* Searches this {@code ArrayList} for the specified object.
*
* @param object
* the object to search for.
* @return {@code true} if {@code object} is an element of this
* {@code ArrayList}, {@code false} otherwise
*/
@Override public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
检查是否包含。遍历array找出与目标相同的对象。indexOf方法和lastIndexOf方法也是相同的实现思路。
/**
* Removes the object at the specified location from this list.
*
* @param index
* the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location >= size()}
*/
@Override public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}
删。将array对应位置的对象找出以便返回，再通过数组复制将该位置后的对象前移一位，最后为了防止内存泄漏将原来的末位置空。
/**
* Replaces the element at the specified location in this {@code ArrayList}
* with the specified object.
*
* @param index
* the index at which to put the specified object.
* @param object
* the object to add.
* @return the previous element at the index.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location >= size()}
*/
@Override public E set(int index, E object) {
Object[] a = array;
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
a[index] = object;
return result;
}
改。直接将array里对应位置的对象指向新对象。
private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeInt(array.length);
for (int i = 0; i < size; i++) {
stream.writeObject(array[i]);
}
}
private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
stream.defaultReadObject();
int cap = stream.readInt();
if (cap < size) {
throw new InvalidObjectException(
"Capacity: " + cap + " < size: " + size);
}
array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]);
for (int i = 0; i < size; i++) {
array[i] = stream.readObject();
}
}
writeObject和readObject这两个方法是序列化和反序列化需要特殊处理的类必须实现的方法，因为上文所说的transient修饰符的关系ArrayList并非直接序列化array。ArrayList序列化时只序列化实际存储大小的部分而不是整个array，从而提高了序列化效率。
总而言之，ArrayList是基于数组实现的列表结构，查找指定位置快，相对的增删慢。
