集合框架體系概述

1. 為什么出現(xiàn)集合類?
   方便多個對象的操作,就對對象進行存儲,集合就是存儲對象最常用的一種方法.

2. 數(shù)組和集合類同時容器, 有何不可?

• 數(shù)組雖然也可存儲對象,但長度固定; 而集合長度可變
• 集合只用于存儲對象, 集合長度是可變的, 集合可以存儲不同類型的對象.

Java 集合定義了兩種基本的數(shù)據(jù)結構植锉，一種是 Collection范舀，表示一組對象的集合荡含；另一種是Map零酪，表示對象間的一系列映射或關聯(lián)關系。Java 集合的基本架構如下圖驮肉。

集合類及其繼承關系

在這種架構中熏矿，Set 是一種 Collection，不過其中沒有重復的對象离钝； List 也是一種Collection 票编，其中的元素按順序排列（不過可能有重復）。
SortedSet 和 SortedMap 是特殊的集和映射卵渴，其中的元素按順序排列慧域。
Collection、Set 浪读、List 昔榴、Map 辛藻、SortedSet和 SortedMap 都是接口，不過 java.util 包定義了多個具體實現(xiàn)互订，例如基于數(shù)組和鏈表的列表吱肌，基于哈希表或二叉樹的映射和集。除此之外屁奏，還有兩個重要的接口岩榆， Iterator 和 Iterable 错负，用于遍歷集合中的對象坟瓢，稍后會介紹。

Collection共性方法

注意: 集合存儲的都是對象的引用(地址)

boolean add(E e)添加指定的元素(可選操作)     
boolean addAll(Collection<? extends E> c) 將指定 collection 中的所有元素都添加到此 collection 中（可選操作）犹撒。 
clear(): 清空集合中所有元素     
boolean contains(Object o) 是否包含指定元素     
boolean containsAll(Collection<?> c) 只判斷參數(shù)中的集合是否都包含在A集合內(nèi),最終A集合沒有任何變化.     
boolean isEmpty() 判斷是否為空     
boolean remove(Object o)   移除單個實例     
boolean removeAll(Collection<?> c)  取差集    
boolean retainAll(Collection<?> c)  取交集     
int size():返回collection中的元素     
Object[] toArray() 這個可以理解     
<T> T[]  toArray(T[] a)  //應這么寫String[] y =  c.toArray(new String[collection.size()])較好

// 創(chuàng)建幾個集合折联，供后面的代碼使用
Collection<String> c = new HashSet<>(); // 一個空集
Collection<String> d = Arrays.asList("one", "two");
Collection<String> e = Collections.singleton("three");

// 向集合中添加一些元素
// 如果集合的內(nèi)容變化了，這些方法返回true
// 這種表現(xiàn)對不允許重復的Set類型很有用
c.add("zero");           // 添加單個元素
c.addAll(d);             // 添加d中的所有元素

// 復制集合：多數(shù)實現(xiàn)都有副本構造方法
Collection<String> copy = new ArrayList<String>(c);

// 把元素從集合中移除识颊。
// 除了clear()方法之外诚镰，如果集合的內(nèi)容變化了，都返回true
c.remove("zero");        // 移除單個元素
c.removeAll(e);          // 移除一組元素
c.retainAll(d);          // 移除不在集合d中的所有元素
c.clear();               // 移除所有元素

// 獲取集合的大小
boolean b = c.isEmpty(); // c是空的祥款，所以返回true
int s = c.size();        // 現(xiàn)在c的大小是0

// 使用前面創(chuàng)建的副本復原集合
c.addAll(copy);

// 測試元素是否在集合中清笨。測試基于equals()方法，而不是==運算符
b = c.contains("zero");  // true
b = c.containsAll(d);    // true

// 多數(shù)Collection實現(xiàn)都有toString()方法
System.out.println(c);

// 使用集合中的元素創(chuàng)建一個數(shù)組刃跛。
// 如果迭代器能保證特定的順序抠艾，數(shù)組就有相同的順序
// 得到的數(shù)組是個副本，而不是內(nèi)部數(shù)據(jù)結構的引用
Object[] elements = c.toArray();

// 如果想把集合中的元素存入String[]類型的數(shù)組桨昙，必須在參數(shù)中指定這個類型
String[] strings = c.toArray(new String[c.size()]);

// 或者傳入一個類型為String[]的空數(shù)組检号，指定所需的類型
// toArray()方法會為這個數(shù)組分配空間
strings = c.toArray(new String[0]);

記住，上述各個方法都能用于 Set蛙酪、List 或 Queue齐苛。這幾個子接口可能會對集合中的元素做些限制或有順序上的約束，但都提供了相同的基本方法桂塞。

修改集合的方法凹蜂，例如 add()、remove()阁危、clear() 和 retainAll()炊甲，是可選的 API。不過欲芹，這個規(guī)則在很久以前就定下了卿啡，那時認為如果不提供這些方法，明智的做法是拋出 UnsupportedOperationException 異常菱父。因此颈娜，某些實現(xiàn)（尤其是只讀方法）可能會拋出未檢異常剑逃。

