第十一章 持有对象

Java实用类库还提供了一套相当完整的容器类来解决这个问题，其中基本的类型是List、Set、Queue和Map。这些对象类型也称为集合类，但由于J巴德类库中使用了Collection这个名字来代指该类库的一个特殊子集，所以可以使用了范围更广的术语“容器”称呼它们。

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类是有区别的,它们除了都是Object之外没有任何共性（如果一个类没有显示地声明继承自哪个类，那么它自动地继承自Object）。ArrayList保存的是Object，因此不仅可以通过ArrayList的add()方法将Apple对象放进容器，还可以添加Orange对象，而且无论在编译期还是运行时都不会有wenti8。当在使用ArrayList的get()方法来取出Apple对象时，其实得到的只是Object引用，必须将其转型为Apple，因此需要将整个表达式括起来，在滴阿勇Apple的id()方法之前，必须执行强制转型。

要想定义用来保存Apple对象的ArrayList，可以声明ArrayList<Apple>,而不仅仅只是ArrayList，其中尖括号括起来的是类型参数(可以有多个),它制定了这个容器实例可以保存的类型.

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);
        }
    }
}

当指定了某个类型作为泛型参数时,并不仅限于只能讲该确切类型的对象放置到容器中.向上转型也可以像作用于其他类型一样作用于泛型.

11.2基本概念

1. Collection.一个独立元素的序列,这些元素都服从一条或多条规则.List必须按照插入的顺序保存元素,而Set不能有重复元素.Queue按照排队规则来确定对象产生的顺序(通常与元素被插入的顺序相同).
2. Map.一组承兑的"键值对"对象,允许使用键来查找值.ArrayList允许使用数字来查找值,因此在某种意义上讲,它将数字与对象关联在一起.映射表允许我们是用另一个对象来查找某个对象,它也被称为"关联数组"或"字典"

11.3 添加一组元素

在java.util包中的Arrays和Collections类中都有很多使用方法,可以在一个Collection中添加一组元素.Arrays.asList()方法接收一个数组或是一个用逗号分隔的元素列表(使用多变参数),并将其转换为一个List对象.Collections.addAll()方法接收一个Collection对象,以及一个数组或是一个用逗号分好的列表,将元素添加到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的构造器可以接受另一个Collection,用来将自身初始化,因此可以使用Arrays.List()为这个构造器产生输入.但Collections.addAll()方法运行起来要快得多,而且构建一个不包含元素的Collection,然后调用Collections.addAll(),这种方式很方便,因此是首选.

Collection.addAll()成员方法只能接受另一个Collection对象作为参数,因此不如Arrays.asList()或Collections.addAll()灵活.

也可以直接使用Arrays.asList()的输出,将其当做List,但在这种情况下,其底层表示的是数组,因此不能调整尺寸.

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());
    }
}

正如从创建snow4的操作中,可以在Arrays.asList()中间差一条"线索",以告诉编译器对于由Arrays.asList()产生的List类型,实际的目标类型应该是什么,这称为显示类型参数说明

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容器类库中的两种主要类型,主要区别在于容器中每个"槽"保存的元素个数.Collection在每个槽中只能保存一个元素.此类容器包括:List,以特定的顺序保存一组元素;Set,元素不能重复;Queue,只允许在容器的一端插入对象,并从另外一端移除对象.Map在每个槽内保存两个对象,即键值对.

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

HashSet,TreeSet和LinkedHashSet都是Set类型,每个相同的项只保存一次.HashSet是最快的获取元素方式;TreeSet按照比较结果的升序保存对象;LinkedHashSet按照被添加的顺序保存对象.

Map可以用键来查找对象.键所关联的对象称为值.对于每个键,Map只接受存储一次.HashMap提供了最快的查找技术,没有按照任何明显顺序保存其元素.TreeMap按照比较结果的升序保存键;LinkedHashMap按照插入顺序保存键,同时还保留了HashMap的查询速度.

11.5 List

