讀代碼跟寫代碼一樣重要
List及實(shí)現(xiàn)類關(guān)系
集合類圖.jpg
上述類圖中耻蛇，Collection恶座、List為接口鲤拿；AbstractCollection、AbstractList歼疮、AbstractSequentialList為抽象類杂抽；Vector、ArrayList韩脏、LinkedList為實(shí)現(xiàn)類
類的組織結(jié)構(gòu)與比較
咱們從Collection的方法開始
Collection的方法
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);
default boolean removeIf(Predicate<? super E> filter);//具有默認(rèn)實(shí)現(xiàn),可繼承
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
default Spliterator<E> spliterator();
default Stream<E> stream();
default Stream<E> parallelStream()
上述列舉的方法少了查和改默怨，基本滿足我們的集合操作了，那么AbstractCollection實(shí)現(xiàn)Collection是否只要將其全部實(shí)現(xiàn)就完事了呢
AbstractCollection的方法
public abstract int size();
public abstract Iterator<E> iterator();
boolean isEmpty();
boolean contains(Object o);
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();
String toString();
//不可繼承骤素，只是toArray的輔助方法
private static <T> T[] finishToArray(T[] r, Iterator<?> it);
private static int hugeCapacity(int minCapacity);
從上我們發(fā)現(xiàn)AbstractCollection只新增toString一個(gè)可繼承的方法匙睹，相比較Collection并沒有給出更多的可繼承的方法。沒有hashCode济竹、equals等方法痕檬。
這里我們具體看下AbstractCollection的toArray方法
/*
其中size()和iterator()都是abstract
*/
public Object[] toArray() {
// Estimate size of array; be prepared to see more or fewer elements
Object[] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) // fewer elements than expected
return Arrays.copyOf(r, i);
r[i] = it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
public <T> T[] toArray(T[] a) {
//提供了數(shù)組a，夠大可以直接用作返回的數(shù)組
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array//創(chuàng)建不曉得類型的數(shù)組所用的方法
.newInstance(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { // 返回獲取的r數(shù)組,容量跟a的容量相關(guān)
if (a == r) {//a和r一樣大送浊，直接返回r數(shù)組
r[i] = null; // null-terminate
} else if (a.length < i) {
//a比當(dāng)前獲取的元素小梦谜，返回當(dāng)前獲取的元素,數(shù)組的容量也為當(dāng)前元素集的大小
return Arrays.copyOf(r, i);
} else {
//a比當(dāng)前獲取的元素大，返回當(dāng)前獲取的元素袭景，但是數(shù)組的容量大唁桩，為a的容量
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T)it.next();
}
// more elements than expected
return it.hasNext() ? finishToArray(r, it) : r;
}
//對數(shù)組進(jìn)行擴(kuò)容
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;
while (it.hasNext()) {
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;
// overflow-conscious code
if (newCap - MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
明確toArray的思想，就是將集合轉(zhuǎn)成數(shù)組耸棒，然后看源碼荒澡，AbstractCollection的實(shí)現(xiàn)方式是通過abstract修飾的迭代器來進(jìn)行遍歷，然后將遍歷得到的元素存入數(shù)組与殃，迭代開始之前或者操作過程中单山，集合的元素可能發(fā)生了改變碍现，如果元素變少了，那么就將當(dāng)前迭代獲取的元素返回米奸，數(shù)組容量跟a相關(guān)昼接。如果元素變多了，那么就開辟一個(gè)更大的空間悴晰，然后繼續(xù)遍歷集合元素慢睡，獲取全部元素后返回。數(shù)組容量看上代碼铡溪。
注意：
在使用迭代器遍歷的時(shí)候漂辐，如果不是通過迭代器內(nèi)部提供的增刪改來修改集合，那么就會(huì)拋出異常佃却，在AbatractList中可以看到具體的迭代器實(shí)現(xiàn)
List的方法
//Collection繼承過來的接口方法
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();
default Spliterator<E> spliterator()
//List定義的接口方法
boolean addAll(int index, Collection<? extends E> c);
default void replaceAll(UnaryOperator<E> operator)
default void sort(Comparator<? super 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);
從上面的代碼可以看出者吁，Collection中的方法是不帶順序的窘俺。而List自己的接口方法就看到很多index饲帅，是有序的。
這里咱們看下replaceAll和sort
//UnaryOperator接口繼承Function瘤泪，提供了apply方法灶泵，給傳入的參數(shù)做一層自定義的包裝
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
上面的兩個(gè)方法很簡單，主要是調(diào)用了ListIterator和Arrays的方法來實(shí)現(xiàn)的对途。咱們下面先看下個(gè)ListIterator接口赦邻，Arrays內(nèi)容比較多，下次再看
ListIterator的方法
//繼承自Iterator接口
boolean hasNext();
E next();
void remove();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void set(E e);
void add(E e);
看到上面的代碼实檀，咱們發(fā)現(xiàn)ListIterator是繼承Iterator的，可以進(jìn)向前或者向后迭代。但是為什么還要實(shí)現(xiàn)set和add方法呢
AbstractList的方法
//繼承自AbstractCollection的方法
public boolean add(E e)邑贴；
public void clear()
public Iterator<E> iterator()
public boolean equals(Object o)
public int hashCode()
//List接口中的方法
abstract public E get(int index);
public E set(int index, E element)
public void add(int index, E element)
public E remove(int index)
public int indexOf(Object o)
public int lastIndexOf(Object o)
public boolean addAll(int index, Collection<? extends E> c)
public ListIterator<E> listIterator()
public ListIterator<E> listIterator(final int index)
public List<E> subList(int fromIndex, int toIndex)
//AbstractList內(nèi)部方法
protected void removeRange(int fromIndex, int toIndex)
private void rangeCheckForAdd(int index)
private String outOfBoundsMsg(int index)
從上面代碼可以看出AbstractList實(shí)現(xiàn)了AbstractCollection的add蜂林、clear、iterator须床、equals铐料、hashCode方法，結(jié)合AbstractCollection的實(shí)現(xiàn)的方法豺旬，AbstractCollection只剩size()方法未被實(shí)現(xiàn)钠惩。
我們來看下indexOf、lastIndexOf族阅、listIterator篓跛、subList等方法
public int indexOf(Object o) {
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))//待會(huì)會(huì)看到next是先取值，然后移動(dòng)index,previous也是一樣
return it.previousIndex();
}
return -1;
}
public int lastIndexOf(Object o) {
ListIterator<E> it = listIterator(size());//將index指向末尾
if (o==null) {
while (it.hasPrevious())
if (it.previous()==null)
return it.nextIndex();
} else {
while (it.hasPrevious())
if (o.equals(it.previous()))
return it.nextIndex();
}
return -1;
}
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
indexof(o)和lastIndexOf(o)都很容易理解坦刀，indexof是順序查找是否有相等的元素举塔，然后返回绑警。lastIndexOf是倒敘查找是否有相等的元素，然后返回央渣。
listIterator和subList是對外提供的listItr和SubList對外提供實(shí)例化的方法
下面分別來看下Itr计盒、ListItr、SubList芽丹、RandomAccessSubList
Itr
private class Itr implements Iterator<E> {
/**
* Index of element to be returned by subsequent call to next.
*/
int cursor = 0;
/**
* Index of element returned by most recent call to next or
* previous. Reset to -1 if this element is deleted by a call
* to remove.
*/
int lastRet = -1;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();//查看下標(biāo)是否到達(dá)末尾
}
public E next() {
checkForComodification();//檢查迭代過程中北启，是否不同過本迭代器提供的方法改變了list元素，如果實(shí)例元素發(fā)生變化拔第，則拋出異常咕村。
//檢查方式是通過每次改變元素位置的操作都記錄list的操作次數(shù)到迭代器，操作之前先進(jìn)行是否相等的判斷
try {
int i = cursor;
E next = get(i); //通過list的get(i)獲取元素
lastRet = i; //lastRet記錄本次操作的位置
cursor = i + 1; //移動(dòng)下標(biāo)到下一個(gè)元素
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
//迭代器可以向前或者向后蚊俺，如果向后懈涛，那么下標(biāo)肯定比上一次位置要大，如果向前泳猬，從下面源碼可以看出批钠，下標(biāo)和上一次操作的位置是一樣的，所以不需要移動(dòng)下標(biāo)
if (lastRet < cursor)
cursor--;
lastRet = -1;//不允許繼續(xù)remove或者set
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
從上面的源碼咱們可以看出得封，iterator()方法獲取的迭代器只能使用其內(nèi)部提供的方法來修改元素埋心，不然會(huì)拋出異常
ListItr
//繼承自Itr，實(shí)現(xiàn)ListIterator接口
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;//檢查下標(biāo)是否在首部
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);//獲取上一個(gè)元素
lastRet = cursor = i;//再移動(dòng)下標(biāo)到上一個(gè)元素
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);//remove和set都是相對上次操作過的迭代器元素
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);//在迭代器可見范圍的末尾添加元素
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
ListItr 繼承了Itr實(shí)現(xiàn)了ListIterator接口忙上。提供向前遍歷拷呆，增加了獲取下標(biāo)的方法。
為什么next是先獲取元素疫粥，再移動(dòng)到下一個(gè)位置茬斧，而previous是先移動(dòng)到上一個(gè)位置，再獲取元素呢梗逮？
因?yàn)閏ursor初始值為0项秉，而hasNext和hasPrevious判斷的寫法也限制了元素的順序
SubList
class SubList<E> extends AbstractList<E> {
private final AbstractList<E> l;
private final int offset;
private int size;
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return l.get(index+offset);
}
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
l.add(index+offset, element);
this.modCount = l.modCount;
size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = l.remove(index+offset);
this.modCount = l.modCount;
size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
l.removeRange(fromIndex+offset, toIndex+offset);
this.modCount = l.modCount;
size -= (toIndex-fromIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
l.addAll(offset+index, c);
this.modCount = l.modCount;
size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
public E next() {
if (hasNext())
return i.next();
else
throw new NoSuchElementException();
}
public boolean hasPrevious() {
return previousIndex() >= 0;
}
public E previous() {
if (hasPrevious())
return i.previous();
else
throw new NoSuchElementException();
}
public int nextIndex() {
return i.nextIndex() - offset;
}
public int previousIndex() {
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
SubList.this.modCount = l.modCount;
size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
SubList.this.modCount = l.modCount;
size++;
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkForComodification() {
if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
}
subList是List的一個(gè)子視圖，我們看到SubList(AbstractList<E> list, int fromIndex, int toIndex)構(gòu)造的時(shí)候傳入AbstractList,后續(xù)sublist中的內(nèi)容都是從AbstractList中獲取的库糠。
從checkForComodification函數(shù)看出伙狐，假如宿主AbstractList被修改后，操作sublist中的方法將會(huì)報(bào)ConcurrentModificationException異常
RandomAccessSubList
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}
這個(gè)類和sublist的區(qū)別在于實(shí)現(xiàn)了RandomAccess接口瞬欧，這個(gè)接口是用來標(biāo)識(shí)是否本類可以進(jìn)行快速訪問的贷屎。
從AbstractList的subList方法能夠看到RandomAccess的用法
ArrayList
講到AbstractList時(shí)，大家想是否AbstractList就可以正常使用了呢艘虎。為什么還要往下講唉侄。因?yàn)锳bstractList沒有可以存數(shù)據(jù)的容器。而且其大部分操作都是通過iterator來實(shí)現(xiàn)的野建，而AbstractList中的iterator則是通過為實(shí)現(xiàn)的list中的接口來實(shí)現(xiàn)的属划。下面咱們看下其具體的實(shí)現(xiàn)子類ArrayList
ArrayList的方法
//構(gòu)造
public ArrayList(int initialCapacity)
public ArrayList()
public ArrayList(Collection<? extends E> c)
//abstractCollection方法
public int size()
public boolean isEmpty()
public boolean contains(Object o)
public Object[] toArray()
public <T> T[] toArray(T[] a)
public boolean add(E e)
public boolean remove(Object o)
public void clear()
public boolean addAll(Collection<? extends E> c)
public boolean removeAll(Collection<?> c)
public boolean retainAll(Collection<?> c)
public Iterator<E> iterator()
//abstractList
public int indexOf(Object o)
public int lastIndexOf(Object o)
public E get(int index)
public E set(int index, E element)
public void add(int index, E element)
public E remove(int index)
public boolean addAll(int index, Collection<? extends E> c)
protected void removeRange(int fromIndex, int toIndex)
private String outOfBoundsMsg(int index)
public ListIterator<E> listIterator(int index)
public ListIterator<E> listIterator()
public List<E> subList(int fromIndex, int toIndex)
//Cloneable的方法
public Object clone()
private void fastRemove(int index)
//Serializable的方法
private void writeObject(java.io.ObjectOutputStream s)
private void readObject(java.io.ObjectInputStream s)
//Iterable的方法恬叹，Collection繼承自Iterable
public void forEach(Consumer<? super E> action)
E elementData(int index)
//內(nèi)部方法
private void rangeCheck(int index)
private void rangeCheckForAdd(int index)
private boolean batchRemove(Collection<?> c, boolean complement)
從上面介紹的方法來看，之前在AbstractCollection中實(shí)現(xiàn)的Collection的方法同眯，都被ArrayList給重新實(shí)現(xiàn)了一遍绽昼，而且還實(shí)現(xiàn)了List接口中的方法。此外還實(shí)現(xiàn)了Cloneable须蜗、Serializable等一系列的方法硅确。
下面咱們首先看下AbstractCollection中被重寫的方法，然后對比下為什么要重新
ArrayList重寫的Collection的方法,列舉部分
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);//之前是從迭代器中取值明肮，然后轉(zhuǎn)成數(shù)組菱农，現(xiàn)在拿到就是數(shù)組，直接按大小返回柿估，一次操作不怕中間容器結(jié)構(gòu)發(fā)生改變
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
public boolean add(E e) {//之前只是把a(bǔ)dd轉(zhuǎn)到add(i,e)上循未，并沒有真實(shí)現(xiàn)
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {//null代表的是空值，用==比較是否同一東西
fastRemove(index);//之前是通過iterator中的remove實(shí)現(xiàn)的
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {//比較對象的值是否相等
fastRemove(index);
return true;
}
}
return false;
}
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
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 removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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++)
//根據(jù)complement來決定新新容器elementData保留哪些元素
if (c.contains(elementData[r]) == complement)
//w的值是從0開始秫舌，所以要直接覆蓋elementData當(dāng)為新容器使用
//在用下標(biāo)遍歷的時(shí)候是不能修改集合結(jié)構(gòu)的的妖，所以不能直接用remove
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;//直接把w之后的剩余元素置空
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//使用arraycopy將i+1開始的元素覆蓋的i開始的元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
public void ensureCapacity(int minCapacity) {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA在三個(gè)構(gòu)造函數(shù)其中一個(gè)看到，是elementData屬性的初始值
//剛剛構(gòu)造過舅巷，就來擴(kuò)容的話羔味，就給DEFAULT_CAPACITY河咽，10個(gè)
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)//頻繁比較钠右，估計(jì)是避免無味的擴(kuò)容吧
grow(minCapacity);
}
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
上面方法相比與AbstractCollection實(shí)現(xiàn)的方法來說，是可以正常使用了忘蟹，使用實(shí)例屬性elementData來成為真正的容器實(shí)現(xiàn)各種增刪改查飒房。
這里說下retainAll，跟AbstractCollection的retainAll實(shí)現(xiàn)思路是一樣的媚值。保留交集的元素狠毯，返回值跟是否交集無關(guān)
//ArrayList
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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)//true,c里面包含list集合的元素，就把list集合的元素保留下來
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;//清空w之后的所有元素
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
//AbstractCollection
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();//不存在list中褥芒，就把list中的元素移除
modified = true;
}
}
return modified;//返回值跟交集無關(guān)
}
ArrayList實(shí)現(xiàn)List接口的方法嚼松，其實(shí)就是多了具體下標(biāo)的操作，思路就是通過內(nèi)存復(fù)制的方式來移動(dòng)數(shù)組锰扶。具體的可以看代碼献酗，其實(shí)跟上面的abstractCollection方法實(shí)現(xiàn)類似。
ArrayList不僅實(shí)現(xiàn)了集合和list的功能坷牛，還添加了克隆和序列化的功能罕偎。
ArrayList的克隆
繼承Cloneable接口實(shí)現(xiàn)的克隆方式，有些人說是淺克隆京闰，其實(shí)他是真的把一個(gè)集合的數(shù)據(jù)拷貝到另一個(gè)地址的颜及。不玩虛的甩苛。只是集合里面可能有對象元素，對象元素本身就是引用俏站，所以拷過來的也就是那個(gè)對象的引用讯蒲，在拷貝集合的層面上算是真實(shí)拷貝了，如果想把集合元素的對象的值也給克隆成一個(gè)新對象肄扎，咱們可以連帶著把那個(gè)對象也克隆了爱葵，使那個(gè)對象實(shí)現(xiàn)Cloneable就可以了。
ArrayList的序列化
還有就是序列化反浓，這個(gè)可以單獨(dú)研究下萌丈，代碼還是比較復(fù)雜的。最終就是通過反射的方式拿到ArrayList中實(shí)現(xiàn)的writeObject和readObject來調(diào)用實(shí)現(xiàn)ArrayList的序列化
LinkedList
LinkedList的東西也是比較多的雷则。就等之后再寫個(gè)新的來講
類封裝的思想
從集合框架圖看辆雾，架構(gòu)還是比較復(fù)雜的。咱們這里只是分析了List相關(guān)的類圖月劈。從上面的分析過程來看度迂，為什么要把類封裝成這樣呢。
首先咱們知道Collection主要分為List猜揪、set和Queue(上面的集合框架圖是不全的惭墓。)
其實(shí)是三種不同的數(shù)據(jù)結(jié)構(gòu)。把他們的共性抽象到Collection接口中去而姐，讓AbstractCollection來實(shí)現(xiàn)其共性腊凶，當(dāng)然也不是全實(shí)現(xiàn)，只是框定一個(gè)結(jié)構(gòu)拴念，具體的差異實(shí)現(xiàn)比如add和remove還是要到具體的數(shù)據(jù)結(jié)構(gòu)類中去實(shí)現(xiàn)的钧萍。
再把三種不同數(shù)據(jù)結(jié)構(gòu)的差異抽象到各自的接口中去，List,Set（我們看到set并沒有實(shí)現(xiàn)具體的差異接口）,Queue政鼠。
使用AbstractList风瘦、AbstractSet、AbstractQueue類分別實(shí)現(xiàn)集合的共性（AbstractCollection）和各自的差異接口公般。
當(dāng)然從上面分析也看到了万搔，到了這一步還是沒有完成的，因?yàn)長ist又可以分為用數(shù)組實(shí)現(xiàn)和用鏈表實(shí)現(xiàn)的官帘。所以AbstractList瞬雹、AbstractSet、AbstractQueue還是只能實(shí)現(xiàn)一些與具體數(shù)據(jù)結(jié)構(gòu)無關(guān)的函數(shù)遏佣。
再到下面我們就看到帶有具體數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)類了挖炬，比如ArrayList和LinkedList。
其實(shí)看完ArrayList和LinkedList的代碼，大家也會(huì)很疑惑意敛，為什么ArrayList等都是自己全部實(shí)現(xiàn)Collection和List接口的方法馅巷。壓根就不理會(huì)AbstractList和AbstractCollection這一級別的實(shí)現(xiàn)呢。
也許實(shí)現(xiàn)這些抽象類只是一種代碼風(fēng)格草姻，也許是為了給大家一個(gè)更好的擴(kuò)展點(diǎn)吧
等把其他幾個(gè)分支擼完钓猬，再回來看這是怎么回事，現(xiàn)在理解還是不夠
