計算機程序的思維邏輯 (38)，思維38

計算機程序的思維邏輯 (38)，思維38

從本節開始，我們探討Java中的容器類，所謂容器，顧名思義就是容納其他數據的，計算機課程中有一門課叫數據結構，可以粗略對應於Java中的容器類，我們不會介紹所有數據結構的內容，但會介紹Java中的主要實現，並分析其基本原理和主要實現代碼。

前幾節在介紹泛型的時候，我們自己實現了一個簡單的動態數組容器類DynaArray，本節，我們介紹Java中真正的動態數組容器類ArrayList。

我們先來看它的基本用法。

基本用法

新建ArrayList

ArrayList是一個泛型容器，新建ArrayList需要實例化泛型參數，比如：

ArrayList<Integer> intList = new ArrayList<Integer>();
ArrayList<String> strList = new ArrayList<String>();

添加元素

add方法添加元素到末尾

ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(123);
intList.add(456);
ArrayList<String> strList = new ArrayList<String>();
strList.add("老馬");
strList.add("編程");

長度方法

判斷是否為空

public boolean isEmpty()

獲取長度

public int size()

訪問指定位置的元素

public E get(int index)

如：

ArrayList<String> strList = new ArrayList<String>();
strList.add("老馬");
strList.add("編程");
for(int i=0; i<strList.size(); i++){
    System.out.println(strList.get(i));
}

查找元素

public int indexOf(Object o)

如果找到，返回索引位置，否則返回-1。

從後往前找

public int lastIndexOf(Object o)

是否包含指定元素 

public boolean contains(Object o)

相同的依據是equals方法返回true。如果傳入的元素為null，則找null的元素。

刪除元素

刪除指定位置的元素

public E remove(int index)

返回值為被刪對象。

刪除指定對象

public boolean remove(Object o)

與indexOf一樣，比較的依據的是equals方法，如果o為null，則刪除值為null的元素。另外，remove只刪除第一個相同的對象，也就是說，即使ArrayList中有多個與o相同的元素，也只會刪除第一個。返回值為boolean類型，表示是否刪除了元素。

刪除所有元素

public void clear() 

插入元素

在指定位置插入元素

public void add(int index, E element)

index為0表示插入最前面，index為ArrayList的長度表示插到最後面。

修改元素

修改指定位置的元素內容

public E set(int index, E element) 

基本原理

內部組成

可以看出，ArrayList的基本用法是比較簡單的，它的基本原理也是比較簡單的，原理與我們在前面幾節介紹的DynaArray類似，內部有一個數組elementData，一般會有一些預留的空間，有一個整數size記錄實際的元素個數，如下所示：

private transient Object[] elementData;
private int size;

我們暫時可以忽略transient這個關鍵字。各種public方法內部操作的基本都是這個數組和這個整數，elementData會隨著實際元素個數的增多而重新分配，而size則始終記錄實際的元素個數。

Add方法

雖然基本思路是簡單的，但內部代碼有一些比較晦澀，我們來看下add方法的代碼：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

它首先調用ensureCapacityInternal確保數組容量是夠的，ensureCapacityInternal的代碼是：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

它先判斷數組是不是空的，如果是空的，則首次至少要分配的大小為DEFAULT_CAPACITY，DEFAULT_CAPACITY的值為10，接下來調用ensureExplicitCapacity，代碼為：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

modCount++是什麼意思呢？modCount表示內部的修改次數，modCount++當然就是增加修改次數，為什麼要記錄修改次數呢？我們待會解釋。

如果需要的長度大於當前數組的長度，則調用grow方法。這段代碼前面有個注釋：overflow-conscious code，翻譯一下，大意就是代碼考慮了溢出這種情況，溢出是什麼意思呢？我們解釋下，假設a,b都是int，下面兩行代碼是不一樣的：

1 if(a>b)
2 if(a-b>0)

為什麼呢？考慮a=Integer.MAX_VALUE, b=Integer.MIN_VALUE：

a>b為true

但由於溢出，a-b的結果為-1

反之，再考慮a=Integer.MIN_VALUE, b=Integer.MAX_VALUE:

a>b為false

但由於溢出，a-b的結果為1。

不過，在a, b都為正數且數值沒有那麼大的情況下，一般也沒有溢出問題，為便於理解，在後續的分析中，我們將忽略溢出問題。

接下來，看grow方法：

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);
}

排除邊緣情況，長度增長的主要代碼為：

int newCapacity = oldCapacity + (oldCapacity >> 1);