• Collection (集合)和 Map(映射) 及其子接口都沒擴展 Cloneable 或 Serializable 接口。不過官辽，在 Java 集合框架中蛹磺，實現(xiàn)集合和映射的所有類都實現(xiàn)了這兩個接口。
• 有些集合對其可以包含的元素做了限制同仆。例如萤捆，有的集合禁止使用 null 作為元素。EnumSet 要求其中的元素只能是特定的枚舉類型俗批。
• 如果嘗試把禁止使用的元素添加到集合中俗或，會拋出未檢異常，例如 NullPointerException 或 ClassCastException岁忘。檢查集合中是否包含禁止使用的元素辛慰，可能也會拋出這種異常，或者僅僅返回 false干像。

List接口

List 是一組有序的對象集合帅腌。列表中的每個元素都有特定的位置，而且 List 接口定義了一些方法麻汰，用于查詢或設定特定位置（或叫索引）的元素速客。從這個角度來看，List 對象和數(shù)組類似五鲫，不過列表的大小能按需變化溺职，以適應其中元素的數(shù)量。和Set不同臣镣，列表允許出現(xiàn)重復的元素辅愿。

除了基于索引的 get() 和 set() 方法之外，List 接口還定義了一些方法忆某，用于把元素添加到特定的索引点待，把元素從特定的索引移除，或者返回指定值在列表中首次出現(xiàn)或最后出現(xiàn)的索引弃舒。從 Collection 接口繼承的 add() 和 remove() 方法癞埠，前者把元素添加到列表末尾，后者把指定值從列表中首次出現(xiàn)的位置移除聋呢。繼承的 addAll() 方法把指定集合中的所有元素添加到列表的末尾苗踪，或者插入指定的索引。retainAll() 和 removeAll() 方法的表現(xiàn)與其他 Collection 對象一樣削锰，如果需要通铲，會保留或刪除多個相同的值。

List 接口沒有定義操作索引范圍的方法器贩，但是定義了一個 subList() 方法颅夺。這個方法返回一個 List 對象朋截，表示原列表指定范圍內(nèi)的元素。子列表會回饋父列表吧黄，只要修改了子列表部服，父列表立即就能察覺到變化。下述代碼演示了 subList() 方法和其他操作 List 對象的基本方法：

// 創(chuàng)建兩個列表拗慨，供后面的代碼使用
List<String> l = new ArrayList<String>(Arrays.asList(args));
List<String> words = Arrays.asList("hello", "world");

// 通過索引查詢和設定元素
String first = l.get(0);        // 列表的第一個元素
String last = l.get(l.size -1); // 列表的最后一個元素
l.set(0, last);                 // 把最后一個元素變成第一個元素

// 添加和插入元素
// add()方法既可以把元素添加到列表末尾廓八，也可以把元素插入指定索引
l.add(first);       // 把第一個詞添加到列表末尾
l.add(0, first);    // 再把第一個詞添加到列表的開頭
l.addAll(words);    // 把一個集合添加到列表末尾
l.addAll(1, words); // 在第一個詞之后插入一個集合

// 子列表：回饋原列表
List<String> sub = l.subList(1,3); // 第二個和第三個元素
sub.set(0, "hi");                  // 修改l的第二個元素
// 子列表可以把操作限制在原列表索引的子范圍內(nèi)
String s = Collections.min(l.subList(0,4));
Collections.sort(l.subList(0,4));
// 子列表的獨立副本不影響父列表
List<String> subcopy = new ArrayList<String>(l.subList(1,3));

// 搜索列表
int p = l.indexOf(last); // 最后一個詞在哪個位置？
p = l.lastIndexOf(last); // 反向搜索

// 打印last在l中出現(xiàn)的所有索引赵抢。注意剧蹂，使用了子列表
int n = l.size();
p = 0;
do {
    // 創(chuàng)建一個列表，只包含尚未搜索的元素
    List<String> list = l.subList(p, n);
    int q = list.indexOf(last);
    if (q == -1) break;
    System.out.printf("Found '%s' at index %d%n", last, p+q);
    p += q+1;
} while(p < n);

// 從列表中刪除元素
l.remove(last);         // 把指定元素從首次出現(xiàn)的位置上刪除
l.remove(0);            // 刪除指定索引對應的元素
l.subList(0,2).clear(); // 使用subList()方法昌讲，刪除一個范圍內(nèi)的元素
l.retainAll(words);     // 刪除所有不在words中的元素
l.removeAll(words);     // 刪除所有在words中的元素
l.clear();              // 刪除所有元素

重點講講用于查找的Iterator迭代器接口
Iterator it = al.iterator();
實際上是集合類在List和Set都包含的iterator方法,返回Iterator對象,具體實現(xiàn)方式是內(nèi)部類.可以認為是繼承了AbstractList,實現(xiàn)了Iterable接口.把取出方式定義成內(nèi)部類,每個容器的數(shù)據(jù)結構不同,取出的動作細節(jié)也不一樣.但是都用共性的判斷和取出,可以將共性方法抽取.對外提供了Iterator方法.

集合中的迭代器

     //一般寫法
     while(it.hasNext()){
          System.out.println(it.next());
     }
 
     //老外為了節(jié)省空間,寫成這樣
     for(Iterator it = al.iterator(); it.hasNext(); ){
          System.out.println(it.next());
     }

List共性方法

(List也被成為序列, 它的對象的元素有序可重復,正因為有序,所以操作角標的方法都是該體系特有的方法)

