第十一章 持有對象

Java實(shí)用類庫還提供了一套相當(dāng)完整的容器類來解決這個問題，其中基本的類型是List察藐、Set皮璧、Queue和Map。這些對象類型也稱為集合類分飞，但由于J巴德類庫中使用了Collection這個名字來代指該類庫的一個特殊子集悴务，所以可以使用了范圍更廣的術(shù)語“容器”稱呼它們。

11.1 泛型和類型安全的容器

import java.util.ArrayList;

class Apple{
    private static long counter;
    private final long id = counter++;
    public long id(){return id;}
}

class Orange{}

public class Eleven {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        ArrayList apples = new ArrayList();
        for (int i = 0; i < 3; i++) {
            apples.add(new Apple());
        }
        apples.add(new Orange());
        for (int i = 0; i < apples.size(); i++) {
            ((Apple)apples.get(i)).id();
        }
    }
}

自定義的Apple和Orange類是有區(qū)別的,它們除了都是Object之外沒有任何共性（如果一個類沒有顯示地聲明繼承自哪個類，那么它自動地繼承自O(shè)bject）讯檐。ArrayList保存的是Object羡疗，因此不僅可以通過ArrayList的add()方法將Apple對象放進(jìn)容器，還可以添加Orange對象别洪，而且無論在編譯期還是運(yùn)行時都不會有wenti8叨恨。當(dāng)在使用ArrayList的get()方法來取出Apple對象時，其實(shí)得到的只是Object引用，必須將其轉(zhuǎn)型為Apple，因此需要將整個表達(dá)式括起來，在滴阿勇Apple的id()方法之前，必須執(zhí)行強(qiáng)制轉(zhuǎn)型铛铁。

要想定義用來保存Apple對象的ArrayList，可以聲明ArrayList<Apple>,而不僅僅只是ArrayList秧骑，其中尖括號括起來的是類型參數(shù)(可以有多個),它制定了這個容器實(shí)例可以保存的類型.

import java.util.ArrayList;

class GrannySmith extends Apple{}

class Gala extends Apple{}

class Fuji extends Apple{}

class Braeburn extends Apple{}

public class GenericsAndUpcasting {
    public static void main(String[] args) {
        ArrayList<Apple> apples = new ArrayList<Apple>();
        apples.add(new GrannySmith());
        apples.add(new Gala());
        apples.add(new Fuji());
        apples.add(new Braeburn());
        for (Apple a:apples){
            System.out.println(a);
        }
    }
}

當(dāng)指定了某個類型作為泛型參數(shù)時,并不僅限于只能講該確切類型的對象放置到容器中.向上轉(zhuǎn)型也可以像作用于其他類型一樣作用于泛型.

11.2基本概念

1. Collection.一個獨(dú)立元素的序列,這些元素都服從一條或多條規(guī)則.List必須按照插入的順序保存元素,而Set不能有重復(fù)元素.Queue按照排隊(duì)規(guī)則來確定對象產(chǎn)生的順序(通常與元素被插入的順序相同).
2. Map.一組承兌的"鍵值對"對象,允許使用鍵來查找值.ArrayList允許使用數(shù)字來查找值,因此在某種意義上講,它將數(shù)字與對象關(guān)聯(lián)在一起.映射表允許我們是用另一個對象來查找某個對象,它也被稱為"關(guān)聯(lián)數(shù)組"或"字典"

11.3 添加一組元素

在java.util包中的Arrays和Collections類中都有很多使用方法,可以在一個Collection中添加一組元素.Arrays.asList()方法接收一個數(shù)組或是一個用逗號分隔的元素列表(使用多變參數(shù)),并將其轉(zhuǎn)換為一個List對象.Collections.addAll()方法接收一個Collection對象,以及一個數(shù)組或是一個用逗號分好的列表,將元素添加到Collocation中.

import java.util.*;

public class AddingGroups {
    public static void main(String[] args) {
        Collection<Integer> collection = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5));
        Integer[] moreInts = {6,7,8,9,10};
        collection.addAll(Arrays.asList(moreInts));
        Collections.addAll(collection,11,12,13,14,15);
        Collections.addAll(collection,moreInts);
        List<Integer> list = Arrays.asList(16,17,18,19,20);
        list.set(1,99);
    }
}

Collection的構(gòu)造器可以接受另一個Collection,用來將自身初始化,因此可以使用Arrays.List()為這個構(gòu)造器產(chǎn)生輸入.但Collections.addAll()方法運(yùn)行起來要快得多,而且構(gòu)建一個不包含元素的Collection,然后調(diào)用Collections.addAll(),這種方式很方便,因此是首選.

Collection.addAll()成員方法只能接受另一個Collection對象作為參數(shù),因此不如Arrays.asList()或Collections.addAll()靈活.

也可以直接使用Arrays.asList()的輸出,將其當(dāng)做List,但在這種情況下,其底層表示的是數(shù)組,因此不能調(diào)整尺寸.

class Snow{}
class Powder extends Snow{};
class Light extends Powder{};
class Heavy extends Powder{};
class Crusty extends Snow{};
class Slush extends Snow{};

public class AsListInference {
    public static void main(String[] args) {
        List<Snow> snow1 = Arrays.asList(new Crusty(),new Slush(),new Powder());
        //List<Snow> snow2 = Arrays.asList(new Light(),new Heavy());
        List<Snow> snow4 = Arrays.<Snow>asList(new Light(),new Heavy());
        List<Snow> snow3 = new ArrayList<Snow>();
        Collections.addAll(snow3,new Light(),new Heavy());
    }
}

正如從創(chuàng)建snow4的操作中,可以在Arrays.asList()中間差一條"線索",以告訴編譯器對于由Arrays.asList()產(chǎn)生的List類型,實(shí)際的目標(biāo)類型應(yīng)該是什么,這稱為顯示類型參數(shù)說明

11.4 容器的打印

import java.util.*;

public class PrintingContainers {
    static Collection fill(Collection<String> collection){
        collection.add("rat");
        collection.add("cat");
        collection.add("dog");
        collection.add("dog");
        return collection;
    }

    static Map fill (Map<String,String> map){
        map.put("rat","Fuzzy");
        map.put("cat","Rags");
        map.put("dog","Bosco");
        map.put("dog","Spot");
        return map;
    }

    public static void main(String[] args) {
        System.out.println(fill(new ArrayList<String>()));
        System.out.println(fill(new LinkedList<String>()));
        System.out.println(fill(new HashSet<String>()));
        System.out.println(fill(new TreeSet<String>()));
        System.out.println(fill(new LinkedHashSet<String>()));
        System.out.println(fill(new HashMap<String, String>()));
        System.out.println(fill(new TreeMap<String, String>()));
        System.out.println(fill(new LinkedHashMap<String, String>()));
    }

}

此處展示了java容器類庫中的兩種主要類型,主要區(qū)別在于容器中每個"槽"保存的元素個數(shù).Collection在每個槽中只能保存一個元素.此類容器包括:List,以特定的順序保存一組元素;Set,元素不能重復(fù);Queue,只允許在容器的一端插入對象,并從另外一端移除對象.Map在每個槽內(nèi)保存兩個對象,即鍵值對.

ArrayList和LinkedList都是List類型,他們都按照被插入的順序保存元素,LinkedList包含的操作比ArrayList多.

HashSet,TreeSet和LinkedHashSet都是Set類型,每個相同的項(xiàng)只保存一次.HashSet是最快的獲取元素方式;TreeSet按照比較結(jié)果的升序保存對象;LinkedHashSet按照被添加的順序保存對象.

Map可以用鍵來查找對象.鍵所關(guān)聯(lián)的對象稱為值.對于每個鍵,Map只接受存儲一次.HashMap提供了最快的查找技術(shù),沒有按照任何明顯順序保存其元素.TreeMap按照比較結(jié)果的升序保存鍵;LinkedHashMap按照插入順序保存鍵,同時還保留了HashMap的查詢速度.

11.5 List

List接口在Collection的基礎(chǔ)上添加了大量的方法,使得可以在List的中間插入和移除元素

• 基本的ArrayList,常用于隨機(jī)訪問元素,但是在List的中間插入和移除元素時較慢.
• LinkedList,通過代價較低的在List中間進(jìn)行的插入和刪除操作.提供了優(yōu)化的順序訪問,LinkedList在隨機(jī)訪問方面相對較慢,但它的特性集較ArrayList更大.

contains()方法來確定某個對象是否在列表中,如果想移除一個對象,則可以將這個對象的引用傳遞給remove()方法.如果有一個對象的引用,則可以使用indexOf()來發(fā)現(xiàn)該對象在List中所處位置的索引編號.

當(dāng)確定一個元素是否屬于某個LIst,發(fā)現(xiàn)某個元素的索引,以及從某個List中移除一個元素,都會用到equals()方法(根類Object 的一部分).

在List中插入元素,對于LinkedList,在列表中間插入和刪除都是廉價操作,但是對于ArrayList是代價高昂的操作.

containsAll()方法

retainAll()方法是一種有效的"交集",其行為依賴于eauals()方法.

remove()根據(jù)元素索引值移除元素的效果,此時不比擔(dān)心equals()行為.

