這個系列的三將開啟集合源碼閱讀中燥，以及總結(jié)java集合api注意點和使用建議寇甸。好，廢話不多說疗涉，開始吧拿霉。
本系列以前的文章：
(1) 深入Java基礎(chǔ)（一）——基本數(shù)據(jù)類型及其包裝類
(2)深入Java基礎(chǔ)（二）——字符串家族
文章結(jié)構(gòu)：（1）集合整體概述；（2）分析Collection繼承樹咱扣；（3）注意點（包括迭代器的使用細節(jié)）
一绽淘、集合整體概述
這里寫圖片描述
補充map的繼承樹，它依賴于collection接口
這里寫圖片描述
Collection是一個接口闹伪，是高度抽象出來的集合沪铭，它包含了集合的基本操作和屬性。
可以看出 Collection包含了List偏瓤、Set杀怠、Queue三大分支
（1）List：1.代表有序、重復(fù)的集合硼补。2.像一個數(shù)組驮肉，可以記住每次添加元素的順序（要以對象的形式來理解）熏矿，且長度是可變的已骇。3.訪問的時候根據(jù)元素的索引值來訪問。
（2）Set：1.代表無序票编、不可重復(fù)的集合褪储。2.就像一個罐子，但元素單獨存在慧域。訪問元素只能根據(jù)元素本身來訪問鲤竹。3.元素不可以重復(fù)
（3）Queue：1.代表隊列集合。2.直接對應(yīng)數(shù)據(jù)結(jié)構(gòu)的隊列昔榴。3.LinkedList類實現(xiàn)了Queue接口辛藻，因此我們可以把LinkedList當成Queue來用。
（4）Map：1.是一個映射接口互订，即key-value鍵值對吱肌。Map中的每一個元素包含“一個key”和“key對應(yīng)的value”。2.AbstractMap是個抽象類仰禽，它實現(xiàn)了Map接口中的大部分API氮墨。而HashMap纺蛆，TreeMap，WeakHashMap都是繼承于AbstractMap规揪。3. Hashtable雖然繼承于Dictionary桥氏，但它實現(xiàn)了Map接口。
二猛铅、分析Collection繼承樹：
（1）先來大致看下標記是可遍歷的接口：Iterable
Iterable此接口的目的：實現(xiàn)了這個接口的集合對象支持迭代字支，是可迭代的。而Iterator則是迭代器奕坟，它就是提供迭代機制的對象祥款，具體如何迭代，都是Iterator接口規(guī)范的月杉。Spliterator就是一個并行遍歷的接口刃跛。
public interface Iterable<T> {
//這個目的是：返回傳來的T類型的元素上的一個迭代器
Iterator<T> iterator();
//這個是Java8的新特性：Default方法是指，在接口內(nèi)部包含了一些默認的方法實現(xiàn)（也就是接口中可以包含方法體苛萎，這打破了Java之前版本對接口的語法限制）桨昙，從而使得接口在進行擴展的時候，不會破壞與接口相關(guān)的實現(xiàn)類代碼
/**
翻譯哦：
* 對這個Iterable的每一個元素執(zhí)行給定的動作腌歉，直到所有元素都被處理或者動作拋出一個異常
* 為止蛙酪。除非被實現(xiàn)類指定，動作將以迭代的順序執(zhí)行（如果一個迭代的順序被指定）翘盖。被動作
* 拋出的異常將被傳遞給調(diào)用者
*/
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
/**
直譯了桂塞，再往上的Spliterator接口也就是跟Iterator差不多，不過它是并行遍歷的馍驯。
Spliterator： https://segmentfault.com/q/1010000007087438
* 創(chuàng)建一個被這個Iterable接口描述的元素上Spliterator阁危。
*
* 默認實現(xiàn)從iterable的Iterator中創(chuàng)建一個早期綁定的spliterator。這個spliterator
* 繼承iterable的iterator的fail-fast性質(zhì)汰瘫。
*
* 默認實現(xiàn)應(yīng)該總是被重寫狂打。被默認實現(xiàn)返回的spliterator擁有不好分解能力，是不依據(jù)指定
* 大小定制的混弥，而且不報告任何spliterator的性質(zhì)趴乡。實現(xiàn)類差不多總是能提供更好的實現(xiàn)。
*/
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
//這個就是迭代器啦
public interface Iterator<E> {
boolean hasNext();//每次next之前蝗拿，先調(diào)用此方法探測是否迭代到終點晾捏，判斷是否要去下一個
E next(); //返回當前迭代元素 ，同時哀托，迭代游標后移
//刪除最近一次已近迭代出出去的那個元素惦辛。只有當next執(zhí)行完后，才能調(diào)用remove函數(shù)萤捆。比如你要刪除第一個元素裙品，不能直接調(diào)用 remove()而要先next一下( );在沒有先調(diào)用next 就調(diào)用remove方法是會拋出異常的俗批。
default void remove() {
throw new UnsupportedOperationException("remove");
}
//也是1.8后的特性，支持lamdba表達式市怎，主要是遍歷游標后面的數(shù)據(jù)舅世，按照所給的action去呈現(xiàn)隐岛，遍歷嗓违。
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
（2）跟著繼承樹往下看就是Collection接口啦：
可以看出：一個高度抽象出來的集合蛙埂，包含了集合的基本操作：添加、刪除驰弄、清空麻汰、遍歷、是否為空戚篙、獲取大小等五鲫。Collection接口的所有子類（直接子類和間接子類）都必須實現(xiàn)2種構(gòu)造函數(shù)：不帶參數(shù)的構(gòu)造函數(shù)和參數(shù)為Collection的構(gòu)造函數(shù)。帶參數(shù)的構(gòu)造函數(shù)可以用來轉(zhuǎn)換Collection的類型岔擂。
//這是接口位喂，不是實現(xiàn)的地方，所以是一系列的規(guī)范
public interface Collection<E> extends Iterable<E> {
int size();//返回大小的方法
boolean isEmpty();//判空方法
boolean contains(Object o);//判是否存在方法
Iterator<E> iterator();//迭代器
Object[] toArray();//把集合轉(zhuǎn)成數(shù)組
<T> T[] toArray(T[] a); //*返回包含此 collection 中所有元素的數(shù)組乱灵；返回數(shù)組的運行時類型與指定數(shù)組的運行時類型相同塑崖。
boolean add(E e);//加入元素，返回決定失敗還是成功
boolean remove(Object o);//同樣刪除元素痛倚，返回決定失敗還是成功
boolean containsAll(Collection<?> c);//同上规婆，只是判別對象變了而已
boolean addAll(Collection<? extends E> c);//同上
boolean removeAll(Collection<?> c);//同上
//Java8搞的事情：刪除所有該集合的元素，滿足給定的預(yù)測蝉稳。該方法將會批量刪除符合filter條件的所有元素抒蚜，該方法需要一個Predicate對象作為作為參數(shù)，Predicate也是函數(shù)式接口颠区，因此可使用Lambda表達式作為參數(shù)削锰。
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
//用于從列表中移除未包含在指定collection中的所有元素通铲，返回值：如果List集合對象由于調(diào)用retainAll方法而發(fā)生更改毕莱，則返回 true。
boolean retainAll(Collection<?> c);
//全清咯
void clear();
//下面的兩個方法都是object類過來的颅夺，從而要覆寫的存在朋截。
boolean equals(Object o);
int hashCode();
//在Iterable接口中有大致講解
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
//也是Java8搞的事情：給予博客：http://www.cnblogs.com/guguli/p/4396093.html
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
（3）還有一個抽象類呢：AbstractCollection
它實現(xiàn)了Collection中除了iterator()和size()之外的所有方法。AbstractCollection的主要作用是方便其他類實現(xiàn)Collection.吧黄，比如ArrayList部服、LinkedList等。它們想要實現(xiàn)Collection接口拗慨，通過集成AbstractCollection就已經(jīng)實現(xiàn)大部分方法了廓八，再實現(xiàn)一下iterator()和size()即可奉芦。
但是要注意一個東西，默認不支持添加單個元素剧蹂，所以它的add()本身的實現(xiàn)是直接拋UnsupportedOperationException異常的声功。實際上add()是一種“可選操作”，目的是延遲到需要時再實現(xiàn)宠叼，也就是說子類想自己去添加單個的話需要自己去實現(xiàn)啦Ｏ劝汀！冒冬！
//講些有趣的重要常用的咯伸蚯。
public abstract class AbstractCollection<E> implements Collection<E> {
//上面說過，用collection接口都要兩個構(gòu)造器咯
protected AbstractCollection() {
}
//迭代的根據(jù)自己的子類的不同從而實現(xiàn)自己的迭代＜蚩尽＜劣省！
public abstract Iterator<E> iterator();
public abstract int size();
//判空
public boolean isEmpty() {
return size() == 0;
}
//判是否存在方法
public boolean contains(Object o) {
Iterator<E> 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;
}
/*接口規(guī)定的抗斤，將集合轉(zhuǎn)變成數(shù)組*/
public Object[] toArray() {
Object[] r = new Object[size()];//創(chuàng)建與集合大小相同的數(shù)組
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext())
return Arrays.copyOf(r, i);//第二個參數(shù)是待copy的長度，如果這個長度大于r丈咐，則保留r的長度
r[i] = it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
//同上瑞眼，不過參數(shù)是泛型而已。引入泛型模板機制后的新調(diào)用方法棵逊，也就是明確了類型而轉(zhuǎn)換伤疙。
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) {
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;
}
//最大的數(shù)組分配容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//兩個參數(shù)r和it分別是toArray方法中放置集合元素的對象數(shù)組和迭代器
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;//初始數(shù)組大小
while (it.hasNext()) {//第一次進入該while循環(huán)，那么就會分配一個更大的數(shù)組（增加一半的大小辆影，注意可能會溢出徒像，這里處理了分配超大數(shù)組的情況）
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;//分配更大的數(shù)組
// overflow-conscious code
if (newCap - MAX_ARRAY_SIZE > 0)//一旦超過，還會繼續(xù)分配大數(shù)組蛙讥。最后只返回i個元素（即迭代器中元素個數(shù)）對應(yīng)的數(shù)組
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);//擴容機制：然后將原來數(shù)組r中的元素拷貝到新數(shù)組中锯蛀，后續(xù)將元素放置在擴容數(shù)組中，一旦超過次慢，還會繼續(xù)分配大數(shù)組旁涤。
}
r[i++] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
//分配大型數(shù)組時的異常處理
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
// MAX_ARRAY_SIZE的值是0x7ffffff7，如果需要分配的數(shù)組過大迫像，可能導致內(nèi)存溢出
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
//添加一個元素的add的默認實現(xiàn)總是拋出該異常劈愚。因為不支持添加一個元素，子類想實現(xiàn)就要自己去覆寫
public boolean add(E e) {
throw new UnsupportedOperationException();
}
// 刪除對象o 闻妓，使用迭代器去刪除菌羽，也就是迭代過程中刪除。問題根源文章：http://blog.csdn.net/qh_java/article/details/50154405 由缆。一會還會詳解這個問題注祖。
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;
}
// 判斷是否包含集合c中所有元素
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
//添加另一個集合中的所有元素addAll猾蒂。！Ｊ浅俊；榉颉！這里是要求子類實現(xiàn)該類時如果需要調(diào)用addAll方法的話必須自己覆蓋add操作署鸡。
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
//下面兩個方法的時間復(fù)雜度都是O(this.size() * c.size())案糙。
//刪除集合c中所有元素（如果存在的話）
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
//取得兩個List的交集的方法
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();
modified = true;
}
}
return modified;
}
//迭代清楚集合數(shù)據(jù)
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
//將集合元素顯示成[String]
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(' ');
}
}
}
三、我們來講下集合的一些注意點：
（1）迭代器：
迭 代器是一種設(shè)計模式靴庆，它是一個對象时捌，它可以遍歷并選擇序列中的對象，而開發(fā)人員不需要了解該序列的底層結(jié)構(gòu)炉抒。迭代器通常被稱為“輕量級”對象奢讨，因為創(chuàng)建它的代價小。在Collection集合中都會實現(xiàn)Iterator焰薄，因此可以通過iterator()函數(shù)獲得一個iterator對象拿诸，然后就可以利用提供的函數(shù)進行相應(yīng)的輸出操作。而ListIterator迭代器是一個另類迭代器塞茅，允許對容器中的元素進行雙向遍歷亩码。
注意：使用集合子類的迭代器，我們是可以在遍歷中進行刪除操作的喔Ｒ笆荨Ｃ韫怠！鞭光！
在遍歷的過程中吏廉，不允許對集合進行增刪操作。如果想要對集合進行刪除操作惰许，也必須調(diào)用迭代器的remove（）方法席覆！其實是那個集合子類重寫過的remove方法的處理！汹买！例子如下：
能邊遍歷邊刪除原因是：子類重寫remove實現(xiàn)拷貝跟AbstractCollection中的remove是不一樣的佩伤！
public class IteratorTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
List list=new ArrayList();//創(chuàng)建一個線性表
list.add("a");
list.add("#");
list.add("b");
list.add("#");
list.add("c");
list.add("#");
Iterator it=list.iterator();//返回線性表的迭代器
while(it.hasNext()) //遍歷線性表 ，先檢查是否還有元素可以迭代
{
String element=(String) it.next();//取出迭代的元素
if("#".equals(element))//如果元素=="#",則刪除
{
it.remove();//true
//這個remove方法是ArrayList重寫過的remove方法卦睹，是經(jīng)過拷貝的一個處理畦戒。將在下一篇文章ArrayList源碼解析中重點講解
}
System.out.println(element);
}
System.out.println(list);
}
}
//輸出是abc
Collection的remove導致的線程錯誤：也就是AbstractCollection中的remove
//將會出現(xiàn)Exception in thread "main" java.util.ConcurrentModificationException
public class IteratorTest4 {
public static void main(String args[]) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
//單純的使用方库，真單純结序。邊遍歷邊刪除，錯死你Ｗ萘省徐鹤！
for (String s : list) {
if (s.equals("b")) {
list.remove(s);
}
}
}
}
原因就要對比源碼去看了嘛垃环。AbstractCollection中的remove
//單純的邊遍歷邊刪除，它就搞死你咯返敬，遂庄，像銀行取錢，沒有做處理劲赠。線程就會搶占涛目。
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;
}
