Java容器類庫概覽

Java容器類的框架圖

Java容器類庫的主要作用是“保存對象”，我們將其劃分成以下兩個不同的概念：

Collection

一個獨(dú)立的元素序列（一種存放一組對象的方式），這些元素都服從一條或多條規(guī)則。List必須按照插入的順序保存元素；Set中不能有重復(fù)的元素；Queue按排隊(duì)規(guī)則來確定對象產(chǎn)生的順序。

Collection是一個高度抽象的容器接口，其中包含了容器的基本操作和屬性。

Map

一組成對的“鍵值對”對象，允許你使用鍵來查找值。

框架類圖中還包含了許多Abstract類，主要方便于我們創(chuàng)建容器的實(shí)例，Abstract類中已基本實(shí)現(xiàn)了接口中的方法，我們只需要選擇我們需要的方法進(jìn)行覆蓋即可。

Iterator

我們再來看Iterator，我們通常是使用Iterator迭代器來遍歷容器。上圖存在的Collection依賴于Iterator是指：實(shí)現(xiàn)Collection需要實(shí)現(xiàn)iterator()函數(shù)，可以返回一個Iterator對象。ListIterator是專門用于遍歷List的迭代器。

工具類Arrays和Collections為容器添加元素

java.util包中的Arrays和Collections類中包含了很多的實(shí)用方法。Arrays類中包含操作數(shù)組的各種方法，還包含一個靜態(tài)的Arrays.asList()方法接受一個數(shù)組或是用逗號分隔的元素列表，將其轉(zhuǎn)換成一個列表對象。Collection類包含對集合操作的各種方法。我們也可以使用Collections.addAll()想容器中添加一組元素。Collections.addAll()接受一個Collection對象以及一個數(shù)組或者用逗號分隔的元素列表，將元素添加到Collection對象中。

Arrays.asList()的底層實(shí)現(xiàn)是一個數(shù)組，即使用Arrays.asList()生成的List的尺寸是不可以修改的（添加或刪除元素），否則將會拋出UnsupportedOperationException異常。

List

List接口繼承自Collection接口，用于Collection中的所有方法，在Collection的基礎(chǔ)上也添加了許多方法，使得可以在List中插入和刪除元素。List有兩種基本的實(shí)現(xiàn)：ArrayList和LinkedList

• 基本的ArrayList，它適合于隨機(jī)訪問元素，但是在插入和刪除元素時就比較慢
• LinkedList適合于在元素插入和刪除較頻繁時使用，隨機(jī)訪問的速度比較慢

Set

Set中不保存重復(fù)的元素，含義同數(shù)學(xué)概念上的集合。 Set常用于測試歸屬性，即查詢某個元素是否在某個Set中。正因?yàn)槿绱瞬檎乙簿统闪薙et中重要的操作。通常會選擇HashSet的實(shí)現(xiàn)，它對快速查找進(jìn)行了優(yōu)化。Set也有多種不同的實(shí)現(xiàn)，不同的Set實(shí)現(xiàn)不僅具有不同的行為，而且它們對于可以在特定的Set中防止元素的類型也有不同的要求。

• Set(interface)

  存入Set的每個元素必須是唯一對的。加入Set的元素必須定義equals()方法以確保對象的唯一性。Set接口不保證維護(hù)元素的次序。

• HashSet

  為快速查找而設(shè)計(jì)的Set。存入HashSet的元素必須定義hashCode()。使用HashMap實(shí)現(xiàn)。

• TreeSet

  保持次序的Set，底層為樹結(jié)構(gòu)。使用它可以從Set中提取有序的序列。元素必須實(shí)現(xiàn)Comparable接口。使用TreeSet實(shí)現(xiàn)。

• LinkedHashSet

  具有HashSet的查詢速度，且內(nèi)部使用鏈表維護(hù)元素的順序（插入的次序）。在使用迭代器遍歷該Set時，結(jié)果會按照元素插入的次序顯示。元素也必須定義hashCode()方法