removeAll()方法的行為也是基于equals()方法,它將從List中移除在參數(shù)List中的所有元素.

set()方法命名與Set類存在潛在沖突,可用replace,在置頂?shù)乃饕?第一個參數(shù))沒用第二個參數(shù)替換這個位置的元素.

對于List,有一個重載的addAll()方法使得我們可以在初始List中間插入新的列表,而不僅僅只能用Collection的addAll()方法將其追加到表尾.

toArray()將任意的Collection轉(zhuǎn)換為一個數(shù)組,這是一個重載方法,其無參數(shù)版本返回的是Object數(shù)組.但如果想該重載版本傳遞目標(biāo)類型的數(shù)據(jù),那么將產(chǎn)生指定類型的數(shù)據(jù).

11.6 迭代器

迭代器(也是一種設(shè)計(jì)模式)的概念可以用于轉(zhuǎn)換容器中的數(shù)據(jù)類型.迭代器是一個對象,它的工作是遍歷并選擇序列中的對象,而客戶端程序員不必知道或關(guān)心該序列底層的結(jié)構(gòu).迭代器通常被稱為輕量級對象:創(chuàng)建它的代價小.

Java的Iterator只能單向移動,:

1. 使用方法iterator()要求容器返回一個Iterator.Iterator將準(zhǔn)備好返回序列的第一個元素
2. next()獲得序列中的下一個元素
3. hasNest()檢查序列中是否還有元素.
4. remove()將迭代器新近返回的元素刪除.

11.6.1 ListIterator

ListIterator是Iterator的子類型,只能用于各種List類的訪問.可以雙向移動,可以產(chǎn)生相對于迭代器在列表中指向當(dāng)前位置的前一個和后一個元素的索引,并且可以使用set()方法替換它訪問過的最后一個元素,可以調(diào)用listIterator()方法產(chǎn)生一個執(zhí)行List開始處的ListIterator,并且還可以通過調(diào)用ListIterator(n)方法創(chuàng)建一個一開始就指向列表索引為n的元素處的ListIterator.

11.7 LinkedList

LinkedList在List中間插入和刪除時比ArrayList更搞笑,但在隨機(jī)訪問操作方面卻要遜色一些.

LinkedList還添加了可以使其用作棧,隊(duì)列或雙端隊(duì)列的方法.

getFirst()和element()完全一樣,都返回列表的第一個元素,而并不移除它,如果List為空,則拋出NoSuchElementException.peek()方法在列表為空時返回null.

removeFirst()和remove()完全一樣,移除并返回列表的第一個元素,而在列表為空時拋出NoSuchElementException.poll()在列表為空時返回null.

addFirst()與add()和addLast()相同,豆?jié){某個元素插入到列表的尾部.

removeLast()移除并返回列表的最后一個元素.

11.8 Stack

"棧"通常是指"后進(jìn)先出"(LIFO)的容器.有時棧也被稱為疊加棧

LinkedList具有能夠直接實(shí)現(xiàn)棧的所有功能的方法,因此可以直接將LinkedList作為棧使用.

import java.util.LinkedList;

public class Stack<T> {
    private LinkedList<T> storage = new LinkedList<T>();
    public void push(T v){storage.addFirst(v);}
    public T peek(){return storage.getFirst();}
    public T pop(){return storage.removeFirst();}
    public boolean empty(){return storage.isEmpty();}
    public String toString(){return storage.toString();}
}

這里通過使用泛型,引入了在棧的類定義中最簡單的可行示例.類名之后的<T>告訴編譯器這將是一個參數(shù)化類型,而其中的類型參數(shù),即在類被使用時將會被實(shí)際類型替換的參數(shù),就是T.大體上,該類就是在聲明"定義一個可以持有T類型對象的Stack",Stack是LinkedList實(shí)現(xiàn)的,而LinkedList也被告知它將持有T類型對象.push()接受的是T類型的對象,而peek()和pop()將返回T類型的對象.peek()方法將提供棧頂元素,但是并不將其從棧頂移除,而pop()將移除并返回棧頂元素.

11.9 Set

Set不保存重復(fù)的元素.Set中最常被使用的是測試歸屬性.Set具有與Collection完全一樣的接口,因此沒有任何額外的功能,不像具有兩種形式的List,實(shí)際上Set就是Collection,只是行為不同.

TreeSet將元素存儲在紅-黑數(shù)據(jù)結(jié)構(gòu)中,而HashSet使用的是散列函數(shù).LinkedList因?yàn)椴樵兯俣鹊脑蚴褂昧松⒘?但它使用了鏈表來維護(hù)元素的插入順序.

TreeSet的結(jié)果是排序的,排序是按字典序進(jìn)行的,因此大小寫被劃分到了不同的組中.如果想要按照字母序排序,那么可以向TreeSet的構(gòu)造器傳入String.CASE_INSENTIVE_ORDER比較器

11.10 Map

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Statistics {
    public static void main(String[] args) {
        Random random = new Random(47);
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < 10000; i++) {
            int r = random.nextInt(20);
            Integer freq = map.get(r);
            map.put(r,freq==null?1:freq+1);
        }
        System.out.println(map);
    }
}

containsKey()和containValue()

Map與數(shù)組和其他的Collection一樣,可以擴(kuò)展到多維,只需將其值設(shè)置為Map.

11.11 Queue

隊(duì)列是一個典型的先進(jìn)先出(FIFO)的容器.即從容器的一端放入事務(wù),從另一端取出,并且事務(wù)放入容器的順序與取出的順序是相同的.隊(duì)列常被當(dāng)做一種可靠的將對象從程序的某個區(qū)域傳輸?shù)搅硪粋€區(qū)域的途徑.隊(duì)列在并發(fā)編程中特別重要.

LinkedList提供了方法以支持隊(duì)列的行為,并且它實(shí)現(xiàn)了Queue接口,因此LinkedList可以用作Queue的一種實(shí)現(xiàn).

offer()方法是與Queue相關(guān)的方法之一,它在允許的情況下,將一個元素插入到隊(duì)尾,或者返回false.peek()和element()都將在不移除的情況下返回隊(duì)頭,但是peek()方法在隊(duì)列為空時返回null,element()會拋出NoSuchElementException異常.poll()和remove()方法將移除并返回隊(duì)頭,但是poll()在隊(duì)列為空時會返回null,而remove()會拋出NoSuchElementException異常.

11.11.1 PriorityQueue

優(yōu)先級隊(duì)列聲明下一個彈出元素是最需要的元素(具有最高的優(yōu)先級).

在PriorityQueue上調(diào)用offer()方法來插入一個對象時,這個對象會在隊(duì)列中被排序.默認(rèn)的排序?qū)⑹褂脤ο笤陉?duì)列中的自然順序,可以通過Comparator來修改這個順序.PriorityQueue可以確保當(dāng)你調(diào)用peek(),poll()和remove()方法時,獲取的元素將是隊(duì)列中優(yōu)先級最高的元素.

允許重復(fù),最小的值擁有最高的優(yōu)先級,(如果是String,空格也可以算作值,并且比字母的優(yōu)先級高)

11.12 Collection和Iterator

Collection是描述所有序列容器的共性的根接口.

使用接口描述,可以創(chuàng)建更通用的代碼,通過針對接口而非具體實(shí)現(xiàn)來編寫代碼,可以應(yīng)用于更多的對象類型.

生成Iterator是將隊(duì)列與消費(fèi)隊(duì)列的方法連接在一起耦合度最小的方式,并且與實(shí)現(xiàn)Collection相比,它序列類上所施加的約束也少得多.

11.13 Foreach與迭代器

java SE5引入了新的被稱為Iterable的接口,該接口包含一個能夠產(chǎn)生Iterator的iterator()方法,并且Iterable接口被foreach用來在序列中移動.因此如果創(chuàng)建了任何實(shí)現(xiàn)Iterable的類,都可以將它用于foreach語句中.

在java SE5中,大量的類都是Iterable類型,主要包括所有的Collection類(但是不包括各種Map)

import java.util.Arrays;

public class ArrayIsNotIterable {
    static <T> void test(Iterable<T> ib){
        for (T t:ib)
            System.out.println(t+" ");
    }

    public static void main(String[] args) {
        test(Arrays.asList(1,2,3));
        String[] strings = {"A","B","C"};
        //test(strings);
        test(Arrays.asList(strings));
    }
}

嘗試把數(shù)組當(dāng)做一個Iterable參數(shù)傳遞會導(dǎo)致失敗.這說明不存在任何從數(shù)組到Iterable的自動轉(zhuǎn)換.

13.11.1 適配器方法慣用法

假設(shè)希望可以選擇以向前的方向或是向后迭代一個單詞列表,如果直接繼承這個類,并覆蓋iterator()方法????

一種解決方案是所謂適配器方法,"適配器"部分來自于設(shè)計(jì)模式,因此必須提供特定接口以滿足foreach語句.當(dāng)有一個接口并需要另一個接口時,編寫適配器就可以解決問題.在默認(rèn)的向前迭代器基礎(chǔ)上,添加產(chǎn)生反向迭代器的能力,因此不能使用覆蓋,而是添加了一個能夠產(chǎn)生Iterable對象的方法,該對象可以用于foreach語句.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;

