Java Collections Framework - Java集合架構之概要

一、概述 在Java語言中，Java語言的設計者對常用的資料結構和算法做了一些規範（接口）和實作（具體實作接口的類）。所有抽象出來的資料結構和操作（算法）統稱為Java集合架構（Java Collection Framework）。 Java程式員在具體應用時，不必考慮資料結構和算法實作細節，隻需要用這些類建立出來一些對象，然後直接應用就可以了。這樣就大大提高了程式設計效率。

二，List和Set Java集合架構的基本接口/類層次結構： 

java.util.Collection [I] 

+--java.util.List [I] 

   +--java.util.ArrayList [C] 

   +--java.util.LinkedList [C] 

   +--java.util.Vector [C] 

      +--java.util.Stack 

+--java.util.Set [I] 

   +--java.util.HashSet [C] 

   +--java.util.SortedSet [I] 

      +--java.util.TreeSet [C] 

java.util.Map 

+--java.util.SortedMap [I] 

   +--java.util.TreeMap [C] 

+--java.util.Hashtable [C] 

+--java.util.HashMap [C] 

+--java.util.LinkedHashMap [C] 

+--java.util.WeakHashMap [C] 

[I]：接口 

[C]：類 

Collection是集合接口         |————Set子接口:無序，不允許重複。         |————List子接口:有序，可以有重複元素。   差別：Collections是集合類   Set和List對比： Set：檢索元素效率低下，删除和插入效率高，插入和删除不會引起元素位置改變。 List：和數組類似，List可以動态增長，查找元素效率高，插入删除元素效率低，因為會引起其他元素位置改變。

  同時， List 還提供一個 listIterator() 方法，傳回一個 ListIterator 接口對象，和 Iterator 接口相比， ListIterator 添加元素的添加，删除，和設定等方法，還能向前或向後周遊。  

Set和List具體子類： Set  |————HashSet：以哈希表的形式存放元素，插入删除速度很快。   List  |————ArrayList：動态數組  |————LinkedList：連結清單、隊列、堆棧。   Array和java.util.Vector Vector是一種老的動态數組，是線程同步的，效率很低，一般不贊成使用。 三，對集合操作的工具類  Java提供了java.util.Collections，以及java.util.Arrays類簡化對集合的操作 

java.util.Collections主要提供一些static方法用來操作或建立Collection，Map等集合。 

java.util.Arrays主要提供static方法對數組進行操作。 

四、集合架構之外的Map接口

Map将鍵映射到值的對象。一個映射不能包含重複的鍵；每個鍵最多隻能映射一個值。

Map接口是Dictionary（字典）抽象類的替代品。

Map 接口提供三種collection 視圖，允許以鍵集、值集合或鍵-值映射關系集的形式檢視某個映射的内容。映射的順序 定義為疊代器在映射的 collection 視圖中傳回其元素的順序。某些映射實作可明確定證其順序，如 TreeMap 類；某些映射實作則不保證順序，如 HashMap 類。

有兩個常見的已實作的子類：

HashMap：基于哈希表的 Map 接口的實作。此實作提供所有可選的映射操作，并允許使用 null 值和 null 鍵。（除了不同步和允許使用 null 之外，HashMap 類與 Hashtable 大緻相同。）此類不保證映射的順序，特别是它不保證該順序恒久不變。

TreeMap：它實作SortedMap 接口的基于紅黑樹的實作。此類保證了映射按照升序順序排列關鍵字，根據使用的構造方法不同，可能會按照鍵的類的自然順序 進行排序（參見 Comparable），或者按照建立時所提供的比較器進行排序。

Hashtable：此類實作一個哈希表，該哈希表将鍵映射到相應的值。任何非 null 對象都可以用作鍵或值。

五、線程安全類

在集合架構中，有些類是線程安全的，這些都是JDK1.1中的出現的。在JDK1.2之後，就出現許許多多非線程安全的類。

下面是這些線程安全的同步的類：

Vector：就比ArrayList多了個同步化機制（線程安全）。

