JAVA—咖啡館

讓我們來看看AbstracyList如何創(chuàng)建Iterator。首先AbstractList定義了一個內(nèi)部類（inner class）：

       private class Itr implements Iterator {

                       ...

                   }

而iterator()方法的定義是：

       public Iterator iterator() {

                       return new Itr();

                   }

因此客戶端不知道它通過Iterator it = a.iterator();所獲得的Iterator的真正類型。

現(xiàn)在我們關(guān)心的是這個申明為private的Itr類是如何實現(xiàn)遍歷AbstractList的：

       private class Itr implements Iterator {

                       int cursor = 0;

                       int lastRet = -1;

                       int expectedModCount = modCount;

                   }

Itr類依靠3個int變量（還有一個隱含的AbstractList的引用）來實現(xiàn)遍歷，cursor是下一次next()調(diào)用時元素的位置，第一次調(diào)用next()將返回索引為0的元素。lastRet記錄上一次游標(biāo)所在位置，因此它總是比cursor少1。

變量cursor和集合的元素個數(shù)決定hasNext()：

       public boolean hasNext() {

                       return cursor != size();

                   }

方法next()返回的是索引為cursor的元素，然后修改cursor和lastRet的值：

       public Object next() {

                       checkForComodification();

                       try {

                           Object next = get(cursor);

                           lastRet = cursor++;

                           return next;

                       } catch(IndexOutOfBoundsException e) {

                           checkForComodification();

                           throw new NoSuchElementException();

                       }

                   }

expectedModCount表示期待的modCount值，用來判斷在遍歷過程中集合是否被修改過。AbstractList包含一個 modCount變量，它的初始值是0，當(dāng)集合每被修改一次時（調(diào)用add，remove等方法），modCount加1。因此，modCount如果不變，表示集合內(nèi)容未被修改。

Itr初始化時用expectedModCount記錄集合的modCount變量，此后在必要的地方它會檢測modCount的值：

       final void checkForComodification() {

                       if (modCount != expectedModCount)

                           throw new ConcurrentModificationException();

                   }

如果modCount與一開始記錄在expectedModeCount中的值不等，說明集合內(nèi)容被修改過，此時會拋出ConcurrentModificationException。

這個ConcurrentModificationException是RuntimeException，不要在客戶端捕獲它。如果發(fā)生此異常，說明程序代碼的編寫有問題，應(yīng)該仔細(xì)檢查代碼而不是在catch中忽略它。

但是調(diào)用Iterator自身的remove()方法刪除當(dāng)前元素是完全沒有問題的，因為在這個方法中會自動同步expectedModCount和modCount的值：

       public void remove() {

                       ...

                       AbstractList.this.remove(lastRet);

                       ...

                       // 在調(diào)用了集合的remove()方法之后重新設(shè)置了expectedModCount：

                       expectedModCount = modCount;

                       ...

                   }

要確保遍歷過程順利完成，必須保證遍歷過程中不更改集合的內(nèi)容（Iterator的remove()方法除外），因此，確保遍歷可靠的原則是只在一個線程中使用這個集合，或者在多線程中對遍歷代碼進(jìn)行同步。

最后給個完整的示例：

       Collection c = new ArrayList();

                   c.add("abc");

                   c.add("xyz");

                   for(Iterator it = c.iterator(); it.hasNext(); ) {

                       String s = (String)it.next();

                       System.out.println(s);

                   }

如果你把第一行代碼的ArrayList換成LinkedList或Vector，剩下的代碼不用改動一行就能編譯，而且功能不變，這就是針對抽象編程的原則：對具體類的依賴性最小。

List接口
　　List是有序的Collection，使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引（元素在List中的位置，類似于數(shù)組下標(biāo)）來訪問List中的元素，這類似于Java的數(shù)組。
和下面要提到的Set不同，List允許有相同的元素。
　　除了具有Collection接口必備的iterator()方法外，List還提供一個listIterator()方法，返回一個 ListIterator接口，和標(biāo)準(zhǔn)的Iterator接口相比，ListIterator多了一些add()之類的方法，允許添加，刪除，設(shè)定元素，還能向前或向后遍歷。
　　實現(xiàn)List接口的常用類有LinkedList，ArrayList，Vector和Stack。