• 增 void add(int index, E element) 在列表的指定位置插入指定元素（可選操作）国夜。
• 刪 E remove(int index) 移除列表中指定位置的元素（可選操作）减噪。
• 改 E set(int index, E element) 用指定元素替換列表中指定位置的元素（可選操作）短绸。
• 查 ListIterator<E> listIterator() 返回此列表元素的列表迭代器（按適當順序）。
• 獲取 E get(int index) 返回列表中指定位置的元素筹裕。

//由于get(index)方法, list因此多了一種取出所有元素的方法. 但還是常用迭代器
for(int i=0;i<al.size();i++){                　　
    輸出al.get(i);          　　
} 

獲取<E> subList(int fromIndex, int toIndex) 返回列表中指定的 fromIndex(包括)和 toIndex（不包括）之間的部分視圖醋闭。

ListIterator

List有自己更強功能的的ListIterator是Iterator的子接口,是帶下標的.

集合引用和迭代器引用在同時操作元素，通過集合獲取到對應的迭代器后朝卒，在迭代中证逻，進行集合引用的元素添加，迭代器并不知道抗斤，所以會出現(xiàn)ConcurrentModificationException異常情況囚企。ListIterator列表迭代器接口具備了對元素的增、刪瑞眼、改龙宏、查的動作。

原 查 next() 但是 增加了previous()
原 刪 void remove()
增加了特有了

• 增void add(E e)
• 改 void set(E e)
• 和獨有的int nextIndex(), int previousIndex() 和 int nextIndex()

List集合的三個常見子類對象(List有序可重復,因為體系有索引)

• ArrayList: 底層使用數(shù)組結構, 查詢塊,增刪稍慢. 線程不同步, JDK1.2以上
• LinkedList: 底層是鏈表結構, 增刪塊,查詢稍慢, 線程不同步, JDK1.2以上
• Vector: 底層使用數(shù)組結構, 查詢塊,增刪慢. 線程同步.被ArrayList替代了. 枚舉就是Vector特有的取出方式.

ArrayList詳解:擁有角標的方法是其特有方法
可變長度數(shù)組的原理 ：當元素超出數(shù)組長度伤疙，會產(chǎn)生一個新數(shù)組银酗，將原數(shù)組的數(shù)據(jù)復制到新數(shù)組中，再將新的元素添加到新數(shù)組中徒像。

• ArrayList：是按照原數(shù)組的 50%延長構造一個初始容量為10的空列表黍特。
• Vector：是按照原數(shù)組的 100%延長

LinkedList詳解:
特有的add,get,remove方法

//在1.6后新方法        
boolean offerFirst(E e)                
在此列表的開頭插入指定的元素。      
boolean offerLast(E e)                
在此列表末尾插入指定的元素锯蛀。 
E peek()           
獲取但不移除此列表的頭（第一個元素）灭衷。
E peekFirst()                
獲取但不移除此列表的第一個元素；如果此列表為空旁涤，則返回 null翔曲。           
E peekLast()           
獲取但不移除此列表的最后一個元素经备；如果此列表為空，則返回 null部默。            
E pollFirst()                
獲取并移除此列表的第一個元素侵蒙；如果此列表為空，則返回 null傅蹂。           
E pollLast()                
獲取并移除此列表的最后一個元素纷闺；如果此列表為空，則返回 null份蝴。 

Vector(過時)詳解
枚舉是Vector特有的取出方式hasMoreElements()和nextElement()方法,發(fā)現(xiàn)枚舉和迭代器很像.其實枚舉和迭代一樣的.

在List下的ArrayList和LinkedList的contains和remove方法都是使用了Object的equals方法. 可以自己重寫equals方法判斷集合內(nèi)兩對象是否"一致"

隨機訪問列表中的元素

我們一般期望實現(xiàn) List 接口的類能高效迭代犁功，而且所用時間和列表的大小成正比。然而婚夫，不是所有列表都能高效地隨機訪問任意索引上的元素浸卦。按順序訪問的列表，例如 LinkedList 類案糙，提供了高效的插入和刪除操作限嫌，但降低了隨機訪問性能。提供高效隨機訪問的類都實現(xiàn)了標記接口 RandomAccess时捌，因此怒医，如果需要確定是否能高效處理列表，可以使用 instanceof 運算符測試是否實現(xiàn)了這個接口：

// 隨便創(chuàng)建一個列表奢讨，供后面的代碼處理
List<?> l = ...;

// 測試能否高效隨機訪問
// 如果不能稚叹，先使用副本構造方法創(chuàng)建一個支持高效隨機訪問的副本，然后再處理
if (!(l instanceof RandomAccess)) l = new ArrayList<?>(l);

在 List 對象上調(diào)用 iterator() 方法會得到一個 Iterator 對象拿诸，這個對象按照元素在列表中的順序迭代各元素扒袖。List 實現(xiàn)了 Iterable 接口搪柑，因此列表可以像其他集合一樣使用遍歷循環(huán)迭代亏拉。

下表總結了 Java 平臺中五種通用的 List 實現(xiàn)哮翘。Vector 和 Stack 類已經(jīng)過時绞铃，別再用了师坎。CopyOnWriteArrayList 類在 java.util.concurrent 包中狼钮，只適合在多線程環(huán)境中使用卧抗。

實現(xiàn)List接口的類

Set接口

• Set集合的方法和Collection一致,不用多講, 但對這些方法做了限制, 是無重復對象組成的集合

