Java - 剖析ArrayList
一巷怜、基本用法
ArrayList 是一個(gè)泛型容器，在新建 ArrayList 的時(shí)候需要實(shí)例化泛型參數(shù)瓢姻，如下：
ArrayList<Integer> intList = new ArrayList<Integer>();
ArrayList<String> strList = new ArrayList<String>();
在 ArrayList 中常用的方法如下：
public boolean add(E e) // 添加元素到末尾
public boolean isEmpty() //判斷是否為空
public int size() //獲取元素個(gè)數(shù)
public E get(int index) //訪問指定位置的元素
public int indexOf(Object o) // 查找指定元素祝蝠，如果找到返回索引位置，否則返回-1
public int lastIndexOf(Object o) // 從后往前找
public boolean contains(Object o) // 是否判斷指定元素幻碱，判斷依據(jù)是調(diào)用 equals 方法
public E remove(int index) // 刪除指定位置的元素绎狭，返回值為刪除的元素
//刪除指定對象，只刪除第一個(gè)相同的對象褥傍，返回值為被刪對象
//如果o為null儡嘶，則刪除值為null的元素
public boolean remove(Object o)
public void clear() // 清空所有元素
// 在指定位置插入元素， index 為0表示插入到最前面恍风，index為ArrayList的長度則表示插入到最后面
public void add(int index, E element)
public E set(int index, E element) // 修改指定位置的元素內(nèi)容
二蹦狂、基本原理
ArrayList內(nèi)部有一個(gè)數(shù)組 elementData， 在一般情況下會有一些預(yù)留口那件邻耕，同時(shí)又一個(gè)整數(shù) size 記錄實(shí)際的元素個(gè)數(shù)鸥咖。
/**
* 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
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
該類的方法內(nèi)部操作的基本都是這個(gè)數(shù)組和這個(gè)整數(shù)， 其中 elementData 會跟著實(shí)際元素的個(gè)數(shù)增多而重新分配兄世，而size使用記錄實(shí)際的元素個(gè)數(shù)啼辣。
接下來查看 add 方法的實(shí)現(xiàn)，其代碼為：
/**
* 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) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
首先調(diào)用ensureCapacityInternal方法來確保數(shù)組容量是足夠的御滩，其實(shí)現(xiàn)為：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
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);
}
首先調(diào)用calculateCapacity用于返回現(xiàn)在需要的最小容量鸥拧，接下來進(jìn)入ensureExplicitCapacity方法判斷現(xiàn)有容量是否足夠，如果不夠則調(diào)用 grow 方法削解，對數(shù)組進(jìn)行擴(kuò)容富弦，其實(shí)現(xiàn)為：
/**
* 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;
}
從oldCapacity >> 1可以看出是對原有數(shù)組容量除以2，因此每一次擴(kuò)容都是原有容量的 1.5 倍氛驮。如果發(fā)現(xiàn)擴(kuò)展1.5倍之后還是不夠腕柜， 則直接擴(kuò)容為minCapacity，與此同時(shí)還會對擴(kuò)容的數(shù)量進(jìn)行邊界判斷矫废，在合法之后對數(shù)據(jù)元素進(jìn)行拷貝盏缤，其中MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。
接下來我們查看remove方法的實(shí)現(xiàn)
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
}
首先對邊界進(jìn)行檢查蓖扑，獲取元素唉铜。然后計(jì)算需要移動(dòng)的元素的個(gè)數(shù)，從index之后的元素均需要移動(dòng)律杠，之后調(diào)用System.arraycopy方法進(jìn)行元素的移動(dòng)潭流。 在元素移動(dòng)完成之后竞惋，使用elementData[--size] = null，將 size - 1的同時(shí)將最后一個(gè)元素設(shè)置為 null灰嫉，使得不再引用原有對象拆宛，這樣就便于垃圾回收。
三熬甫、ArrayList實(shí)現(xiàn)的接口
ArrayList實(shí)現(xiàn)了三個(gè)主要的接口：
- Collection
- List
- RandomAccess
3.1 Collection
Collection表示一個(gè)數(shù)據(jù)集合胰挑，數(shù)據(jù)間沒有位置或順序的概念蔓罚，接口定義為：
public interface Collection<E> extends Iterable<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
}
Java 8對Collection接口添加了幾個(gè)默認(rèn)方法椿肩，包括removeIf、stream豺谈、spliterator等郑象，具體可參見API文檔。
3.2 List
List表示有順序或位置的數(shù)據(jù)集合茬末，它擴(kuò)展了Collection厂榛，增加的主要方法有（Java 7）：
boolean addAll(int index, Collection<? extends E> c);
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
3.3 RandomAccess
RandomAccess的定義為：
public interface RandomAccess {
}
這種沒有任何代碼的接口在Java中被稱為標(biāo)記接口，用于聲明類的一種屬性丽惭。
實(shí)現(xiàn)了RandomAccess接口的類表示可以隨機(jī)訪問击奶，可隨機(jī)訪問就是具備類似數(shù)組那樣的特性，數(shù)據(jù)在內(nèi)存是連續(xù)存放的责掏，根據(jù)索引值就可以直接定位到具體的元素柜砾，訪問效率很高。
比如换衬，Collections類中有一個(gè)方法binarySearch痰驱，在List中進(jìn)行二分查找，它的實(shí)現(xiàn)代碼就根據(jù)list是否實(shí)現(xiàn)了RandomAccess而采用不同的實(shí)現(xiàn)機(jī)制瞳浦，如下所示：
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if(list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
四担映、總結(jié)
ArrayList，它的特點(diǎn)是內(nèi)部采用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)叫潦，有以下的特點(diǎn)：
- 可以隨機(jī)訪問蝇完，按照索引位置進(jìn)行訪問效率很高，用算法描述中的術(shù)語矗蕊，效率是O（1）
- 除非數(shù)組已排序短蜕，否則按照內(nèi)容查找元素效率比較低，具體是O（N）拔妥，N為數(shù)組內(nèi)容長度忿危，也就是說，性能與數(shù)組長度成正比没龙。
- 加元素的效率還可以铺厨，重新分配和復(fù)制數(shù)組的開銷被平攤了缎玫，具體來說，添加N個(gè)元素的效率為O（N）解滓。
- 插入和刪除元素的效率比較低赃磨，因?yàn)樾枰苿?dòng)元素，具體為O（N）洼裤。
需要說明的是邻辉，ArrayList不是線程安全的。此外腮鞍，需要了解的是值骇，還有一個(gè)類Vector，它是Java最早實(shí)現(xiàn)的容器類之一移国，也實(shí)現(xiàn)了List接口吱瘩，基本原理與ArrayList類似，內(nèi)部使用synchronized實(shí)現(xiàn)了線程安全迹缀，不需要線程安全的情況下使碾，推薦使用ArrayList。
