Map List Set等集合類：
一、概述
在JAVA的util包中有兩個所有集合的父接口Collection和Map,它們的父子關系：
+Collection 這個接口extends自 –java.lang.Iterable接口
├+List(接口 代表有序，可重復的集合。列表）
│├ ArreyList (Class 數組，隨機訪問，沒有同步，線程不安全)
│├ Vector (Class 數組 同步 線程全)
│├ LinkedList (Class 鏈表 插入刪除 沒有同步 線程不安全)
│└ Stack (Class)
└+Set（接口 不能含重復的元素。僅接收一次并做內部排序，集）
│├ HashSet (Class）
│├ LinkedHashSet (Class）
│└ TreeSet (Class）
+Map(接口)
├ +Map(接口 映射集合)
│ ├ HashMap (Class 不同步，線程不安全。除了不同和允許使用null 鍵值之外，與Hashtable大致相同)
│ ├ Hashtable (Class 同步 ，線程安全 。不允許實施null 鍵值)
│ ├ +SortedMap 接口
│ │ ├ TreeMap (Class)
│ ├ WeakHashMap (Class)
以下對眾多接口和類的簡單說明：首先不能不先說一下數組（Array）
1、效率高，但容量固定且無法動態改變。array還有一個缺點是，無法判斷其中實際存有多少元素，length只是告訴我們array的容量。
2、Java中有一個Arrays類，專門用來操作array。
arrays中擁有一組static函數，
equals()：比較兩個array是否相等。array擁有相同元素個數，且所有對應元素兩兩相等。
fill()：將值填入array中。
sort()：用來對array進行排序。
binarySearch()：在排好序的array中尋找元素。
System.arraycopy()：array的復制。
一、數組Array和集合的區別：
1) 數組是大小固定的，并且同一個數組只能存放類型一樣的數據（基本類型/引用類型）
2) JAVA集合可以存儲和操作數目不固定的一組數據。
3) 若程序時不知道究竟需要多少對象，需要在空間不足時自動擴增容量，則需要使用容器類庫，array不適用。
二 set map list的區別
都是集合接口
set －－其中的值不允許重復，無序的數據結構
list －－其中的值允許重復，因為其為有序的數據結構
map－－成對的數據結構，健值必須具有唯一性（鍵不能同，否則值替換）
List 按對象進入的順序保存對象，不做排序或編輯操作。
Set對每個對象只接受一次，并使用自己內部的排序方法（通常，你只關心某個元素是否屬于Set,而不關心它的順序–否則應該使用List）。
Map同樣對每個元素保存一份，但這是基于"鍵"的，Map也有內置的排序，因而不關心元素添加的順序。如果添加元素的順序對你很重要，應該使用 LinkedHashSet或者LinkedHashMap.
Collection 是對象集合， Collection 有兩個子接口 List 和 Set
List 可以通過下標 (1,2..)
來取得值，值可以重復
而 Set 只能通過游標來取值，并且值是不能重復的
ArrayList ， Vector ， LinkedList 是 List 的實現類
ArrayList 是線程不安全的， Vector 是線程安全的，這兩個類底層都是由數組實現的
LinkedList 是線程不安全的，底層是由鏈表實現的
Map 是鍵值對集合
HashTable 和 HashMap 是 Map 的實現類
HashTable 是線程安全的，不能存儲 null 值
HashMap 不是線程安全的，可以存儲 null 值
三、 Collections類和Collection接口
Collections是針對集合類的一個幫助類，他提供一系列靜態方法實現對各種集合的搜索、排序、線程安全化等操作。
Collection是最基本的集合接口，一個Collection代表一組Object，即Collection的元素（Elements）。一些 Collection允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的 類，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。
所有實現 Collection 接口的類都必須提供兩個標準的構造函數：無參數的構造函數用于創建一個空的 Collection ，有一個 Collection 參數的構造函數用于創建一個新的 Collection ，這個新的 Collection
與傳入的 Collection 有相同的元素。后一個構造函數允許用戶復制一個 Collection 。
集合類的遍歷:遍歷通用Collection:
如何遍歷 Collection 中的每一個元素？不論 Collection 的實際類型如何，它都支持一個 iterator() 的方法，該方法返回一個迭代子，使用該迭代子即可逐一訪問 Collection 中每一個元素。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個元素
}
由 Collection 接口派生的兩個接口是 List 和 Set 。 List 按對象進入的順序保存對象，不做排序或編輯操作。 Set 對每個對象只接受一次，并使用自己內部的排序方法 ( 通常，你只關心某個元素是否屬于 Set, 而不關心它的順序–
否則應該使用 List) 。
四、 List接口，有序可重復的集合
實際上有兩種List: 一種是基本的ArrayList,其優點在于隨機訪問元素，另一種是更強大的LinkedList,它并不是為快速隨機訪問設計的，而是具有一套更通用的方法。
List : 次序是List最重要的特點：它保證維護元素特定的順序。List為Collection添加了許多方法，使得能夠向List中間插入與移除元素（這只推薦LinkedList使用。）一個List可以生成ListIterator,使用它可以從兩個方向遍歷List,也可以從List中間插入和移除元素。
1. ArrayList類
1) ArrayList實現了可變大小的數組。它允許所有元素，包括null。ArrayList沒有同步。
2) size，isEmpty，get，set方法運行時間為常數。但是add方法開銷為分攤的常數，添加n個元素需要O(n)的時間。其他的方法運行時間為線性。
3) 每個ArrayList實例都有一個容量（Capacity），即用于存儲元素的數組的大小。這個容量可隨著不斷添加新元素而自動增加，但是增長算法 并沒有定義。當需要插入大量元素時，在插入前可以調用ensureCapacity方法來增加ArrayList的容量以提高插入效率。
4) 和LinkedList一樣，ArrayList也是非同步的（unsynchronized）。
5) 由數組實現的List。允許對元素進行快速隨機訪問，但是向List中間插入與移除元素的速度很慢。ListIterator只應該用來由后向前遍歷ArrayList,而不是用來插入和移除元素。因為那比LinkedList開銷要大很多。
2. Vector類
Vector非常類似ArrayList，但是Vector是同步的。由Vector創建的Iterator，雖然和ArrayList創建的Iterator是同一接口，但是，因為Vector是同步的，當一個Iterator被創建而且正在被使用，另一個線程改變了Vector的狀態（例如，添加或刪除了一些元素），這時調用Iterator的方法時將拋出ConcurrentModificationException，因此必須捕獲該異常。
3. LinkedList類
LinkedList實現了List接口，允許null元素。此外LinkedList提供額外的get，remove，insert方法在 LinkedList的首部或尾部。如下列方法：addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 這些方法 （沒有在任何接口或基類中定義過）。這些操作使LinkedList可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。
注意LinkedList沒有同步方法。如果多個線程同時訪問一個List，則必須自己實現訪問同步。一種解決方法是在創建List時構造一個同步的List：
List list = Collections.synchronizedList(new LinkedList(…));
4. Stack 類
Stack繼承自Vector，實現一個后進先出的堆棧。Stack提供5個額外的方法使得Vector得以被當作堆棧使用?；镜膒ush和pop方法，還有peek方法得到棧頂的元素，empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。Stack剛創建后是空棧。
用法：
package Test;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class TestList {
public static void main(String dd[]) {
// new了一個存儲list
List l = new ArrayList();
// 因為Collection framework只能存儲對象所以new封裝類
l.add(new Integer(1));
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(4));
Iterator it = l.iterator();
//使用 迭代器（Iterator）:
// hasNext是取值取的是當前值.他的運算過程是判斷下個是否有值如果有繼續.
while (it.hasNext()) {
System.out.println("iterator：Element in list is : " + it.next());
}
//用for循環和get()方法：
for (int i = 0; i < l.size(); i++) {
System.out.println("for：Element in list is : " + l.get(i));
}
}
}
LinkedList
package Test;
import java.util.Iterator;
import java.util.LinkedList;
public class TestLinkedList {
public static void main(String arg[]) {
LinkedList ll = new LinkedList();// 聲明LinkedList并實例化
// 使用add（）方法添加元素
ll.add("a");
ll.add("b");
ll.add("c");
// 使用Iterator迭代器遍歷出集合的元素并打印
Iterator it = ll.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
System.out.println("------------------");
// 向鏈表頭和尾分別添加x和z
ll.addFirst("z");
ll.addLast("x");
// 遍歷查看添加后的結果
for (Iterator i = ll.iterator(); i.hasNext();) {
System.out.println(i.next());
}
}
}
ArrayList和LinkedList的區別。
1.ArrayList是實現了基于動態數組的數據結構，LinkedList基于鏈表的數據結構。
2.對于隨機訪問get和set，ArrayList覺得優于LinkedList，因為LinkedList要移動指針。
3.對于新增和刪除操作add和remove，LinedList比較占優勢，因為ArrayList要移動數據。
如果熟悉數據結構的同學，就會一下明白，ArrayList就是線性表的順序表示，LinkedList就是線性表的鏈表表示。
五、 Set接口，代表無序，不可重復的集合
Set具有與Collection完全一樣的接口，因此沒有任何額外的功能，不像前面有兩個不同的List。實際上Set就是Collection,只是行為不同。（這是繼承與多態思想的典型應用：表現不同的行為。）Set不保存重復的元素（至于如何判斷元素相同則較為負責）
Set : 存入Set的每個元素都必須是唯一的，因為Set不保存重復元素。加入Set的元素必須定義equals()方法以確保對象的唯一性。Set與Collection有完全一樣的接口。Set接口不保證維護元素的次序。
1. HashSet
為快速查找設計的Set。存入HashSet的對象必須定義hashCode()。
2. TreeSet
保存次序的Set, 底層為樹結構。使用它可以從Set中提取有序的序列。
3. LinkedHashSet
具有HashSet的查詢速度，且內部使用鏈表維護元素的順序（插入的次序）。于是在使用迭代器遍歷Set時，結果會按元素插入的次序顯示。
用法：
Set set=new HashSet();
String s1=new String("hello");
String s2=s1;
String s3=new String("world");
set.add(s1);
set.add(s2);
set.add(s3);
System.out.println(set.size());//打印集合中對象的數目 為 2。
Set 的 add()方法是如何判斷對象是否已經存放在集合中？
boolean isExists=false;
Iterator iterator=set.iterator();
while(it.hasNext()) {
String oldStr=it.next();
if(newStr.equals(oldStr)){
isExists=true;
}
}
六、 Map接口：映射
Map沒有繼承Collection接口， Map 提供 key 到 value 的映射，你可以通過“鍵”查找“值”。一個 Map 中不能包含相同的 key ，每個 key 只能映射一個 value 。 Map 接口提供3
種集合的視圖， Map 的內容可以被當作一組 key 集合，一組 value 集合，或者一組 key–value 映射。
方法 put(Object key, Object value) 添加一個“值” ( 想要得東西 ) 和與“值”相關聯的“鍵” (key) ( 使用它來查找 ) 。方法get(Object
key) 返回與給定“鍵”相關聯的“值”?？梢杂?containsKey() 和 containsValue() 測試 Map 中是否包含某個“鍵”或“值”。 標準的 Java 類庫中包含了幾種不同的 Map ： HashMap, TreeMap, LinkedHashMap, WeakHashMap, IdentityHashMap 。它們都有同樣的基本接口 Map ，但是行為、效率、排序策略、保存對象的生命周期和判定“鍵”等價的策略等各不相同。
Map 同樣對每個元素保存一份，但這是基于 " 鍵"
的， Map 也有內置的排序，因而不關心元素添加的順序。如果添加元素的順序對你很重要，應該使用 LinkedHashSet 或者 LinkedHashMap.
執行效率是 Map 的一個大問題?？纯?get() 要做哪些事，就會明白為什么在 ArrayList 中搜索“鍵”是相當慢的。而這正是 HashMap 提高速度的地方。 HashMap 使用了特殊的值，稱為“散列碼” (hash code) ，來取代對鍵的緩慢搜索?！吧⒘写a”是“相對唯一”用以代表對象的int
值，它是通過將該對象的某些信息進行轉換而生成的（在下面總結二：需要的注意的地方有更進一步探討）。所有 Java 對象都能產生散列碼，因為 hashCode() 是定義在基類 Object 中的方法 。 HashMap 就是使用對象的 hashCode() 進行快速查詢的。此方法能夠顯著提高性能。
1. Hashtable類
Hashtable繼承Map接口，實現一個key-value映射的哈希表。任何非空（non-null）的對象都可作為key或者value。Hashtable是同步的。
添加數據使用 put(key, value) ，取出數據使用get(key)
，這兩個基本操作的時間開銷為常數。
Hashtable 通過初始化容量 (initial capacity) 和負載因子 (load factor) 兩個參數調整性能。通常缺省的 load factor0.75 較好地實現了時間和空間的均衡。增大 load factor 可以節省空間但相應的查找時間將增大，這會影響像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));
要取出一個數，比如 2 ，用相應的 key ：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two=
”+ n);
由于作為 key 的對象將通過計算其散列函數來確定與之對應的 value 的位置，因此任何作為 key 的對象都必須實現 hashCode 方法和 equals 方法。 hashCode 方法和 equals 方法繼承自根類 Object ，如果你用自定義的類當作 key 的話，要相當小心，按照散列函數的定義，如果兩個對象相同，即 obj1.equals(obj2)=true
，則它們的 hashCode 必須相同，但如果兩個對象不同，則它們的 hashCode 不一定不同，如果兩個不同對象的 hashCode 相同，這種現象稱為沖突，沖突會導致操作哈希表的時間開銷增大，所以盡量定義好的 hashCode() 方法，能加快哈希表的操作。
如果相同的對象有不同的 hashCode ，對哈希表的操作會出現意想不到的結果（期待的 get 方法返回null
），要避免這種問題，只需要牢記一條：要同時復寫 equals 方法和 hashCode 方法，而不要只寫其中一個。
Hashtable 是同步的。
2. HashMap類
HashMap和Hashtable類似，也是基于hash散列表的實現。不同之處在于 HashMap是非同步的，并且允許null，即null value和null key。，但是將HashMap視為Collection時 （values()方法可返回Collection），其迭代子操作時間開銷和HashMap的容量成比例。因此，如果迭代操作的性能相當重要的話，不要 將HashMap的初始化容量設得過高，或者load factor過低。
LinkedHashMap 類：類似于 HashMap ，但是迭代遍歷它時，取得“鍵值對”的順序是其插入次序，或者是最近最少使用 (LRU) 的次序。只比 HashMap 慢一點。而在迭代訪問時發而更快，因為它使用鏈表維護內部次序。
3. WeakHashMap類 （弱鍵（ weak key ））
WeakHashMap是一種改進的HashMap，它是為解決特殊問題設計的，它對key實行“弱引用”，如果一個key不再被外部所引用，那么該key可以被GC回收。
4. TreeMap 類
基于紅黑樹數據結構的實現。查看“鍵”或“鍵值對”時，它們會被排序 ( 次序由 Comparabel 或 Comparator 決定 ) 。 TreeMap 的特點在于，你得到的結果是經過排序的。 TreeMap 是唯一的帶有 subMap() 方法的 Map ，它可以返回一個子樹。
5. IdentifyHashMap 類
使用 == 代替 equals() 對“鍵”作比較的 hash map 。專為解決特殊問題而設計。
用法：
1 添加，刪除操作：
Object put(Object key, Object value): 向集合中加入元素 Object remove(Object key): 刪除與KEY相關的元素 void putAll(Map t): 將來自特定映像的所有元素添加給該映像 void clear(): 從映像中刪除所有映射
2 查詢操作：
Object get(Object key): 獲得與關鍵字key相關的值
Map集合中的鍵對象不允許重復，也就說，任意兩個鍵對象通過equals()方法比較的結果都是false.
但是可以將任意多個鍵獨享映射到同一個值對象上。
Conllections : 集合實用類
Conllections提供了供JAVA集合實用的靜態方法
七、 如何選擇
1、容器類和Array的區別、擇取
1)容器類僅能持有對象引用（指向對象的指針），而不是將對象信息copy一份至數列某位置。
2)一旦將對象置入容器內，便損失了該對象的型別信息。
2、
1) 在各種Lists中，最好的做法是以ArrayList作為缺省選擇。當插入、刪除頻繁時，使用LinkedList()；
Vector總是比ArrayList慢，所以要盡量避免使用。
2) 在各種Sets中，HashSet通常優于HashTree（插入、查找）。只有當需要產生一個經過排序的序列，才用TreeSet。
HashTree存在的唯一理由：能夠維護其內元素的排序狀態。
3) 在各種Maps中,HashMap用于快速查找。
4) 當元素個數固定，用Array，因為Array效率是最高的。
結論：最常用的是ArrayList，HashSet，HashMap，Array。而且，我們也會發現一個規律，用TreeXXX都是排序的。
注意：
1、Collection沒有get()方法來取得某個元素。只能通過iterator()遍歷元素。
2、Set和Collection擁有一模一樣的接口。
3、List，可以通過get()方法來一次取出一個元素。使用數字來選擇一堆對象中的一個，get(0)…。(add/get)
4、一般使用ArrayList。用LinkedList構造堆棧stack、隊列queue。
5、Map用 put(k,v) / get(k)，還可以使用containsKey()/containsValue()來檢查其中是否含有某個key/value。
HashMap會利用對象的hashCode來快速找到key。
* hashing
哈希碼就是將對象的信息經過一些轉變形成一個獨一無二的int值，這個值存儲在一個array中。
我們都知道所有存儲結構中，array查找速度是最快的。所以，可以加速查找。
發生碰撞時，讓array指向多個values。即，數組每個位置上又生成一個梿表。
6、Map中元素，可以將key序列、value序列單獨抽取出來。
使用keySet()抽取key序列，將map中的所有keys生成一個Set。
使用values()抽取value序列，將map中的所有values生成一個Collection。
為什么一個生成Set，一個生成Collection？那是因為，key總是獨一無二的，value允許重復。
轉自：http://blog.csdn.net/hguisu/article/details/7644395
原創文章，作者：s19930811，如若轉載，請注明出處：http://www.www58058.com/2811