右移一位相當於除2，所以，newCapacity相當於oldCapacity的1.5倍。

Remove方法

我們再來看Remove方法的代碼：

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;
}

它也增加了modCount，然後計算要移動的元素個數，從index往後的元素都往前移動一位，實際調用System.arraycopy方法移動元素。elementData[--size] = null;這行代碼將size減一，同時將最後一個位置設為null，設為null後就不再引用原來對象，如果原來對象也不再被其他對象引用，就可以被垃圾回收。

基本原理小結

其他方法大多是比較簡單的，我們就不贅述了。總體而言，內部操作要考慮各種情況，代碼有一些晦澀復雜，但接口一般都是簡單直接的，這就是使用容器類的好處了，這也是計算機程序中的基本思維方式，封裝復雜操作，提供簡單接口。

迭代

foreach用法

理解了ArrayList的基本用法和原理，接下來，我們來看一個常見的操作 - 迭代，比如說，循環打印ArrayList中的每個元素，ArrayList支持foreach語法，比如：

ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(123);
intList.add(456);
intList.add(789);
for(Integer a : intList){
    System.out.println(a);
}

當然，這種循環也可以使用如下代碼實現：

for(int i=0; i<intList.size(); i++){
    System.out.println(intList.get(i));
}

不過，foreach看上去更為簡潔，而且，它適用於各種容器，更為通用。

這種foreach語法背後是怎麼實現的呢？其實，編譯器會將它轉換為類似如下代碼：

Iterator<Integer> it = intList.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

接來下，我們解釋一下其中的代碼。

迭代器接口

ArrayList實現了Iterable接口，Iterable表示可迭代，它的定義為：

public interface Iterable<T> {
    Iterator<T> iterator();
}

定義很簡單，就是要求實現iterator方法。iterator方法的聲明為：

public Iterator<E> iterator()

它返回一個實現了Iterator接口的對象，Iterator接口的定義為：

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

hasNext()判斷是否還有元素未訪問，next()返回下一個元素，remove()刪除最後返回的元素，只讀訪問的基本模式就類似於：

Iterator<Integer> it = intList.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

我們待會再看迭代中間要刪除元素的情況。

只要對象實現了Iterable接口，就可以使用foreach語法，編譯器會轉換為調用Iterable和Iterator接口的方法。

初次見到Iterable和Iterator，可能會比較容易混淆，我們再澄清一下：

• Iterable表示對象可以被迭代，它有一個方法iterator()，返回Iterator對象，實際通過Iterator接口的方法進行遍歷。
• 如果對象實現了Iterable，就可以使用foreach語法。
• 類可以不實現Iterable，也可以創建Iterator對象。

ListIterator

除了iterator()，ArrayList還提供了兩個返回Iterator接口的方法：

public ListIterator<E> listIterator()
public ListIterator<E> listIterator(int index)

ListIterator擴展了Iterator接口，增加了一些方法，向前遍歷、添加元素、修改元素、返回索引位置等，添加的方法有：

public interface ListIterator<E> extends Iterator<E> {
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void set(E e);
    void add(E e);
}

listIterator()方法返回的迭代器從0開始，而listIterator(int index)方法返回的迭代器從指定位置index開始，比如，從末尾往前遍歷，代碼為：

public void reverseTraverse(List<Integer> list){
    ListIterator<Integer> it = list.listIterator(list.size());
    while(it.hasPrevious()){
        System.out.println(it.previous());
    }
}

迭代的陷阱

關於迭代器，有一種常見的誤用，就是在迭代的中間調用容器的刪除方法，比如要刪除一個整數ArrayList中所有小於100的數，直覺上，代碼可以這麼寫：

public void remove(ArrayList<Integer> list){
    for(Integer a : list){
        if(a<=100){
            list.remove(a);
        }
    }
}

但，運行時會拋出異常：

java.util.ConcurrentModificationException

發生了並發修改異常，為什麼呢？迭代器內部會維護一些索引位置相關的數據，要求在迭代過程中，容器不能發生結構性變化，否則這些索引位置就失效了。所謂結構性變化就是添加、插入和刪除元素，只是修改元素內容不算結構性變化。

如何避免異常呢？可以使用迭代器的remove方法，如下所示：

public static void remove(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
        if(it.next()<=100){
            it.remove();
        }
    }
}

迭代器如何知道發生了結構性變化，並拋出異常？它自己的remove方法為何又可以使用呢？我們需要看下迭代器的工作原理。

迭代器實現的原理

