Android開發資料結構與演算法——ArrayList原始碼講解

語言: CN / TW / HK
時間 2022-10-31 06:15:07

theme: smartblue

簡介

ArrayList是List介面的一個實現類，它是一個集合容器，我們通常會通過指定泛型來儲存同一類資料，ArrayList預設容器大小為10，自身可以自動擴容，當容量不足時，擴大為原來的1.5倍，和上篇文章的Vector的最大區別應該就是執行緒安全了，ArrayList不能保證執行緒安全，但我們也可以通過其他方式來實現執行緒安全。

ArrayList原始碼講解

開頭部分程式碼

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { @java.io.Serial //序列化uid private static final long serialVersionUID = 8683452581122892189L; //預設初始容量 private static final int DEFAULT_CAPACITY = 10; //一個空物件 private static final Object[] EMPTY_ELEMENTDATA = {}; //一個空物件，如果使用預設建構函式建立，則預設物件內容預設是該值 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //當前資料物件存放地方，當前物件不參與序列化 transient Object[] elementData; // non-private to simplify nested class access //當前陣列長度 private int size;　　//其他程式碼}

這部分可做出有關ArrayList的相關結構，如下圖所示

初始化

``` 　　public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity];　　　　 } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        elementData = EMPTY_ELEMENTDATA;
    }
}　　//此處為copyOf執行程式碼　　public static <T> T[] copyOf(T[] original, int newLength) {    return (T[]) copyOf(original, newLength, original.getClass());　　}　　public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {    @SuppressWarnings("unchecked")    T[] copy = ((Object)newType == (Object)Object[].class)        ? (T[]) new Object[newLength]        : (T[]) Array.newInstance(newType.getComponentType(), newLength);    System.arraycopy(original, 0, copy, 0,                     Math.min(original.length, newLength));    return copy;　　}

```

以上程式碼為ArrayList的初始化，分為三種方式：

1.為給定容量的初始化，傳入引數為陣列的初始化長度，當該引數大於等於0時，進行初始化，當該引數小於0時，丟擲異常

2.過於簡單

3.首先通過c.toArray()得到了集合c對應的資料陣列，如果c也是ArrayList，直接將c.toArray()賦給elementData，而關於toArray的關鍵程式碼如上程式碼中關於copyOf的部分所示，從該段程式碼中可知此處的Arrays.copyOf呼叫的是三引數版本的函式。這個三引數的copyOf函式比較複雜，作用就是返回一個指定的newType型別的陣列，這個陣列的長度是newLength，值從original拷貝而來。拷貝的功能由System.arraycopy( )完成：如果newLength大於原陣列的長度，多出來的元素初始化為null；如果小於原陣列長度，將會進行截斷操作。在這裡，兩參版本呼叫三參版本的三個引數為original, newLength, original.getClass()，故得到的陣列元素型別和原陣列型別一致，長度為newLength，資料由原陣列複製而來。

總之，ArrayList的無參版toArray( )返回了一個和elemantData一模一樣的拷貝陣列。所以判斷c也是ArrayList物件時，直接令elemantData 為c.toArray( )了。否則，會執行elementData = Arrays.copyOf(a, size, Object[].class)。經過上面的分析，三參的copyOf( )是返回一個數據內容和a一模一樣的陣列，但是陣列型別轉為Object[ ]型別。之所以有這條語句，猜想可能是某些集合的toArray( )方法，返回的陣列不是Object[ ]型別，比方說用一個類繼承ArrayList，並且重寫toArray( )方法，讓它返回一些別的型別。

擴容

``` public void ensureCapacity(int minCapacity) { if (minCapacity > elementData.length && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA && minCapacity <= DEFAULT_CAPACITY)) { modCount++; grow(minCapacity); } } 　　//核心部分 private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, / minimum growth / oldCapacity >> 1 / preferred growth /); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }

private Object[] grow() {
    return grow(size + 1);
}

//newLength部分 public static int newLength(int oldLength, int minGrowth, int prefGrowth) {

    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        // put code cold in a separate method
        return hugeLength(oldLength, minGrowth);
    }
}

private static int hugeLength(int oldLength, int minGrowth) {
    int minLength = oldLength + minGrowth;
    if (minLength < 0) { // overflow
        throw new OutOfMemoryError(
            "Required array length " + oldLength + " + " + minGrowth + " is too large");
    } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
        return SOFT_MAX_ARRAY_LENGTH;
    } else {
        return minLength;
    }
}　　 public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

```

關於擴容部分，private Object[] grow(int minCapacity)為核心部分，故我們先看這部分，if(oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)部分說明當該陣列不是還未初始化的陣列時，用newLength以及位運算來進行相應的擴容，而newLength相應的程式碼已經貼在了上面，讓我們來進行具體分析：此處的minGrowth在grow部分為“minCapacity - oldCapacity”，即滿足我們需要的容量，此處的prefGrowth在grow部分為“oldCapacity >> 1”，即原來容量的一半，當沒有溢位時，擴容時所擴的容量就是這兩者中最大的那個，而當溢位時，呼叫hugeLength()來滿足minGrowth，如果還時溢位則最多隻能給到 Integer.MAX_VALUE - 8** 這個量。

那麼當計算好長度之後，return elementData = Arrays.copyOf(elementData, newCapacity)，即得到一個長度改變，元素型別和原陣列相同的新陣列。而當該陣列不滿足oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA這個條件時，進行陣列的初始化。

增加元素

一個元素

``` 　　//在尾部新增一個元素　　private void add(E e, Object[] elementData, int s) { if (s == elementData.length)　　//此處s為size的意思 elementData = grow(); elementData[s] = e; size = s + 1; }

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}　　//在指定位置新增元素　　public void add(int index, E element) {    rangeCheckForAdd(index);    modCount++;    final int s;    Object[] elementData;    if ((s = size) == (elementData = this.elementData).length)        elementData = grow();    System.arraycopy(elementData, index,                     elementData, index + 1,                     s - index);    elementData[index] = element;    size = s + 1;　　}　　private void rangeCheckForAdd(int index) {    if (index > size || index < 0)        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));　　}

```

此處分為兩個部分，一是向尾部新增一個元素的add()，如上面所示，當size與elementData.length相等時，說明陣列中無多餘空間進行新增，故進行擴容操作。將你要新增的值放入elementData[s]即陣列的尾部，然後將size加一，這裡的modCount是用來計算ArrayList中的結構性變化次數。

二是在指定位置新增元素的add()，如上面所示，首先對你想要新增的元素的位置進行判定

一堆元素

``` public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); modCount++; int numNew = a.length; if (numNew == 0) return false; Object[] elementData; final int s; //elementData剩餘容量不足則進行擴容 if (numNew > (elementData = this.elementData).length - (s = size)) elementData = grow(s + numNew); //上文有提到的關於arraycopy的程式碼，此處為從陣列尾部新增元素 System.arraycopy(a, 0, elementData, s, numNew); size = s + numNew; return true; }

public boolean addAll(int index, Collection<? extends E> c) {
    //上文提到的判定語句
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    modCount++;
    //要新增進來的元素的數量
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    //計算要將多少元素向後移動
    int numMoved = s - index;
    if (numMoved > 0)
    //要在index位置，新增numNew個元素，所以從index位置開始，往後挪numNew位，一共有numMoved個元素需要挪動
        System.arraycopy(elementData, index,
                elementData, index + numNew,
                numMoved);
    //空出來的位置即為要新增的元素的位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size = s + numNew;
    return true;
}

```

關於新增一堆元素時的程式碼與之前的程式碼較為相似，故此處直接在程式碼中註釋標出，應該很好理解。

刪除元素

一個元素

``` public E remove(int index) { Objects.checkIndex(index, size); final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;

} public staticint checkIndex(int index, int length) { return Preconditions.checkIndex(index, length, null);} private void fastRemove(Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1) > i) System.arraycopy(es, i + 1, es, i, newSize - i); es[size = newSize] = null; }//刪除指定元素方法 public boolean remove(Object o) { final Object[] es = elementData; final int size = this.size; int i = 0; // 正序找對應元素下標 found: { if (o == null) { for (; i < size; i++) if (es[i] == null) break found; } else { for (; i < size; i++) if (o.equals(es[i])) break found; } return false; } // 找到了，呼叫fastRemove，進行刪除 fastRemove(es, i); return true;}

```

此處的刪除是按照下標刪，首先檢查index是否合法，接著取到oldValue值也就是要刪的元素值，然後呼叫fastRemove( )函式。在fastRemove裡，首先自增modCount，再判斷要刪的元素是不是elemantData的第size個元素（也就是實際上的最後一個元素），如果是，不需要挪動元素操作，直接賦值為null即可，否則，還需要將刪除位置之後的元素都往前挪一位。

當然也有個刪除指定元素的方法，具體如上面public boolean remove(Object o)所示。

一堆元素

``` //刪除集合c中的所有元素public boolean removeAll(Collection<?> c) { return batchRemove(c, false, 0, size); }//保留集合c中的所有元素 public boolean retainAll(Collection<?> c) { return batchRemove(c, true, 0, size); }//核心程式碼 boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {　　　　　//判斷集合c是否為空 Objects.requireNonNull(c); final Object[] es = elementData; int r; // Optimize for initial run of survivors for (r = from;; r++) { if (r == end) return false; if (c.contains(es[r]) != complement) break; }　　　　　//w用於寫入保留的元素 int w = r++; try { for (Object e; r < end; r++) if (c.contains(e = es[r]) == complement) es[w++] = e;　　//當這個元素可以保留時，將其賦給es[] } catch (Throwable ex) { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. System.arraycopy(es, r, es, w, end - r); w += end - r; throw ex; } finally {　　　　　　　//相關善後工作　　 modCount += end - w; shiftTailOverGap(es, w, end); } return true; } private void shiftTailOverGap(Object[] es, int lo, int hi) {　　　　//善後工作相關程式碼 System.arraycopy(es, hi, es, lo, size - hi); 　　　// 從索引hi開始，有size-hi個元素需要往左挪，這些元素依次挪到lo以及lo之後的位置 // 它們都向左挪了hi-lo個單位 　　// 挪動之後，原先的索引size-1的元素，對應的是size-1-(hi-lo)，這個索引之後的元素都賦值為null for (int to = size, i = (size -= hi - lo); i < to; i++) es[i] = null;}

```

此處的關於多個元素的操作分為刪除多個元素和保留多個元素，而這兩個操作均需要呼叫 “batchRemove“ ，故進行關於其的具體分析。

“batchRemove“ 首先進行了變數”r“的宣告，接著是一段for迴圈，而不管是“removeAll”還是“retainAll”都是from = 0 ，end = size，即從頭到尾用r作為索引遍歷陣列，當c.contains(es[r]) != complement時break出去。對於“removeAll”，其complement為false，故當c.contains(es[r])為true的時候退出迴圈，即c中包含es[r]，即找到了要刪除的元素，此時的r為第一個要刪除的元素的索引。以此類推，對於“retainAll”，r為要保留的第一個元素的索引。關於後面w的部分，w是第一個要刪的元素索引，找到要保留的元素，則把索引w的元素賦值為此元素，再自增w。這樣子r一遍遍歷完成後，要保留的元素也都向前移動好了。最後再進行善後工作，具體程式碼如上所示，詳細過程已做註釋。

修改元素

public E set(int index, E element) { Objects.checkIndex(index, size); E oldValue = elementData(index); elementData[index] = element; return oldValue; } public static int checkIndex(int index, int length) { return Preconditions.checkIndex(index, length, null); } public static <X extends RuntimeException> int checkIndex(int index, int length, BiFunction<String, List<Number>, X> oobef) { if (index < 0 || index >= length) throw outOfBoundsCheckIndex(oobef, index, length); return index; }

修改元素部分也與之前大同小異，首先對index是否合法進行判斷，成功後再對這個元素的值進行修改，並返回舊值

查詢元素

``` 　　public int indexOf(Object o) { return indexOfRange(o, 0, size); }

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

```

關於此處，首先是indexOf函式，就是根據元素找索引，呼叫”indexOfRange“，從左往右找，找到第一個索引就返回；在ArrayList中還有個lastIndexOf，與前面提到的查詢正好相反，為從右往左找。

還有一些其他較為簡單的函式，這裡就不一一列出了，下一篇試著分析下迭代器。格式沒怎麼調。

以上就是Android開發中的部分技術點，屬於資料結構與演算法這塊。Android開發需要進階的東西有很多，我們該如何讓進階自己必須瞭解自己技術層在那個位置；Android開發進階的技術點總結如下圖：

總結

ArrayList總結

ArrayList的優點

  • ArrayList底層以陣列實現，是一種隨機訪問模式，再加上它實現了
  • RandomAccess介面，因此查詢也就是get的時候非常快。
  • ArrayList在順序新增一個元素的時候非常方便，只是往數組裡面添加了一個元素而已。
  • 根據下標遍歷元素，效率高
  • 根據下標訪問元素，效率高
  • 可以自動擴容，預設為每次擴容為原來的1.5倍

ArrayList的缺點

  • 插入和刪除元素的效率不高
  • 根據元素的值查詢元素的下標需要遍歷整個元素陣列，效率不高
  • 執行緒不安全
「」
「」