一、Collection介面 從《Java集合：整體結構》一文中我們知道所有的List和Set都繼承自Collection介面，該介面類提供了集合最基本的方法，雖然List介面和Set等都有一些自己獨有的方法，但是基本的操作類似。我們先看下Collection介面提供的方法： 總體上可以將Colle ...
一、Collection介面
從《Java集合：整體結構》一文中我們知道所有的List和Set都繼承自Collection介面，該介面類提供了集合最基本的方法，雖然List介面和Set等都有一些自己獨有的方法，但是基本的操作類似。我們先看下Collection介面提供的方法：
總體上可以將Collection的方法分為以下幾大類：
1、增加（add/addAll）
2、刪除（remove/removeAll/clear/retainAll）
3、查詢（contain/containAll/iterator/size/isEmpty）
4、轉數組（toArray/toArray(T[])）
直接實現該介面的類只有AbstractCollection類，該類也只是一個抽象類，提供了對集合類操作的一些基本實現。List和Set的具體實現類基本上都直接或間接的繼承了該類。為了方便以後更清晰的理解這些類的實現，我們先看下AbstractCollection的實現。
二、AbstractCollection源碼解析
package java.util;
public abstract class AbstractCollection<E> implements Collection<E> {
protected AbstractCollection() {
}
public abstract Iterator<E> iterator();
public abstract int size();
//判斷集合中是否有數據
public boolean isEmpty() {
return size() == 0;
}
/**
* 判斷是否包含指定的元素
* （1）如果參數為null，查找值為null的元素，如果存在，返回true，否則返回false。
* （2）如果參數不為null，則根據equals方法查找與參數相等的元素，如果存在，則返回true，否則返回false。
* 註意：這裡必須對null單獨處理，否則null.equals會報空指針異常
*/
public boolean contains(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
/**
* 功能：將集合元素轉換為數組
* 實現：
* （1）創建一個數組，大小為集合中元素的數量
* （2）通過迭代器遍歷集合，將當前集合中的元素複製到數組中（複製引用）
* （3）如果集合中元素比預期的少，則調用Arrays.copyOf()方法將數組的元素複製到新數組中，並返回新數組，Arrays.copyOf的源碼在後續文章中會分析.
* （4）如果集合中元素比預期的多，則調用finishToArray方法生成新數組，並返回新數組，否則返回（1）中創建的數組
*/
public Object[] toArray() {
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;
}
/**
* 功能：通過泛型約束返回指定類型的數組
* 實現：
* （1）如果傳入數組的長度的長度大於等於集合的長度，則將當前集合的元素複製到傳入的數組中
* （2）如果傳入數組的長度小於集合的大小，則將創建一個新的數組來進行集合元素的存儲
*/
public <T> 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<E> it = iterator();
for (int i = 0; i < r.length; i++) {
//集合元素大小小於數組的長度
if (! it.hasNext()) { // fewer elements than expected
if (a == r) {//如果數組是參數中的數組，則將剩餘部分的值都設置為null
r[i] = null; // null-terminate
} else if (a.length < i) {//如果傳入的數組長度小於集合長度，則通過Arrays.copyOf將之前數組中的元素複製到新數組中
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 final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 功能：數組擴容
* （1）當數組索引指向最後一個元素+1時，對數組進行擴容：即創建一個更長的數組，然後將原數組的內容複製到新數組中
* （2）擴容大小：cap + cap/2 +1
* （3）擴容前需要先判斷是否數組長度是否溢出
* 註意：這裡的迭代器是從上層的方法（toArray）傳過來的，並且這個迭代器已執行了一部分，而不是從頭開始迭代的
*/
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;
}
/**
* 未實現
*/
public boolean add(E e) {
throw new UnsupportedOperationException();
}
/**
* 功能：移除指定元素
* （1）如果參數為null，則找到第一個值為null的元素，並將其刪除，返回true，如果不存在null的元素，返回false。
* （2）如果參數不為null，則根據equals方法找到第一個與參數相等的元素，並將其刪除，返回true，如果找不到，返回false。
*/
public boolean remove(Object o) {
Iterator<E> 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;
}
/**
* 遍歷參數集合，依次判斷參數集合中的元素是否在當前集合中，
* 只要有一個不存在，則返回false
* 如果參數集合中所有的元素都在當前集合中，則返回true
*/
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
/**
* 遍歷參數集合，依次將參數集合中的元素添加當前集合中
*/
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
/**
* 功能：移除參數集合的元素
* （1）獲取當前集合的迭代器進行遍歷
* （2）如果當前集合中的元素包含在參數集合中，則刪除當前集合中的元素
* 註：只要參數集合中有任何一個元素在當前元素中，則返回true，表示當前集合有發送變化，否則返回false。
*/
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;
}
/***
* 功能：求參數集合與當前集合的交集
* （1）獲取當前集合的迭代器進行遍歷
* （2）如果當前集合中的元素不在參數集合中，則將其移除。
* 註意：如果當前集合是參數集合中的子集，則返回false，表示當前集合未發送變化，否則返回true。
*/
public boolean retainAll(Collection<?> c) {
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
//刪除所有元素
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
public String toString() {
Iterator<E> 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(' ');
}
}
}
整體上來說，AbstractCollection的源碼還是比較容易理解，尤其是集合增、刪、查等操作都非常簡單。比較複雜的是關於集合轉數組的操作，有幾個點不是特別好理解，這裡解釋一下：
（1）MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，為什麼最大長度要減8，根據官方的解釋：
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
這段話的意思就是有的虛擬機實現，數組對象的頭部會占用這8個位元組。
（2）轉換為數組的操作時，為什麼長度會比size()長或者短？這個的原因還是考慮到併發情況下，當然，在併發環境上面的機制不一定可行，如在ArrayList中就重寫了該方法，遇到size()與hasNext不一致的情況會直接報錯。不過有些場景下可以通過這種方式保持弱一致性，具體後續遇到這種情況的時候再具體說明。
（3）這裡面執行數組拷貝時，用到兩個方法，一個是Arrays.copyOf，另一個是System.arraycopy(r, 0, a, 0, i)方法，這兩個方法的區別也會在後續文章中討論，這裡暫不細說。
三、總結
本文主要分析了AbstractCollection類的源碼，很多實現類會重寫AbstractCollection中已實現的方法。但是弄明白AbstractCollection源碼之後，再看其子類的實現，會更容易理解其源碼實現背後的設計原因，其實，很多源碼本身不難理解，難理解的地方在於其背後的設計思想和原因，這也是我們去看源碼和真正要學習的東西。