我們來看下ArrayList中iterator方法的實現，代碼為：

public Iterator<E> iterator() {
    return new Itr();
}

新建了一個Itr對象，Itr是一個成員內部類，實現了Iterator接口，聲明為：

private class Itr implements Iterator<E>

它有三個實例成員變量，為：

int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

cursor表示下一個要返回的元素位置，lastRet表示最後一個返回的索引位置，expectedModCount表示期望的修改次數，初始化為外部類當前的修改次數modCount，回顧一下，成員內部類可以直接訪問外部類的實例變量。

每次發生結構性變化的時候modCount都會增加，而每次迭代器操作的時候都會檢查expectedModCount是否與modCount相同，這樣就能檢測出結構性變化。

我們來具體看下，它是如何實現Iterator接口中的每個方法的，先看hasNext()，代碼為：

public boolean hasNext() {
    return cursor != size;
}

cursor與size比較，比較直接，看next()方法：

public E next() {
    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];
}

首先調用了checkForComodification，它的代碼為：

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

所以，next()前面部分主要就是在檢查是否發生了結構性變化，如果沒有變化，就更新cursor和lastRet的值，以保持其語義，然後返回對應的元素。

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();
    }
}

它調用了ArrayList的remove方法，但同時更新了cursor, lastRet和expectedModCount的值，所以它可以正確刪除。

不過，需要注意的是，調用remove方法前必須先調用next，比如，通過迭代器刪除所有元素，直覺上，可以這麼寫：

public static void removeAll(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
        it.remove();    
    }
}

實際運行，會拋出異常：

java.lang.IllegalStateException

正確寫法是：

public static void removeAll(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
        it.next();
        it.remove();
    }
}

當然，如果只是要刪除所有元素，ArrayList有現成的方法clear()。

listIterator()的實現使用了另一個內部類ListItr，它繼承自Itr，基本思路類似，我們就不贅述了。

迭代器的好處

為什麼要通過迭代器這種方式訪問元素呢？直接使用size()/get(index)語法不也可以嗎？在一些場景下，確實沒有什麼差別，兩者都可以。不過，foreach語法更為簡潔一些，更重要的是，迭代器語法更為通用，它適用於各種容器類。

此外，迭代器表示的是一種關注點分離的思想，將數據的實際組織方式與數據的迭代遍歷相分離，是一種常見的設計模式。需要訪問容器元素的代碼只需要一個Iterator接口的引用，不需要關注數據的實際組織方式，可以使用一致和統一的方式進行訪問。

而提供Iterator接口的代碼了解數據的組織方式，可以提供高效的實現。在ArrayList中, size/get(index)語法與迭代器性能是差不多的，但在後續介紹的其他容器中，則不一定，比如LinkedList，迭代器性能就要高很多。

從封裝的思路上講，迭代器封裝了各種數據組織方式的迭代操作，提供了簡單和一致的接口。

ArrayList實現的接口

Java的各種容器類有一些共性的操作，這些共性以接口的方式體現，我們剛剛介紹的Iterable接口就是，此外，ArrayList還實現了三個主要的接口Collection, List和RandomAccess，我們逐個來看下。

Collection

Collection表示一個數據集合，數據間沒有位置或順序的概念，接口定義為：

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();
}

這些方法中，除了兩個toArray方法和幾個xxxAll()方法外，其他我們已經介紹過了。

這幾個xxxAll()方法的含義基本也是可以顧名思義的，addAll添加，removeAll刪除，containsAll檢查是否包含了參數容器中的所有元素，只有全包含才返回true，retainAll只保留參數容器中的元素，其他元素會進行刪除。

有一個抽象類AbstractCollection對這幾個方法都提供了默認實現，實現的方式就是利用迭代器方法逐個操作，比如說，我們看removeAll方法，代碼為：

public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

代碼比較簡單，就不解釋了。ArrayList繼承了AbstractList，而AbstractList又繼承了AbstractCollection，ArrayList對其中一些方法進行了重寫，以提供更為高效的實現，具體我們就不介紹了。

關於toArray方法，我們待會再介紹。

List

List表示有順序或位置的數據集合，它擴展了Collection，增加的主要方法有：

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);

這些方法都與位置有關，容易理解，就不介紹了。

RandomAccess

RandomAccess的定義為：

public interface RandomAccess {
}

沒有定義任何代碼。這有什麼用呢？這種沒有任何代碼的接口在Java中被稱之為標記接口，用於聲明類的一種屬性。