LinkedList類
　　LinkedList實現(xiàn)了List接口，允許null元素。此外LinkedList提供額外的get，remove，insert方法在 LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。
　　注意LinkedList沒有同步方法。如果多個線程同時訪問一個List，則必須自己實現(xiàn)訪問同步。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List：
　　　　List list = Collections.synchronizedList(new LinkedList(...));

ArrayList類
　　ArrayList實現(xiàn)了可變大小的數(shù)組。它允許所有元素，包括null。ArrayList沒有同步。
size，isEmpty，get，set方法運行時間為常數(shù)。但是add方法開銷為分?jǐn)偟某?shù)，添加n個元素需要O(n)的時間。其他的方法運行時間為線性。
　　每個ArrayList實例都有一個容量（Capacity），即用于存儲元素的數(shù)組的大小。這個容量可隨著不斷添加新元素而自動增加，但是增長算法并沒有定義。當(dāng)需要插入大量元素時，在插入前可以調(diào)用ensureCapacity方法來增加ArrayList的容量以提高插入效率。
　　和LinkedList一樣，ArrayList也是非同步的（unsynchronized）。

Vector類
　　Vector非常類似ArrayList，但是Vector是同步的。由Vector創(chuàng)建的Iterator，雖然和ArrayList創(chuàng)建的 Iterator是同一接口，但是，因為Vector是同步的，當(dāng)一個Iterator被創(chuàng)建而且正在被使用，另一個線程改變了Vector的狀態(tài)（例如，添加或刪除了一些元素），這時調(diào)用Iterator的方法時將拋出ConcurrentModificationException，因此必須捕獲該異常。

Stack 類
　　Stack繼承自Vector，實現(xiàn)一個后進(jìn)先出的堆棧。Stack提供5個額外的方法使得 Vector得以被當(dāng)作堆棧使用?；镜膒ush和pop方法，還有peek方法得到棧頂?shù)脑?，empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧。

Set接口
　　Set是一種不包含重復(fù)的元素的Collection，即任意的兩個元素e1和e2都有e1.equals(e2)=false，Set最多有一個null元素。
　　很明顯，Set的構(gòu)造函數(shù)有一個約束條件，傳入的Collection參數(shù)不能包含重復(fù)的元素。
　　請注意：必須小心操作可變對象（Mutable Object）。如果一個Set中的可變元素改變了自身狀態(tài)導(dǎo)致Object.equals(Object)=true將導(dǎo)致一些問題。

Map接口
　　請注意，Map沒有繼承Collection接口，Map提供key到value的映射。一個Map中不能包含相同的key，每個key只能映射一個 value。Map接口提供3種集合的視圖，Map的內(nèi)容可以被當(dāng)作一組key集合，一組value集合，或者一組key-value映射。

Hashtable類
　　Hashtable繼承Map接口，實現(xiàn)一個key-value映射的哈希表。任何非空（non-null）的對象都可作為key或者value。
　　添加數(shù)據(jù)使用put(key, value)，取出數(shù)據(jù)使用get(key)，這兩個基本操作的時間開銷為常數(shù)。
Hashtable 通過initial capacity和load factor兩個參數(shù)調(diào)整性能。通常缺省的load factor 0.75較好地實現(xiàn)了時間和空間的均衡。增大load factor可以節(jié)省空間但相應(yīng)的查找時間將增大，這會影響像get和put這樣的操作。
使用Hashtable的簡單示例如下，將1，2，3放到Hashtable中，他們的key分別是”one”，”two”，”three”：
　　　　Hashtable numbers = new Hashtable();
　　　　numbers.put(“one”, new Integer(1));
　　　　numbers.put(“two”, new Integer(2));
　　　　numbers.put(“three”, new Integer(3));
　　要取出一個數(shù)，比如2，用相應(yīng)的key：
　　　　Integer n = (Integer)numbers.get(“two”);
　　　　System.out.println(“two = ” + n);
　　由于作為key的對象將通過計算其散列函數(shù)來確定與之對應(yīng)的value的位置，因此任何作為key的對象都必須實現(xiàn)hashCode和equals方法。hashCode和equals方法繼承自根類Object，如果你用自定義的類當(dāng)作key的話，要相當(dāng)小心，按照散列函數(shù)的定義，如果兩個對象相同，即obj1.equals(obj2)=true，則它們的hashCode必須相同，但如果兩個對象不同，則它們的hashCode不一定不同，如果兩個不同對象的hashCode相同，這種現(xiàn)象稱為沖突，沖突會導(dǎo)致操作哈希表的時間開銷增大，所以盡量定義好的hashCode()方法，能加快哈希表的操作。
　　如果相同的對象有不同的hashCode，對哈希表的操作會出現(xiàn)意想不到的結(jié)果（期待的get方法返回null），要避免這種問題，只需要牢記一條：要同時復(fù)寫equals方法和hashCode方法，而不要只寫其中一個。
　　Hashtable是同步的。