class ReversibleArrayList<T> extends ArrayList<T>{
    public ReversibleArrayList(Collection<T> c){super(c);}
    public Iterable<T> reversed(){
        return new Iterable<T>(){
            public Iterator<T> iterator() {
                return new Iterator<T>() {
                    int current = size()-1;

                    public void remove() {
                        throw new UnsupportedOperationException();
                    }

                    public boolean hasNext() {
                        return current>-1;
                    }

                    public T next() {
                        return get(current--);
                    }
                };
            }
        };
    }
}

public class AdapterMethodIdiom {
    public static void main(String[] args) {
        ReversibleArrayList<String> ral = new ReversibleArrayList<String>(Arrays.asList("To be or not to be".split(" ")));
        for (String s:ral)
            System.out.println(s+" ");
        System.out.println();
        for (String s:ral.reversed())
            System.out.println(s+" ");
    }
}

import java.util.*;  
  
public class Modify {  
    public static void main(String[] args){  
        Random rand=new Random(47);  
        Integer[] ia={0,1,2,3,4,5,6,7,8,9};  
        List<Integer> list=new ArrayList<Integer>(Arrays.asList(ia));  
        System.out.println("Before shufflig: "+list);  
        Collections.shuffle(list,rand);  
        System.out.println("After shuffling: "+list);  
        System.out.println("array: "+Arrays.toString(ia));  
        List<Integer> list1=Arrays.asList(ia);  
        System.out.println("Before shuffling: "+list1);  
        Collections.shuffle(list1,rand);  
        System.out.println("After shuffling: "+list1);  
        System.out.println("array: "+Arrays.toString(ia));  
          
    }  
}  

在第一種情況中霎奢，Arrays.asList（）的輸出被傳遞給了ArrayList()的構(gòu)造器，這將創(chuàng)建一個引用ia的元素的ArrayList梢灭，因此打亂這些引用不會修改該數(shù)組夷家。 但是，如果直接使用Arrays.asList(ia）的結(jié)果敏释， 這種打亂就會修改ia的順序库快。意識到Arrays.asList（）產(chǎn)生的List對象會使用底層數(shù)組作為其物理實(shí)現(xiàn)是很重要的。 只要你執(zhí)行的操作 會修改這個List钥顽，并且你不想原來的數(shù)組被修改义屏，那么你就應(yīng)該在另一個容器中創(chuàng)建一個副本。

Collection.shuffle()方法沒有影響到原來的數(shù)組,而只是打亂了shuffled的引用.之所以這樣,是因?yàn)锳rrayList將Arrays.asList()方法的結(jié)果包裝了起來,如果這個由Arrays.asList()方法產(chǎn)生的List被直接打亂,那么它就會修改底層的數(shù)組.

11.14 總結(jié)

1. 數(shù)組將數(shù)字與對象聯(lián)系起來.他保存類型明確的對象,查詢對象時,不需要對結(jié)果做類型轉(zhuǎn)換,它可以是多維的,可以保存基本類型的數(shù)據(jù).但是,數(shù)組一旦生成,其容量就不能改變.
2. Collection保存單一的元素,而Map保存相關(guān)聯(lián)的鍵值對.有了Java的泛型,就可以指定容器中存放的對象類型,因此就不會將錯誤類型的對象放置到容器中,并且在從容器中獲取元素時,不必進(jìn)行類型轉(zhuǎn)換.各種Collection和各種Map都可以在向其中添加更多的元素時,自動調(diào)整其尺寸.容器不能持有基本類型,但是自動包裝機(jī)制會仔細(xì)地執(zhí)行基本類型到容器中所持有的包裝器類型之間的雙向轉(zhuǎn)換.
3. 像數(shù)組一樣,List也建立數(shù)字索引和對象的關(guān)聯(lián),因此,數(shù)組和List都是排好序的容器.List能夠自動擴(kuò)充容器.
4. 如果要進(jìn)行大量的隨機(jī)訪問,就是用ArrayList;如果要經(jīng)常從表中間插入或刪除元素,則應(yīng)該使用LinkedList.
5. 各種Queue以及棧的行為,有LinkedList提供支持.
6. Map是一種將對象(非數(shù)字)與對象相關(guān)聯(lián)的設(shè)計(jì).HashMap設(shè)計(jì)用來快速訪問;而TreeMap保持"鍵"始終處于排序狀態(tài),所以沒有HashMap快.LinkedHashMap保持元素插入的順序,但是也通過散列提供了快速訪問能力.
7. Set不接受重復(fù)元素.HashSet提供最快的查詢速度,而TreeSet保持元素處于排序狀態(tài).LinkedHashSet以插入順序保存元素.
8. 新程序中不應(yīng)該使用過時的Vector,HashTable和Stack

[圖片上傳失敗...(image-eab3f-1524392810247)]

第十五章 泛型

泛型的概念:編寫更通用的代碼,要使代碼能夠應(yīng)用于"某種不具體的類型",而不是一個具體的接口或類.

15.2 簡單泛型

可以讓這個類直接持有Object類型的對象.

class Automobile{}
/*p353*/
public class Holder2 {
    private Object a;

    public Holder2(Object a) {
        this.a = a;
    }

    public Object get() {
        return a;
    }

    public void set(Object a) {
        this.a = a;
    }

    public static void main(String[] args) {
        Holder2 h2 = new Holder2(new Automobile());
        Automobile a = (Automobile)h2.get();
        h2.set("Not an Automobile");
        String s = String.valueOf(h2.get());
        h2.set(1);
        Integer x = (Integer) h2.get();
    }

}

有些情況下,容器能夠同時持有多種類型的對象,但是,通常而言,只會使用容器來存儲對一種類型的對象.泛型的主要目的之一就是用來指定容器要持有什么類型的對象,而且由編譯器來保證類型的正確性.

若使用Object,則必須指定參數(shù)類型.如若不指定參數(shù)類型,則需要使用類型參數(shù),用尖括號擴(kuò)朱,放在類名后面.然后再使用這個類的時候,在用實(shí)際的類型替換此類型參數(shù).如下.T就是類型參數(shù).

/*p354*/
public class Holder3<T> {
    private T a;
    public Holder3(T a){this.a=a;}

    public T get() {
        return a;
    }

    public void set(T a) {
        this.a = a;
    }

    public static void main(String[] args) {
        Holder3<Automobile> h3 = new Holder3<Automobile>(new Automobile());
//        h3.set("Not an Automobile");
//        h3.set(1);
    }

}

Java泛型的核心概念:告訴編譯器想使用什么類型,然后編譯器可以處理一切細(xì)節(jié).

15.2.1 一個元組類庫

元組:將一組對象直接打包存儲于其中的一個單一對象.這個容器對象允許讀取其中元素,但是不允許向其中存放新的對象.(這個概念也稱為數(shù)據(jù)傳送對象或信使)

可以利用繼承機(jī)制實(shí)現(xiàn)長度更長的元組.

/*p354*/
public class TwoTuple<A,B> {
    public final A first;
    public final B second;

    public TwoTuple(A first, B second) {
        this.first = first;
        this.second = second;
    }

    public String toString(){
        return "(" + first +"." + second + ")";
    }

}

15.2.2 一個堆棧類

public class LinkedStack<T> {
    private static class Node<U>{
        U item;
        Node<U> next;
        Node() {item = null;next = null;}
        Node(U item,Node<U> next){
            this.item=item;
            this.next=next;
        }
        boolean end(){return item==null && next == null;}
    }

    private Node<T> top = new Node<T>();

    public void push(T item){
        top = new Node<T>(item,top);
    }

    public T pop(){
        T result = top.item;
        if (!top.end())
            top = top.next;
        return result;
    }

    public static void main(String[] args) {
        LinkedStack<String> lss = new LinkedStack<String>();
        for (String s:"Phasers on stun!".split(" "))
            lss.push(s);
        String s;

        while ((s=lss.pop())!=null) System.out.println(s);
    }

}

該例子使用了末端哨兵(end sentinel)來判斷堆棧何時為空.該末端燒餅是在構(gòu)建LinkedStack時創(chuàng)建的.每調(diào)用一次push()方法,就會創(chuàng)建一個Node<T>對象,并將其鏈接到前一個Node<T>對象.調(diào)用pop()方法時,返回top.item,然后丟棄當(dāng)前top所指的Node<T>,并將top轉(zhuǎn)移到下一個Node<T>,直到遇到末端哨兵.

15.3 泛型接口

泛型也可以應(yīng)用于接口,如生成器(generator),這是一種專門負(fù)責(zé)創(chuàng)建對象的類.實(shí)際上,這是工廠方法設(shè)計(jì)模式的一種應(yīng)用.不過,當(dāng)使用生成器創(chuàng)建新的對象時,它不需要任何參數(shù),而工廠方法一般需要參數(shù).也就是說,生成器無需額外的信息就知道如何創(chuàng)建新對象.

public interface Generator<T> {T next();}

一般而言,一個生成器只定義一個方法,該方法用于生產(chǎn)新的對象.

/*p360*/
public class Fibonacci implements Generator<Integer> {
    private int count = 0;
    public Integer next() {return fib(count++);}

    private Integer fib(int n) {
        if (n<2) return 1;
        return fib(n-2)+fib(n-1);
    }