Map

Map有以下特點(diǎn):

• Map是將鍵映射到值的鍵值對（key-value）接口

• 映射中不能包含重復(fù)的鍵，每個鍵最多可以映射到一個值，但是一個值可以被多個鍵映射

• Map提供了三個Set視圖供我們訪問：鍵的Set、值的Set和鍵值對的Set

• 映射的順序定義為訪問的映射Set上的迭代器返回元素的順序。TreeMa類，可以對映射的順序做出特定保證；其他的，則不能保證

• 可變對象作為映射鍵需要非常小心

• Map的實(shí)現(xiàn)類應(yīng)該提供兩個“標(biāo)準(zhǔn)“構(gòu)造函數(shù)

  第一個，void（無參數(shù)）構(gòu)造方法，用于創(chuàng)建空映射

  第二個，帶有單個 Map 類型參數(shù)的構(gòu)造方法，用于創(chuàng)建一個與其參數(shù)具有相同鍵-值映射關(guān)系的新映射。帶有單個 Map 類型參數(shù)的構(gòu)造方法，用于創(chuàng)建一個與其參數(shù)具有相同鍵-值映射關(guān)系的新映射

Map的幾種基本實(shí)現(xiàn)：

• HashMap

  Map是基于散列表的實(shí)現(xiàn)（取代了HashTable）。HashMap使用散列碼（對象hashCode()生成的值）來進(jìn)行快速搜索。

• LinkedHashMap

  類似于HashMap，但是迭代的時候，取得鍵值對的順序是起插入的順序，或者是最近最少使用（LRU）的次序。只比HashMap慢一點(diǎn)，而迭代訪問的時候更快，因?yàn)槭褂面湵砭S護(hù)了內(nèi)部次序。

• TreeMap

  基于紅黑樹的實(shí)現(xiàn)。查看“鍵”或者“鍵值對”時，它們會被排序（次序由Comparable或Comparator決定）。TreeMap的特點(diǎn)在于所得到的結(jié)果是經(jīng)過排序的。TreeMap是唯一的帶有subMap()的Map，可以返回一個子樹。

• WeakHashMap

  弱鍵（weak key）映射，允許釋放映射所指向的對象，這是為了解決某類特殊問題而設(shè)計(jì)的。如果映射之外沒有引用指向某個“鍵”，則此“鍵”可以被垃圾回收。

• ConcurrentHashMap

  一種線程安全的Map，不涉及同步加鎖。在并發(fā)中還會介紹。

Stack和Queue

Stack是一個先進(jìn)后出（LIFO）的容器。往盒子中放書，先放進(jìn)去的最后才拿得出來，最后放進(jìn)去的第一個就可以取出，這種模型就是棧（Stack）可以描述的。LinkedList中有可以實(shí)現(xiàn)棧所有功能的方法，有時也可以直接將LinkedList作為棧使用。

隊(duì)列是一個典型的先進(jìn)先出（FIFO）的容器。事物放進(jìn)容器的順序和取出的順序是相同的（優(yōu)先級隊(duì)列根據(jù)事物優(yōu)先級出隊(duì)事物）。隊(duì)列常被當(dāng)做一種可靠的將對象從程序的某個區(qū)域傳輸?shù)搅硪粋€區(qū)域的途徑。隊(duì)列在并發(fā)編程中特別重要。同樣，LinkedList也提供了方法支持隊(duì)列的行為，并且它實(shí)現(xiàn)了Queue接口。

優(yōu)先級隊(duì)列PriorityQueue

先進(jìn)先出描述了典型的隊(duì)列規(guī)則。隊(duì)列規(guī)則是指在給定一組隊(duì)列的元素情況下，確定下一個彈出隊(duì)列的元素的規(guī)則。優(yōu)先級隊(duì)列聲明的下一個彈出的元素是最需要的元素（具有最高優(yōu)先級的元素）。