下表列出了實現(xiàn) Set 接口的類读跷，而且總結了各個類的內(nèi)部表示方式啊掏、排序特性蠢络、對成員的限制，以及 add()迟蜜、remove()刹孔、contains 等基本操作和迭代的性能。這些類的詳細信息，請參見各自的文檔髓霞。注意卦睹，CopyOnWriteArraySet 類在 java.util.concurrent 包中，其他類則在 java.util 包中方库。還要注意结序，java.util.BitSet 類沒有實現(xiàn) Set 接口，這個類過時了纵潦，用于緊湊而高效地表示布爾值組成的列表徐鹤，但不是 Java 集合框架的一部分。

實現(xiàn)Set接口的類

SortedSet(接口)

SortedSet 接口提供了多個有趣的方法邀层，這些方法都考慮到了元素是有順序的返敬，如下述代碼所示：

public static void testSortedSet(String[] args) {
    // 創(chuàng)建一個SortedSet對象
    SortedSet<String> s = new TreeSet<>(Arrays.asList(args));

    // 迭代集：元素已經(jīng)自動排序
    for (String word : s) {
        System.out.println(word);
    }

    // 特定的元素
    String first = s.first(); // 第一個元素
    String last = s.last();   // 最后一個元素

    // 除第一個元素之外的其他所有元素
    SortedSet<String> tail = s.tailSet(first + '\0');
    System.out.println(tail);

    // 除最后一個元素之外的其他所有元素
    SortedSet<String> head = s.headSet(last);
    System.out.println(head);

    SortedSet<String> middle = s.subSet(first+'\0', last);
    System.out.println(middle);
}

必須加上 \0 字符，因為 tailSet() 等方法要使用某個元素后面的元素寥院，對字符串來說劲赠，要在后面加上 NULL 字符（對應于 ASCII 中的 0）。

TreeSet(類)

TreeSet 類使用紅黑樹數(shù)據(jù)結構維護集秸谢，這個集中的元素按照 Comparable 對象的自然順序升序迭代凛澎，或者按照 Comparator 對象指定的順序迭代。其實钮追，TreeSet 實現(xiàn)的是 Set 的子接口预厌，SortedSet 接口阿迈。

TreeSet排序

• 第一種方式: 需要比較的對象實現(xiàn)Comparable接口,覆蓋int compareTo()方法,讓元素自身具備比較性
• 第二種方式:構造實現(xiàn)java.util.Comparator接口,覆蓋int compare(T o1, T o2)方法,將比較器對象作為參數(shù)傳遞給TreeSet集合的構造函數(shù).

HashSet(線程不同步)

• 底層數(shù)據(jù)結構是哈希表,線程非同步.
• 通過hasHashCode()和equals()來完成
• 如果元素的HashCode相同,才會判斷equals是否為true
• 如果元素的HashCode不同,不會調(diào)用equals,直接是不等.

注意,對于判斷元素是否存在,以及刪除等操作,依賴的方法依次是hashcode和equals方法. 在使用HashSet,一定要覆蓋int hashCode()和boolean equals (Object obj)方法.

Map接口

將鍵映射到值的對象,一對一對往里存,而且要保證鍵的唯一性.

映射（map）是一系列鍵值對元媚，一個鍵對應一個值。Map 接口定義了用于定義和查詢映射的 API苗沧。Map 接口屬于 Java 集合框架刊棕，但沒有擴展 Collection 接口，因此 Map 只是一種集合待逞，而不是 Collection 類型甥角。Map 是參數(shù)化類型，有兩個類型變量识樱。類型變量 K 表示映射中鍵的類型嗤无，類型變量 V 表示鍵對應的值的類型。例如怜庸，如果有個映射当犯，其鍵是 String 類型，對應的值是 Integer 類型割疾，那么這個映射可以表示為 Map<String,Integer>嚎卫。

Map 接口定義了幾個最有用的方法：put() 方法定義映射中的一個鍵值對，get() 方法查詢指定鍵對應的值宏榕，remove() 方法把指定的鍵及對應的值從映射中刪除拓诸。一般來說侵佃，實現(xiàn) Map 接口的類都要能高效執(zhí)行這三個基本方法：一般應該運行在常數(shù)時間中，而且絕不能比在對數(shù)時間中運行的性能差奠支。

Map 的重要特性之一是馋辈，可以視作集合。雖然 Map 對象不是 Collection 類型倍谜，但映射的鍵可以看成 Set 對象(因此不能有重復元素首有。)，映射的值可以看成 Collection 對象枢劝，而映射的鍵值對可以看成由 Map.Entry 對象組成的 Set 對象井联。（Map.Entry 是 Map 接口中定義的嵌套接口，表示一個鍵值對您旁。）

添加               
    put(K key, V value)               
    putAll(Map<? extends K, ? extends V> m)         
刪除                 
    clear()               
    remove(Object key)          
判斷               
    containsKey(Object key)               
    containsValue(Object value)               
    isEmpty()          
獲取               
    get(Object key)               
    size()               
    values()               
    entrySet()               
    keySet()

下述示例代碼展示了如何使用 get()烙常、put() 和 remove() 等方法操作 Map 對象，還演示了把 Map 對象視作集合后的一些常見用法：

// 新建一個空映射
Map<String,Integer> m = new HashMap();

