/**
* 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是底層用數(shù)組實(shí)現(xiàn)的List贮尉。支持增刪改等操作。支持包括null的任意類型元素朴沿。Vector使用synchronized來進(jìn)行線程同步猜谚；CopyOnWriteArrayList適合確保高并發(fā)場景下的線程安全败砂；在一般情況下使用ArrayList效率較高。
下面從代碼里的幾個(gè)主要屬性和方法入手魏铅。
/**
* 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數(shù)組array用來存儲元素。值得注意的是修飾符transient沧竟。transient的作用是使可序列化對象中的指定屬性不被序列化铸敏。而在這里使用transient的目的，是因?yàn)橹苯有蛄谢痑rray的話array里可能存在一定數(shù)量的空值導(dǎo)致浪費(fèi)資源悟泵。
/**
* 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;
}
增搞坝。如果數(shù)組已滿則進(jìn)行擴(kuò)容。擴(kuò)容方式為：若容量小于6則增加12魁袜，否則1.5倍擴(kuò)容桩撮。
/**
* 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實(shí)現(xiàn)不同：JDK是擴(kuò)容為新容量與1.5倍容量的較大者峰弹；此處為 以新容量為基準(zhǔn)1.5倍擴(kuò)容店量。如newCapacity方法的注釋所寫：這是時(shí)間空間權(quán)衡，既不想頻繁擴(kuò)容（數(shù)組復(fù)制）鞠呈，又不想浪費(fèi)過多冗余空間融师。就這種擴(kuò)容方式而言，容量比JDK的方式要大蚁吝，減少了擴(kuò)容次數(shù)旱爆，想必思路傾向于以空間換時(shí)間。
@SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
查窘茁。直接返回array里對應(yīng)位置的對象怀伦。
/**
* 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找出與目標(biāo)相同的對象山林。indexOf方法和lastIndexOf方法也是相同的實(shí)現(xiàn)思路房待。
/**
* 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對應(yīng)位置的對象找出以便返回驼抹，再通過數(shù)組復(fù)制將該位置后的對象前移一位桑孩，最后為了防止內(nèi)存泄漏將原來的末位置空。
/**
* 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里對應(yīng)位置的對象指向新對象流椒。
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這兩個(gè)方法是序列化和反序列化需要特殊處理的類必須實(shí)現(xiàn)的方法，因?yàn)樯衔乃f的transient修飾符的關(guān)系A(chǔ)rrayList并非直接序列化array明也。ArrayList序列化時(shí)只序列化實(shí)際存儲大小的部分而不是整個(gè)array宣虾，從而提高了序列化效率极谊。
總而言之，ArrayList是基于數(shù)組實(shí)現(xiàn)的列表結(jié)構(gòu)安岂，查找指定位置快，相對的增刪慢帆吻。
