ArrayList源碼解析（中）

2019-11-10 20:24:41

字體：大中小

來源：轉載

供稿：網友

判斷元素位置

這些函數都相對簡單。因為存儲的元素可能為null，所以判斷的時候多了一次。

public int size() { return size;}public boolean isEmpty() { return size == 0;}public boolean contains(Object o) { return indexOf(o) >= 0;}public int indexOf(Object o) { 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;}public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1;}

數組轉化

toArray()重載了兩個方法，其中一個返回Object[]，另外一個返回指定類型的數組。對于有參的方法的調用建議：傳入一個空的對象，如 new Integer[]{} 作為參數。關于ClassCastException異常：經常會需要將ArrayList里的內容轉化為特定類型的數組，但是如果使用無參的toArray()進行強制轉換，就會出現ClassCastException異常。此時需要使用第二個有參的方法。例如類似于： (Integer[]) ArrayList某個實例.toArray(new Integer[]{})。在我們使用 T[] toArray(T[] a) 的時候還需要再一次進行顯式的轉化，這點有點不懂。因為這個函數內部已經轉化了，但是我們還需要 (Integer[]) ArrayList某個實例.toArray(new Integer[]{}) 這么寫，而不是 ArrayList某個實例.toArray(new Integer[]{}) 這么寫？依舊是有參的那個函數，如果傳入的參數的長度大于size，得到的結果會變得沒有使用意義，正如下面代碼注釋里演示的一樣。public Object clone() { try { @Sup增刪改查// Positional access Operations@SuppressWarnings("unchecked")E elementData(int index) { return (E) elementData[index];}public E get(int index) { rangeCheck(index); return elementData(index);}public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;}add操作時怎么擴充容量？調用ensureCapacityInternal(size + 1) 方法，如果 size+1 < elementData.length，則表示容量充足，不需要擴充；如果反之，那么容量擴充到原來的elementData.length 的1.5倍。在進行add操作的時候，都會嘗試對elementData擴充容量(ensureCapacityInternal()方法)，這里有個提升效率的技巧，詳見ArrayList源碼解析（上）的 “關于擴展容量的相關操作” 段落。/*** 每次進行增加操作的時候，都會嘗試擴充elementData的容量*/public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true;}public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++;}public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0;}public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0;}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;}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;}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}public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0;}protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize;}private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size;}public boolean removeAll(Collection<?> c) { return batchRemove(c, false);}public boolean retainAll(Collection<?> c) { return batchRemove(c, true);}

關于batchRemove()方法 1. 批量刪除的方法，具體是對集合c和elementData的交集處理，這里詳細說明一下。

假如集合c和elementData的交集是U，那么，如果complement是true，elementData最終會只存儲U；如果complement是false，elementData最終刪除U。

2. 在對elementData的元素進行篩選的時候，這里使用了r、w兩個游標，從而避免從新開辟一個新的數組進行存儲。這種方法也是比較常見的一種算法題。

private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { // 在原有數組上進行篩選的方法，而不是另外開辟一個新的數組 for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified;}

上一篇：Duilib中帶有權重的靈活控件排列實現（一）

下一篇：搜索代碼所使用過的boost庫函數等關鍵字