// 不可變的映射鹤盒，只包含一個鍵值對
Map<String,Integer> singleton = Collections.singletonMap("test", -1);

// 注意蚕脏，極少使用下述句法顯式指定通用方法emptyMap()的參數(shù)類型
// 得到的映射不可變
Map<String,Integer> empty = Collections.<String,Integer>emptyMap();

// 使用put()方法填充映射，把數(shù)組中的元素映射到元素的索引上
String[] words = { "this", "is", "a", "test" };
for(int i = 0; i < words.length; i++) {
    m.put(words[i], i); // 注意侦锯，int會自動裝包成Integer
}

// 一個鍵只能映射一個值
// 不過驼鞭，多個鍵可以映射同一個值
for(int i = 0; i < words.length; i++) {
    m.put(words[i].toUpperCase(), i);
}

// putAll()方法從其他映射中復制鍵值對
m.putAll(singleton);

// 使用get()方法查詢映射
for(int i = 0; i < words.length; i++) {
    if (m.get(words[i]) != i) throw new AssertionError();
}

// 測試映射中是否有指定的鍵和值
m.containsKey(words[0]);       // true
m.containsValue(words.length); // false

// 映射的鍵、值和鍵值對都可以看成集合
Set<String> keys = m.keySet();
Collection<Integer> values = m.values();
Set<Map.Entry<String,Integer>> entries = m.entrySet();

// 映射和上述幾個集合都有有用的toString()方法
System.out.printf("Map: %s%nKeys: %s%nValues: %s%nEntries: %s%n",
                  m, keys, values, entries);

// 可以迭代這些集合
// 多數(shù)映射都沒定義迭代的順序（不過SortedMap定義了）
for(String key : m.keySet()) System.out.println(key);
for(Integer value: m.values()) System.out.println(value);

// Map.Entry<K,V>類型表示映射中的一個鍵值對
for(Map.Entry<String,Integer> pair : m.entrySet()) {
    // 打印鍵值對
    System.out.printf("'%s' ==> %d%n", pair.getKey(), pair.getValue());
    // 然后把每個Entry對象的值增加1
    pair.setValue(pair.getValue() + 1);
}

// 刪除鍵值對
m.put("testing", null);   // 映射到null上可以“擦除”一個鍵值對
m.get("testing");         // 返回null
m.containsKey("testing"); // 返回true：鍵值對仍然存在
m.remove("testing");      // 刪除鍵值對
m.get("testing");         // 還是返回null
m.containsKey("testing"); // 這次返回false

// 也可以把映射視作集合尺碰，然后再刪除
// 不過挣棕，向集合中添加鍵值對時不能這么做
m.keySet().remove(words[0]); // 等同于m.remove(words[0]);

// 刪除一個值為2的鍵值對——這種方式一般效率不高，用途有限
m.values().remove(2);
// 刪除所有值為4的鍵值對
m.values().removeAll(Collections.singleton(4));
// 只保留值為2和3的鍵值對
m.values().retainAll(Arrays.asList(2, 3));

// 還可以通過迭代器刪除
Iterator<Map.Entry<String,Integer>> iter = m.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry<String,Integer> e = iter.next();
    if (e.getValue() == 2) iter.remove();
}

// 找出兩個映射中都有的值
// 一般來說亲桥，addAll()和retainAll()配合keySet()和values()使用洛心，可以獲取交集和并集
Set<Integer> v = new HashSet<Integer>(m.values());
v.retainAll(singleton.values());

// 其他方法
m.clear();                // 刪除所有鍵值對
m.size();                 // 返回鍵值對的數(shù)量：目前為0
m.isEmpty();              // 返回true
m.equals(empty);          // true：實現(xiàn)Map接口的類覆蓋了equals()方法

實現(xiàn)Map接口的類

java.util.concurrent 包中的 ConcurrentHashMap 和 ConcurrentSkipListMap 兩個類實現(xiàn)了同一個包中的 ConcurrentMap 接口。ConcurrentMap 接口擴展 Map 接口题篷，而且定義了一些對多線程編程很重要的原子操作方法词身。例如，putIfAbsent() 方法番枚，它的作用和 put() 方法類似法严，不過，僅當指定的鍵沒有映射到其他值上時葫笼，才會把鍵值對添加到映射中深啤。

TreeMap 類實現(xiàn) SortedMap 接口。這個接口擴展 Map 接口渔欢，添加了一些方法墓塌，利用這種映射的有序特性。SortedMap 接口和 SortedSet 接口非常相似。firstKey() 和 lastKey() 方法分別返回 keySet() 所得集的第一個和最后一個鍵苫幢。而 headMap()访诱、tailMap() 和 subMap() 方法都返回一個新映射，由原映射特定范圍內(nèi)的鍵值對組成韩肝。

Map集合的共性方法注意

1. 添加元素,如果出現(xiàn)相同的鍵,那么后添加的值會覆蓋原有鍵對應的值, put方法會會返回被覆蓋的值
2. 可通過get方法的返回值來判斷一個鍵是否存在,通過返回null判斷.
3. 獲取map集合中所有的值

兩個重要的獲取方法: keySet()和entrySet()

1. 通過keyset()獲取key的Set集合,然后Iterator獲取key,最終get(Object key) 獲取.
2. 通過entryset()獲取關系,然后Iterator獲取鍵值對,最終Map.Entry的getKey和getValue方法獲取. (其實Map.Entry也是一個接口,它是Map接口中的一個內(nèi)部接口)