我們可以在PriorityQueue上調(diào)用offer()方法來插入一個對象，這個對象就會在隊(duì)列中被排序，默認(rèn)排序?yàn)樽匀慌判?，即按插入的先后進(jìn)行排序，但是我們可以通過提供自己的Comparator來修改這個排序。當(dāng)調(diào)用peek()、poll()和remove()方法時，將獲取隊(duì)列優(yōu)先級最高的元素。

優(yōu)先級隊(duì)列算法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)通常是一個堆。

迭代器

對于訪問容器而言，有沒有一種方式使得同一份遍歷的代碼可以適用于不同類型的容器？要實(shí)現(xiàn)這樣的目的就可以使用迭代器。使用迭代器對象，遍歷并選擇序列中的對象，而客戶端不必知道或關(guān)心該序列底層的結(jié)構(gòu)。Java中對迭代器有一些限制，比如Java的Iterator只能單向移動，這個Iterator只能用來：

• 使用next()方法獲得序列的下一個元素
• 使用hasNext()方法檢查序列中是否還有元素
• 使用remove()方法將迭代器新近返回的元素刪除，意味著在調(diào)用remove()之前必須先調(diào)用next()

API中的Iterator接口中方法如上，實(shí)現(xiàn)Iterator對象需要實(shí)現(xiàn)hashNext()方法和next()方法，remove方法是一個可選操作。forEachRemaining是Java 1.8（Java SE8）中加入的方法，用于Lambda表達(dá)式。

舉一個簡單的使用迭代器訪問容器的例子：

class Cat{
    private static int counter = 0;
    private int id = counter++;
    @Override
    public String toString() {
        return "Cat: " + id;
    }
}

public class IteratorAccessContainer {
    //不包含任何容器類型信息的遍歷容器方法
    public static void showElement(Iterator it) {
        while (it.hasNext()) {      //hasNext()檢查序列中是否還有元素
            Cat cat = it.next();    //next()返回序列中的元素
            System.out.print(cat + "	");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        ArrayList cats1 = new ArrayList();
        LinkedList cats2 = new LinkedList<>(); //可以省略類型參數(shù) 編譯器可自動推斷出
        HashSet cats3 = new HashSet<>();
        for(int i=0;i<3; i++) {
            cats1.add(new Cat());
            cats2.add(new Cat());
            cats3.add(new Cat());
        }
        showElement(cats1.iterator());
        showElement(cats2.iterator());
        showElement(cats3.iterator());
    }
}
/*
output:
Cat: 0  Cat: 3  Cat: 6  
Cat: 1  Cat: 4  Cat: 7  
Cat: 2  Cat: 8  Cat: 5  
*/

showElement()方法不包含任何有關(guān)它遍歷的序列類型信息，這就展示了Iterator的好處：能夠?qū)⒈闅v序列的操作與序列底層結(jié)構(gòu)分離。也可以說，迭代器統(tǒng)一了對容器的訪問方式。

從容器框架圖中我們可以看出，Collection是描述所有序列容器的共性的根接口。但是在C++中，標(biāo)準(zhǔn)的C++類庫中沒有其他容器的任何公共基類，容器之間的共性都是通過迭代器達(dá)成的。在Java中，則將兩種方法綁定到了一起，實(shí)現(xiàn)Collection的同時也要實(shí)現(xiàn)iterator()方法（返回該容器的迭代器）。

ListIterator

ListIterator是一個更加強(qiáng)大的Iterator子類型，但是它只能用于各種List的訪問。Iterator只能前向移動，但ListIterator允許我們可以前后移動。它還可以產(chǎn)生相對于迭代器在列表中指向當(dāng)前位置的前一個和后一個索引，并且可以使用set()方法替換它訪問過的最后一個元素。remove()方法可以刪除它訪問過的最后一個元素。需要注意，這兩處的最后一個元素只的都是調(diào)用next()或者previous返回的元素，也就意味著調(diào)用set()、remove()這兩個方法之前，要先調(diào)用next()或者previous()。