    public static void main(String[] args) {
        Fibonacci gen = new Fibonacci();
        for (int i = 0; i < 18; i++) {
            System.out.println(gen.next());
        }
    }

}

Java泛型的一個局限性:基本類型無法作為類型參數(shù).

15.4 泛型方法

是否擁有泛型方法,與其所在的類是否具有泛型沒有關(guān)系.

泛型方法使得該方法能夠獨(dú)立于類而產(chǎn)生變化.基本指導(dǎo)原則:無論何時,只要能做到,就應(yīng)該盡量使用泛型方法.也就是說如果使用泛型方法可以取代將整個類泛型化,那么就應(yīng)該只使用泛型方法,因?yàn)樗梢允故虑楦宄靼?另外,對于一個static的方法而言,無法訪問泛型類的類型參數(shù),所以如果static方法需要使用泛型能力,就必須使其成為泛型方法.

要定義泛型方法,只需將泛型參數(shù)列表置于返回值之前.

/*p361*/
public class GenericMethods {
    public <T> void f(T x){
        System.out.println(x.getClass().getName());
    }
    public static void main(String[] args) {
        GenericMethods gm = new GenericMethods();
        gm.f("");
        gm.f(1);
        gm.f(1.0);
        gm.f(1.0F);
        gm.f('c');
        gm.f(gm);
    }
}

注意:當(dāng)使用泛型類時,必須在創(chuàng)建對象的時候指定類型參數(shù)的值,而使用泛型方法時,通常不比指明參數(shù)類型,因此編譯器會找出具體的類型.這稱為類型參數(shù)判斷(type argument inference)

第十七章 容器深入研究

17.2 填充容器 (沒太明臺)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class StringAddress{
    private String s;
    public StringAddress(String s){
        this.s = s;
    }

    @Override
    public String toString() {
        return super.toString() + " " + s;
    }
}

public class FillingLists {
    public static void main(String[] args) {
        List<StringAddress> list = new ArrayList<StringAddress>(
                Collections.nCopies(4,new StringAddress("Hello"))
        );
        System.out.println(list);
        Collections.fill(list,new StringAddress("World"));
        System.out.println(list);
    }
}

兩種對單個對象的引用來填充Collection的方式:

1. 使用Collections.nCopies()創(chuàng)建傳遞給構(gòu)造器List,
2. 使用Collections.fill(),fill()方法用處有限,只能替換已經(jīng)在List中存在的元素,而不能添加新的元素.

17.2.1 一種Generator解決方案

所有的Collection子類型都有一個接收另一個Collection對象的構(gòu)造器,用于接收的Collection對象中的元素來填充新的容器.

import fifteen.Generator;

import java.util.ArrayList;

/*p461*/
public class CollectionData<T> extends ArrayList{
    public CollectionData(Generator<T> gen,int quantity){
        for (int i = 0; i < quantity; i++) {
            add(gen.next());
        }
    }
    public static <T> CollectionData<T> list(Generator<T> gen,int quantity){
        return new CollectionData<T>(gen,quantity);
    }
}

這個類使用Generator在容器中防止所需數(shù)量的對象,然后所產(chǎn)生的容器可以傳遞給任何Collection的構(gòu)造器,這個構(gòu)造器會把其中的數(shù)據(jù)復(fù)制到自身中.addAll()方法是所有Collection子類型的一部分,它也可以用來組裝現(xiàn)有的Collection.

CollectionData是適配器設(shè)計(jì)模式的一個實(shí)例.

17.2.2適配器

可以對Map使用相同的方式蜂大，但這需要一個Pair類闽铐，為了組裝Map，每次調(diào)用Generator的next()方法都必須產(chǎn)生一個對象對(一個鍵和一個值)

import fifteen.Generator;

import java.util.LinkedHashMap;

public class MapData<K,V> extends LinkedHashMap {
    //使用單一的Generator<Pair<k,v>>
    public MapData(Generator<Pair<K,V>> gen ,int quantity){
        for (int i = 0; i < quantity; i++) {
            Pair<K,V> p = gen.next();
            put(p.key,p.value);
        }
    }
    //兩個分離的Generator
    public MapData(Generator<K> genK,Generator<V> genV,int quanlity){
        for (int i = 0; i < quanlity; i++) {
            put(genK.next(), genV.next());
        }
    }
    //一個Generator和一個常量值
    public MapData(Generator<K> genK,V value,int quanlity){
        for (int i = 0; i < quanlity; i++) {
            put(genK.next(),value);
        }
    }
    //一個Iterable(包括任何Collection)和一個Generator
    public MapData(Iterable<K> genK,Generator<V> genV){
        for (K key:genK){
            put(key,genV.next());
        }
    }
    //一個Iterable和一個單一值
    public MapData(Iterable<K> genK,V value){
        for (K k:genK){
            put(k,value);
        }
    }


    public static <K,V> MapData<K,V> map(Generator<Pair<K,V>> gen,int quantity){
        return new MapData<K, V>(gen,quantity);
    }

    public static <K,V> MapData<K,V> map(Generator<K> genK,V value,int quantity){
        return new MapData<K, V>(genK,value,quantity);
    }

    public static <K,V> MapData<K,V> map(Iterable<K> genK,Generator<V> genV){
        return new MapData<K, V>(genK,genV);
    }

    public static <K,V> MapData<K,V> map (Iterable<K> genK,V value){
        return new MapData<K, V>(genK,value);
    }

}

17.2.3 使用Abstract類

享元:可以在普通的解決方案需要過多的對象,或者生產(chǎn)普通對象太占用空間時使用.享元模式使得對象的一部分可以被具體化,所以,與對象中的所有事務(wù)都包含在對象內(nèi)部不同,可以更加高效的外部表中查找對象的一部分或整體(或者通過某些其他節(jié)省空間的計(jì)算來產(chǎn)生對象的一部分貨整體).

可以通過繼承java.util.Abstract來創(chuàng)建定制的Map和Collection. 為了創(chuàng)建只讀的Map, 可以繼承AbstractMap并實(shí)現(xiàn)entrySet(). 為了創(chuàng)建只讀的Set, 可以繼承AbstractSet并實(shí)現(xiàn)iterator()和size().

17.3 Collection的功能方法

注意:其中不包括隨機(jī)訪問所選擇元素的get()方法. 因?yàn)镃ollection包括set, 而set是自己維護(hù)內(nèi)部順序的(這使得所及訪問變得沒有意義). 因此, 如果想檢查Collection中的元素, 就必須使用迭代器.

17.4 可選操作

執(zhí)行各種不同的添加和移除的方法在Collection接口中都是可選操作. 這意味著實(shí)現(xiàn)類并不需要為這些方法提供功能接口.

為什么將方法定義為可選的?

因?yàn)檫@樣做可以防止在設(shè)計(jì)中出現(xiàn)接口爆炸的情況. 容器類庫中的其他設(shè)計(jì)看起來總是為了描述某個主題的各種變體, 而最終患上了令人困惑的接口過剩癥. 甚至這么做仍不能捕捉接口的各種特例, 因?yàn)榭偸菚l(fā)明新的接口. "未獲得支持的操作" 這種方式可以實(shí)現(xiàn)Java容器類庫的一個重要目標(biāo): 容器應(yīng)該易學(xué)易用. 未獲支持的操作是一種特例, 可以延遲到需要時在實(shí)現(xiàn).

1. UnsupportOperationException必須是一種罕見事件. 即, 對于大多數(shù)類來說, 所有操作都應(yīng)該可以工作, 只有在特例中才會有位或支持的操作. 在Java容器類庫中確實(shí)如此, 因?yàn)樵诖蠖鄶?shù)使用的容器, 如ArrayList, LinkedList, HashSet和HashMap, 以及其他的具體實(shí)現(xiàn), 都支持所有的操作. 這種設(shè)計(jì)有一個弊端, 如果想創(chuàng)建新的Collection, 但是沒有為Collection接口中的所有方法都提供有意義的定義, 那么它仍舊適合現(xiàn)有的類庫.
2. 如果一個操作是未獲支持的,那么在實(shí)現(xiàn)接口的時候可能會導(dǎo)致UnsupportedOperationException異常.

17.4.4 未獲支持的操作

最常見的未獲支持的操作, 都來源于背后由固定尺寸的數(shù)據(jù)接口支持的容器. 當(dāng)用Arrays.asList()將數(shù)組轉(zhuǎn)換為List時, 就會得到這樣的數(shù)組.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

