文章出自：聽雲博客
Java collection是java提供的工具包，包含了常用的數據結構：集合、鏈表、隊列、棧、數組、映射等。
Java集合主要可以劃分為4個部分：List列表、Set集合、Map映射、工具類(Iterator、Arrays和Collections)。
Java collection 結構圖
通過上圖我們可以看出
Collection是一個interface
Collection有List和Set兩大分支。
List<E>是一個隊列，根據下標索引，第一個元素的下標是0，List的實現類有LinkedList, ArrayList, Vector, Stack。List是有序的隊列，List中可以有重復的值。
Set<E>是一個集合，SET中的值是唯一的，我們經常會遇到List去重的問題，把List轉為SET就可以快速實現 Set的實現類有HastSet和TreeSet。HashSet。其中TreeSet是有序的。
Ma<K,V>是一個interface，即key-value鍵值對。Map中的每一個元素包含“一個key”和“key對應的value”。
AbstractMap是個抽象類，它實現了Map接口中的大部分API。而HashMap，TreeMap，WeakHashMap都是繼承於AbstractMap。
Iterator。它是遍歷集合的工具，我們經常使用Iterator迭代器來遍歷集合。Collection的實現類都要實現iterator()函數，返回一個Iterator對象。
抽象類AbstractCollection、AbstractList、AbstractSet、AbstractMap是抽象類，他們都實現了各自的大部分方法，我們直接繼承Abstract類就可以省去重復編碼相同的方法 。PS當時來面試的時候被問到這個問題竟然一下沒想起來。
1、List 是一個接口，它繼承於Collection的接口。它代表著有序的隊列。
2、AbstractList 是一個抽象類，它繼承於AbstractCollection。AbstractList實現List接口中除size()、get(int location)之外的函數。
3、AbstractSequentialList 是一個抽象類，它繼承於AbstractList。AbstractSequentialList 實現了“鏈表中，根據index索引值操作鏈表的全部函數”。
4、ArrayList, LinkedList, Vector, Stack是List的4個實現類。
ArrayList 是一個數組隊列。它由數組實現，實現了RandomAccess, Cloneable, java.io.Serializable接口，所以可以隨便訪問，克隆，序列化，隨機訪問效率高，隨機插入、隨機刪除效率低。
LinkedList 是一個雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率低。
Vector 是矢量隊列，和ArrayList一樣，它也是一個動態數組，由數組實現。但是ArrayList是非線程安全的，而Vector是線程安全的。
Stack 是棧，繼承於Vector。棧的特點是：先進後出(First In Last Out)。
List和Vector不同，ArrayList中的操作不是線程安全的！所以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList。
1、如果涉及到“棧”、“隊列”、“鏈表”等操作，應該考慮用List，具體的選擇哪個List，根據下面的標准來取捨。
2、對於需要快速插入，刪除元素，應該使用LinkedList。
3、對於需要快速隨機訪問元素，應該使用ArrayList。
4、對於“單線程環境” 或者 “多線程環境，但List僅僅只會被單個線程操作”，此時應該使用非同步的類(如ArrayList)。
5、對於“多線程環境，且List可能同時被多個線程操作”，此時，應該使用同步的類(如Vector)。
fail-fast 機制是java集合(Collection)中的一種錯誤機制。當一個線程遍歷某集合時，這個集合的值被其它線程改變，該線程就會拋出ConcurrentModificationException異常。
fail-fast示例。
package Test;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class FastFailEX {
private static List<Integer> list = new ArrayList<Integer>();
public static void main(String[] args) {
//使用兩個線程操作list
new ThreadA().start();
new ThreadB().start();
}
private static void print() {
System.out.println("");
Integer value = null;
Iterator<Integer> iter = list.iterator();
while(iter.hasNext()) {
value = (Integer)iter.next();
System.out.print(value+", ");
}
}
//向list添加元素
private static class ThreadA extends Thread {
public void run() {
for(int i=0;i<10;i++){
list.add(i);
print();
}
}
}
//向list添加元素
private static class ThreadB extends Thread {
public void run() {
for(int i=10;i<20;i++){
list.add(i);
print();
}
}
}
}
運行結果：
結果說明：
當某一個線程遍歷list的過程中，list的內容被另外一個線程所改變了；就會拋出ConcurrentModificationException異常，產生fail-fast事件。
ConcurrentModificationException是在操作Iterator時拋出的異常。我們先看看Iterator的源碼。在AbstractList.java中
通過以上代碼段我們看到兩點
1、執行next()時，要先判斷iterator返回的對象中的modCount”和“當前的modCount”是否相等
2、如果不相等，則拋回異常
接下來我們要知道在什麼情況下 modCount!= expectedModCount
我們來看ArrayList.java中的代碼
我們現在知道，只要修改集合中的元素個數時，都會改變modCount的值。
添加時在決定是否擴空list前修改modCount，刪除元素時直接修改
至此，我們就完全了解了fail-fast是如何產生的。
即，當多個線程對同一個集合進行操作的時候，某線程訪問集合的過程中，該集合的內容被其他線程所改變(即其它線程通過add、remove、clear等方法，改變了modCount的值)；這時，就會拋出ConcurrentModificationException異常，產生fail-fast事件。
使用CopyOnWriteArrayList 就不會產生fail-fast
上源碼
從中，我們可以看出:
CopyOnWriteArrayList是自己實現了Iterator 為COWIterator。
ArrayList的Iterator調用next()時，會調用checkForComodification()比較expectedModCount和modCount的大小；CopyOnWriteArrayList的Iterator實現類中，沒有checkForComodification()，所以不會拋出ConcurrentModificationException異常。
Map是什麼：public interface Map<K,V> { }
Map 是一個鍵值對(key-value)映射接口。Map映射中不能包含重復的鍵；每個鍵最多只能映射到一個值。
Map 接口提供三種collection 視圖，允許以鍵集、值集或鍵-值映射關系集的形式查看某個映射的內容。
Map 映射順序。有些實現類，可以明確保證其順序，如 TreeMap；另一些映射實現則不保證順序，如 HashMap 類。
Map 的實現類應該提供2個“標准的”構造方法：第一個，void（無參數）構造方法，用於創建空映射；第二個，帶有單個 Map 類型參數的構造方法，用於創建一個與其參數具有相同鍵-值映射關系的新映射。實際上，後一個構造方法允許用戶復制任意映射，生成所需類的一個等價映射。盡管無法強制執行此建議（因為接口不能包含構造方法），但是 JDK 中所有通用的映射實現都遵從它。
1、Map 是映射接口，Map中存儲的內容是鍵值對(key-value)。
2、AbstractMap 是繼承於Map的抽象類，它實現了Map中的大部分API。其它Map的實現類可以通過繼承AbstractMap來減少重復編碼。
3、SortedMap 是繼承於Map的接口。SortedMap中的內容是排序的鍵值對，排序的方法是通過比較器(Comparator)。
4、NavigableMap 是繼承於SortedMap的接口。相比於SortedMap，NavigableMap有一系列的導航方法；如"獲取大於/等於某對象的鍵值對"、“獲取小於/等於某對象的鍵值對”等等。
5、TreeMap 繼承於AbstractMap，且實現了NavigableMap接口；因此，TreeMap中的內容是“有序的鍵值對”， 它是通過紅黑樹實現的。它一般用於單線程中存儲有序的映射。
6、HashMap 繼承於AbstractMap，沒實現SortedMap或NavigableMap接口；因此，HashMap的內容是無序的鍵值對。
7、Hashtable繼承於Dictionary(Dictionary也是鍵值對的接口)，實現Map接口；因此，Hashtable的內容也是“鍵值對，是無序的”。 Hashtable是線程安全的。
8、WeakHashMap 繼承於AbstractMap。它和HashMap的鍵類型不同，WeakHashMap的鍵是“弱鍵”， 當“弱鍵”被GC回收時，它對應的鍵值對也會被從WeakHashMap中刪除。JVM提供的弱引用
Set 是繼承於Collection的接口。它是一個不允許有重復元素的集AbstractSet 是一個抽象類，它繼承於AbstractCollection，AbstractCollection實現了Set中的絕大部分函數，為Set的實現類提供了便利。
HastSet 和 TreeSet 是Set的兩個實現類。
HashSet中的元素是無序的。
TreeSet中的元素是有序的，不支持快速隨機遍歷，只能通過迭代器進行遍歷。
在Java集合中，我們通常都通過 “Iterator(迭代器)” 或 “Enumeration(枚舉類)” 去遍歷集合
Enumeration是一個接口，它的源碼如下
Iterator也是一個接口，它的源碼如下：
1、函數接口不同
Enumeration只有2個函數接口。通過Enumeration，我們只能讀取集合的數據，而不能對數據進行修改。
Iterator只有3個函數接口。Iterator除了能讀取集合的數據之外，也能數據進行刪除操作。
2、Iterator支持fail-fast機制，而Enumeration不支持。
Iterator和Enumeration性能對比
package Test;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Random;
public class IteratorEnumerationEX {
public static void main(String[] args) {
int val;
Random r = new Random();
Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
for (int i=0; i<100000; i++) {
val = r.nextInt(100);
table.put(i, val);
}
iterateHashtable(table) ;
enumHashtable(table);
}
private static void iterateHashtable(Hashtable<Integer, Integer> table) {
long startTime = System.currentTimeMillis();
Iterator<Entry<Integer, Integer>> iter = table.entrySet().iterator();
while(iter.hasNext()) {
iter.next();
}
long endTime = System.currentTimeMillis();
countTime("iterate",startTime, endTime);
}
private static void enumHashtable(Hashtable<Integer, Integer> table) {
long startTime = System.currentTimeMillis();
Enumeration<Integer> enu = table.elements();
while(enu.hasMoreElements()) {
enu.nextElement();
}
long endTime = System.currentTimeMillis();
countTime("enum",startTime, endTime);
}
private static void countTime(String type,long start, long end) {
System.out.println(type+":"+(end-start)+"ms");
}
}
輸出結果
因為Iterator支持fail-fast所以做操作多一些性能也相對慢一些
原文鏈接：http://blog.tingyun.com/web/article/detail/268