Map和Set很像,其實Set底層就是使用了Map集合.

練習TreeMap

• key: 學生Student, value: 地址addr

• 學生屬性:姓名和年齡,注意姓名和年齡相同視為同一個學生,需保證學生的唯一性

  
  

Queue接口和BlockingQueue接口

隊列（queue）是一組有序的元素触菜，提取元素時按順序從隊頭讀取。隊列一般按照插入元素的順序實現(xiàn)哀峻，因此分成兩類：先進先出（first-in, first-out涡相，F(xiàn)IFO）隊列和后進先出（last-in, first-out，LIFO）隊列剩蟀。

LIFO 隊列也叫棧（stack）催蝗，Java 提供了 Stack 類，但強烈不建議使用——應該使用實現(xiàn) Deque 接口的類育特。

隊列也可以使用其他順序：優(yōu)先隊列（priority queue）根據(jù)外部 Comparator 對象或 Comparable 類型元素的自然順序排序元素丙号。與 Set 不同的是，Queue 的實現(xiàn)往往允許出現(xiàn)重復的元素缰冤。而與 List 不同的是犬缨，Queue 接口沒有定義處理任意索引位元素的方法，只有隊列的頭一個元素能訪問棉浸。Queue 的所有實現(xiàn)都要具有一個固定的容量：隊列已滿時怀薛，不能再添加元素。類似地迷郑，隊列為空時枝恋，不能再刪除元素。很多基于隊列的算法都會用到滿和空這兩個狀態(tài)三热，所以 Queue 接口定義的方法通過返回值表明這兩個狀態(tài)鼓择，而不會拋出異常。具體而言就漾，peek() 和 poll() 方法返回 null 表示隊列為空。因此念搬，多數(shù) Queue 接口的實現(xiàn)不允許用 null 作元素抑堡。

阻塞式隊列（blocking queue）是一種定義了阻塞式 put() 和 take() 方法的隊列。put() 方法的作用是把元素添加到隊列中朗徊，如果需要首妖，這個方法會一直等待，直到隊列中有存儲元素的空間為止爷恳。而 take() 方法的作用是從隊頭移除元素有缆，如果需要，這個方法會一直等待，直到隊列中有元素可供移除為止棚壁。阻塞式隊列是很多多線程算法的重要組成部分杯矩，因此 BlockingQueue 接口（擴展 Queue 接口）在 java.util.concurrent 包中定義。

隊列不像集袖外、列表和映射那么常用史隆，只在特定的多線程編程風格中會用到。這里曼验，我們不舉實例泌射，而是試著厘清一些令人困惑的隊列插入和移除操作。

1. 把元素添加到隊列中
add()方法
這個方法在 Collection 接口中定義鬓照，只是使用常規(guī)的方式添加元素熔酷。對有界的隊列來說，如果隊列已滿豺裆，這個方法可能會拋出異常纯陨。

offer()方法
這個方法在 Queue 接口中定義，但是由于有界的隊列已滿而無法添加元素時留储，這個方法返回 false翼抠，而不會拋出異常。
BlockingQueue 接口定義了一個超時版 offer() 方法获讳，如果隊列已滿阴颖，會在指定的時間內(nèi)等待空間。這個版本和基本版一樣丐膝，成功插入元素時返回 true量愧，否則返回 false。

put()方法
這個方法在 BlockingQueue 接口中定義帅矗，會阻塞操作：如果因為隊列已滿而無法插入元素偎肃，put() 方法會一直等待，直到其他線程從隊列中移除元素浑此，有空間插入新元素為止累颂。

2. 把元素從隊列中移除
remove()方法
Collection 接口中定義了 remove() 方法，把指定的元素從隊列中移除凛俱。除此之外紊馏，Queue接口還定義了一個沒有參數(shù)的 remove() 方法，移除并返回隊頭的元素蒲犬。如果隊列為空朱监，這個方法會拋出 NoSuchElementException 異常。

poll()方法
這個方法在 Queue 接口中定義原叮，作用和 remove() 方法類似赫编，移除并返回隊頭的元素巡蘸，不過，如果隊列為空擂送，這個方法會返回 null悦荒，而不拋出異常。
BlockingQueue 接口定義了一個超時版 poll() 方法团甲，在指定的時間內(nèi)等待元素添加到空隊列中逾冬。

take()方法
這個方法在 BlockingQueue 接口中定義，用于刪除并返回隊頭的元素躺苦。如果隊列為空身腻，這個方法會等待，直到其他線程把元素添加到隊列中為止匹厘。

drainTo()方法
這個方法在 BlockingQueue 接口中定義嘀趟，作用是把隊列中的所有元素都移除，然后把這些元素添加到指定的 Collection 對象中愈诚。這個方法不會阻塞操作她按，等待有元素添加到隊列中。這個方法有個變體炕柔，接受一個參數(shù)酌泰，指定最多移除多少個元素。

3. 查詢
就隊列而言匕累，“查詢”的意思是訪問隊頭的元素陵刹，但不將其從隊列中移除。
element()方法
這個方法在 Queue 接口中定義欢嘿，其作用是返回隊頭的元素衰琐，但不將其從隊列中移除。如果隊列為空炼蹦，這個方法拋出 NoSuchElementException 異常羡宙。