List接口在Collection的基础上添加了大量的方法,使得可以在List的中间插入和移除元素

• 基本的ArrayList,常用于随机访问元素,但是在List的中间插入和移除元素时较慢.
• LinkedList,通过代价较低的在List中间进行的插入和删除操作.提供了优化的顺序访问,LinkedList在随机访问方面相对较慢,但它的特性集较ArrayList更大.

contains()方法来确定某个对象是否在列表中,如果想移除一个对象,则可以将这个对象的引用传递给remove()方法.如果有一个对象的引用,则可以使用indexOf()来发现该对象在List中所处位置的索引编号.

当确定一个元素是否属于某个LIst,发现某个元素的索引,以及从某个List中移除一个元素,都会用到equals()方法(根类Object 的一部分).

在List中插入元素,对于LinkedList,在列表中间插入和删除都是廉价操作,但是对于ArrayList是代价高昂的操作.

containsAll()方法

retainAll()方法是一种有效的"交集",其行为依赖于eauals()方法.

remove()根据元素索引值移除元素的效果,此时不比担心equals()行为.

removeAll()方法的行为也是基于equals()方法,它将从List中移除在参数List中的所有元素.

set()方法命名与Set类存在潜在冲突,可用replace,在置顶的索引处(第一个参数)没用第二个参数替换这个位置的元素.

对于List,有一个重载的addAll()方法使得我们可以在初始List中间插入新的列表,而不仅仅只能用Collection的addAll()方法将其追加到表尾.

toArray()将任意的Collection转换为一个数组,这是一个重载方法,其无参数版本返回的是Object数组.但如果想该重载版本传递目标类型的数据,那么将产生指定类型的数据.

11.6 迭代器

迭代器(也是一种设计模式)的概念可以用于转换容器中的数据类型.迭代器是一个对象,它的工作是遍历并选择序列中的对象,而客户端程序员不必知道或关心该序列底层的结构.迭代器通常被称为轻量级对象:创建它的代价小.

Java的Iterator只能单向移动,:

1. 使用方法iterator()要求容器返回一个Iterator.Iterator将准备好返回序列的第一个元素
2. next()获得序列中的下一个元素
3. hasNest()检查序列中是否还有元素.
4. remove()将迭代器新近返回的元素删除.

11.6.1 ListIterator

ListIterator是Iterator的子类型,只能用于各种List类的访问.可以双向移动,可以产生相对于迭代器在列表中指向当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素,可以调用listIterator()方法产生一个执行List开始处的ListIterator,并且还可以通过调用ListIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator.

11.7 LinkedList

LinkedList在List中间插入和删除时比ArrayList更搞笑,但在随机访问操作方面却要逊色一些.

LinkedList还添加了可以使其用作栈,队列或双端队列的方法.

getFirst()和element()完全一样,都返回列表的第一个元素,而并不移除它,如果List为空,则抛出NoSuchElementException.peek()方法在列表为空时返回null.

removeFirst()和remove()完全一样,移除并返回列表的第一个元素,而在列表为空时抛出NoSuchElementException.poll()在列表为空时返回null.

addFirst()与add()和addLast()相同,豆浆某个元素插入到列表的尾部.

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

11.8 Stack

"栈"通常是指"后进先出"(LIFO)的容器.有时栈也被称为叠加栈

LinkedList具有能够直接实现栈的所有功能的方法,因此可以直接将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>告诉编译器这将是一个参数化类型,而其中的类型参数,即在类被使用时将会被实际类型替换的参数,就是T.大体上,该类就是在声明"定义一个可以持有T类型对象的Stack",Stack是LinkedList实现的,而LinkedList也被告知它将持有T类型对象.push()接受的是T类型的对象,而peek()和pop()将返回T类型的对象.peek()方法将提供栈顶元素,但是并不将其从栈顶移除,而pop()将移除并返回栈顶元素.

11.9 Set