HashMap類
　　HashMap和Hashtable類似，不同之處在于HashMap是非同步的，并且允許null，即null value和null key。，但是將HashMap視為Collection時（values()方法可返回Collection），其迭代子操作時間開銷和HashMap 的容量成比例。因此，如果迭代操作的性能相當(dāng)重要的話，不要將HashMap的初始化容量設(shè)得過高，或者load factor過低。

WeakHashMap類
　　WeakHashMap是一種改進(jìn)的HashMap，它對key實行“弱引用”，如果一個key不再被外部所引用，那么該key可以被GC回收。

總結(jié)
　　如果涉及到堆棧，隊列等操作，應(yīng)該考慮用List，對于需要快速插入，刪除元素，應(yīng)該使用LinkedList，如果需要快速隨機訪問元素，應(yīng)該使用ArrayList。
　　如果程序在單線程環(huán)境中，或者訪問僅僅在一個線程中進(jìn)行，考慮非同步的類，其效率較高，如果多個線程可能同時操作一個類，應(yīng)該使用同步的類。
　　要特別注意對哈希表的操作，作為key的對象要正確復(fù)寫equals和hashCode方法。
　　盡量返回接口而非實際的類型，如返回List而非ArrayList，這樣如果以后需要將ArrayList換成LinkedList時，客戶端代碼不用改變。這就是針對抽象編程。

同步性
Vector 是同步的。這個類中的一些方法保證了Vector中的對象是線程安全的。而ArrayList則是異步的，因此ArrayList中的對象并不是線程安全的。因為同步的要求會影響執(zhí)行的效率，所以如果你不需要線程安全的集合那么使用ArrayList是一個很好的選擇，這樣可以避免由于同步帶來的不必要的性能開銷。
數(shù)據(jù)增長
從內(nèi)部實現(xiàn)機制來講ArrayList和Vector都是使用數(shù)組(Array)來控制集合中的對象。當(dāng)你向這兩種類型中增加元素的時候，如果元素的數(shù)目超出了內(nèi)部數(shù)組目前的長度它們都需要擴展內(nèi)部數(shù)組的長度，Vector缺省情況下自動增長原來一倍的數(shù)組長度， ArrayList是原來的50%,所以最后你獲得的這個集合所占的空間總是比你實際需要的要大。所以如果你要在集合中保存大量的數(shù)據(jù)那么使用 Vector有一些優(yōu)勢，因為你可以通過設(shè)置集合的初始化大小來避免不必要的資源開銷。
使用模式
在ArrayList和Vector中，從一個指定的位置（通過索引）查找數(shù)據(jù)或是在集合的末尾增加、移除一個元素所花費的時間是一樣的，這個時間我們用 O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花費的時間會呈線形增長：O(n-i)，其中n代表集合中元素的個數(shù)，i代表元素增加或移除元素的索引位置。為什么會這樣呢？以為在進(jìn)行上述操作的時候集合中第i和第i個元素之后的所有元素都要執(zhí)行位移的操作。這一切意味著什么呢？
這意味著，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好選擇其他的集合操作類。比如，LinkList集合類在增加或移除集合中任何位置的元素所花費的時間都是一樣的?O(1)，但它在索引一個元素的使用缺比較慢－O (i),其中i是索引的位置.使用 ArrayList也很容易，因為你可以簡單的使用索引來代替創(chuàng)建iterator對象的操作。LinkList也會為每個插入的元素創(chuàng)建對象，所有你要明白它也會帶來額外的開銷。
最后，在《Practical Java》一書中Peter Haggar建議使用一個簡單的數(shù)組（Array）來代替Vector或ArrayList。尤其是對于執(zhí)行效率要求高的程序更應(yīng)如此。因為使用數(shù)組 (Array)避免了同步、額外的方法調(diào)用和不必要的重新分配空間的操作。
在使用java的時候，我們都會遇到使用集合（collection）的時候，但是java api提供了多種集合的實現(xiàn)。