peek()方法
這個方法在 Queue 接口中定義，作用和 element() 方法類似掐隐，但隊列為空時狗热，返回 null。

使用隊列時瑟枫，最好選定一種處理失敗的方式斗搞。例如，如果想在操作成功之前一直阻塞慷妙，應該選擇 put() 和 take() 方法；如果想檢查方法的返回值允悦，判斷操作是否成功膝擂，應該選擇 offer() 和 poll() 方法虑啤。

LinkedList 類也實現(xiàn)了 Queue 接口，提供的是無界 FIFO 順序架馋，插入和移除操作需要常數(shù)時間狞山。LinkedList 對象可以使用 null 作元素，不過叉寂，當列表用作隊列時不建議使用 null萍启。

java.util 包中還有另外兩個 Queue 接口的實現(xiàn)。一個是 PriorityQueue
類屏鳍，這種隊列根據(jù)Comparator 對象排序元素勘纯，或者根據(jù) Comparable
類型元素的 compareTo() 方法排序元素。PriorityQueue 對象的隊頭始終是根據(jù)指定排序方式得到的最小值钓瞭。另外一個是 ArrayDeque類驳遵，實現(xiàn)的是雙端隊列，一般在需要用到棧的情況下使用山涡。

java.util.concurrent 包中也包含一些 BlockingQueue 接口的實現(xiàn)堤结，目的是在多線程編程環(huán)境中使用。有些實現(xiàn)很高級鸭丛，甚至無需使用同步方法竞穷。

實用方法

java.util.Collections 類定義了一些靜態(tài)實用方法，用于處理集合鳞溉。其中有一類方法很重要瘾带，是集合的包裝方法：這些方法包裝指定的集合，返回特殊的集合穿挨。包裝集合的目的是把集合本身沒有提供的功能綁定到集合上月弛。包裝集合能提供的功能有：線程安全性、寫保護和運行時類型檢查科盛。包裝集合都以原來的集合為后盾帽衙，因此，在包裝集合上調(diào)用的方法其實會分派給原集合的等效方法完成贞绵。這意味著厉萝，通過包裝集合修改集合后，改動也會體現(xiàn)在原集合身上榨崩；反之亦然谴垫。

第一種包裝方法為包裝的集合提供線程安全性。java.util 包中的集合實現(xiàn)母蛛，除了過時的 Vector 和 Hashtable 類之外翩剪，都沒有 synchronized 方法，不能禁止多個線程并發(fā)訪問彩郊。如果需要使用線程安全的集合前弯，而且不介意同步帶來的額外開銷蚪缀，可以像下面這樣創(chuàng)建集合：

List<String> list =
    Collections.synchronizedList(new ArrayList<String>());
Set<Integer> set =
    Collections.synchronizedSet(new HashSet<Integer>());
Map<String,Integer> map =
    Collections.synchronizedMap(new HashMap<String,Integer>());

第二種包裝方法創(chuàng)建的集合對象不能修改底層集合，得到的集合是只讀的恕出，只要試圖修改集合的內(nèi)容询枚，就會拋出 UnsupportedOperationException 異常。如果要把集合傳入方法浙巫，但不允許修改集合金蜀，也不允許使用任何方式改變集合的內(nèi)容，就可以使用這種包裝集合：

List<Integer> primes = new ArrayList<Integer>();
List<Integer> readonly = Collections.unmodifiableList(primes);
// 可以修改primes列表
primes.addAll(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));
// 但不能修改只讀的包裝集合
readonly.add(23); // 拋出UnsupportedOperationException異常

java.util.Collections 類還定義了用來操作集合的方法的畴。其中最值得關注的是排序和搜索集合元素的方法：

Collections.sort(list);
// 必須先排序列表中的元素
int pos = Collections.binarySearch(list, "key");

Collections 類中還有些方法值得關注：

// 把list2中的元素復制到list1中渊抄，覆蓋list1
Collections.copy(list1, list2);
// 使用對象o填充list
Collections.fill(list, o);
// 找出集合c中最大的元素
Collections.max(c);
// 找出集合c中最小的元素
Collections.min(c);

Collections.reverse(list); // 反轉列表
Collections.shuffle(list); // 打亂列表

Collections.addAll(c, elements ...) // 添加元素

你最好全面熟悉 Collections 和 Arrays 類中的實用方法，這樣遇到常見任務時就不用自己動手實現(xiàn)了苗傅。

特殊的集合
除了包裝方法之外抒线，java.util.Collections 類還定義了其他實用方法，一些用于創(chuàng)建只包含一個元素的不可變集合實例渣慕，一些用于創(chuàng)建空集合嘶炭。singleton()、singletonList() 和 singletonMap() 方法分別返回不可變的 Set逊桦、List 和 Map 對象眨猎，而且只包含一個指定的對象或鍵值對。如果要把單個對象當成集合傳入方法强经，可以使用這些方法睡陪。

Collections 類還定義了一些返回空集合的方法。如果你編寫的方法要返回一個集合匿情，遇到?jīng)]有返回值的情況時兰迫，一般最好返回空集合，而不要返回 null 等特殊的值：

Set<Integer> si = Collections.emptySet();
List<String> ss = Collections.emptyList();
Map<String,Integer> m = Collections.emptyMap();