Set不保存重复的元素.Set中最常被使用的是测试归属性.Set具有与Collection完全一样的接口,因此没有任何额外的功能,不像具有两种形式的List,实际上Set就是Collection,只是行为不同.

TreeSet将元素存储在红-黑数据结构中,而HashSet使用的是散列函数.LinkedList因为查询速度的原因使用了散列,但它使用了链表来维护元素的插入顺序.

TreeSet的结果是排序的,排序是按字典序进行的,因此大小写被划分到了不同的组中.如果想要按照字母序排序,那么可以向TreeSet的构造器传入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与数组和其他的Collection一样,可以扩展到多维,只需将其值设置为Map.

11.11 Queue

队列是一个典型的先进先出(FIFO)的容器.即从容器的一端放入事务,从另一端取出,并且事务放入容器的顺序与取出的顺序是相同的.队列常被当做一种可靠的将对象从程序的某个区域传输到另一个区域的途径.队列在并发编程中特别重要.

LinkedList提供了方法以支持队列的行为,并且它实现了Queue接口,因此LinkedList可以用作Queue的一种实现.

offer()方法是与Queue相关的方法之一,它在允许的情况下,将一个元素插入到队尾,或者返回false.peek()和element()都将在不移除的情况下返回队头,但是peek()方法在队列为空时返回null,element()会抛出NoSuchElementException异常.poll()和remove()方法将移除并返回队头,但是poll()在队列为空时会返回null,而remove()会抛出NoSuchElementException异常.

11.11.1 PriorityQueue

优先级队列声明下一个弹出元素是最需要的元素(具有最高的优先级).

在PriorityQueue上调用offer()方法来插入一个对象时,这个对象会在队列中被排序.默认的排序将使用对象在队列中的自然顺序,可以通过Comparator来修改这个顺序.PriorityQueue可以确保当你调用peek(),poll()和remove()方法时,获取的元素将是队列中优先级最高的元素.

允许重复,最小的值拥有最高的优先级,(如果是String,空格也可以算作值,并且比字母的优先级高)

11.12 Collection和Iterator

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

使用接口描述,可以创建更通用的代码,通过针对接口而非具体实现来编写代码,可以应用于更多的对象类型.

生成Iterator是将队列与消费队列的方法连接在一起耦合度最小的方式,并且与实现Collection相比,它序列类上所施加的约束也少得多.

11.13 Foreach与迭代器

java SE5引入了新的被称为Iterable的接口,该接口包含一个能够产生Iterator的iterator()方法,并且Iterable接口被foreach用来在序列中移动.因此如果创建了任何实现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));
    }
}

尝试把数组当做一个Iterable参数传递会导致失败.这说明不存在任何从数组到Iterable的自动转换.

13.11.1 适配器方法惯用法

假设希望可以选择以向前的方向或是向后迭代一个单词列表,如果直接继承这个类,并覆盖iterator()方法????