總的說來，java api中所用的集合類，都是實現(xiàn)了collection接口，他的一個類繼承結(jié)構(gòu)如下：

                  collection<--list<--vector
                          collection<--list<--arraylist
                          collection<--list<--linkedlist
                          collection<--set<--hashset
                          collection<--set<--hashset<--linkedhashset
                          collection<--set<--sortedset<--treeset

vector : 基于array的list，其實就是封裝了array所不具備的一些功能方便我們使用，它不可能走入array的限制。性能也就不可能超越array。所以，在可能的情況下，我們要多運用array。另外很重要的一點就是vector&ldquo;sychronized&rdquo; 的，這個也是vector和arraylist的唯一的區(qū)別。

arraylist：同vector一樣是一個基于array上的鏈表，但是不同的是arraylist不是同步的。所以在性能上要比vector優(yōu)越一些，但是當(dāng)運行到多線程環(huán)境中時，可需要自己在管理線程的同步問題。

linkedlist：linkedlist 不同于前面兩種list，它不是基于array的，所以不受array性能的限制。它每一個節(jié)點（node）都包含兩方面的內(nèi)容：1.節(jié)點本身的數(shù)據(jù)（data）；2.下一個節(jié)點的信息（nextnode）。所以當(dāng)對linkedlist做添加，刪除動作的時候就不用像基于array的list一樣，必須進(jìn)行大量的數(shù)據(jù)移動。只要更改nextnode的相關(guān)信息就可以實現(xiàn)了。這就是linkedlist的優(yōu)勢。

list總結(jié)：

1. 所有的list中只能容納單個不同類型的對象組成的表，而不是key－value鍵值對。例如：[ tom,1,c ]；

2. 所有的list中可以有相同的元素，例如vector中可以有 [ tom,koo,too,koo ]；

3. 所有的list中可以有null元素，例如[ tom,null,1 ]；

4. 基于array的list（vector，arraylist）適合查詢，而linkedlist（鏈表）適合添加，刪除操作。

hashset：雖然set同list都實現(xiàn)了collection接口，但是他們的實現(xiàn)方式卻大不一樣。list基本上都是以array為基礎(chǔ)。但是set則是在 hashmap的基礎(chǔ)上來實現(xiàn)的，這個就是set和list的根本區(qū)別。hashset的存儲方式是把hashmap中的key作為set的對應(yīng)存儲項?？纯磆ashset的add（object  obj）方法的實現(xiàn)就可以一目了然了。

    public boolean add(object obj)
    {
        return map.put(obj, present) == null;
    }

這個也是為什么在set中不能像在list中一樣有重復(fù)的項的根本原因，因為hashmap的key是不能有重復(fù)的。

linkedhashset：hashset的一個子類，一個鏈表。

treeset：sortedset的子類，它不同于hashset的根本就是treeset是有序的。它是通過sortedmap來實現(xiàn)的。

set總結(jié)：

1. set實現(xiàn)的基礎(chǔ)是map（hashmap）；

2.  set中的元素是不能重復(fù)的，如果使用add(object obj)方法添加已經(jīng)存在的對象，則會覆蓋前面的對象。