java集合框架02——Collection架構與源碼分析
Collection是一個接口，它主要的兩個分支是List和Set。如下圖所示：
List和Set都是接口，它們繼承與Collection。List是有序的隊列，可以用重復的元素；而Set是數學概念中的集合，不能有重復的元素。List和Set都有它們各自的實現類。
為了方便，我們抽象出AbstractCollection類來讓其他類繼承，該類實現類Collection中的絕大部分方法。AbstractList和AbstractSet都繼承與AbstractCollection，具體的List實現類繼承與AbstractList，而Set的實現類則繼承與AbstractSet。
另外，Collection中有個iterator()方法，它的作用是返回一個Iterator接口。通常，我們通過Iterator迭代器來遍歷集合。ListIterator是List接口所特有的，在List接口中，通過ListIterator()返回一個ListIterator對象。
我們首先來閱讀下這些接口和抽象類以及他們的實現類中都有哪些方法：
1. Collection
Collection的定義如下：
public interface Collection extends Iterable {}
從它的定義中可以看出，Collection是一個接口。它是一個高度抽象出來的集合，包含了集合的基本操作：添加、刪除、清空、遍歷、是否為空、獲取大小等。
Collection接口的所有子類（直接子類和簡介子類）都必須實現2種構造函數：不帶參數的構造函數和參數為Collection的構造函數。帶參數的構造函數可以用來轉換Collection的類型。下面是Collection接口中定義的API：
// Collection的API
abstract boolean add(E object)
abstract boolean addAll(Collection collection)
abstract void clear()
abstract boolean contains(Object object)
abstract boolean containsAll(Collection collection)
abstract boolean equals(Object object)
abstract int hashCode()
abstract boolean isEmpty()
abstract Iterator iterator()
abstract boolean remove(Object object)
abstract boolean removeAll(Collection collection)
abstract boolean retainAll(Collection collection)
abstract int size()
abstract T[] toArray(T[] array)
abstract Object[] toArray()
2. List
List的定義如下：
public interface List extends Collection {}
從List定義中可以看出，它繼承與Collection接口，即List是集合的一種。List是有序的隊列，List中的每一個元素都有一個索引，第一個元素的索引值為0，往後的元素的索引值依次+1.，List中允許有重復的元素。
List繼承Collection自然包含了Collection的所有接口，由於List是有序隊列，所以它也有自己額外的API接口。API如下：
// Collection的API
abstract boolean add(E object)
abstract boolean addAll(Collection collection)
abstract void clear()
abstract boolean contains(Object object)
abstract boolean containsAll(Collection collection)
abstract boolean equals(Object object)
abstract int hashCode()
abstract boolean isEmpty()
abstract Iterator iterator()
abstract boolean remove(Object object)
abstract boolean removeAll(Collection collection)
abstract boolean retainAll(Collection collection)
abstract int size()
abstract T[] toArray(T[] array)
abstract Object[] toArray()
// 相比與Collection，List新增的API：
abstract void add(int location, E object) //在指定位置添加元素
abstract boolean addAll(int location, Collection collection) //在指定位置添加其他集合中的元素
abstract E get(int location) //獲取指定位置的元素
abstract int indexOf(Object object) //獲得指定元素的索引
abstract int lastIndexOf(Object object) //從右邊的索引
abstract ListIterator listIterator(int location) //獲得iterator
abstract ListIterator listIterator()
abstract E remove(int location) //刪除指定位置的元素
abstract E set(int location, E object) //修改指定位置的元素
abstract List subList(int start, int end) //獲取子list
3. Set
Set的定義如下：
public abstract class AbstractCollection implements Collection {}
AbstractCollection是一個抽象類，它實現了Collection中除了iterator()和size()之外的所有方法。AbstractCollection的主要作用是方便其他類實現Collection.，比如ArrayList、LinkedList等。它們想要實現Collection接口，通過集成AbstractCollection就已經實現大部分方法了，再實現一下iterator()和size()即可。
下面看一下AbstractCollection實現的部分方法的源碼：
public abstract class AbstractCollection implements Collection {
protected AbstractCollection() {
}
public abstract Iterator iterator();//iterator()方法沒有實現
public abstract int size(); //size()方法也沒有實現
public boolean isEmpty() { //檢測集合是否為空
return size() == 0;
}
/*檢查集合中是否包含特定對象*/
public boolean contains(Object o) {
Iterator it = iterator();
if (o==null) {
while (it.hasNext()) //從這裡可以看出，任何非空集合都包含null
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
/*將集合轉變成數組*/
public Object[] toArray() {
// Estimate size of array; be prepared to see more or fewer elements
Object[] r = new Object[size()]; //創建與集合大小相同的數組
Iterator it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) // fewer elements than expected
//Arrays.copy(**,**)的第二個參數是待copy的長度，如果這個長度大於r，則保留r的長度
return Arrays.copyOf(r, i);
r[i] = it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
public T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), size);
Iterator it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { // fewer elements than expected
if (a == r) {
r[i] = null; // null-terminate
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else {
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;
}
private static 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;
}
// 刪除對象o
public boolean remove(Object o) {
Iterator it = iterator();
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
// 判斷是否包含集合c中所有元素
public boolean containsAll(Collection c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
//添加集合c中所有元素
public boolean addAll(Collection c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
//刪除集合c中所有元素（如果存在的話）
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;
}
//清空
public void clear() {
Iterator it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
//將集合元素顯示成[String]
public String toString() {
Iterator it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
}
5. AbstractList
AbstractList的定義如下：
public abstract class AbstractList extends AbstractCollection implements List {}
從定義中可以看出，AbstractList是一個繼承AbstractCollection，並且實現了List接口的抽象類。它實現了List中除了size()、get(int location)之外的方法。
AbstractList的主要作用：它實現了List接口中的大部分函數，從而方便其它類繼承List。另外，和AbstractCollection相比，AbstractList抽象類中，實現了iterator()方法。
AbstractList抽象類的源碼如下：
public abstract class AbstractList extends AbstractCollection implements List {
protected AbstractList() {
}
public boolean add(E e) {
add(size(), e);
return true;
}
abstract public E get(int index);
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
/***************************** Search Operations**********************************/
public int indexOf(Object o) { //搜索對象o的索引
ListIterator it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null) //執行it.next()，會先返回it指向位置的值，然後it會移到下一個位置
return it.previousIndex(); //所以要返回it.previousIndex(); 關於it幾個方法的源碼在下面
} else {
while (it.hasNext())
if (o.equals(it.next()))
return it.previousIndex();
}
return -1;
}
public int lastIndexOf(Object o) {
ListIterator it = listIterator(size());
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;
}
/**********************************************************************************/
/****************************** Bulk Operations ***********************************/
public void clear() {
removeRange(0, size());
}
public boolean addAll(int index, Collection c) {
rangeCheckForAdd(index);
boolean modified = false;
for (E e : c) {
add(index++, e);
modified = true;
}
return modified;
}
protected void removeRange(int fromIndex, int toIndex) {
ListIterator it = listIterator(fromIndex);
for (int i=0, n=toIndex-fromIndex; i iterator() {
return new Itr();
}
public ListIterator listIterator() {
return listIterator(0); //返回的iterator索引從0開始
}
public ListIterator listIterator(final int index) {
rangeCheckForAdd(index); //首先檢查index范圍是否正確
return new ListItr(index); //ListItr繼承與Itr且實現了ListIterator接口，Itr實現了Iterator接口，往下看
}
private class Itr implements Iterator {
int cursor = 0; //元素的索引，當調用next()方法時，返回當前索引的值
int lastRet = -1; //lastRet也是元素的索引，但如果刪掉此元素，該值置為-1
/*
*迭代器都有個modCount值，在使用迭代器的時候，如果使用remove,add等方法的時候都會修改modCount，
*在迭代的時候需要保持單線程的唯一操作，如果期間進行了插入或者刪除，modCount就會被修改，迭代器就會檢測到被並發修改，從而出現運行時異常。
*舉個簡單的例子，現在某個線程正在遍歷一個List，另一個線程對List中的某個值做了刪除，那原來的線程用原來的迭代器當然無法正常遍歷了
*/
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size(); //當索引值和元素個數相同時表示沒有下一個元素了，索引是從0到size-1
}
public E next() {
checkForComodification(); //檢查modCount是否改變
try {
int i = cursor; //next()方法主要做了兩件事：
E next = get(i);
lastRet = i;
cursor = i + 1; //1.將索引指向了下一個位置
return next; //2. 返回當前索引的值
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet < 0) //lastRet<0表示已經不存在了
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--; //原位置的索引值減小了1，但是實際位置沒變
lastRet = -1; //置為-1表示已刪除
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
private class ListItr extends Itr implements ListIterator {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1; //previous()方法中也做了兩件事：
E previous = get(i); //1. 將索引向前移動一位
lastRet = cursor = i; //2. 返回索引處的值
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() { //iterator中的index本來就是下一個位置，在next()方法中可以看出
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);
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();
}
}
}
/**********************************************************************************/
//獲得子List，詳細源碼往下看SubList類
public List subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
/*************************** Comparison and hashing *******************************/
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator e1 = listIterator();
ListIterator e2 = ((List) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}
public int hashCode() { //hashcode
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
/**********************************************************************************/
protected transient int modCount = 0;
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();
}
}
class SubList extends AbstractList {
private final AbstractList l;
private final int offset;
private int size;
/* 從SubList源碼可以看出，當需要獲得一個子List時，底層並不是真正的返回一個子List，還是原來的List，只不過
* 在操作的時候，索引全部限定在用戶所需要的子List部分而已
*/
SubList(AbstractList 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; //原封不動的將原來的list賦給l
offset = fromIndex; //偏移量，用在操作新的子List中
size = toIndex - fromIndex; //子List的大小，所以子List中不包括toIndex處的值，即子List中包括左邊不包括右邊
this.modCount = l.modCount;
}
//注意下面所有的操作都在索引上加上偏移量offset，相當於在原來List的副本上操作子List
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 c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection 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 iterator() {
return listIterator();
}
public ListIterator listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator() {
private final ListIterator i = l.listIterator(index+offset); //相當子List的索引0
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 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();
}
}
class RandomAccessSubList extends SubList implements RandomAccess {
RandomAccessSubList(AbstractList list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}
6. AbstractSet
AbstractSet的定義如下：
public abstract class AbstractSet extends AbstractCollection implements Set {}
AbstractSet是一個繼承與AbstractCollection，並且實現了Set接口的抽象類。由於Set接口和Collection接口中的API完全一樣，所以Set也就沒有自己單獨的API。和AbstractCollection一樣，它實現了List中除iterator()和size()外的方法。所以源碼和AbstractCollection的一樣。
AbstractSet的主要作用：它實現了Set接口總的大部分函數，從而方便其他類實現Set接口。
7. Iterator
Iterator的定義如下：
public interface Iterator {}
Iterator是一個接口，它是集合的迭代器。集合可以通過Iterator去遍歷其中的元素。Iterator提供的API接口包括：是否存在下一個元素，獲取下一個元素和刪除當前元素。
注意：Iterator遍歷Collection時，是fail-fast機制的。即，當某一個線程A通過iterator去遍歷某集合的過程中，若該集合的內容被其他線程所改變了，那麼線程A訪問集合時，就會拋出CurrentModificationException異常，產生fail-fast事件。下面是Iterator的幾個API。
// Iterator的API
abstract boolean hasNext()
abstract E next()
abstract void remove()
8. ListIterator
ListIterator的定義如下：
public interface ListIterator extends Iterator {}
ListIterator是一個繼承Iterator的接口，它是隊列迭代器。專門用於遍歷List，能提供向前和向後遍歷。相比於Iterator，它新增了添加、是否存在上一個元素、獲取上一個元素等API接口：// 繼承於Iterator的接口
abstract boolean hasNext()
abstract E next()
abstract void remove()
// 新增API接口
abstract void add(E object)
abstract boolean hasPrevious()
abstract int nextIndex()
abstract E previous()
abstract int previousIndex()
abstract void set(E object)