/*473*/
public class Unsupported {
    static void test(String msg, List<String> list) {
        System.out.println("--- " + msg + " ---");
        Collection<String> c = list;
        Collection<String> subList = list.subList(1,8);
        Collection<String> c2 = new ArrayList<String>(subList);
        try {
            c.retainAll(c2);
        }
        catch(Exception e) {
            System.out.println("retainAll(): " + e);
        }
        try { c.removeAll(c2); } catch(Exception e) {
            System.out.println("removeAll(): " + e);
        }
        try { c.clear(); } catch(Exception e) {
            System.out.println("clear(): " + e);
        }
        try { c.add("X"); } catch(Exception e) {
            System.out.println("add(): " + e);
        }
        try { c.addAll(c2); } catch(Exception e) {
            System.out.println("addAll(): " + e);
        }
        try { c.remove("C"); } catch(Exception e) {
            System.out.println("remove(): " + e);
        }
        // The List.set() 雖然改變了值但沒有改變它的數(shù)據(jù)結(jié)構(gòu)尺寸
        try {
            list.set(0, "X");
        } catch(Exception e) {
            System.out.println("List.set(): " + e);
        }
    }
    public static void main(String[] args) {
        List<String> list =
                Arrays.asList("A B C D E F G H I J K L".split(" "));
        System.out.println(list.getClass());
        test("Arrays.asList()", list);
        // System.out.println(list1.getClass());
        test("Modifiable Copy", new ArrayList<String>(list));
        //test("unmodifiableList()",Collections.unmodifiableList(new ArrayList<String>(list)));
    }
}

因?yàn)锳rrays.asList()會生成一個list, 它基于一個固定大小的數(shù)組, 僅支持哪些不會改變數(shù)組大小的操作. 任何會引起對底層數(shù)據(jù)結(jié)構(gòu)的尺寸進(jìn)行修改的方法都會產(chǎn)生一個UnsupportedOperationException異常,以表示對未獲支持操作的調(diào)用.

Arrays.asList()返回固定尺寸的List, 而Collections.unmodifiableList()產(chǎn)生不可修改的列表.

17.5 List的功能方法

import java.util.*;
import static net.mindview.util.Print.print;
import static net.mindview.util.Print.printnb;

public class Lists {
    private static boolean b;
    private static String s;
    private static int i;
    private static Iterator<String> it;
    private static ListIterator<String> lit;
    public static void basicTest(List<String> a) {
        a.add(1, "x"); // Add at location 1
        a.add("x"); // Add at end
        // Add a collection:
        a.addAll(Countries.names(25));
        // Add a collection starting at location 3:
        a.addAll(3, Countries.names(25));
        b = a.contains("1"); // Is it in there?
        // Is the entire collection in there?
        b = a.containsAll(Countries.names(25));
        // Lists allow random access, which is cheap
        // for ArrayList, expensive for LinkedList:
        s = a.get(1); // Get (typed) object at location 1
        i = a.indexOf("1"); // Tell index of object
        b = a.isEmpty(); // Any elements inside?
        it = a.iterator(); // Ordinary Iterator
        lit = a.listIterator(); // ListIterator
        lit = a.listIterator(3); // Start at loc 3
        i = a.lastIndexOf("1"); // Last match
        a.remove(1); // Remove location 1
        a.remove("3"); // Remove this object
        a.set(1, "y"); // Set location 1 to "y"
        // Keep everything that's in the argument
        // (the intersection of the two sets):
        a.retainAll(Countries.names(25));
        // Remove everything that's in the argument:
        a.removeAll(Countries.names(25));
        i = a.size(); // How big is it?
        a.clear(); // Remove all elements
    }

    public static void iterMotion(List<String> a){
        ListIterator<String> it = a.listIterator();
        b = it.hasNext();
        b = it.hasPrevious();
        s = it.next();
        i = it.nextIndex();
        s = it.previous();
        i = it.previousIndex();
    }

    public static void iterManipulation(List<String> a) {
        ListIterator<String> it = a.listIterator();
        it.add("47");
        // Must move to an element after add():
        it.next();
        // Remove the element after the newly produced one:
        it.remove();
        // Must move to an element after remove():
        it.next();
        // Change the element after the deleted one:
        it.set("47");
    }
    public static void testVisual(List<String> a) {
        print(a);
        List<String> b = Countries.names(25);
        print("b = " + b);
        a.addAll(b);
        a.addAll(b);
        print(a);
        // Insert, remove, and replace elements
        // using a ListIterator:
        ListIterator<String> x = a.listIterator(a.size()/2);
        x.add("one");
        print(a);
        print(x.next());
        x.remove();
        print(x.next());
        x.set("47");
        print(a);
        // Traverse the list backwards:
        x = a.listIterator(a.size());
        while(x.hasPrevious())
            printnb(x.previous() + " ");
        print();
        print("testVisual finished");
    }
    // There are some things that only LinkedLists can do:
    public static void testLinkedList() {
        LinkedList<String> ll = new LinkedList<String>();
        ll.addAll(Countries.names(25));
        print(ll);
        // Treat it like a stack, pushing:
        ll.addFirst("one");
        ll.addFirst("two");
        print(ll);
        // Like "peeking" at the top of a stack:
        print(ll.getFirst());
        // Like popping a stack:
        print(ll.removeFirst());
        print(ll.removeFirst());
        // Treat it like a queue, pulling elements
        // off the tail end:
        print(ll.removeLast());
        print(ll);
    }
    public static void main(String[] args) {
        // Make and fill a new list each time:
        basicTest(
                new LinkedList<String>(Countries.names(25)));
        basicTest(
                new ArrayList<String>(Countries.names(25)));
        iterMotion(
                new LinkedList<String>(Countries.names(25)));
        iterMotion(
                new ArrayList<String>(Countries.names(25)));
        iterManipulation(
                new LinkedList<String>(Countries.names(25)));
        iterManipulation(
                new ArrayList<String>(Countries.names(25)));
        testVisual(
                new LinkedList<String>(Countries.names(25)));
        testLinkedList();
    }

}

17.6 Set和存儲順序

在HashSet上打星號表示, 如果沒有其他的限制, 這應(yīng)該就是默認(rèn)的選擇, 因?yàn)樗鼘λ俣冗M(jìn)行了優(yōu)化.

必須為散列存儲和樹形存儲都創(chuàng)建一個equals()方法, 但是hashCode()只有在這個類將會被置于HashSet(這是有可能的, 因?yàn)樗ǔＪ荢et實(shí)現(xiàn)的首選)或者LinkedHashSet中時才是必須的. 對于良好的編程風(fēng)格, 應(yīng)該覆蓋equals() 方法時, 同時覆蓋hashCode()方法.

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

/*p477*/
class SetType{
    int i;
    public SetType(int n){i = n;}
    public boolean equals(Object o){return o instanceof SetType && (i == ((SetType)o).i);}
    public String toString(){return Integer.toString(i);}
}

class HashType extends SetType{
    public HashType(int n) {super(n);}
    public int hashCode(){return i;}
}

class TreeType extends SetType implements Comparable<TreeType>{
    public TreeType(int n) {super(n);}

    public int compareTo(TreeType arg) {
        return (arg.i<i ? -1:(arg.i ==i ? 0:1));
    }
}

public class TypesForSets {
    static <T> Set<T> fill(Set<T> set, Class<T> type) {
        try {
            for(int i = 0; i < 10; i++)
                set.add(
                        type.getConstructor(int.class).newInstance(i));
        } catch(Exception e) {
            throw new RuntimeException(e);
        }
        return set;
    }
    static <T> void test(Set<T> set, Class<T> type) {
        fill(set, type);
        fill(set, type); // Try to add duplicates
        fill(set, type);
        System.out.println(set);
    }
    public static void main(String[] args) {
        test(new HashSet<HashType>(), HashType.class);
        test(new LinkedHashSet<HashType>(), HashType.class);
        test(new TreeSet<TreeType>(), TreeType.class);
        // Things that don't work:
        test(new HashSet<SetType>(), SetType.class);
        test(new HashSet<TreeType>(), TreeType.class);
        test(new LinkedHashSet<SetType>(), SetType.class);
        test(new LinkedHashSet<TreeType>(), TreeType.class);
        try {
            test(new TreeSet<SetType>(), SetType.class);
        } catch(Exception e) {
            System.out.println(e.getMessage());
        }
        try {
            test(new TreeSet<HashType>(), HashType.class);
        } catch(Exception e) {
            System.out.println(e.getMessage());
        }
    }
}
/* Output: (Sample)
[2, 4, 9, 8, 6, 1, 3, 7, 5, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[9, 9, 7, 5, 1, 2, 6, 3, 0, 7, 2, 4, 4, 7, 9, 1, 3, 6, 2, 4, 3, 0, 5, 0, 8, 8, 8, 6, 5, 1]
[0, 5, 5, 6, 5, 0, 3, 1, 9, 8, 4, 2, 3, 9, 7, 3, 4, 4, 0, 7, 1, 9, 6, 2, 1, 8, 2, 8, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
java.lang.ClassCastException: SetType cannot be cast to java.lang.Comparable
java.lang.ClassCastException: HashType cannot be cast to java.lang.Comparable
*///:~

基類SetType只存儲一個int, 并且通過toString()方法產(chǎn)生它的值. 因?yàn)樗性赟et中存儲的類型都必須具有equals()方法.

HashType繼承自SetType, 并且添加了hashCode()方法, 該方法對于放置到Set的散列實(shí)現(xiàn)中的對象來說是必須的.

TreeType實(shí)現(xiàn)了Comparable接口, 如果一個對象被用于任何種類的排序容器中, 例如SortedSet(TreeSet是其唯一實(shí)現(xiàn)),那么它必須實(shí)現(xiàn)這個接口.

17.6.1 SortedSet