一种解决方案是所谓适配器方法,"适配器"部分来自于设计模式,因此必须提供特定接口以满足foreach语句.当有一个接口并需要另一个接口时,编写适配器就可以解决问题.在默认的向前迭代器基础上,添加产生反向迭代器的能力,因此不能使用覆盖,而是添加了一个能够产生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()的构造器，这将创建一个引用ia的元素的ArrayList，因此打乱这些引用不会修改该数组。 但是，如果直接使用Arrays.asList(ia）的结果， 这种打乱就会修改ia的顺序。意识到Arrays.asList（）产生的List对象会使用底层数组作为其物理实现是很重要的。 只要你执行的操作 会修改这个List，并且你不想原来的数组被修改，那么你就应该在另一个容器中创建一个副本。

Collection.shuffle()方法没有影响到原来的数组,而只是打乱了shuffled的引用.之所以这样,是因为ArrayList将Arrays.asList()方法的结果包装了起来,如果这个由Arrays.asList()方法产生的List被直接打乱,那么它就会修改底层的数组.

11.14 总结

1. 数组将数字与对象联系起来.他保存类型明确的对象,查询对象时,不需要对结果做类型转换,它可以是多维的,可以保存基本类型的数据.但是,数组一旦生成,其容量就不能改变.
2. Collection保存单一的元素,而Map保存相关联的键值对.有了Java的泛型,就可以指定容器中存放的对象类型,因此就不会将错误类型的对象放置到容器中,并且在从容器中获取元素时,不必进行类型转换.各种Collection和各种Map都可以在向其中添加更多的元素时,自动调整其尺寸.容器不能持有基本类型,但是自动包装机制会仔细地执行基本类型到容器中所持有的包装器类型之间的双向转换.
3. 像数组一样,List也建立数字索引和对象的关联,因此,数组和List都是排好序的容器.List能够自动扩充容器.
4. 如果要进行大量的随机访问,就是用ArrayList;如果要经常从表中间插入或删除元素,则应该使用LinkedList.
5. 各种Queue以及栈的行为,有LinkedList提供支持.
6. Map是一种将对象(非数字)与对象相关联的设计.HashMap设计用来快速访问;而TreeMap保持"键"始终处于排序状态,所以没有HashMap快.LinkedHashMap保持元素插入的顺序,但是也通过散列提供了快速访问能力.
7. Set不接受重复元素.HashSet提供最快的查询速度,而TreeSet保持元素处于排序状态.LinkedHashSet以插入顺序保存元素.
8. 新程序中不应该使用过时的Vector,HashTable和Stack

[图片上传失败...(image-eab3f-1524392810247)]

第十五章 泛型

泛型的概念:编写更通用的代码,要使代码能够应用于"某种不具体的类型",而不是一个具体的接口或类.

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,则必须指定参数类型.如若不指定参数类型,则需要使用类型参数,用尖括号扩朱,放在类名后面.然后再使用这个类的时候,在用实际的类型替换此类型参数.如下.T就是类型参数.

/*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泛型的核心概念:告诉编译器想使用什么类型,然后编译器可以处理一切细节.

15.2.1 一个元组类库

元组:将一组对象直接打包存储于其中的一个单一对象.这个容器对象允许读取其中元素,但是不允许向其中存放新的对象.(这个概念也称为数据传送对象或信使)

可以利用继承机制实现长度更长的元组.

/*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)来判断堆栈何时为空.该末端烧饼是在构建LinkedStack时创建的.每调用一次push()方法,就会创建一个Node<T>对象,并将其链接到前一个Node<T>对象.调用pop()方法时,返回top.item,然后丢弃当前top所指的Node<T>,并将top转移到下一个Node<T>,直到遇到末端哨兵.

15.3 泛型接口

泛型也可以应用于接口,如生成器(generator),这是一种专门负责创建对象的类.实际上,这是工厂方法设计模式的一种应用.不过,当使用生成器创建新的对象时,它不需要任何参数,而工厂方法一般需要参数.也就是说,生成器无需额外的信息就知道如何创建新对象.

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

一般而言,一个生成器只定义一个方法,该方法用于生产新的对象.

/*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泛型的一个局限性:基本类型无法作为类型参数.

15.4 泛型方法

是否拥有泛型方法,与其所在的类是否具有泛型没有关系.

泛型方法使得该方法能够独立于类而产生变化.基本指导原则:无论何时,只要能做到,就应该尽量使用泛型方法.也就是说如果使用泛型方法可以取代将整个类泛型化,那么就应该只使用泛型方法,因为它可以使事情更清楚明白.另外,对于一个static的方法而言,无法访问泛型类的类型参数,所以如果static方法需要使用泛型能力,就必须使其成为泛型方法.

要定义泛型方法,只需将泛型参数列表置于返回值之前.

/*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);
    }
}

注意:当使用泛型类时,必须在创建对象的时候指定类型参数的值,而使用泛型方法时,通常不比指明参数类型,因此编译器会找出具体的类型.这称为类型参数判断(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()创建传递给构造器List,
2. 使用Collections.fill(),fill()方法用处有限,只能替换已经在List中存在的元素,而不能添加新的元素.

17.2.1 一种Generator解决方案

所有的Collection子类型都有一个接收另一个Collection对象的构造器,用于接收的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在容器中防止所需数量的对象,然后所产生的容器可以传递给任何Collection的构造器,这个构造器会把其中的数据复制到自身中.addAll()方法是所有Collection子类型的一部分,它也可以用来组装现有的Collection.

CollectionData是适配器设计模式的一个实例.

17.2.2适配器

可以对Map使用相同的方式，但这需要一个Pair类，为了组装Map，每次调用Generator的next()方法都必须产生一个对象对(一个键和一个值)

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类

享元:可以在普通的解决方案需要过多的对象,或者生产普通对象太占用空间时使用.享元模式使得对象的一部分可以被具体化,所以,与对象中的所有事务都包含在对象内部不同,可以更加高效的外部表中查找对象的一部分或整体(或者通过某些其他节省空间的计算来产生对象的一部分货整体).

可以通过继承java.util.Abstract来创建定制的Map和Collection. 为了创建只读的Map, 可以继承AbstractMap并实现entrySet(). 为了创建只读的Set, 可以继承AbstractSet并实现iterator()和size().

17.3 Collection的功能方法

注意:其中不包括随机访问所选择元素的get()方法. 因为Collection包括set, 而set是自己维护内部顺序的(这使得所及访问变得没有意义). 因此, 如果想检查Collection中的元素, 就必须使用迭代器.

17.4 可选操作

执行各种不同的添加和移除的方法在Collection接口中都是可选操作. 这意味着实现类并不需要为这些方法提供功能接口.

为什么将方法定义为可选的?

因为这样做可以防止在设计中出现接口爆炸的情况. 容器类库中的其他设计看起来总是为了描述某个主题的各种变体, 而最终患上了令人困惑的接口过剩症. 甚至这么做仍不能捕捉接口的各种特例, 因为总是会发明新的接口. "未获得支持的操作" 这种方式可以实现Java容器类库的一个重要目标: 容器应该易学易用. 未获支持的操作是一种特例, 可以延迟到需要时在实现.

1. UnsupportOperationException必须是一种罕见事件. 即, 对于大多数类来说, 所有操作都应该可以工作, 只有在特例中才会有位或支持的操作. 在Java容器类库中确实如此, 因为在大多数使用的容器, 如ArrayList, LinkedList, HashSet和HashMap, 以及其他的具体实现, 都支持所有的操作. 这种设计有一个弊端, 如果想创建新的Collection, 但是没有为Collection接口中的所有方法都提供有意义的定义, 那么它仍旧适合现有的类库.
2. 如果一个操作是未获支持的,那么在实现接口的时候可能会导致UnsupportedOperationException异常.

17.4.4 未获支持的操作

最常见的未获支持的操作, 都来源于背后由固定尺寸的数据接口支持的容器. 当用Arrays.asList()将数组转换为List时, 就会得到这样的数组.

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() 虽然改变了值但没有改变它的数据结构尺寸
        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)));
    }
}

因为Arrays.asList()会生成一个list, 它基于一个固定大小的数组, 仅支持哪些不会改变数组大小的操作. 任何会引起对底层数据结构的尺寸进行修改的方法都会产生一个UnsupportedOperationException异常,以表示对未获支持操作的调用.

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

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上打星号表示, 如果没有其他的限制, 这应该就是默认的选择, 因为它对速度进行了优化.

必须为散列存储和树形存储都创建一个equals()方法, 但是hashCode()只有在这个类将会被置于HashSet(这是有可能的, 因为它通常是Set实现的首选)或者LinkedHashSet中时才是必须的. 对于良好的编程风格, 应该覆盖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()方法产生它的值. 因为所有在Set中存储的类型都必须具有equals()方法.

HashType继承自SetType, 并且添加了hashCode()方法, 该方法对于放置到Set的散列实现中的对象来说是必须的.

TreeType实现了Comparable接口, 如果一个对象被用于任何种类的排序容器中, 例如SortedSet(TreeSet是其唯一实现),那么它必须实现这个接口.

17.6.1 SortedSet

SortedSet中的元素可以保证处于排序状态, 这使得它可以通过在SortedSet接口中的下列方法提供附加功能: Comparator comparator()返回当前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 队列

除了并发应用, Queue在Java SE5中仅有两个实现: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 优先级队列

该列表中每个对象都包含一个字符串和一个主要的以及次要的优先级值. 该列表的排序顺序也是通过实现Comparable而进行控制的.

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 双向队列

双向队列(双端队列)就像是一个队列, 但是可以在任何一段添加或移除元素. 在LinkedList中包含支持双向队列的方法, 但是在Java标准类库中没有任何显示的用于双向队列的接口. 因此, LinkedList无法去实现这样的接口,也无法像前面示例中转型到Queue那样去向上转型到DDeque. 但是++可以组合来创建一个Deque类++, 并直接从LinkedList中暴露相关的方法:

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

标准的Java类库中包含了Map的几种基本实现, 包括:HashMap, TreeMap, LinkedHashMap, WeakHashMap, CouncurrentHashMap, IdentityHashMap.

17.8.1 性能

性能是映射表中的一个重要问题, 挡在get()中使用线性搜索时, 执行速度回相当地慢, 而这正是HashMap提高速度的地方. HashMap使用了特殊的值, 称作散列码, 来取代对键的缓慢搜索. 散列码是"相对唯一"的,用以代表对象的int值, 它是通过将该对象的某些信息进行转换而生成的. hashCode()是根类Object中的方法, 因此所有Java对象都能产生散列码. HashMap就是使用对象的hashCode()进行快速查询的, 此方法能够显著提高性能.

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

17.8.2 SortedMap

使用SortedMap(TreeMap是其现阶段的唯一实现),可以确保键处于排序状态.

Comparator comparator():返回当前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()会迭代遍历该映射, 因此可以看到遍历的结果). 此外, 可以在构造器中设定LinkedHashMap, 使之采用基于访问的最近最少使用(LRU)算法, 于是没有被访问过的(可能看做需要删除的)元素就会出现在队列的前面. 对于需要定期清理元素以节省空间的程序来说, 此功能使得程序很容易得以实现.

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()方法判断当前的键是否与表中存在的键相同. 正确的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, 如果对象中用于等价比较的信息没有改变, 那么无论调用x.equals(y)多少次, 返回的结果应该保持一致, 要么一直是true, 要么一直是false.
5. 对任何不是null的x,x.equals(null)一定返回false.

默认的Object.equals()只是比较对象的地址

在HashSet中使用自己的类作为键

17.9.1 理解hashCode()

17.9.2 为速度而散列

散列将键保存在某处, 以便能够很快找到. 存储一组元素最快的数据结构是数组, 所以使用它来表示键的信息(是键的信息, 而不是键本身). 但是数组不能调整容量, 因此

数组本身并不保存键本身. 而是通过键对象生成一个数组, 将其作为数组的下标. 这个数字就是散列码, 由定义在Object中的,且可能由自定义的类覆盖的hashCode()方法(在计算机科学的术语中称为散列函数)生成.

为解决数组容量被固定的问题, 不同的键可以产生相同的下标. 也就是说, 可能会有冲突, 因此, 数组多大就不重要了, 任何键总能在数组中找到它的位置.

于是查询一个值的过程首先就是计算散列码, 然后使用散列码查询数组. 如果能够保证没有冲突(如果值的数量是固定的, 那么就有可能), 那可能就有一个完美的散列函数, 但是这种情况只是特例. 通常冲突由外部链接处理: 数组并不直接保存值, 而是保存值的list. 然后对list的值使用equals()方法进行线性的查询. 这部分的查询自然会比较慢, 但是如果散列函数好的话, 数组的每个位置就只有较少的值. 因此, 不是查询整个list, 而是快速地跳到数组的某个位置, 只对很少的元素进行比较.

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有个特点: 如果程序中有多个String对象, 都包含相同的字符串序列, 那么这些String对象都映射到相同的一块内存区域. 所以new String("Hello")生成的两个实例, 虽然是相互独立地, 但是对它们使用hashCode应该生成同样的结果.

要想使hashCode()实用, 它必须速度快, 并且必须有意义. 也就是说, 它必须基于对象的内容生成散列码. 散列码不必是独一无二的(应该更关注生成速度, 而不是唯一性), 但是通过hashCode()和equals(), 必须能够完全确定对象的身份.

好的hashCode()应该产生分布均匀的散列码. 如果散列码都几种在一块, 那么HashMap或HashSet在某些区域的负载会很重.

17.10 选择接口的不同实现

有时某个特定容器的不同实现会拥有一些共同的操作, 但是这些操作的性能却并不相同. 在这种情况下, 可以基于使用某个特定操作的频率, 以及需要执行的速度来在它们中间进行选择. 对于类似地情况, 一种查看容器实现之间的差异的方式是使用性能测试.

看书p499

17.10.2 对List的选择

对于由数组职称的List和ArrayList, 无论列表的大小如何, 这些访问都很快速和一致; 而对于LinkedList, 访问时间对于较大的列表将明显增减.

对于ArrayList, 当列表变大时, 其开销将变得很高昂, 但对于LinkedList, 相对来说比较低廉, 并且不随列表尺寸而发生变化. 这是因为ArrayList在插入时, 必须创建空间并将它的所有引用向前移动, 这会随ArrayList的尺寸增加而产生高昂的代价. LinkedList只需链接新的元素, 而不必修改列表中剩余的元素, 因此可以认为无论列表尺寸如何变化, 其代价大致相同.

17.10.3 微基准测试的危险

p507

17.10.4 对Set的选择

HashSet的性能基本上总是比TreeSet好, 特别是在添加和查询元素时, 而这两个操作也是最重要的操作. TreeSet存在的唯一原因是它可以维持元素的排序状态; 所以只有当需要一个排好序的Set时, 才应该使用TreeSet. 因为其内部结构支持排序, 并且因为迭代是更有可能执行的操作, 所以TreeSet迭代通常比用HashSet要快.

对于插入操作, LinkedHashSet比HashSet的代价更高, 这是由维护链表所带来的额外开销造成的.

17.10.5 对Map的选择

除了IndentityHashMap, 所有的Map实现的插入操作都会随着Map尺寸的变大而明显变慢. 但是查找的代价通常比插入要小得多,

HashTable的性能大体上与HashMap相当. 因为HashMap是用来代替HashTable的, 因此他们使用了相同的底层存储和查找机制.

TreeMap通常比HashMap要慢. 与使用TreeSet一样, TreeMap是一种创建有序列表的方式. 树的行为:总是保证有序, 并且不必进行特殊排序. 一旦填充了一个TreeMap, 就可以调用keySet()来获取键的Set视图, 然后调用toArray()来产生由这些键构成的数组. 之后可以使用静态方法Arrays.binarySearch()在排序数组中快速查找对象. 当然这只有在HashMap的行为不可接受的情况下才有意义, 因为HashMap本身就被设计为可以快速查找键.

LinkedHashMap在插入时比HashMap慢一点, 因为它维护散列表数据结构的同时还要维护链表(以保持插入顺序).

IdentityHashMap则具有完全不同的性能, 因为它使用==而不是equals()来比较元素.

HashMap参数:

• 容量:表中的桶位数
• 初始容量:表在创建时所拥有的桶位数. HashMap和HashSet都具有允许你指定初始容量的构造器
• 尺寸:表中当前存储的项数.
• 负载因子: 尺寸/容量.

17.11 实用方法

课本p512

17.11.1 List的排序和查询

17.11.2 设定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)));
    }
} 

对特定类型"不可修改"的方法的调用并不会产生编译时的检查, 但是转换完成后, 任何改变容器的内容的操作都会引起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>());
    }
}

快速报错

Java容器有一种保护机制, 能够防止多个进程同时修改同一个容器的内容. 如果在迭代遍历某个容器的工程中, 另一个进程介入其中, 并且插入, 删除或修改此容器内的某个对象, 那么就会出现问题: 也许迭代过程已经处理过容器中的该元素, 也许还没处理, 也许在调用size之后容器的尺寸收缩了--还有许多灾难情景. Java容器类类库采用快速报错机制. 它会检查容器上的任何除了你的进程所进行的操作以外的所有变化, 一旦它发现其他进程修改了容器, 就会立刻抛出ConcurrentModificationException异常.

ConcurrentHashMap,CopyOnWriteArrayList和CopyOnWriteArraySet都使用了可以避免ConcurrentModificationException的技术

17.12 持有引用

有三个继承自抽象类Reference的类:SoftReference,WeakReference和PhantomReference.

对象是++可获得的++(reachable), 是指此对象可在程序中的某处找到. 这意味着在栈中有一个普通的引用, 而它正指向此对象; 也可能是引用指向某个对象, 而那个对象含有零一个引用向正在讨论对象; 也可能有更多的中间链接. 如果一个对象是"可获得的",垃圾回收器就不能释放它, 因为它仍然为程序所用. 如果一个对象不是"可获得的", 那么程序将无法使用到它, 所以将其回收是安全的.

SoftReference, WeakReference和Phantomreference由强到弱排列, 对应不同级别的"可获得性". Softreference用以实现内存敏感的高速缓存. Weakreference是为实现"规范映射"而设计的, 它不妨碍垃圾回收映射"键"(或"值"). "规范映射"中对象的实例可以在程序的多处被同时使用, 以节省存储空间. Phantomreference用以调度回收前的清理工作, 它比Java终止机制更灵活.

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();
        }
    }
}

第二十一章 并发

21.1 并发的多面性

用并发解决的问题大体上可以分为"速度"和"设计可管理性"两种.

21.1.1 更快的执行

并发是用于多处理编程的基本工具.

在单处理器上运行的并发程序开销确实应该比改程序的所有部分都顺序执行的开销大, 因为其中增加了所谓上下文切换的代价(从一个任务切换到另一个任务). 但是因为阻塞, 如果程序中的某个任务因为改程序控制范围之外的某些条件(通常是I/O)而导致不能继续执行, 那么就说这个任务或线程阻塞了.

21.2 基本的线程机制

并发编程可以将程序划分为多个分离的,独立运行的任务. 通过使用多线程机制, 这些独立任务(也被称为子任务)中的每一个都将有执行线程来驱动. 一个线程就是在进程中的一个单一的顺序控制流, 因此单个进程可以拥有多个并发执行的任务, 其底层机制是切分CPU时间.

线程模型为编程带来了便利, 它简化了在单一程序中同时交织在一起的多个操作的处理. 在使用线程时, CPU将轮流给每个任务分配器占用时间. 每个任务都觉得自己在一直占用CPU, 但事实上CPU时间是划分成片段分配给了所有的任务(例外:程序确实运行在多个CPU之上).

21.2.1 定义任务

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()中对静态方法Thread.yield()的调用是对线程调度器(Java线程机制的一部分, 可以将CPU从一个线程转移给另一个线程)的建议.

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构造器只需要一个Runnable对象. 调用Thread对象的start()方法为该线程执行必须的初始化操作, 然后调用Runnable的run()方法, 以便在这个新线程中启动该任务. 尽管start()看起来是产生一个对长期运行方法的调用, 但是从输出中可以看到, start()迅速地返回了, 因为Waiting for LiftOff消息在倒计时完成之前就出现了. 实际上shiduLiftOff.run()的方法调用, 并且这个方法还没有完成, 但是因为