Statck：堆棧類，先進後出。

Hashtable：就比HashMap多了個線程安全。

Enumeration：枚舉，相當于疊代器。

除了這些之外，其他的都是非線程安全的類和接口。

線程安全的類其方法是同步的，每次隻能一個通路。是重量級對象，效率較低。對于非線程安全的類和接口，在多線程中需要程式員自己處理線程安全問題。

六，

1. Hash表

Hash表是一種資料結構，用來查找對象。Hash表為每個對象計算出一個整數，稱為Hash Code(哈希碼)。Hash表是個連結式清單的陣列。每個清單稱為一個buckets(哈希表元)。對象位置的計算　index = HashCode % buckets (HashCode為對象哈希碼，buckets為哈希表元總數)。

當你添加元素時，有時你會遇到已經填充了元素的哈希表元，這種情況稱為Hash Collisions(哈希沖突)。這時，你必須判斷該元素是否已經存在于該哈希表中。

如果哈希碼是合理地随機分布的，并且哈希表元的數量足夠大，那麼哈希沖突的數量就會減少。同時，你也可以通過設定一個初始的哈希表元數量來更好地控制哈 希表的運作。初始哈希表元的數量為　buckets = size * 150% + 1 (size為預期元素的數量)。

如果哈希 表中的元素放得太滿，就必須進行rehashing(再哈希)。再哈希使哈希表元數增倍，并将原有的對象重新導入新的哈希表元中，而原始的哈希表元被删 除。load factor(加載因子)決定何時要對哈希表進行再哈希。在Java程式設計語言中，加載因子預設值為0.75，預設哈希表元為101。

2. Comparable接口和Comparator接口

在“集合架構”中有兩種比較接口：Comparable接口和Comparator接口。像String和Integer等Java内建類實作 Comparable接口以提供一定排序方式，但這樣隻能實作該接口一次。對于那些沒有實作Comparable接口的類、或者自定義的類，您可以通過 Comparator接口來定義您自己的比較方式。

3. Comparable接口

在java.lang包中，Comparable接口适用于一個類有自然順序的時候。假定對象集合是同一類型，該接口允許您把集合排序成自然順序。

(1) int compareTo(Object o): 比較目前執行個體對象與對象o，如果位于對象o之前，傳回負值，如果兩個對象在排序中位置相同，則傳回0，如果位于對象o後面，則傳回正值

在 Java 2 SDK版本1.4中有二十四個類實作Comparable接口。下表展示了8種基本類型的自然排序。雖然一些類共享同一種自然排序，但隻有互相可比的類才能排序。

類	排序
BigDecimal,BigInteger,Byte, Double, Float,Integer,Long,Short	按數字大小排序
Character	按 Unicode 值的數字大小排序
String	按字元串中字元 Unicode 值排序

利用Comparable接口建立您自己的類的排序順序，隻是實作compareTo()方法的問題。通常就是依賴幾個資料成員的自然排序。同時類也應該覆寫equals()和hashCode()以確定兩個相等的對象傳回同一個哈希碼。

4. Comparator接口

若一個類不能用于實作java.lang.Comparable，或者您不喜歡預設的Comparable行為并想提供自己的排序順序(可能多種排序方式)，你可以實作Comparator接口，進而定義一個比較器。

(1)int compare(Object o1, Object o2): 對兩個對象o1和o2進行比較，如果o1位于o2的前面，則傳回負值，如果在排序順序中認為o1和o2是相同的，傳回0，如果o1位于o2的後面，則傳回正值

“與Comparable相似，0傳回值不表示元素相等。一個0傳回值隻是表示兩個對象排在同一位置。由Comparator使用者決定如何處理。如果兩個不相等的元素比較的結果為零，您首先應該确信那就是您要的結果，然後記錄行為。”

(2)boolean equals(Object obj): 訓示對象obj是否和比較器相等。

“該方法覆寫Object的equals()方法，檢查的是Comparator實作的等同性，不是處于比較狀态下的對象。”