SortedSet中的元素可以保證處于排序狀態(tài), 這使得它可以通過在SortedSet接口中的下列方法提供附加功能: Comparator comparator()返回當(dāng)前Set使用的Comparator; 或者返回null, 表示以自然方式排序.

• Object first()返回容器中的第一個元素
• Object last()返回容器中的最末一個元素
• SortedSet subSet(fromElement, toElement)生成此Set的子集, 范圍從fromElement(包含)到toElement(不包含)
• SortedSet headSet(toElement)生成此Set的子集, 由小于toElement的元素組成.
• SortedSet tailSet(fromElement)生成此Set的子集, 由大于或等于fromElement的元素組成.

import java.util.Collections;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
import static net.mindview.util.Print.print;

/*p479*/
public class SortedSetDemo {
    public static void main(String[] args) {
        SortedSet<String> sortedSet = new TreeSet<String>();
        Collections.addAll(sortedSet,"one tow three four five six seven eight".split(" "));
        print(sortedSet);
        String low = sortedSet.first();
        String high = sortedSet.last();
        print(low);
        print(high);
        Iterator<String> it = sortedSet.iterator();
        for (int i = 0; i <= 6; i++) {
            if (i==3) low = it.next();
            if (i==6) high = it.next();
            else it.next();
        }

        print(low);
        print(high);
        print(sortedSet.subSet(low,high));
        print(sortedSet.headSet(high));
        print(sortedSet.tailSet(low));

    }
}
/*output
[eight, five, four, one, seven, six, three, tow]
eight
tow
one
tow
[one, seven, six, three]
[eight, five, four, one, seven, six, three]
[one, seven, six, three, tow]
*/

17.7 隊(duì)列

除了并發(fā)應(yīng)用, Queue在Java SE5中僅有兩個實(shí)現(xiàn):LinkedList和PriorityQueue,他們的差異在于排序行為而不是性能.

import fifteen.Generator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.*;

/*p480*/
public class QueueBehavior {
    private static int count = 10;
    static <T> void test(Queue<T> queue, Generator<T> gen){
        for (int i=0;i<count;i++){
            queue.offer(gen.next());
        }
        while (queue.peek()!=null){
            System.out.print(queue.remove() + " ");
        }
        System.out.println();
    }
    static class Gen implements Generator<String>{
        String[] s = "one two three four five six seven eight nine ten".split(" ");
        int i;
        public String next() {
            return s[i++];
        }
    }

    public static void main(String[] args) {
        test(new LinkedList<String>(),new Gen());
        test(new PriorityQueue<String>(),new Gen());
        test(new ArrayBlockingQueue<String>(count),new Gen());
        test(new ConcurrentLinkedQueue<String>(),new Gen());
        test(new LinkedBlockingQueue<String>(),new Gen());
        test(new PriorityBlockingQueue<String>(),new Gen());
    }

}
/*
output:
one two three four five six seven eight nine ten 
eight five four nine one seven six ten three two 
one two three four five six seven eight nine ten 
one two three four five six seven eight nine ten 
one two three four five six seven eight nine ten 
eight five four nine one seven six ten three two 
*/

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

該列表中每個對象都包含一個字符串和一個主要的以及次要的優(yōu)先級值. 該列表的排序順序也是通過實(shí)現(xiàn)Comparable而進(jìn)行控制的.

import java.util.PriorityQueue;
/*p481*/
class ToDoList extends PriorityQueue<ToDoList.ToDoItem>{
    static class ToDoItem implements Comparable<ToDoItem>{
        private char primary;
        private int secondary;
        private String item;

        public ToDoItem(String td,char pri,int sec) {
            primary = pri;
            secondary = sec;
            item = td;
        }

        public int compareTo(ToDoItem arg) {

            if (primary>arg.primary) return +1;
            if (primary == arg.primary)
                if (secondary > arg.secondary)
                    return +1;
                else if (secondary == arg.secondary)
                    return 0;
            return -1;
        }

        @Override
        public String toString() {
            return Character.toString(primary) + secondary + ":" + item;
        }
    }
    public void add(String td,char pri ,int sec){
        super.add(new ToDoItem(td,pri,sec));
    }

    public static void main(String[] args) {
        ToDoList toDoList = new ToDoList();
        toDoList.add("Empty trash", 'C', 4);
        toDoList.add("Feed dog", 'A', 2);
        toDoList.add("Feed bird", 'B', 7);
        toDoList.add("Mow lawn", 'C', 3);
        toDoList.add("Water lawn", 'A', 1);
        toDoList.add("Feed cat", 'B', 1);
        while(!toDoList.isEmpty())
            System.out.println(toDoList.remove());
    }

}
/*output
A1:Water lawn
A2:Feed dog
B1:Feed cat
B7:Feed bird
C3:Mow lawn
C4:Empty trash
*/

17.7.2 雙向隊(duì)列

雙向隊(duì)列(雙端隊(duì)列)就像是一個隊(duì)列, 但是可以在任何一段添加或移除元素. 在LinkedList中包含支持雙向隊(duì)列的方法, 但是在Java標(biāo)準(zhǔn)類庫中沒有任何顯示的用于雙向隊(duì)列的接口. 因此, LinkedList無法去實(shí)現(xiàn)這樣的接口,也無法像前面示例中轉(zhuǎn)型到Queue那樣去向上轉(zhuǎn)型到DDeque. 但是++可以組合來創(chuàng)建一個Deque類++, 并直接從LinkedList中暴露相關(guān)的方法:

import java.util.LinkedList;
/*p480*/
public class Deque<T> {
    private LinkedList<T> deque = new LinkedList<T>();
    public void addFirst(T e){deque.addFirst(e);}
    public void addLast(T e){deque.addLast(e);}
    public T getFirst(){return deque.getFirst();}
    public T getLast(){return deque.getLast();}
    public T removeFirst(){return deque.removeFirst();}
    public T removeLast(){return deque.removeLast();}
    public int size(){return deque.size();}

    @Override
    public String toString() {
        return deque.toString();
    }
}

17.8 理解Map

標(biāo)準(zhǔn)的Java類庫中包含了Map的幾種基本實(shí)現(xiàn), 包括:HashMap, TreeMap, LinkedHashMap, WeakHashMap, CouncurrentHashMap, IdentityHashMap.

17.8.1 性能

性能是映射表中的一個重要問題, 擋在get()中使用線性搜索時, 執(zhí)行速度回相當(dāng)?shù)芈? 而這正是HashMap提高速度的地方. HashMap使用了特殊的值, 稱作散列碼, 來取代對鍵的緩慢搜索. 散列碼是"相對唯一"的,用以代表對象的int值, 它是通過將該對象的某些信息進(jìn)行轉(zhuǎn)換而生成的. hashCode()是根類Object中的方法, 因此所有Java對象都能產(chǎn)生散列碼. HashMap就是使用對象的hashCode()進(jìn)行快速查詢的, 此方法能夠顯著提高性能.

散列是映射中存儲元素時最常用的方式.

17.8.2 SortedMap

使用SortedMap(TreeMap是其現(xiàn)階段的唯一實(shí)現(xiàn)),可以確保鍵處于排序狀態(tài).

Comparator comparator():返回當(dāng)前Map使用的Comparator;或者返回null, 表示以自然方式排序. T firstKey()返回Map中的第一個鍵. T lastKey()返回Map中的最末一個鍵. SortedMap subMap(fromKey,toKey)生成此Map的子集, 范圍由fromKey(包含)到tokey(不包含)的鍵確定. SortedMap headMap(toKey)生成此Map的子集, 由鍵大于或等于fromKey的所有鍵值對組成.

鍵值對是按鍵的次序排序的. TreeMap中的次序是有意義的, 因此"位置"的概念才有意義, 所以才能取得第一個和最后一個元素, 并且可以提取Map的子集.

17.8.3 LinkedHashMap

為了提高速度,LinkedHashMap散列化所有的元素, 但是在遍歷鍵值對時, 卻又以元素的插入順序返回鍵值對(System.out.println()會迭代遍歷該映射, 因此可以看到遍歷的結(jié)果). 此外, 可以在構(gòu)造器中設(shè)定LinkedHashMap, 使之采用基于訪問的最近最少使用(LRU)算法, 于是沒有被訪問過的(可能看做需要刪除的)元素就會出現(xiàn)在隊(duì)列的前面. 對于需要定期清理元素以節(jié)省空間的程序來說, 此功能使得程序很容易得以實(shí)現(xiàn).

import net.mindview.util.CountingMapData;

import java.util.LinkedHashMap;

import static net.mindview.util.Print.print;

/*p487*/
public class LinkedHashMapDemo {
    public static void main(String[] args) {
        LinkedHashMap<Integer,String> linkedMap = new LinkedHashMap<Integer, String>(new CountingMapData(9));
        print(linkedMap);
        linkedMap = new LinkedHashMap<Integer, String>(16,0.75f,true);
        linkedMap.putAll(new CountingMapData(9));
        print(linkedMap);
        for (int i = 0; i < 6; i++)
            linkedMap.get(i);
        print(linkedMap);
        linkedMap.get(0);
        print(linkedMap);

    }
}
/*output:
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{6=G0, 7=H0, 8=I0, 0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0}
{6=G0, 7=H0, 8=I0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 0=A0}
*/

