ArrayList源碼解析（中）

2019-11-10 20:04:46

字體：大中小

供稿：網(wǎng)友

判斷元素位置

這些函數(shù)都相對(duì)簡(jiǎn)單。因?yàn)榇鎯?chǔ)的元素可能為null，所以判斷的時(shí)候多了一次。

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

數(shù)組轉(zhuǎn)化

toArray()重載了兩個(gè)方法，其中一個(gè)返回Object[]，另外一個(gè)返回指定類(lèi)型的數(shù)組。對(duì)于有參的方法的調(diào)用建議：傳入一個(gè)空的對(duì)象，如 new Integer[]{} 作為參數(shù)。關(guān)于ClassCastException異常：經(jīng)常會(huì)需要將ArrayList里的內(nèi)容轉(zhuǎn)化為特定類(lèi)型的數(shù)組，但是如果使用無(wú)參的toArray()進(jìn)行強(qiáng)制轉(zhuǎn)換，就會(huì)出現(xiàn)ClassCastException異常。此時(shí)需要使用第二個(gè)有參的方法。例如類(lèi)似于： (Integer[]) ArrayList某個(gè)實(shí)例.toArray(new Integer[]{})。在我們使用 T[] toArray(T[] a) 的時(shí)候還需要再一次進(jìn)行顯式的轉(zhuǎn)化，這點(diǎn)有點(diǎn)不懂。因?yàn)檫@個(gè)函數(shù)內(nèi)部已經(jīng)轉(zhuǎn)化了，但是我們還需要 (Integer[]) ArrayList某個(gè)實(shí)例.toArray(new Integer[]{}) 這么寫(xiě)，而不是 ArrayList某個(gè)實(shí)例.toArray(new Integer[]{}) 這么寫(xiě)？依舊是有參的那個(gè)函數(shù)，如果傳入的參數(shù)的長(zhǎng)度大于size，得到的結(jié)果會(huì)變得沒(méi)有使用意義，正如下面代碼注釋里演示的一樣。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操作時(shí)怎么擴(kuò)充容量？調(diào)用ensureCapacityInternal(size + 1) 方法，如果 size+1 < elementData.length，則表示容量充足，不需要擴(kuò)充；如果反之，那么容量擴(kuò)充到原來(lái)的elementData.length 的1.5倍。在進(jìn)行add操作的時(shí)候，都會(huì)嘗試對(duì)elementData擴(kuò)充容量(ensureCapacityInternal()方法)，這里有個(gè)提升效率的技巧，詳見(jiàn)ArrayList源碼解析（上）的 “關(guān)于擴(kuò)展容量的相關(guān)操作” 段落。/*** 每次進(jìn)行增加操作的時(shí)候，都會(huì)嘗試擴(kuò)充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);}

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

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

2. 在對(duì)elementData的元素進(jìn)行篩選的時(shí)候，這里使用了r、w兩個(gè)游標(biāo)，從而避免從新開(kāi)辟一個(gè)新的數(shù)組進(jìn)行存儲(chǔ)。這種方法也是比較常見(jiàn)的一種算法題。

private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { // 在原有數(shù)組上進(jìn)行篩選的方法，而不是另外開(kāi)辟一個(gè)新的數(shù)組 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;}

上一篇：filter-設(shè)置action編碼

下一篇：筆試面試中涉及位運(yùn)算的題目總結(jié)（一）