[TOC]
0.概述
Resizable-array implementation of the List interface.
Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list.
(This class is roughly equivalent to Vector, except that it is unsynchronized.)
- ArrayList是基于對象數(shù)組的線性數(shù)據(jù)結(jié)構(gòu)
- 支持動態(tài)擴(kuò)容
- 基礎(chǔ)默認(rèn)容量10
- 最大容量為Integer.MAX_VALUE
- 支持null值
- 動態(tài)擴(kuò)容基于數(shù)組拷貝
1. 創(chuàng)建ArrayList
三種構(gòu)造器：
- 無參構(gòu)造器
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
無參構(gòu)造器，初始化內(nèi)部對象數(shù)組為空數(shù)組 {}，此方式創(chuàng)建的list會在第一次add元素的時候就觸發(fā)擴(kuò)容。
- 指定初始容量
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
所做的工作是，初始化對象數(shù)組。
- 從其他集合包裝
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
首先這個方法使用了泛型邊界通配符<? extends E>，限定了傳入方法的集合的元素類型，而后做的事情是數(shù)組拷貝（也就是元素拷貝），注意此處給size變量賦了值，size變量的值的作用是指代容器中元素的個數(shù)，因?yàn)橛性乜截愡M(jìn)來，自然要設(shè)置size。
2. 動態(tài)擴(kuò)容的觸發(fā)
ArrayList在add元素的時候，會比較當(dāng)前容量和元素數(shù)量，當(dāng)發(fā)現(xiàn)元素數(shù)量達(dá)到容器的容量時，就會觸發(fā)擴(kuò)容操作。
- add
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 針對無參構(gòu)造器創(chuàng)建ArrayList的情況，add時設(shè)置默認(rèn)容量
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//當(dāng)size+1 > elementData.length時，也就是在add之前，size（元素數(shù)量）==容量（數(shù)組長度），表示已經(jīng)裝滿了
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
和HashMap的擴(kuò)容機(jī)制不同，在ArrayList中沒有l(wèi)oadFactor的存在，擴(kuò)容的閾值就是當(dāng)前容量。
在使用無參構(gòu)造器初始化階段，內(nèi)部數(shù)組為空的Object數(shù)組，即length為0。在第一次add元素時，會以默認(rèn)容量（10）來創(chuàng)建新的數(shù)組，并將引用傳遞給原始的數(shù)組。隨著元素數(shù)量的增長，數(shù)組的容量會不夠，于是會動態(tài)增長數(shù)組容量，動態(tài)增長是通過創(chuàng)建新數(shù)組再將舊數(shù)據(jù)轉(zhuǎn)移到新數(shù)組中的動作來完成的。Arrays.copyof();
3. 擴(kuò)容方法
/**
* 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;
// new = 1.5*old
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// MAX_ARRAY_SIZE = Integer.MAX_VALUE-8
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;
}
4. 容器行為
4.1 indexof() -> ArrayList是支持null值的
public int indexOf(Object o) {
// 如果元素是null，遍歷數(shù)組尋找null返回index
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
另外lastIndexOf()則是倒序遍歷數(shù)組，contains（）則是調(diào)用indexOf判斷返回值是否為-1。
4.2 get()
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
就是數(shù)組元素的訪問。
4.3 remove（）
在ArrayList內(nèi)部，對元素的處理實(shí)際上都是對數(shù)組的處理，很多情況下都要使用數(shù)組copy操作。比如remove：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 把被刪除元素后續(xù)的元素拷貝到被刪元素開始的位置上
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 把最后一個元素置null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
這個方法把index后的數(shù)據(jù)覆蓋index-1開始的數(shù)據(jù)，最后把最后的無效值置null（方便垃圾回收）；
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;
}
// fastremove 沒有rangeCheck(index)的remove
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
}
對象的remove沒有什么高級的做法，也只是遍歷找相等的對象，找到index去remove（index）；
4.4 clear（）
遍歷數(shù)組，置null；
4.5 遍歷
定義一個list：
List<Integer> list = new ArrayList<Integer>() {
private static final long serialVersionUID = 1L;
{
add(0);
add(1);
add(2);
add(3);
add(4);
add(5);
}
};
4.5.1 for循環(huán)
for (Integer i : list) {
System.out.println(i);
}
for (int i = 0; i < list.size();) {
System.out.println(list.get(i++));
}
4.5.2 forEach循環(huán)lambda
list.forEach(i -> {
System.out.println(i);
});
4.5.3 迭代器
// listIterator可以指定迭代開始的游標(biāo)位置，且支持正向和反向地迭代集合
ListIterator<Integer> listitera = list.listIterator(list.size());
while (listitera.hasPrevious()) {
System.out.print(listitera.previous());
}
System.out.println();
while (listitera.hasNext()) {
System.out.print(listitera.next());
}
System.out.println();
// 普通迭代器
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
System.out.print(iter.next());
}
System.out.println();
5 ConcurrentModificationException
ArrayList實(shí)際上并不是線程安全的集合容器，ConcurrentModificationException這個并發(fā)修改異常只能檢測到并發(fā)的修改并快速失?。╢ail-fast)來提醒開發(fā)者。
for (Integer i : list) {
System.out.print(i);
list.remove(i);
}
這種情況下就會拋出ConcurrentModificationException。
上述的增強(qiáng)版for循環(huán)語法糖實(shí)際上內(nèi)部使用的其實(shí)是迭代器來遍歷元素的。在內(nèi)部迭代時相當(dāng)于：
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
Integer e = iter.next();
System.out.print(e);
list.remove(e);
}
原因是什么呢？看一下迭代器的next()（list的remove(e)的源碼前面已有）：
// ArrayList$Itr.next()
public E next() {
// 有一個檢測并發(fā)修改的方法
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
這里的異常就是從checkForComodification()拋出的，查看方法發(fā)現(xiàn)拋出原因很簡單：modCount != expectedModCount,modCount和expectedModCount究竟在哪邊使用了呢？
modCount是list用來計數(shù)在list上修改操作的，add，remove都會modCount++，而expectedModCount則是在取得迭代器的時候拷貝list的Modcount值，在迭代過程中，expectedModCount不會改變，用來檢測在迭代過程中l(wèi)ist的修改，一旦檢測到修改，就拋出異常，即fail-fast機(jī)制。
5.1 避開ConcurrentModificationException
如何解決此異常，在并發(fā)環(huán)境下，對迭代器加鎖同步，非并發(fā)情況下，使用迭代器內(nèi)部方法安全remove對象：
@Test
public void testArrayListConcurrentModify1() {
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
Integer e = iter.next();
System.out.print(e);
if (e == 0)
iter.remove();
}
System.out.println(list);
}
可以正常完成。
Iter內(nèi)部的remove方法：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
沒有操作modCount，所以不會拋出異常。
6. subList
ArrayList內(nèi)部定義了一個內(nèi)部類SubList（非靜態(tài)私有類），用于返回ArrayList的子視圖，因?yàn)橹皇翘峁┮粋€視圖，所以對視圖的修改會直接反映到原list之上。
list獲取視圖的方法是public List<E> subList(int fromIndex, int toIndex)。
需要注意的是，在對視圖迭代操作的時候，原list的修改也會導(dǎo)致迭代器拋出ConcurrentModificationException;有趣的是SubList類中獲取的迭代器對象，是一個匿名內(nèi)部類對象，在SubList#listIterator()方法中返回。
7. 性能與注意點(diǎn)
- 初始化ArrayList時，如果能夠判斷數(shù)據(jù)量，就在創(chuàng)建list對象同時設(shè)置容量值，避免數(shù)組頻繁擴(kuò)容的數(shù)組拷貝帶來大量的性能開銷。
- list不適合在列表中間插入或刪除操作，會造成數(shù)組大塊的移動，如果數(shù)據(jù)量很大，會造成嚴(yán)重的性能損失。需要頻繁在中間插入刪除，考慮使用鏈表數(shù)據(jù)結(jié)構(gòu)LinkedList。
- 使用for循環(huán)遍歷元素時，不要增刪元素，需要增刪通過迭代器操作
8. 并發(fā)場景下的list
ArrayList不是并發(fā)安全的類，如果需要在多線程環(huán)境下使用此類，需要對數(shù)據(jù)進(jìn)行明確的加鎖來同步數(shù)據(jù)訪問。
對于并發(fā)場景，JDK有一個原始的線性列表類Vector，它和ArrayList相似，區(qū)別是它的內(nèi)部方法都是同步方法；
另外，JDK提供了Collections工具類的同步包裝器，如synchronizedList（）來包裝一個list，使其成為同步list，原理十分的簡單，是在內(nèi)部創(chuàng)建一個Object的mutex對象，作為鎖對象對list的操作進(jìn)行synchronized(mutex){}加鎖操作。
處理同步包裝器，JDK還提供了適用于并發(fā)的list類：CopyOnwriteArrayList。CopyOnWriteArrayList是java.util.concurrent包中的一個List的實(shí)現(xiàn)類。CopyOnWrite的意思是在寫時拷貝，也就是如果需要對CopyOnWriteArrayList的內(nèi)容進(jìn)行改變，首先會拷貝一份新的List并且在新的List上進(jìn)行修改，最后將原List的引用指向新的List。具體內(nèi)容在并發(fā)部分再看。
9. 排序
9.1 List的排序
- JDK提供的選擇
在Java8中，List接口提供了default方法sort():
default void sort(Comparator<? super E> c) {
Collections.sort(this, c);
}
但是ArrayList重寫了sort方法：
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
注意sort方法修改了modeCount，要注意ConcurrentModificationException
使用的是集合工具類Collations的sort靜態(tài)方法：
public static <T> void sort(List<T> list, Comparator<? super T> c) {
Object[] a = list.toArray();
// 內(nèi)部調(diào)用Arrays的排序方法
Arrays.sort(a, (Comparator)c);
ListIterator<T> i = list.listIterator();
// 排序后數(shù)據(jù)復(fù)制
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}
從源碼角度看，本質(zhì)上調(diào)用的都是Arrays.sort（）方法。
- 使用
@Test
public void sortList() {
List<Integer> l = new ArrayList<Integer>() {
private static final long serialVersionUID = 1L;
{
add(10);
add(1);
add(3);
add(100);
add(19);
}
};
/*
* java 8 list.sort()
*/
// 默認(rèn)升序
l.sort(null);
// 升序 lambda
l.sort((a, b) -> {
return a - b;
});
// 降序 lambda
l.sort((a, b) -> {
return b - a;
});
/*
* Collections.sort()
*/
// 默認(rèn)升序排列
Collections.sort(l);
// 自定義Comparator，降序排序
Collections.sort(l, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
// lambda 風(fēng)格
Collections.sort(l, (o1, o2) -> {
return o2 - o1;
});
}
9.2 Comparator和Comparable
Comparable是排序接口。若一個類實(shí)現(xiàn)了Comparable接口，就意味著該類支持排序。實(shí)現(xiàn)了Comparable接口的類的對象的列表或數(shù)組可以通過Collections.sort或Arrays.sort進(jìn)行自動排序。
Comparator是一個比較器，通過指定比較器可以為集合創(chuàng)建比較的規(guī)則，它通常作為一個外部的比較器來干涉集合的排序規(guī)則。通常它用來修改Comparable類的內(nèi)部排序規(guī)則，或是對一個未實(shí)現(xiàn)Comparable接口的類定義排序規(guī)則。
簡單來說，Comparable類似于一個標(biāo)記接口，實(shí)現(xiàn)此接口說明此類支持默認(rèn)的排序功能，排序規(guī)則根據(jù)實(shí)現(xiàn)的接口方法compareTo來確定，作為一個內(nèi)部的比較器；而Comparator更加的通用，作為一個外部的比較器去干涉其他可排序和不可排序的類的順序。
- 實(shí)現(xiàn)Comparable接口
import java.util.Arrays;
public class Person implements Comparable<Person> {
private int age;
public Person(int age) {
this.age = age;
}
@Override
public int compareTo(Person o) {
return this.age - o.getAge();
}
public int getAge() {
return age;
}
public static void main(String[] args) {
Person[] ps = { new Person(30), new Person(10), new Person(20) };
Arrays.sort(ps);
for (Person i : ps) {
System.out.print(i.getAge() + " ");
}
// 這邊使用了Comparator來修改排序規(guī)則
Arrays.sort(ps, (a, b) -> {
return b.getAge() - a.getAge();
});
for (Person i : ps) {
System.out.print(i.getAge() + " ");
}
}
}
- 不實(shí)現(xiàn)Comparable接口的排序支持
class People {
private int age;
public People(int age) {
this.age = age;
}
public int getAge() {
return age;
}
public static void main(String[] args) {
People[] pa = { new People(3), new People(1), new People(5) };
// Arrays.sort(pa); // 拋異常
Arrays.sort(pa, (a, b) -> {
return a.getAge() - b.getAge();
});
for (People i : pa) {
System.out.print(i.getAge() + " "); // 1,3,5
}
}
}
可以發(fā)現(xiàn)沒有實(shí)現(xiàn)Comparable接口的People類，也可以通過指定Comparator來實(shí)現(xiàn)排序，如果沒有Comparator則會拋出異常。
兩種方法各有優(yōu)劣， 用Comparable 簡單， 只要實(shí)現(xiàn)Comparable 接口的對象直接就成為一個可以比較的對象（擁有默認(rèn)的比較規(guī)則）。
用Comparator 的好處是另外實(shí)現(xiàn)一個比較器，來運(yùn)行時創(chuàng)建比較規(guī)則，無論目標(biāo)類有沒有實(shí)現(xiàn)Comparable接口。
9.3 排序算法
9.3.1 基礎(chǔ)排序算法
| 算法 | 時間復(fù)雜度 |
|---|---|
| 冒泡排序 | O(n2) |
| 選擇排序 | O(n2) |
| 插入排序 | O(n2) |
| 希爾排序 | O(n1.5) |
| 快速排序 | O(N*logN) |
| 歸并排序 | O(N*logN) |
| 堆排序 | O(N*logN) |
| 基數(shù)排序 | O(d(n+r)) |
9.3.2 Arrays.sort()
從前文的sort的源碼可以發(fā)現(xiàn)，list的排序最后調(diào)用的方法是Arrays.sort（）方法，查看JavaDoc文檔，ArrayList采用的排序算法是TimSort：
/*
*
* <p>The implementation was adapted from Tim Peters's list sort for Python
* (<a >
* TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
* Sorting and Information Theoretic Complexity", in Proceedings of the
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
* January 1993.
*
*/
TimSort算法是一種起源于歸并排序和插入排序的混合排序算法。
排序算法另外整理。
參考資料
[1] Java中Comparable和Comparator區(qū)別小結(jié)
[2] 阿里巴巴Java開發(fā)手冊
[3] 排序算法總結(jié)