17.9 散列與散列碼

HashMap使用equals()方法判斷當(dāng)前的鍵是否與表中存在的鍵相同. 正確的equals()方法必須滿足下列5個條件:

1. 自反性. 對任意x, x.equals(x)一定返回true
2. 對稱性. 對任意x和y, 如果y.equals(x)返回true, 則x.equals(y)也返回true.
3. 傳遞性. 對任意x,y,z, 如果有x.equals(y)返回true, y.equals(z)返回true, 則x.equals(z)一定返回true.
4. 一致性. 對任意x和y, 如果對象中用于等價比較的信息沒有改變, 那么無論調(diào)用x.equals(y)多少次, 返回的結(jié)果應(yīng)該保持一致, 要么一直是true, 要么一直是false.
5. 對任何不是null的x,x.equals(null)一定返回false.

默認(rèn)的Object.equals()只是比較對象的地址

在HashSet中使用自己的類作為鍵

17.9.1 理解hashCode()

17.9.2 為速度而散列

散列將鍵保存在某處, 以便能夠很快找到. 存儲一組元素最快的數(shù)據(jù)結(jié)構(gòu)是數(shù)組, 所以使用它來表示鍵的信息(是鍵的信息, 而不是鍵本身). 但是數(shù)組不能調(diào)整容量, 因此

數(shù)組本身并不保存鍵本身. 而是通過鍵對象生成一個數(shù)組, 將其作為數(shù)組的下標(biāo). 這個數(shù)字就是散列碼, 由定義在Object中的,且可能由自定義的類覆蓋的hashCode()方法(在計(jì)算機(jī)科學(xué)的術(shù)語中稱為散列函數(shù))生成.

為解決數(shù)組容量被固定的問題, 不同的鍵可以產(chǎn)生相同的下標(biāo). 也就是說, 可能會有沖突, 因此, 數(shù)組多大就不重要了, 任何鍵總能在數(shù)組中找到它的位置.

于是查詢一個值的過程首先就是計(jì)算散列碼, 然后使用散列碼查詢數(shù)組. 如果能夠保證沒有沖突(如果值的數(shù)量是固定的, 那么就有可能), 那可能就有一個完美的散列函數(shù), 但是這種情況只是特例. 通常沖突由外部鏈接處理: 數(shù)組并不直接保存值, 而是保存值的list. 然后對list的值使用equals()方法進(jìn)行線性的查詢. 這部分的查詢自然會比較慢, 但是如果散列函數(shù)好的話, 數(shù)組的每個位置就只有較少的值. 因此, 不是查詢整個list, 而是快速地跳到數(shù)組的某個位置, 只對很少的元素進(jìn)行比較.

import java.util.*;

public class SimpleHashMap<K,V> extends AbstractMap<K,V>{
    static final int SIZE = 997;
    LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];
    public V put(K key, V value){
        V oldValue = null;
        int index = Math.abs(key.hashCode())%SIZE;
        if (buckets[index] == null) buckets[index] = new LinkedList<MapEntry<K, V>>();
        LinkedList<MapEntry<K,V>> bucket = new LinkedList<MapEntry<K, V>>();
        MapEntry<K,V> pair = new MapEntry<K, V>(key,value);
        boolean fouond = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        while (it.hasNext()){
            MapEntry<K,V> iPair = it.next();
            if (iPair.getKey().equals(key)){
                oldValue = iPair.getValue();
                it.set(pair);
                fouond = true;
                break;
            }
        }
        if (!fouond) buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key){
        int index = Math.abs(key.hashCode())%SIZE;
        if (buckets[index] == null) return null;
        for (MapEntry<K,V> iPair:buckets[index])
            if (iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Entry<K, V>> entrySet() {
        Set<Map.Entry<K,V>> set = new HashSet<Entry<K, V>>();
        for (LinkedList<MapEntry<K,V>> bucket : buckets){
            if (bucket == null) continue;
            for (MapEntry<K,V> mpair:bucket)
                set.add(mpair);
        }
        return set;
    }
}

17.9.3 覆蓋hashCode()

String有個特點(diǎn): 如果程序中有多個String對象, 都包含相同的字符串序列, 那么這些String對象都映射到相同的一塊內(nèi)存區(qū)域. 所以new String("Hello")生成的兩個實(shí)例, 雖然是相互獨(dú)立地, 但是對它們使用hashCode應(yīng)該生成同樣的結(jié)果.

要想使hashCode()實(shí)用, 它必須速度快, 并且必須有意義. 也就是說, 它必須基于對象的內(nèi)容生成散列碼. 散列碼不必是獨(dú)一無二的(應(yīng)該更關(guān)注生成速度, 而不是唯一性), 但是通過hashCode()和equals(), 必須能夠完全確定對象的身份.

好的hashCode()應(yīng)該產(chǎn)生分布均勻的散列碼. 如果散列碼都幾種在一塊, 那么HashMap或HashSet在某些區(qū)域的負(fù)載會很重.

17.10 選擇接口的不同實(shí)現(xiàn)

有時某個特定容器的不同實(shí)現(xiàn)會擁有一些共同的操作, 但是這些操作的性能卻并不相同. 在這種情況下, 可以基于使用某個特定操作的頻率, 以及需要執(zhí)行的速度來在它們中間進(jìn)行選擇. 對于類似地情況, 一種查看容器實(shí)現(xiàn)之間的差異的方式是使用性能測試.

看書p499

17.10.2 對List的選擇

對于由數(shù)組職稱的List和ArrayList, 無論列表的大小如何, 這些訪問都很快速和一致; 而對于LinkedList, 訪問時間對于較大的列表將明顯增減.

對于ArrayList, 當(dāng)列表變大時, 其開銷將變得很高昂, 但對于LinkedList, 相對來說比較低廉, 并且不隨列表尺寸而發(fā)生變化. 這是因?yàn)锳rrayList在插入時, 必須創(chuàng)建空間并將它的所有引用向前移動, 這會隨ArrayList的尺寸增加而產(chǎn)生高昂的代價. LinkedList只需鏈接新的元素, 而不必修改列表中剩余的元素, 因此可以認(rèn)為無論列表尺寸如何變化, 其代價大致相同.

17.10.3 微基準(zhǔn)測試的危險

p507

17.10.4 對Set的選擇

HashSet的性能基本上總是比TreeSet好, 特別是在添加和查詢元素時, 而這兩個操作也是最重要的操作. TreeSet存在的唯一原因是它可以維持元素的排序狀態(tài); 所以只有當(dāng)需要一個排好序的Set時, 才應(yīng)該使用TreeSet. 因?yàn)槠鋬?nèi)部結(jié)構(gòu)支持排序, 并且因?yàn)榈歉锌赡軋?zhí)行的操作, 所以TreeSet迭代通常比用HashSet要快.

對于插入操作, LinkedHashSet比HashSet的代價更高, 這是由維護(hù)鏈表所帶來的額外開銷造成的.

17.10.5 對Map的選擇

除了IndentityHashMap, 所有的Map實(shí)現(xiàn)的插入操作都會隨著Map尺寸的變大而明顯變慢. 但是查找的代價通常比插入要小得多,

HashTable的性能大體上與HashMap相當(dāng). 因?yàn)镠ashMap是用來代替HashTable的, 因此他們使用了相同的底層存儲和查找機(jī)制.

TreeMap通常比HashMap要慢. 與使用TreeSet一樣, TreeMap是一種創(chuàng)建有序列表的方式. 樹的行為:總是保證有序, 并且不必進(jìn)行特殊排序. 一旦填充了一個TreeMap, 就可以調(diào)用keySet()來獲取鍵的Set視圖, 然后調(diào)用toArray()來產(chǎn)生由這些鍵構(gòu)成的數(shù)組. 之后可以使用靜態(tài)方法Arrays.binarySearch()在排序數(shù)組中快速查找對象. 當(dāng)然這只有在HashMap的行為不可接受的情況下才有意義, 因?yàn)镠ashMap本身就被設(shè)計(jì)為可以快速查找鍵.

LinkedHashMap在插入時比HashMap慢一點(diǎn), 因?yàn)樗S護(hù)散列表數(shù)據(jù)結(jié)構(gòu)的同時還要維護(hù)鏈表(以保持插入順序).

IdentityHashMap則具有完全不同的性能, 因?yàn)樗褂?=而不是equals()來比較元素.

HashMap參數(shù):

• 容量:表中的桶位數(shù)
• 初始容量:表在創(chuàng)建時所擁有的桶位數(shù). HashMap和HashSet都具有允許你指定初始容量的構(gòu)造器
• 尺寸:表中當(dāng)前存儲的項(xiàng)數(shù).
• 負(fù)載因子: 尺寸/容量.

17.11 實(shí)用方法

課本p512

17.11.1 List的排序和查詢

17.11.2 設(shè)定Collection或Map為不可修改

import java.util.*;
import static net.mindview.util.Print.print;