需要注意ListIterator在序列中的游標(biāo)位置與Iterator不同，Iterator的游標(biāo)位置始終位于調(diào)用previous()將返回的元素和調(diào)用next()將返回的元素之間。長度為n的列表的迭代器的游標(biāo)位置有n+1個。

使用ListIterator對列表進(jìn)行正向和返回迭代，以及使用set()替換列表元素的例子：

public class ListIteration {
    public static void main(String[] args) {
        List catList = new ArrayList<>();
        for(int i=0; i<5; i++) {
            catList.add(new Cat());
        }
        
        ListIterator it = catList.listIterator();
        System.out.println("CatNo.	 nextIndex	 previousIndex");
        
        //正向遍歷
        System.out.println("正向遍歷：");
        while (it.hasNext()) {
            Cat cat = it.next();
            System.out.println(cat+"		"+it.nextIndex()+"		"+it.previousIndex());
        }
        System.out.println();
        
        System.out.println("當(dāng)?shù)饔螛?biāo)處于最后一個元素末尾時：");
        ListIterator it2 = catList.listIterator();
        while (it2.hasNext()) {
            Cat cat = it2.next();
            System.out.println(cat+"		"+it.nextIndex()+"		"+it.previousIndex());
        }
        System.out.println();
        
        //反向遍歷
        System.out.println("反向遍歷");
        while(it.hasPrevious()) {
            Cat cat = it.previous();
            System.out.println(cat+"		"+it.nextIndex()+"		"+it.previousIndex());
        }
        System.out.println();
        
        //產(chǎn)生指定游標(biāo)位置的迭代器 從第二個位置開始向前替換列表中的Cat對象
        System.out.println("從第二個位置開始向前替換列表中的Cat對象");
        it = catList.listIterator(2);
        while(it.hasNext()) {
            it.next();
            it.set(new Cat());
        }
        System.out.println(catList);
    }
}
/*
CatNo.   nextIndex   previousIndex
正向遍歷：
Cat: 0      1       0
Cat: 1      2       1
Cat: 2      3       2
Cat: 3      4       3
Cat: 4      5       4

當(dāng)?shù)饔螛?biāo)處于最后一個元素末尾時：
Cat: 0      5       4
Cat: 1      5       4
Cat: 2      5       4
Cat: 3      5       4
Cat: 4      5       4

反向遍歷
Cat: 4      4       3
Cat: 3      3       2
Cat: 2      2       1
Cat: 1      1       0
Cat: 0      0       -1

從第二個位置開始向前替換列表中的Cat對象
[Cat: 0, Cat: 1, Cat: 5, Cat: 6, Cat: 7]
*/

foreach與迭代器

foreach語法不僅可以用在數(shù)組，也可以用在任何Collection對象。之所以可以用在Collection對象，是因?yàn)镴ava SE5引入了Iterable接口，該接口包含一個能夠產(chǎn)生Iterator的iterator()方法，并且Iterable接口被foreach用來在序列中移動。因此，如果創(chuàng)建了任何實(shí)現(xiàn)Iterable的類，都可以將它用于foreach當(dāng)中。需要注意，數(shù)組雖然可以使用foreach語法遍歷，但不意味著數(shù)組是Iterable的。

實(shí)現(xiàn)一個可迭代的類，使用foreach方法遍歷

public class IterableClass implements Iterable<String>{
    private String[] words = ("This is happy day.").split(" ");
    @Override
    public Iterator iterator() {
        return new Iterator() {
            private int index = 0;
            //判斷是否存在下一個元素
            public boolean hasNext() {
                return index < words.length;
            }
            //返回下一個元素
            public String next() {
                return words[index++];
            }
            public void remove() {  //remove可以不用實(shí)現(xiàn)
                throw new UnsupportedOperationException();
            }
        };
    }
    
    public static void main(String[] args) {
        //foreach語法遍歷實(shí)現(xiàn)了Iterable接口的類
        for(String s : new IterableClass()) {
            System.out.println(s);
        }
    }
}
/*
This
is
happy
day.
*/