這裡，實現了RandomAccess接口的類表示可以隨機訪問，可隨機訪問就是具備類似數組那樣的特性，數據在內存是連續存放的，根據索引值就可以直接定位到具體的元素，訪問效率很高。下節我們會介紹LinkedList，它就不能隨機訪問。

有沒有聲明RandomAccess有什麼關系呢？主要用於一些通用的算法代碼中，它可以根據這個聲明而選擇效率更高的實現。比如說，Collections類中有一個方法binarySearch，在List中進行二分查找，它的實現代碼就根據list是否實現了RandomAccess而采用不同的實現機制，如下所示：

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);
}

ArrayList的其他方法

構造方法

ArrayList還有兩個構造方法

public ArrayList(int initialCapacity)
public ArrayList(Collection<? extends E> c)

第一個方法以指定的大小initialCapacity初始化內部的數組大小，代碼為：

this.elementData = new Object[initialCapacity];

在事先知道元素長度的情況下，或者，預先知道長度上限的情況下，使用這個構造方法可以避免重新分配和拷貝數組。

第二個構造方法以一個已有的Collection構建，數據會新拷貝一份。

與數組的相互轉換

ArrayList中有兩個方法可以返回數組

public Object[] toArray()
public <T> T[] toArray(T[] a) 

第一個方法返回是Object數組，代碼為：

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

第二個方法返回對應類型的數組，如果參數數組長度足以容納所有元素，就使用該數組，否則就新建一個數組，比如：

ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(123);
intList.add(456);
intList.add(789);

Integer[] arrA = new Integer[3];
intList.toArray(arrA);
Integer[] arrB = intList.toArray(new Integer[0]);

System.out.println(Arrays.equals(arrA, arrB));

輸出為true，表示兩種方式都是可以的。

Arrays中有一個靜態方法asList可以返回對應的List，如下所示：

Integer[] a = {1,2,3};
List<Integer> list = Arrays.asList(a);

需要注意的是，這個方法返回的List，它的實現類並不是本節介紹的ArrayList，而是Arrays類的一個內部類，在這個內部類的實現中，內部用的的數組就是傳入的數組，沒有拷貝，也不會動態改變大小，所以對數組的修改也會反映到List中，對List調用add/remove方法會拋出異常。

要使用ArrayList完整的方法，應該新建一個ArrayList，如下所示：

List<Integer> list = new ArrayList<Integer>(Arrays.asList(a));

容量大小控制

ArrayList還提供了兩個public方法，可以控制內部使用的數組大小，一個是：

public void ensureCapacity(int minCapacity)

它可以確保數組的大小至少為minCapacity，如果不夠，會進行擴展。如果已經預知ArrayList需要比較大的容量，調用這個方法可以減少ArrayList內部分配和擴展的次數。

另一個方法是：

public void trimToSize()

它會重新分配一個數組，大小剛好為實際內容的長度。調用這個方法可以節省數組占用的空間。

ArrayList特點分析

後續我們會介紹各種容器類和數據組織方式，之所以有各種不同的方式，是因為不同方式有不同特點，而不同特點有不同適用場合。考慮特點時，性能是其中一個很重要的部分，但性能不是一個簡單的高低之分，對於一種數據結構，有的操作性能高，有的操作性能可能就比較低。

作為程序員，就是要理解每種數據結構的特點，根據場合的不同，選擇不同的數據結構。

對於ArrayList，它的特點是：內部采用動態數組實現，這決定了：

• 可以隨機訪問，按照索引位置進行訪問效率很高，用算法描述中的術語，效率是O(1)，簡單說就是可以一步到位。
• 除非數組已排序，否則按照內容查找元素效率比較低，具體是O(N)，N為數組內容長度，也就是說，性能與數組長度成正比。
• 添加元素的效率還可以，重新分配和拷貝數組的開銷被平攤了，具體來說，添加N個元素的效率為O(N)。
• 插入和刪除元素的效率比較低，因為需要移動元素，具體為O(N)。 

小結

本文詳細介紹了ArrayList，ArrayList是日常開發中最常用的類之一。我們介紹了ArrayList的用法、基本實現原理、迭代器及其實現、Collection/List/RandomAccess接口、ArrayList與數組的相互轉換，最後我們分析了ArrayList的特點。

ArrayList的插入和刪除的性能比較低，下一節，我們來看另一個同樣實現了List接口的容器類，LinkedList，它的特點可以說與ArrayList正好相反。

----------------

未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心原創，保留所有版權。