public class ReadOnly {
    static Collection<String> data =
            new ArrayList<String>(Countries.names(6));
    public static void main(String[] args) {
        Collection<String> c =
                Collections.unmodifiableCollection(
                        new ArrayList<String>(data));
        print(c); // Reading is OK
        //! c.add("one"); // Can't change it

        List<String> a = Collections.unmodifiableList(
                new ArrayList<String>(data));
        ListIterator<String> lit = a.listIterator();
        print(lit.next()); // Reading is OK
        //! lit.add("one"); // Can't change it

        Set<String> s = Collections.unmodifiableSet(
                new HashSet<String>(data));
        print(s); // Reading is OK
        //! s.add("one"); // Can't change it

        // For a SortedSet:
        Set<String> ss = Collections.unmodifiableSortedSet(
                new TreeSet<String>(data));

        Map<String,String> m = Collections.unmodifiableMap(
                new HashMap<String,String>(Countries.capitals(6)));
        print(m); // Reading is OK
        //! m.put("Ralph", "Howdy!");

        // For a SortedMap:
        Map<String,String> sm =
                Collections.unmodifiableSortedMap(
                        new TreeMap<String,String>(Countries.capitals(6)));
    }
} 

對特定類型"不可修改"的方法的調(diào)用并不會產(chǎn)生編譯時的檢查, 但是轉(zhuǎn)換完成后, 任何改變?nèi)萜鞯膬?nèi)容的操作都會引起UnsupportedOperationExection異常.

17.11.3 Collection或Map的同步控制

import java.util.*;

public class Synchronization {
    public static void main(String[] args) {
        Collection<String> c = Collections.synchronizedList(new ArrayList<String>());
        List<String> list = Collections.synchronizedList(new ArrayList<String>());
        Set<String> set = Collections.synchronizedSet(new HashSet<String>());
        Map<String,String> map = Collections.synchronizedMap(new HashMap<String, String>());
    }
}

快速報(bào)錯

Java容器有一種保護(hù)機(jī)制, 能夠防止多個進(jìn)程同時修改同一個容器的內(nèi)容. 如果在迭代遍歷某個容器的工程中, 另一個進(jìn)程介入其中, 并且插入, 刪除或修改此容器內(nèi)的某個對象, 那么就會出現(xiàn)問題: 也許迭代過程已經(jīng)處理過容器中的該元素, 也許還沒處理, 也許在調(diào)用size之后容器的尺寸收縮了--還有許多災(zāi)難情景. Java容器類類庫采用快速報(bào)錯機(jī)制. 它會檢查容器上的任何除了你的進(jìn)程所進(jìn)行的操作以外的所有變化, 一旦它發(fā)現(xiàn)其他進(jìn)程修改了容器, 就會立刻拋出ConcurrentModificationException異常.

ConcurrentHashMap,CopyOnWriteArrayList和CopyOnWriteArraySet都使用了可以避免ConcurrentModificationException的技術(shù)

17.12 持有引用

有三個繼承自抽象類Reference的類:SoftReference,WeakReference和PhantomReference.

對象是++可獲得的++(reachable), 是指此對象可在程序中的某處找到. 這意味著在棧中有一個普通的引用, 而它正指向此對象; 也可能是引用指向某個對象, 而那個對象含有零一個引用向正在討論對象; 也可能有更多的中間鏈接. 如果一個對象是"可獲得的",垃圾回收器就不能釋放它, 因?yàn)樗匀粸槌绦蛩? 如果一個對象不是"可獲得的", 那么程序?qū)o法使用到它, 所以將其回收是安全的.

SoftReference, WeakReference和Phantomreference由強(qiáng)到弱排列, 對應(yīng)不同級別的"可獲得性". Softreference用以實(shí)現(xiàn)內(nèi)存敏感的高速緩存. Weakreference是為實(shí)現(xiàn)"規(guī)范映射"而設(shè)計(jì)的, 它不妨礙垃圾回收映射"鍵"(或"值"). "規(guī)范映射"中對象的實(shí)例可以在程序的多處被同時使用, 以節(jié)省存儲空間. Phantomreference用以調(diào)度回收前的清理工作, 它比Java終止機(jī)制更靈活.

import java.lang.ref.*;
import java.util.*;

class VeryBig{
    private static final int SIZE = 10000;
    private long[] la = new long[SIZE];
    private String ident;
    public VeryBig(String id){ident = id;}
    public String toString (){return ident;}
    protected void finalize(){
        System.out.println("Finalizing" + ident);
    }
}

public class References {
    private static ReferenceQueue<VeryBig> rq =
            new ReferenceQueue<VeryBig>();
    public static void checkQueue() {
        Reference<? extends VeryBig> inq = rq.poll();
        if(inq != null)
            System.out.println("In queue: " + inq.get());
    }
    public static void main(String[] args) {
        int size = 10;
        // Or, choose size via the command line:
        if(args.length > 0)
            size = new Integer(args[0]);
        LinkedList<SoftReference<VeryBig>> sa =
                new LinkedList<SoftReference<VeryBig>>();
        for(int i = 0; i < size; i++) {
            sa.add(new SoftReference<VeryBig>(
                    new VeryBig("Soft " + i), rq));
            System.out.println("Just created: " + sa.getLast());
            checkQueue();
        }
        LinkedList<WeakReference<VeryBig>> wa =
                new LinkedList<WeakReference<VeryBig>>();
        for(int i = 0; i < size; i++) {
            wa.add(new WeakReference<VeryBig>(
                    new VeryBig("Weak " + i), rq));
            System.out.println("Just created: " + wa.getLast());
            checkQueue();
        }
        SoftReference<VeryBig> s =
                new SoftReference<VeryBig>(new VeryBig("Soft"));
        WeakReference<VeryBig> w =
                new WeakReference<VeryBig>(new VeryBig("Weak"));
        System.gc();
        LinkedList<PhantomReference<VeryBig>> pa =
                new LinkedList<PhantomReference<VeryBig>>();
        for(int i = 0; i < size; i++) {
            pa.add(new PhantomReference<VeryBig>(
                    new VeryBig("Phantom " + i), rq));
            System.out.println("Just created: " + pa.getLast());
            checkQueue();
        }
    }
}

第二十一章 并發(fā)

21.1 并發(fā)的多面性

用并發(fā)解決的問題大體上可以分為"速度"和"設(shè)計(jì)可管理性"兩種.

21.1.1 更快的執(zhí)行

并發(fā)是用于多處理編程的基本工具.

在單處理器上運(yùn)行的并發(fā)程序開銷確實(shí)應(yīng)該比改程序的所有部分都順序執(zhí)行的開銷大, 因?yàn)槠渲性黾恿怂^上下文切換的代價(從一個任務(wù)切換到另一個任務(wù)). 但是因?yàn)?strong>阻塞, 如果程序中的某個任務(wù)因?yàn)楦某绦蚩刂品秶獾哪承l件(通常是I/O)而導(dǎo)致不能繼續(xù)執(zhí)行, 那么就說這個任務(wù)或線程阻塞了.

21.2 基本的線程機(jī)制

并發(fā)編程可以將程序劃分為多個分離的,獨(dú)立運(yùn)行的任務(wù). 通過使用多線程機(jī)制, 這些獨(dú)立任務(wù)(也被稱為子任務(wù))中的每一個都將有執(zhí)行線程來驅(qū)動. 一個線程就是在進(jìn)程中的一個單一的順序控制流, 因此單個進(jìn)程可以擁有多個并發(fā)執(zhí)行的任務(wù), 其底層機(jī)制是切分CPU時間.

線程模型為編程帶來了便利, 它簡化了在單一程序中同時交織在一起的多個操作的處理. 在使用線程時, CPU將輪流給每個任務(wù)分配器占用時間. 每個任務(wù)都覺得自己在一直占用CPU, 但事實(shí)上CPU時間是劃分成片段分配給了所有的任務(wù)(例外:程序確實(shí)運(yùn)行在多個CPU之上).

21.2.1 定義任務(wù)

public class LiftOff implements Runnable{

    protected int countDown = 10;
    private static int taskCount = 0;
    private final int id = taskCount++;
    public LiftOff(){}

    public LiftOff(int countDown){this.countDown = countDown;}

    public String status(){
        return "#" + id + "(" + (countDown > 0 ? countDown : "Liftoff!") + "), ";
    }

    public void run() {
        while (countDown-->0){
            System.out.print(status());
            Thread.yield();
        }
    }
}

在run()中對靜態(tài)方法Thread.yield()的調(diào)用是對線程調(diào)度器(Java線程機(jī)制的一部分, 可以將CPU從一個線程轉(zhuǎn)移給另一個線程)的建議.

21.2.2 Thread類

public class BasicThreads {
    public static void main(String[] args) {
        Thread t = new Thread(new LiftOff());
        t.start();
        System.out.println("Wating for LiftOff");
    }
}

Thread構(gòu)造器只需要一個Runnable對象. 調(diào)用Thread對象的start()方法為該線程執(zhí)行必須的初始化操作, 然后調(diào)用Runnable的run()方法, 以便在這個新線程中啟動該任務(wù). 盡管start()看起來是產(chǎn)生一個對長期運(yùn)行方法的調(diào)用, 但是從輸出中可以看到, start()迅速地返回了, 因?yàn)閃aiting for LiftOff消息在倒計(jì)時完成之前就出現(xiàn)了. 實(shí)際上shiduLiftOff.run()的方法調(diào)用, 并且這個方法還沒有完成, 但是因?yàn)?/p>