最后還有個 nCopies() 方法炬称。這個方法返回一個不可變的 List 對象汁果，包含指定數(shù)量個指定對象的副本：
List<Integer> tenzeros = Collections.nCopies(10, 0);

數(shù)組和輔助方法
由對象組成的數(shù)組和集合的作用類似，而且二者之間可以相互轉換：

String[] a ={ "this", "is", "a", "test" }; // 一個數(shù)組
// 把數(shù)組當成大小不可變的列表
List<String> l = Arrays.asList(a);
// 創(chuàng)建一個大小可變的副本
List<String> m = new ArrayList<String>(l);

// asList()是個變長參數(shù)方法玲躯，所以也可以這么做：
Set<Character> abc = new HashSet<Character>(Arrays.asList('a', 'b', 'c'));
// Collection接口定義了toArray()方法据德。不傳入?yún)?shù)時，這個方法創(chuàng)建
// Object[]類型的數(shù)組跷车，把集合中的元素復制到數(shù)組中棘利，然后返回這個數(shù)組
// 把set中的元素存入數(shù)組
Object[] members = set.toArray();
// 把list中的元素存入數(shù)組
Object[] items = list.toArray();
// 把map的鍵存入數(shù)組
Object[] keys = map.keySet().toArray();
// 把map的值存入數(shù)組
Object[] values = map.values().toArray();

// 如果不想返回Object[]類型的值，可以把一個所需類型的數(shù)組傳入toArray()方法
// 如果傳入的數(shù)組不夠大朽缴，會再創(chuàng)建一個相同類型的數(shù)組
// 如果傳入的數(shù)組太大善玫，復制集合元素后剩余的位置使用null填充
String[] c = l.toArray(new String[0]);

除此之外，還有一些有用的輔助方法密强，用于處理 Java 數(shù)組蝌焚。為了完整性裹唆，這里也會介紹誓斥。

java.lang.System 類定義了一個 arraycopy() 方法只洒，作用是把一個數(shù)組中的指定元素復制到另一個數(shù)組的指定位置。這兩個數(shù)組的類型必須相同劳坑，甚至可以是同一個數(shù)組：

char[] text = "Now is the time".toCharArray();
char[] copy = new char[100];
// 從text的第4個元素開始毕谴，復制10個字符到copy中
// 這10個字符的位置從copy[0]開始
System.arraycopy(text, 4, copy, 0, 10);

// 把一些元素向后移，留出位置插入其他元素
System.arraycopy(copy, 3, copy, 6, 7);

Arrays 類還定義了一些有用的靜態(tài)方法：

int[] intarray = new int[] { 10, 5, 7, -3 }; // 由整數(shù)組成的數(shù)組
Arrays.sort(intarray);                       // 原地排序數(shù)組
// 在索引2找到值7
int pos = Arrays.binarySearch(intarray, 7);
// 未找到：返回負數(shù)
pos = Arrays.binarySearch(intarray, 12);

// 由對象組成的數(shù)組也能排序和搜索
String[] strarray = new String[] { "now", "is", "the", "time" };
Arrays.sort(strarray);  // 排序的結果：{ "is", "now", "the", "time" }

// Arrays.equals()方法比較兩個數(shù)組中的所有元素
String[] clone = (String[]) strarray.clone();
boolean b1 = Arrays.equals(strarray, clone); // 是的距芬，兩個數(shù)組相等

// Arrays.fill()方法用于初始化數(shù)組的元素
// 一個空數(shù)組涝开，所有元素都是0
byte[] data = new byte[100];
// 把元素都設為-1
Arrays.fill(data, (byte) -1);
// 把第5-9個元素設為-2
Arrays.fill(data, 5, 10, (byte) -2);

在 Java 中，數(shù)組可以視作對象框仔，也可以按照對象的方法處理舀武。假如有個對象 o，可以使用類似下面的代碼判斷這個對象是否為數(shù)組离斩。如果是银舱，則可以判斷是什么類型的數(shù)組：

public static void main(String args[]) {        
    Class type = args.getClass();
    if (type.isArray()) {
      Class elementType = type.getComponentType();
      System.out.println(elementType == String.class);
    }
}

小知識

List如何在遍歷時刪除元素

當嘗試用 foreach 或者 Iterator 遍歷集合時進行刪除或者插入元素的操作時，會拋出這樣的異常：java.util.ConcurrentModificationException

關于這個異常的原因跛梗，看了很多文章寻馏，基本上解釋如下：ArrayList的父類AbstarctList中有一個域 modCount，每次對集合進行修改（增添核偿、刪除元素）時 modCount 都會+1诚欠。
而 foreach 的實現(xiàn)原理就是迭代器 Iterator，在這里漾岳，迭代ArrayList的Iterator中有一個變量 expectedModCount轰绵，該變量會初始化和 modCount 相等，但當對集合進行插入尼荆，刪除操作左腔，modCount 會改變，就會造成expectedModCount != modCount耀找，此時就會拋出 java.util.ConcurrentModificationException異常

結論：不要在 foreach 循環(huán)里進行元素的 remove/add 操作翔悠。remove 元素請使用 Iterator方式

參考

• 免費公開課_傳智播客和黑馬程序員免費公開課
  http://yun.itheima.com/open
• Java技術手冊: 第6版
• 第 15 章　對象容器——集合-圖靈社區(qū)
  http://www.ituring.com.cn/book/tupubarticle/17746