Thinking in Java——集合(容器)基础
  • 作者:ZJWave
  • 分类: java java基础
  • 发表:2019-01-17 21:59
  • 围观:3328
  • 评论:0

1.前言

如果一个程序包含固定数量的且其生命周期都是已知的对象,那么这是一个非常简单的程序。

通常,程序总是根据运行时才知道的某些条件去创建新对象。在此之前,不会知道所需对象的数量,甚至不知道确切的类型。未解决这个普遍的编程问题,需要在任意时刻和任意位置创建任意数量的对象。所以,就不能依靠创建命名的引用来持有对象:

MyType aReference

因为你不知道实际上会需要多少这样的引用。

大多数语言都提供某种方法来解决这个基本问题。Java有多种方式保存对象(应该说对象的引用)。例如数组,它是编译器支持的类型。数组是保存对象的一种最有效的方式,如果一项保存一组基本类型的数据,也推荐使用这种方式。但是数组具有固定的尺寸,而在更一般的情况中,你在写程序时并不知道将需要多少个对象,或者是否需要更复杂的方式来存储对象,因此数组尺寸固定这一限制显得过于受限了。

Java实用类库还提供了一套相当完整的容器类来解决这个问题,其中基本的类型是List、Set、QueueMap。这些对象类型也称为集合类,但由于Java的类库中实用了Collection这个名字来指代该类库的一个特殊子集,所以我使用了范围更广的术语“容器”称呼它们。容器提供了完善的方法保存对象,你可以使用这些工具来解决数量惊人的问题。

容器还有其他一些特性。例如Set对于每个值都只保存一个对象,Map允许你将某些对象与其他一些对象关联起来的关联数组,Java容器类都可以自动调整自己的尺寸。因此,与数组不同,在编程时,你可以将任意数量的对象放置到容器中,并且不需要担心容器应该设置为多大。

即使在Java中没有直接关键字支持,容器类仍旧是可以显著增强你的编程能力的基本工具。在本文中,你将了解有关Java容器类库的基本知识,以及对典型用法的重点介绍。我们聚焦于你在日复一日的编程工作中将会用到的那些容器。

2.泛型和类型安全的容器

使用Java SE5之前的容器的主要问题就是编译器允许你向容器中插入不正确的类型。例如,考虑一个Apple对象的容器,我们使用最基本最可靠的容器ArrayList。现在你可以把ArrayList当做“可以自动扩充自身尺寸的数组”来看待。使用ArrayList相当简单:创建一个实例,用add()插入对象;然后用get()访问这些对象,此时需要使用索引,就像数组一样,但是不需要方括号[]ArrayList还有一个size()方法,使你可以知道已经有多少元素添加进来了,从而不会不小心因索引越界而引发错误。

在本例中,AppleOrange都放置在了容器中,然后将他们取出。正常情况下,Java编译器会报告警告信息,因为这个示例没有使用泛型。在这里,我们使用Java SE5所特有的注解来抑制了警告信息。注解以“@”符号开头,可以接受参数,这里的@SuppressWarnings注解及其参数表示只有有关“不受检查的异常”的警告信息应该被抑制:

package com.zjwave.thinkinjava.collection.generic;

import java.util.ArrayList;

/**
 * @author ZJ_Wave
 */
public class TestGeneric {

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        ArrayList apples = new ArrayList();
        for (int i = 0; i < 3; i++) {
            apples.add(new Apple());
        }
        //Not prevented from adding an Orange to apples
        apples.add(new Orange());
        for (int i = 0; i < apples.size(); i++) {
            ((Apple)apples.get(i)).getId();
        }
    }
}

class Apple{
    public static long counter;
    private final long id = counter++;


    public long getId() {
        return id;
    }
}

class Orange{
}

AppleOrange类是有区别的,他们除了都是Object之外没有任何共性。因为ArrayList保存的是Object,因此你不仅可以通过ArrayListadd()方法将Apple对象放进这个容器,还可以添加Orange对象,而且无论是在编译器还是运行时都不会有问题。当你在使用ArrayListget()方法来取出你认为是Apple的对象时,你得到的只是Object的引用,必须将其转型为Apple,因此,需要将整个表达式括起来,在调用ApplegetId()方法之前,强制执行转型。否则你就会得到一个语法错误。在运行时,当你试图将Orange对象转型为Apple时,你就会以一个异常的形式得到一个错误。

要想定义用来保存Apple对象的ArrayList,你可以声明ArrayList,而不仅仅只是ArrayList<Apple>,其中尖括号括起来的是类型参数(可以有多个),它指定了这个容器可以保存的类型。通过使用泛型,就可以在编译期防止将错误类型的对象放置到容器中。下面还是这个示例,但是使用了泛型。

package com.zjwave.thinkinjava.collection.generic;

import java.util.ArrayList;

/**
 * @author ZJ_Wave
 */
public class TestGeneric {

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        ArrayList<Apple> apples = new ArrayList<Apple>();
        for (int i = 0; i < 3; i++) {
            apples.add(new Apple());
        }
        //Complie time error
        //apples.add(new Orange());
        for (int i = 0; i < apples.size(); i++) {
            System.out.println(apples.get(i).getId());
        }
        for (Apple apple : apples) {
            System.out.println(apple.getId());
        }
    }
}

class Apple{
    public static long counter;
    private final long id = counter++;


    public long getId() {
        return id;
    }
}

class Orange{
}

现在,编译器可以阻止你将Orange放置到apples中,因此它变成了一个编译期错误,而不再是运行时错误。

你还应该注意到,在将元素从List中取出时,类型转换也不再是必须的了。因为List知道它保存的是什么类型,因此它会在调用get()时替你执行转型。这样,通过使用泛型,你不仅知道编译器将会检查你放置到容器中的对象类型,而且在使用容器中的对象时,可以使用更加清晰的语法。

这个示例还表明,如果不需要使用每个元素的索引,你可以使用forEach语法来选择List中的每个元素。

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

package com.zjwave.thinkinjava.collection.generic;

import java.util.ArrayList;

public class GenericsAndUpcasting {

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

class GrannySmith extends Apple{}
class Gala extends Apple{}
class Fuji extends Apple{}
class Braeburn extends Apple{}

因此,你可以将Apple的子类型添加到被指定为保存Apple对象的容器中。

程序的输出是从Object默认的toString()方法产生的,该方法将打印类名,后面跟随该对象的散列码的无符号十六机制表示(这个散列码是通过hashCode()方法产生的)。

3.基本概念

先上图:

Java容器类类库的用途是“保存对象”,并将其划分为两个不同的概念:

1)Collection。一个独立元素的序列,这些元素都服从一条或多条规则。List必须按照插入的顺序保存元素,而Set不能有重复元素。Queue按照排队规则来确定对象产生的顺序(通常与他们被插入的顺序相同)。

2)Map。一组成对的“键值对”对象,允许你使用键来查找值。ArrayList允许你使用数字来查找值,因此在某种意义上讲,他将数字与对象关联在了一起。映射表允许我们使用另一个对象来查找某个对象,它也被称为“关联数组”,因为它将某些对象与另一些对象关联在了一起;或者被称为“字典”,因为你可以使用键对象来查找值对象,就想在字典中使用单词来定义一样。Map是强大的编程工具。

尽管并非总是这样,但是在理想情况下,你编写的大部分代码都是在于这些接口打交道,并且你唯一需要指定所使用的精确类型的地方就是在创建对象的时候。因此你可以像下面这样创建一个List

List<Apple> apples = new ArrayList<>();

注意,ArrayList已经被向上转型为List,这与之前一个示例中的处理形式正好相反。使用接口的目的在于如果你决定去修改你的实现,你所需要的只是在创建处修改它,就像下面这样:

List<Apple> apples = new LinkedList<>();

因此,你应该创建一个具体类的对象,将其转型为对应的接口,然后在其余的代码中使用这个接口。

这种方式并非总能奏效,因为某些类具有额外的功能,例如,LinkedList具有在List接口中未包含的额外方法,而TreeMap也具有在Map接口中未包含的方法。如果你需要使用这些方法,就不能将它们向上转型为更通用的接口。

Collection接口概括了序列的概念——一种存放一组对象的方式。下面这个简单的示例用Integer对象填充了一个Collection(这里用ArrayList表示),然后打印所产生的容器中的所有的元素。

package com.zjwave.thinkinjava.collection.generic;

import java.util.ArrayList;
import java.util.Collection;

public class SimpleCollection {
    public static void main(String[] args) {
        Collection<Integer> c = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            c.add(i);
        }
        for (Integer i : c) {
            System.out.println(i);
        }
    }
}

因为这个示例只使用了Collection方法,因此任何继承自Collection类的对象都可以正常工作,但是ArrayList是最基本的序列类型。

add()方法的名称就表名它就是要将一个新元素放置到Collection中。但是文档中非常仔细地叙述到:“要确保这个Collection包含指定的元素。”这是因为考虑到了Set的含义,因为在Set中只有元素不存在的情况下才会添加。在使用ArrayList,或者任何种类的List时,add()总是表示“把它放进去”,因为List不关心是否存在重复。

所有的Collection都可以用forEach语法遍历,就像这里所展示的。

4.添加一组元素

java.util包中的ArraysCollections类中都有很多实用的方法,可以在一个Collection中添加一组元素。Arrays.asList()方法接受一个数组或是用逗号分隔的元素列表(使用可变参数),并将其转换为一个List对象。Collections.addAll()方法接受一个Collection对象,以及一个数组或是一个用逗号分隔的列表,将元素添加到Collection中。下面的示例展示了这两个方法,以及更加传统的addAll()方法,所有Collection类型都包含该方法。

package com.zjwave.thinkinjava.collection.generic;

import java.util.*;

public class AddGroups {
    public static void main(String[] args) {
        Collection<Integer> collection = new ArrayList<>(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);
        System.out.println(collection);

        List<Integer> list = Arrays.asList(16,17,18,19,20);
        list.set(1,99);
        System.out.println(list);
        //list.add(21); //Runtime error because the underlying array cannot be resized
    }
}

Collection的构造器可以接受另一个Collection,用它来将自身初始化,因此你可以使用Arrays.asList()来为这个构造器产生输入。但是,Collection.addAll()方法运行起来要快得多,而且构建一个不包含元素的Collection,然后调用Collections.addAll()这种方式很方便,因此它是首选方式。

Collection.addAll()成员方法只能接受另一个Collection对象作为参数,因此他不如Arrays.asList()Collections.addAll()灵活,这两个方法都是使用的可变参数列表。

你也可以直接使用Arrays.asList()的输出,将其当做List,但是在这种情况下,其底层表示的是数组,因此不能调整尺寸。如果你试图用add()remove()方法在这种列表中添加或删除元素,就有可能引发去改变数组尺寸的尝试,因此你将在运行时获得一个“UnsupportedOperationException”错误。

Arrays.asList()方法的限制是它对所产生的List的类型做出了最理想的假设,而并没有注意你对它会赋予什么样的类型。有时这就会引发问题:

package com.zjwave.thinkinjava.collection.generic;

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

public class AsListInterface {
    public static void main(String[] args) {
        List<Snow> snows1 = Arrays.asList(new Crusty(), new Slush(), new Powder());
        List<Snow> snows2 = Arrays.asList(new Light(), new Heavy());
        List<Snow> snows3 = new ArrayList<>();
        Collections.addAll(snows3,new Light(),new Heavy());
        List<Snow> snows4 = Arrays.<Snow>asList(new Light(), new Heavy());

    }
}

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

当试图创建snows2时,Arrays.asList()中只有Powder类型,因此他会创建List<Powder>而不是List<Snow>,尽管Collections.addAll()工作的很好,因为它从第一个参数了解到了目标类型是什么。

正如你从创建snows4的操作中所看到的的,可以在Arrays.asList()中间插入一条“线索”,以告诉编译器对于Arrays.asList()所产生的List类型,实际的目标类型应该是什么。这称为显式类型参数说明。

正如你所见,Map更加复杂,并且除了用另一个Map之外,Java标准类库没有提供其他任何自动初始化它们的方式。

注意:Arrays.asList()的泛型问题存在于Java SE5版本中,笔者所使用的编译器版本为Java8,已不存在此问题。

5.容器的打印

你必须使用Arrays.toString()来产生数组的可打印表示,但是打印容器无需任何帮助。下面是一个例子,这个例子中也介绍了一些基本类型的容器:

package com.zjwave.thinkinjava.collection.generic;

import java.util.*;

public class PrintContainers {


    static Collection fill(Collection<String> c){
        c.add("rat");
        c.add("cat");
        c.add("dog");
        c.add("dog");
        return c;
    }

    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<>()));
        System.out.println(fill(new LinkedList<>()));
        System.out.println(fill(new HashSet<>()));
        System.out.println(fill(new TreeSet<>()));
        System.out.println(fill(new LinkedHashSet<>()));
        System.out.println(fill(new HashMap<>()));
        System.out.println(fill(new TreeMap<>()));
        System.out.println(fill(new LinkedHashMap<>()));
    }
}

这里展示了Java容器类库中的两种主要类型,他们的区别在于容器中每个“槽”保存的元素个数。Collection在每个槽中只能保存一个元素。此类容器包括:List,它以特定的顺序保存一组元素;Set,元素不能重复;Queue,只允许的容器的一“端”插入对象,并从另外一“端”移除对象(对于本例来说,这只是另外一种观察序列的方式,因此并没有展示它)。Map在每个槽内保存两个对象,及键和与之相关联的值。

查看输出会发现,默认的打印行为(使用容器提供的toString()方法)即可生成可读性很好的结果。Collection打印出来的内容用方括号括住,每个元素由逗号分隔。Map则用大括号括住,键与值由等号联系(键在等号左边,值在右边)。

第一个fill()方法可以作用于所有类型的Collection,这些类型都实现了用来添加新元素的add()方法。

ArrayListLinkedList都是List类型,从输出可以看出,它们都按照被插入的顺序保存元素。两者的不同之处不仅在于执行某些类型的操作时的性能,而且LinkedList包含的操作也多余ArrayList。这些将在后续部分更详细的讨论。

HashSetTreeSetLinkedHashSet都是Set类型,输出显示在Set中,每个相同的项只保存一次,但是输出显示了不同的Set实现存储元素的方式也不同。HashSet使用的是相当复杂的方式来存储元素的,这种方式将在后续文章中探讨,此刻你只需要知道这种技术是最快的获取元素的方式,因此,存储的顺序看起来并无实际意义(通常你只关心某个元素是否是某个Set的成员,而不会关心它在Set中的顺序)。如果存储顺序很重要,那么可以使用TreeSet,它按照比较结果的升序保存对象,或者使用LinkedHashSet,它按照被添加的顺序保存对象。

Map(也被称为关联数组)使得你可以用键来查找对象,就像一个简单的数据库。键所关联的对象称为值。使用Map可以将中国的省份与其省会联系起来,如果想知道江苏的省会,可以将江苏作为键进行查找,几乎就像数组使用下标一样。正由于这种行为,对于每个键,Map只接受存储一次。

Map.put(key,value)将增加一个值(你想要增加的对象),并将它与某个键(你用来查找这个值的对象)关联起来。Map.get(key)方法将产生与这个键相关联的值。上面的示例只添加了键值对,并没有执行查找,这将稍后展示。

注意,你不必指定(或考虑)Map的尺寸,因为它会自动的调整尺寸。Map还知道如何打印自己,它会显示相关联的键和值。键和值在Map中保存的顺序并不是它们插入的顺序,因为HashMap实现使用的是一种非常快的算法来控制顺序。

本例使用了三种基本风格的MapHashMapTreeMapLinkedHashMap。与HasSet一样,HashMap也提供了最快的查找技术,也没有按照任何明显的顺序来保存其元素。TreeMap按照比较结果的升序保存键,而LinkedHashMap则按照插入的顺序保存键,同时还保留了HashMap的查询速度。

6.List

List承诺可以将元素维护在特定的序列中。List接口在Collection的基础上添加了大量的方法,使得可以在List中间插入和移除元素。

有两种类型的List

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

下面是示例:

package com.zjwave.thinkinjava.collection.list;

import java.util.*;

public class ListFeatures {
    public static void main(String[] args) {
        Random rand = new Random(47);
        List<Pet> pets = new ArrayList<>();
        Collections.addAll(pets,new Rat(),new Manx(),new Cymric(),new Mutt(),new Pug(),new Cymric(),new Pug());
        System.out.println("1 : " + pets);
        Hamster h = new Hamster();
        pets.add(h);
        System.out.println("2 : " + pets);
        System.out.println("3 : " + pets.contains(h));
        pets.remove(h);//Remove by object
        Pet p = pets.get(2);
        System.out.println("4 : " + p + " " + pets.indexOf(p));
        Pet cymric = new Cymric();
        System.out.println("5 : " + pets.indexOf(cymric));
        System.out.println("6 : " + pets.remove(cymric));
        // Must be exact object
        System.out.println("7 : " + pets.remove(p));
        System.out.println("8 : " + pets);
        pets.add(3,new Mouse());//Insert an index
        System.out.println("9 : " + pets);
        List<Pet> sub = pets.subList(1, 4);
        System.out.println("subList : " + sub);
        System.out.println("10 : " + pets.containsAll(sub));
        Collections.sort(sub);
        System.out.println("sorted subList " + sub);
        //Order is not important in containsAll()
        System.out.println("11 : " + pets.containsAll(sub));
        Collections.shuffle(sub,rand);
        System.out.println("shuffle subList: " + sub);
        System.out.println("12 : " + pets.containsAll(sub));
        List<Pet> copy = new ArrayList<>(pets);
        sub = Arrays.asList(pets.get(1),pets.get(4));
        System.out.println("sub : " + sub);
        copy.retainAll(sub);
        System.out.println("13 : " + copy);
        copy = new ArrayList<>(pets);//Get a fresh copy
        copy.remove(2);//Remove by index
        System.out.println("14 : " + copy);
        copy.removeAll(sub);// Only remove exact objects
        System.out.println("15 : " + copy);
        copy.set(1,new Mutt());//Replace an element
        System.out.println("16 : " + copy);
        copy.addAll(2,sub);//Insert a list in the middle
        System.out.println("17 : " + copy);
        System.out.println("18 : " + pets.isEmpty());
        pets.clear();//Remove all elements
        System.out.println("19 : " + pets);
        System.out.println("20 : " + pets.isEmpty());
        pets.addAll(Arrays.asList(new Hamster(),new Rat(),new Pug(),new Mouse()));
        System.out.println("21 : " + pets);
        Object[] o = pets.toArray();
        System.out.println("22 : " + o[3]);
        Pet[] pa = pets.toArray(new Pet[0]);
        System.out.println("23 : " + pa[3].getId());
    }
}

abstract class Pet implements Comparable<Pet>{

    private static int counter;

    protected int id = counter++;

    @Override
    public String toString() {
        return this.getClass().getSimpleName();
    }

    @Override
    public int compareTo(Pet o) {
        return this.getId() - o.getId();
    }

    public int getId() {
        return id;
    }
}
class Hamster extends Pet{}
class Cymric extends Pet{}
class Rat extends Pet{}
class Manx extends Pet{}
class Mutt extends Pet{}
class Pug extends Pet{}
class Mouse extends Pet{}


打印行都编了号,因此输出可以与源码相关。第一行输出展示了最初的由Pet构成的List。与数组不同,List允许在它被创建之后添加元素,移除元素,或者自我调整尺寸。这正是它的重要价值所在:一种可修改的序列。你可以在输出行2中看到添加一个Hamster的结果,即对象被追加到了表尾。

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

当确定一个元素是否属于某个List,发现某个元素的索引,以及从某个List中移除一个元素时,都会用到equals()方法(它是根类Object的一部分)。每个Pet都被定义为唯一的对象,因此即使在列表中已经有两个Cymric,如果我再新创建一个Cymric,并把它传递给indexOf()方法,其结果仍会是-1(表示未找到它),而且尝试用remove()方法来删除这个对象,也会返回false。对于其他类,equals()的定义可能有所不同。例如,两个String只有在内容完全一样的情况下才会是等价的。因此为了防止意外,就必须意识到List的行为个根据equals()的行为而有所变化。

在输出行7和8中,展示了对精确匹配List中某个对象的对象进行移除是成功的。

List中间插入元素是可行的,就像你在输出行9和它前面的代码中所看到的的一样。但是这带来一个问题:对于LinkedList,在列表中间插入和删除都是廉价操作(在本例中,除了对列表中间进行的真正的随机访问),但是对于ArrayList,这可是代价高昂的操作。这是否意味着你应该永远不要在ArrayList的中间插入一个元素,并且最好是切换到LinkedList?不,这仅仅意味着,你应该意识到这个问题,如果你开始在某个ArrayList的中间执行很多插入操作,并且你的程序开始变慢,那么你应该看看你的List实现有可能是罪魁祸首(发现此类瓶颈的最佳方式是使用仿真器)。优化是一个很棘手的问题,最好的策略就是置之不顾,直到你发现需要担心它了(尽管理解这些问题总是一种好的思路)。

subList()方法允许你很容易的从较大的列表中创建出一个片段,而将其结果传递给这个较大的列表的containsAll()方法时,很自然会得到true。还有一点也很有趣,那就是我们主要到顺序并不重要,你可以在输出行11和12中看到,在sub上调用名字很直观的Collections.sort()Collections.shuffle()方法,不会影响containsAll()的结果。subList()所产生的列表的幕后就是初始列表,因此,对所返回的列表的修改都会反映到初始列表中,反之亦然。

retainAll()方法是一种有效的“交集”操作,在本例中,它保留了所有同时在copysub中的元素。请再次注意,所产生的行为依赖于equals()方法。

removeAll()方法的行为也是基于equals()方法的。就像其名称表示的,它将从List中移除在参数List中的所有元素。

set()方法的命名显得很不合时宜,因为它与Set类存在潜在的冲突。在此处,replace可能会显得更适合,因为它的功能是在指定的索引处(第一个参数),用第二个参数替换整个位置的元素。

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

输出行18-20展示了isEmpty()clear()方法的效果。

输出行22-23展示了你可以如何通过toArray()方法,将任意的Collection转换为一个数组。这是重载的方法,其无参数版本返回的是一个Object数组,但是如果你向这个重载版本传入一个目标类型的数组,那么它将产生指定类型的数组(假设它能通过类型检查)。如果参数数组太小,存放不下List中的所有元素(就像本例一样),toArray()方法将创建一个具有合适尺寸的数组。Pet对象具有一个getId()方法,如你所见,可以在所产生的数组中的对象上调用这个方法。

7.迭代器

任何容器类,都必须具有某种方式插入元素并将他们再次取回。毕竟,持有事物是容器最基本的工作。对于Listadd()是插入元素的方法之一,而get()是取出元素的方法之一。

如果从更高的角度思考,会发现这里有个缺点:要使用容器,必须对确切的类型编程。初看起来没什么不好,但是考虑下面的情况:如果原本是对着List编码的,但是如果能够把相同的代码应用于Set,将会显得非常方便,此时应该怎么做?或者打算从头开始编写通用的代码,他们只是容器,不知道或者说不关心容器的类型,那么如何才能不重写代码就可以应用于不同类型的容器?

迭代器(也是一种设计模式)的概念可以用于达成此目的。迭代器是一个对象,它的工作是遍历并选择序列中的对象,而客户端程序员不必知道或关心改序列底层的结构。此外,迭代器通常被称为轻量级对象:创建它的代价小。因此,经常可以看到对迭代器有些奇怪的限制,例如:Java的Iterator只能单向移动,这个Iterator只能用来:

  1. 使用方法iterator()要求容器返回一个IteratorIterator将准备好返回序列的第一个元素。

  2. 使用next()获得序列中的下一个元素。

  3. 使用hasNext()检查序列中是否还有元素。

  4. 使用remove()将迭代器新近返回的元素删除。

以下是示例:

package com.zjwave.thinkinjava.collection.list;

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

public class SimpleIteration {
    public static void main(String[] args) {
        List<Pet> pets = new ArrayList<>();
        Collections.addAll(pets, new Rat(), new Manx(), new Cymric(), new Mutt(), new Pug(), new Cymric(), new Pug(), new Cymric(), new Mutt());
        Iterator<Pet> it = pets.iterator();
        while(it.hasNext()){
            Pet p = it.next();
            System.out.print(p.getId() + " : " + p + " ");
        }
        System.out.println();
        for (Pet p : pets) {
            System.out.print(p.getId() + " : " + p + " ");
        }
        System.out.println();
        it = pets.iterator();
        //An iterator can also remove elements
        for (int i = 0; i < 4; i++) {
            it.next();
            it.remove();
        }
        System.out.println(pets);
    }
}

有了Iterator就不必为容器中元素的数量操心了,那是由hasNext()next()关心的事。

如果你只是想遍历List,并不打算修改List对象本身,那么可以看到forEach语法会显得更加简洁。

Iterator还可以移除有next()产生的最后一个元素,这意味着在调用remove()之前必须先调用next()

接受容器并传递它,从而在每个对象上都执行操作,这种思想十分强大,并且贯穿于我们整个编程思想中。

现在考虑创建一个display()方法,它不必知晓容器的确切类型:

package com.zjwave.thinkinjava.collection.list;

import java.util.*;


public class CrossContainerIteration {
    public static void main(String[] args) {
        List<Pet> pets = new ArrayList<>();
        Collections.addAll(pets, new Rat(), new Manx(), new Cymric(), new Mutt(), new Pug(), new Cymric(), new Pug(), new Cymric(), new Mutt());
        LinkedList<Pet> petsLL = new LinkedList<>(pets);
        HashSet<Pet> petsHS = new HashSet<>(pets);
        TreeSet<Pet> petsTS = new TreeSet<>(pets);
        display(pets.iterator());
        display(petsLL.iterator());
        display(petsHS.iterator());
        display(petsTS.iterator());
    }

    public static void display(Iterator<Pet> it){
        while (it.hasNext()){
            Pet p = it.next();
            System.out.print(p.getId() + " : " + p + " ");
        }
        System.out.println();
    }

}

请注意,display()方法不包含任何有关它所遍历的序列的类型信息,而这也展示了Iterator真正的威力:能够将遍历序列的操作与序列底层的结构分离。正由于此,有时我们会说:迭代器统一了对容器的访问方式。

7.1 ListIterator

ListIterator是一个更加强大的Iterator的子类型,他只能用于各种List类的访问。尽管Iterator只能向前移动,但是ListIterator可以双向移动。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素。你可以通过调用listIterator()方法产生一个指向List开始处的ListIterator,并且还可以通过调用listIterator(n)方法创建一个一开始就指向索引为n的元素处的ListIterator。下面的示例演示了所有这些能力:

package com.zjwave.thinkinjava.collection.list;

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

public class ListIteration {
    public static void main(String[] args) {
        List<Pet> pets = new ArrayList<>();
        Collections.addAll(pets, new Rat(), new Manx(), new Cymric(), new Mutt(), new Pug(), new Mouse(), new Pug(), new Cymric(), new Mutt());
        ListIterator<Pet> it = pets.listIterator();
        while(it.hasNext()){
            System.out.print(it.next() + ", " + it.nextIndex() + ", " + it.previousIndex() + ";");
        }
        System.out.println();
        //Backwards
        while (it.hasPrevious()){
            System.out.print(it.previous().getId() + " ");
        }
        System.out.println();
        System.out.println(pets);
        it = pets.listIterator(3);
        while (it.hasNext()){
            it.next();
            it.set(new Rat());
        }
        System.out.println(pets);
    }
}

8.LinkedList

LinkedList也像ArrayList一样实现了基本的List接口,但是它执行某些操作(在List中间插入和移除)时比ArrayList更高效,但在随机访问方面却要逊色不少。

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

这些方法中有些彼此之间只是名字有些诧异,或者只存在些许差异,以使得这些名字在特定用法的上下文环境更加适用(特别是在Queue中)。例如,getFirst()element()完全一样,它们都返回列表的头(第一个元素),而并不移除它,如果List为空,则抛出“NoSuchElementException”。peek()方法与这两个方式只是稍有差异,它在列表为空时返回null

removeFirst()remove()也是完全一样的,它们移除并返回列表的头,而在列表为空时抛出“NoSuchElementException”。poll()稍有差异,它在列表为空时返回null

addFirst()add()addLast()相同,它们都将某个元素插入到列表的尾(端)部。

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

package com.zjwave.thinkinjava.collection.list;

import java.util.Collections;
import java.util.LinkedList;

public class LinkedListFeatures {
    public static void main(String[] args) {
        LinkedList<Pet> pets = new LinkedList<>();
        Collections.addAll(pets, new Rat(),new Cymric(), new Mutt(), new Pug(), new Mouse(), new Pug(), new Cymric(), new Mutt());
        System.out.println(pets);
        //Identical
        System.out.println("pets.getFirst() : " + pets.getFirst());
        System.out.println("pets.element() : " +  pets.element());
        //Only differs in empty-list behavior
        System.out.println("pets.peek() : " + pets.peek());
        //Identical ; remove and return the first element
        System.out.println("pets.remove() : " + pets.remove());
        System.out.println("pets.removeFirst() : " + pets.removeFirst());
        //Only differs in empty-list behavior
        System.out.println("pets.poll() : " + pets.poll());
        System.out.println(pets);
        pets.addFirst(new Rat());
        System.out.println("After addFirst : " + pets);
        pets.offer(new Mutt());
        System.out.println("After offer : " + pets);
        pets.add(new Mouse());
        System.out.println("After add : " + pets);
        pets.addLast(new Pug());
        System.out.println("After addLast : " + pets);
        System.out.println("pets.removeLast() : " + pets.removeLast());
    }
}

9.Stack

“栈”通常是指“后进先出”(LIFO)的容器。有时栈也被称为“叠加栈”,因为最后“压入”栈的元素,第一个“弹出”栈。经常用来类比栈的事务是装有弹簧的储放器中的自助餐托盘,最后装入的托盘总是最先拿出来使用的。

LinkedList具有能够实现栈的所有功能的方法,因此可以直接将LinkedList作为栈使用。不过,有时一个真正的“栈”更能把事情讲清楚:

package com.zjwave.thinkinjava.collection.stack;

import java.util.LinkedList;

public class Stack<T> {
    private LinkedList<T> storage = new LinkedList<>();

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

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

这里通过使用泛型,引入了在栈的定义中最简单的可行示例。类名之后的<T>告诉编译器这将是一个参数化类型,而其中的类型参数,即在类被使用时将会被实际类型替换的参数,就是T。大体上,这个类是在声明“我们在定义一个可以持有T类型对象的Stack。”Stack是用LinkedList实现的,而LinkedList也被告知它将持有T类型的对象。注意,push()接受的是T类型的对象,而peek()pop()将返回T类型的对象。peek()方法将提供栈顶元素,但是并不将其从栈顶移除,而pop()方法将移除并返回栈顶元素。

如果你只需要栈的行为,这里使用继承就不合适了,因为这样会产生具有LinkedList的其他所有方法的类(Java1.0的设计者在创建java.util.Stack时,就犯了这个错误)。

下面演示了这个新的Stack类:

package com.zjwave.thinkinjava.collection.stack;

public class StackTest {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        for (String s : "My doy is very happy".split(" ")) {
            stack.push(s);
        }
        while (!stack.empty()){
            System.out.print(stack.pop() + " ");
        }
    }
}

如果你想在自己的代码中使用这个Stack类,当你在创建其实例时,就需要完整指定包名,或者更改这个类的名称;否则,就有可能与java.util.包中是Stack发生冲突。例如,如果我们在上面的例子中导入java.util.*,那么就必须使用包名以防止冲突:

package com.zjwave.thinkinjava.collection.stack;

import com.zjwave.thinkinjava.collection.stack.*;

public class StackCollision {
    public static void main(String[] args) {

        java.util.Stack<String> stack = new java.util.Stack<>();
        for (String s : "My doy is very happy".split(" ")) {
            stack.push(s);
        }
        while (!stack.empty()){
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
        Stack stack2 = new com.zjwave.thinkinjava.collection.stack.Stack();
        for (String s : "My doy is very happy".split(" ")) {
            stack2.push(s);
        }
        while (!stack2.empty()){
            System.out.print(stack2.pop() + " ");
        }
    }
}

这两个Stack具有相同的接口,但是在java.util中没有任何公共的Stack接口,这可能是因为在Java1.0中的设计欠佳,最初的java.util.Stack类占用了这个名字。尽管已经有了java.util.Stack,但是LinkedList可以产生更好的Stack,因此com.zjwave.thinkinjava.collection.stack.Stack所采用的的方式是更可取的。

你还可以通过显式的导入来控制对“首选”Stack实现选择:

import com.zjwave.thinkinjava.collection.stack.Stack;

现在,任何对Stack的引用都将选择com.zjwave.thinkinjava.collection.stack.Stack版本,而选择java.util.Stack时,必须使用全限定名。

10.Set

Set不保存重复的元素(至于如何判断元素相同则较为复杂,稍后便会看到)。如果你试图将相同对象的多个实例添加到Set中,那么它就会阻止这种重复的现象。Set中最常被使用的是测试归属性,你可以很容易的询问某个对象是否在Set中。正因如此,查找就成了Set中最重要的操作,因此你通常都会选择一个HashSet的实现,它专门对快速查找进行了优化。

Set具有和Collection完全一样的接口,因此没有任何额外的功能,不像前面有两个不同的List。实际上Set就是Collection,只是行为不同。(这是继承与多态思想的典型应用:表现不同的行为。)Set是基于对象的值来确定归属性的,而更加复杂的问题将在后续介绍。

下面是使用HashSet存放Integer的示例:

package com.zjwave.thinkinjava.collection.set;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class SetOfInteger {
    public static void main(String[] args) {
        Random random = new Random(47);
        Set<Integer> intset = new HashSet<>();
        for (int i = 0; i < 10000; i++) {
            intset.add(random.nextInt(30));
        }
        System.out.println(intset);
    }
}

在0到29之间的10000个随机数被添加到了Set中,因此你可以想象,每一个数都重复了多少次。但是你可以看到,每一个数只有一个示例出现在结果中。

Set输出的顺序没有任何规律可循,这是因为出于速度原因的考虑(Java1.8的中HashSet实现变了,又因为插入HashSet的是Integer,其hashCode()实现就返回int值本身。所以在对象hashCode这一步引入了巧合的“按大小排序”。),HashSet使用了散列。HashSet所维护的顺序与TreeSetLinkedHashSet都不同,因为他们的实现具有不同的元素存储方式。TreeSet将元素存储在红-黑树数据结构中,而HashSet使用的是散列函数。LinkedHashSet因为查询速度的原因也使用了散列,但是看起来它使用了链表来维护元素的插入顺序。

如果你想对结果排序,一种方式是使用TreeSet代替HashSet

package com.zjwave.thinkinjava.collection.set;

import java.util.*;

public class SortedSetOfInteger {
    public static void main(String[] args) {
        Random random = new Random(47);
        SortedSet<Integer> intset = new TreeSet<>();
        for (int i = 0; i < 10000; i++) {
            intset.add(random.nextInt(30));
        }
        System.out.println(intset);
    }
}

你将会执行的最常见的操作之一,就是使用contains()测试Set的归属性,但是还有很多操作会让你想起上学时所教授的文氏图(用圆表示集与集之间的关系图):

package com.zjwave.thinkinjava.collection.set;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class SetOperations {
    public static void main(String[] args) {
        Set<String> set1 = new HashSet<>();
        Collections.addAll(set1,"A B C D E F G H I J K L".split(" "));
        set1.add("M");
        System.out.println("H : " + set1.contains("H"));
        System.out.println("N : " + set1.contains("N"));
        Set<String> set2 = new HashSet<>();
        Collections.addAll(set2,"H I J K L".split(" "));
        System.out.println("set2 in set1 : " + set1.containsAll(set2));
        set1.remove("H");
        System.out.println("set1 " + set1);
        System.out.println("set2 in set1 : " + set1.containsAll(set2));
        set1.removeAll(set2);
        System.out.println("set2 removed from set1 " + set1);
        Collections.addAll(set1,"X Y Z".split(" "));
        System.out.println(" 'X Y Z' added to set1 " + set1);
    }
}

这些方法名都是自解释型的,而有几个方法可以在JDK文档中找到。(由于笔者使用的是JDK1.8,因此同上解释,散列是被排序了。)

能够产生每个元素都唯一的列表是相当有用的功能。例如:你想要列出在上面SetOperations.java文件中所有单词的时候。如果你想要按照字母顺序排序,那么可以像TreeSet的构造器传入String.CASE_INSENSITIVE_ORDER比较器(比较器就是建立排序顺序的对象):

package com.zjwave.thinkinjava.collection.set;

import java.util.Collections;
import java.util.Set;
import java.util.TreeSet;

public class UniqueWordsAlphabetic {
    public static void main(String[] args) {
        Set<String> words = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
        Collections.addAll(words,"Z Y X L K N O T S D S E B A H J T U K I".split(" "));
        System.out.println(words);

    }
}

Comparator比较器将在后续详细介绍。

11.Map

将对象映射到其他对象的能力是一种解决编程问题的杀手锏。例如,考虑一个程序,用来检查Java的Random类的随机性。理想状态下,Random可以产生理想的数字分布,但要想测试它,则需要生成大量的随机数,并对落入各种不同范围的数字进行计数。Map可以很容易的解决该问题。在本例中,键是由Random产生的数据,而值是该数字出现的次数:

package com.zjwave.thinkinjava.collection.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> m = new HashMap<>();
        for (int i = 0; i < 10000; i++) {
            int r = random.nextInt(20);
            Integer freq = m.get(r);
            m.put(r,freq == null ?  1 : ++freq);
        }
        System.out.println(m);
    }
}

main()中,自动包装机制将随机生成的int转换为HashMap可以使用的Integer引用(不能使用基本类型的容器)。如果键不在容器中,get()方法将返回null(这表示该数字被第一次找到)。否则,get()方法将产生与该键相关联的Integer值,然后这个值被递增(自动包装机制再次简化了表达式,但是确是发生了对Integer的包装和拆包)。

下面的示例允许你使用一个String描述来查找Pet,它还展示了你可以使用怎样的方法通过使用containsKey()containsValue()来测试一个Map,以便查看它是否包含某个键或者某个值。

package com.zjwave.thinkinjava.collection.map;

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

public class PetMap {
    public static void main(String[] args) {
        Map<String,Pet> petMap = new HashMap<>();
        petMap.put("My Cat",new Cat("Molly"));
        petMap.put("My Dog",new Dog("Ginger"));
        petMap.put("My Hamster",new Hamster("Bosco"));
        System.out.println(petMap);
        Pet dog = petMap.get("My Dog");
        System.out.println(dog);
        System.out.println(petMap.containsKey("My Dog"));
        System.out.println(petMap.containsValue(dog));
    }
}

class Dog extends Pet{
    public Dog(String name) {
        super(name);
    }
}
class Cat extends Pet{
    public Cat(String name) {
        super(name);
    }
}
class Hamster extends Pet{
    public Hamster(String name) {
        super(name);
    }
}

abstract class Pet{
    private String name;

    public Pet(){
    }

    public Pet(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return this.getClass().getSimpleName() + " " + this.getName();
    }
}

Map与数组和其他的Collection一样,可以很容易的扩展到多维,而我们只需将其值设为Map(这些Map的值可以是其他容器,甚至可以是其他Map)。因此,我们可以很容易的将容器组合起来从而快速的生成强大的数据结构。例如,假设你正在跟踪拥有多个宠物的人,你所需的只是一个Map<Person,List<Pet>>

package com.zjwave.thinkinjava.collection.map;

import java.util.*;

public class MapOfList {

    public static Map<Person, List<? extends Pet>> petPeople = new HashMap<>();

    static {
        petPeople.put(new Person("Dawn"), Arrays.asList(new Cat("Molly"),new Dog("Spot")));
        petPeople.put(new Person("Kate"), Arrays.asList(new Cat("Shackleton"),new Cat("Elsie May"),new Dog("Margrett")));
        petPeople.put(new Person("Marilyn"), Arrays.asList(new Hamster("Pinkola")));
        petPeople.put(new Person("Luke"),Arrays.asList(new Dog("Fuzzy"),new Cat("Frey")));
        petPeople.put(new Person("Amy"),Arrays.asList(new Cat("Freckly"),new Hamster("Nancy")));
    }


    public static void main(String[] args) {
        System.out.println("People : "+ petPeople.keySet());
        System.out.println("Pets : " + petPeople.values());
        for (Person person : petPeople.keySet()) {
            System.out.print(person + " has ");
            for (Pet pet : petPeople.get(person)) {
                System.out.print(" " + pet);
            }
            System.out.println();
        }

    }
}

class Person{
    private String name;

    public Person(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return this.getClass().getSimpleName();
    }
}

Map可以返回它的键的Set,它的值的Collection,或者它的键值对的SetkeySet()方法产生了由在petPeople中的所有键组成的Set,它的forEach语句中被用来迭代遍历该Map

12.Queue

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

LinkedList提供了方法以支持队列的行为,并且它实现了Queue接口,因此LinkedList可以用作Queue的一种实现。通过将LinkedList向上转型为Queue,下面的示例使用了在Queue接口中与Queue相关的方法:

package com.zjwave.thinkinjava.collection.queue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        Random random = new Random(47);
        for (int i = 0; i < 10; i++) {
            q.offer(random.nextInt(i + 10));
        }
        printQ(q);
        Queue<Character> cq = new LinkedList<>();
        for (char c : "Brontosaurus".toCharArray()) {
            cq.offer(c);
        }
        printQ(cq);
    }

    public static void printQ(Queue queue) {
        while (queue.peek() != null){
            System.out.print(queue.remove() + " ");
        }
        System.out.println();
    }
}

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

自动包装机制会自动的将nextInt()方法的int结果转换为Queue所需的Integer对象,将char转换为cq所需的Character对象。Queue接口窄化了对LinkedList的访问权限,以使得有恰当的方法才可以使用,因此,能够访问LinkedList的方法会变少(这里你实际上可以将Queue转型回LinkedList,但是至少不鼓励这么做)。

注意,与Queue相关的方法提供了完整而独立的功能。即,对于Queue所继承的Collection,在不需要使用它的任何方法的情况下,就可以拥有一个可用的Queue。

12.1 PriorityQueue

先进先出描述了最典型的的队列规则。队列规则是指在给定一组队列中的元素的情况下,确定下一个弹出队列的元素的规则。先进先出声明的是下一个元素应该是等待时间最长的元素。

优先级队列声明下一个弹出的元素是最需要的元素(具有最高的优先级)。例如,在飞机场,当飞机临近起飞时,这架飞机的乘客可以在办理登记手续时排到队头。如果构建了一个消息系统,某些消息比其他消息更重要,因而应该更快的得到处理,那么他们何时得到处理就与它们何时到达无关。PriorityQueue添加到Java SE5中,是为了提供这种行为的一种自动实现。

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

PriorityQueueIntegerStringCharacter这样的内置类型一起工作易如反掌。在下面的示例中,第一个值集与前一个示例的随机值相同,因此你可以看到它们从PriorityQueue中弹出的顺序与前一个示例不同。

package com.zjwave.thinkinjava.collection.queue;

import java.util.*;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        Random random = new Random(47);
        for (int i = 0; i < 10; i++) {
            priorityQueue.offer(random.nextInt(i + 10));
        }
        QueueDemo.printQ(priorityQueue);
        List<Integer> ints = Arrays.asList(25, 22, 20, 13, 18, 14, 8, 9, 27, 99, 86, 53, 24, 72, 5, 4, 1);
        priorityQueue = new PriorityQueue<>(ints);
        QueueDemo.printQ(priorityQueue);
        priorityQueue = new PriorityQueue<>(ints.size(), Collections.reverseOrder());
        priorityQueue.addAll(ints);
        QueueDemo.printQ(priorityQueue);

        String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";
        List<String> strings = Arrays.asList(fact.split(""));
        PriorityQueue<String> stringPQ = new PriorityQueue<>(strings);
        QueueDemo.printQ(stringPQ);
        stringPQ = new PriorityQueue<>(strings.size(),Collections.reverseOrder());
        stringPQ.addAll(strings);
        QueueDemo.printQ(stringPQ);

        Set<Character> charSet = new HashSet<>();
        for (char c : fact.toCharArray()) {
            charSet.add(c);
        }
        PriorityQueue<Character> characterPQ = new PriorityQueue<>(charSet);
        QueueDemo.printQ(characterPQ);
    }
}

你可以看到,重复是允许的,最小的值拥有最高的优先级(如果是String,空格也可以算作值,并且比字幕的优先级高)。为了展示你可以使用怎样的方法通过自己的Comparator对象来改变顺序,第三个对PriorityQueue<Integer>的构造器调用,和第二个对PriorityQueue<String>的调用,使用了由Collections.reverseOrder()(新添加到Java SE5中的)产生的反序Comparator

最后一部分添加了一个HashSet来消除重复的Character,这么做只是为了增添点乐趣。

IntegerStringCharacter可以与PriorityQueue一起工作,因为这个类已经内建了自然排序。如果你想在PriorityQueue中使用自己的类,就必须包括额外的功能以产生自然排序,或者必须提供自己的Comparator

13.Collection和Iterator

Collection是描述所有序列容器的共性根接口,它可能会被认为是一个“附属接口”,即因为因为要表示其他若干个接口的共性而出现的接口。另外,java.util.AbstractCollection类提供了Collection的默认实现,使得你可以创建AbstractCollection的子类型,而其中没有不必要的代码重复。

使用接口描述的理由是它可以使我们能够创建更通用的代码。通过针对接口而非具体实现来编写代码,我们的代码可以应用于更多的对象类型。因此,如果我编写的方法将接受一个Collection,那么该方法就可以应用于任何实现了Collection的类——这也就使得一个新类可以选择去实现Collection接口,以便我的方法可以使用它。但是,有一点很有趣,就是我们注意到标准C++类库并没有其容器的任何公共基类——容器之间的所有共性都是通过迭代器达成的。在Java中,遵循C++的方式看起来似乎很明智,即用迭代器而不是Collection来表示容器之间的共性。但是,这两种方法绑定到了一起,因为实现Collection就意味着需要提供iterator()方法:

package com.zjwave.thinkinjava.collection.list;

import java.util.*;

public class InterfaceVsIterator {
    public static void display(Iterator<Pet> it){
        while (it.hasNext()){
            Pet p = it.next();
            System.out.print(p.getId() + " : " + p + " ");
        }
        System.out.println();
    }

    public static void display(Collection<Pet> pets){
        for (Pet p : pets) {
            System.out.print(p.getId() + " : " + p + " ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        List<Pet> pets = new ArrayList<>();
        Collections.addAll(pets,new Rat(),new Manx(),new Cymric(),new Mutt(),new Pug(),new Cymric(),new Pug(),new Mouse());
        Set<Pet> petSet = new HashSet<>(pets);
        Map<String,Pet> petMap = new LinkedHashMap<>();
        String[] names = ("Ralph, Eric, Robin, Lacey, Britney, Sam, Spot, Fluffy").split(",");
        for (int i = 0; i < names.length; i++) {
            petMap.put(names[i],pets.get(i));
        }
        display(pets);
        display(petSet);
        display(pets.iterator());
        display(petSet.iterator());
        System.out.println(petMap);
        System.out.println(petMap.keySet());
        display(petMap.values());
        display(petMap.values().iterator());
    }
}

两个版本的display()方法都可以使用MapCollection的子类型来工作,而且Collection接口和Iterator都可以将display()方法与底层容器的特定实现解耦。

在本例中,这两种方式都可以凑效。事实上,Collection要更方便一点,因为它是Iterable的类型,因此,在display(Collection)实现中,可以使用forEach结构,从而是代码更清晰。

当你要实现一个不是Collection的外部类时,由于让它去实现Collection接口可能非常困难或麻烦,因此使用Iterator就会变得非常吸引人。例如,如果我们通过继承一个特有的Pet对象的类来创建Collection的实现,那么我们必须实现所有的Collection方法,即使我们在display()方法中不必使用它们,也必须如此。尽管这可以通过继承AbstractCollection而很容易的实现,但是无论如何还是要被强制去实现iterator()size(),以便提供AbstractCollection没有的实现的,但是AbstractCollection中的其他方法会使用到的方法:

package com.zjwave.thinkinjava.collection.list;

import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Iterator;

public class CollectionSequence extends AbstractCollection<Pet> {

    public static void main(String[] args) {
        CollectionSequence c = new CollectionSequence();
        InterfaceVsIterator.display(c);
        InterfaceVsIterator.display(c.iterator());
    }

    private Pet[] pets = new Pet[]{new Rat(), new Manx(), new Cymric(), new Mutt(), new Pug(), new Cymric()};

    @Override
    public Iterator<Pet> iterator() {
        return new Iterator<Pet>() {
            private int index;
            @Override
            public boolean hasNext() {
                return index < pets.length;
            }

            @Override
            public Pet next() {
                return pets[index++];
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("remove");
            }
        };
    }

    @Override
    public int size() {
        return pets.length;
    }
}

remove()方法是一个“可选操作”,这里不必实现它。

在本例中,你可以看到,若果你实现Collection,就必须实现iterator(),并且只拿实现iterator()与继承AbstractCollection相比,花费的代价只有略微减少。但是,如果你的类已经继承其他类,那么你就不能再继承AbstractCollection了。在这种情况下,要实现Collection,就必须实现该接口中的所有方法。此时,继承并提供迭代器的能力就会显得容易得多了:

package com.zjwave.thinkinjava.collection.list;

import java.util.Iterator;

class PetSequence{
    protected Pet[] pets = new Pet[]{new Rat(), new Manx(), new Cymric(), new Mutt(), new Pug(), new Cymric()};
}

public class NonCollectionSequence extends PetSequence{

    public static void main(String[] args) {
        NonCollectionSequence nonCollectionSequence = new NonCollectionSequence();
        InterfaceVsIterator.display(nonCollectionSequence.iterator());
    }

    public Iterator<Pet> iterator(){
        return new Iterator<Pet>() {
            private int index;
            @Override
            public boolean hasNext() {
                return index < pets.length;
            }

            @Override
            public Pet next() {
                return pets[index++];
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("remove");
            }
        };
    }
}

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

14.Foreach与迭代器

到目前为止,foreach语法主要用于数组,但是它也可以应用于任何Collection对象。你实际上已经看到过很多使用ArrayList时用到它的示例,下面是一个更通用的证明:

package com.zjwave.thinkinjava.collection.collection;

import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;

public class ForEachCollections {
    public static void main(String[] args) {
        Collection<String> cs = new LinkedList<>();
        Collections.addAll(cs,"Take the long way home".split(" "));
        for (String c : cs) {
            System.out.print("'" + c + "'");
        }
    }
}

由于cs是一个Collection,所以这段代码展示了能够与foreach工作是所有Collection对象的特性。

之所以能够工作,是因为Java SE5引入了新的被称为Iterable的接口,该接口包含了能够产生Iteratoriterator()方法,并且Iterable接口被foreach用来在序列中移动。因此如果你创建了任何Iterable的类,都可以将它用于foreach语句中:

package com.zjwave.thinkinjava.collection.collection;

import java.util.Iterator;

public class IterableClass implements Iterable<String>{
    protected String[] words = ("And that is how we know the Earth to be banana-shaped.").split(" ");

    @Override
    public Iterator<String> iterator() {
        return new Iterator<String>() {
            private int index;
            @Override
            public boolean hasNext() {
                return index < words.length;
            }

            @Override
            public String next() {
                return words[index++];
            }

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

    public static void main(String[] args) {
        for (String s : new IterableClass()) {
            System.out.print(s + " ");
        }
    }
}

iterator()方法返回的是实现了Iterator<String>的匿名内部类的实例,该匿名内部类可以遍历数组中的所有单词。在main()中,你可以看到IterableClass确实可以用于foreach语句中。

在Java SE5中,大量的类都是Iterable类型,主要包括所有的Collection类(但是不包括各种Map)。例如,下面的代码可以显示所有的操作系统环境变量:

package com.zjwave.thinkinjava.collection.collection;

import java.util.Map;

public class EnvironmentVaribles {
    public static void main(String[] args) {
        for (Map.Entry<String, String> entry : System.getenv().entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

System.getenv()返回一个MapentrySet()产生一个由Map.Entry的元素构成的Set,并且这个Set是一个Iterable,因此它可以用于foreach循环。

foreach语句可以用于数组或其他任何Iterable,但是这并不意味着数组肯定也是一个Iterable,而任何自动包装也不会发生:

package com.zjwave.thinkinjava.collection.collection;

import java.util.Arrays;

public class ArrayIsNotIterable {

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

    public static void main(String[] args) {
        test(Arrays.asList(1, 2, 3));
        String[] strings = {"A", "B", "C"};
        //An Array works in foreach ,but it's not Iterable
        //!test(strings);
        test(Arrays.asList(strings));
    }
}

尝试把数组当做一个Iterable参数传递会导致失败。这说明不存在任何从数组到Iterable的自动转换,你必须手工执行这种转换。

14.1 适配器方法惯用法

如果现有一个Iterable类,你想要添加一种或多种在foreach语句中使用这个类的方法,应该怎么做呢?例如,假设你希望可以选择以向前的方向或是向后的方向迭代一个单词列表。如果直接继承这个类,并覆盖iterator()方法,你只能替换现有的方法,而不能实现选择。

一种解决方案是所谓适配器方法的惯用法。“适配器”部分来自于设计模式,因为你必须提供特定接口以满足foreach语句。当你有一个接口并需要另一个接口时,编写适配器就可以解决问题。这里,我希望在默认的前向迭代器的基础上,添加产生反向迭代器的能力,因此我不能使用覆盖,而是添加了一个能够产生Iterable对象的方法,该对象可以用于foreach语句。正如你所见,这使得我们可以提供多种使用foreach的方式:

package com.zjwave.thinkinjava.collection.collection;

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

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

class ReversibleArrayList<T> extends ArrayList<T> {
    public ReversibleArrayList(Collection<T> c) {
        super(c);
    }

    public Iterable<T> reversed() {
        return new Iterable<T>() {
            @Override
            public Iterator<T> iterator() {
                return new Iterator<T>() {
                    int current = size() - 1;

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

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

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

如果直接将ral对象置于foreach语句中,将得到(默认的)前向迭代器。但是如果在该对象上调用reversed()方法,就会产生不同的行为。

通过使用这种方式,我们可以在IterableClass.java示例中添加两种适配器方法:

package com.zjwave.thinkinjava.collection.collection;

import java.util.*;

public class MultiIterableClass extends IterableClass {

    public Iterable<String> reversed() {
        return new Iterable<String>() {
            @Override
            public Iterator<String> iterator() {
                return new Iterator<String>() {
                    int current = words.length - 1;

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

                    @Override
                    public String next() {
                        return words[current--];
                    }

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

    public Iterable<String> randomized() {
        return new Iterable<String>() {
            @Override
            public Iterator<String> iterator() {
                List<String> shuffled = new ArrayList<>(Arrays.asList(words));
                Collections.shuffle(shuffled, new Random(47));
                return shuffled.iterator();
            }
        };
    }

    public static void main(String[] args) {
        MultiIterableClass mic = new MultiIterableClass();
        for (String s : mic.reversed()) {
            System.out.print(s + " ");
        }
        System.out.println();
        for (String s : mic.randomized()) {
            System.out.print(s + " ");
        }
        System.out.println();
        for (String s : mic) {
            System.out.print(s + " ");
        }
    }
}

注意,第二个方法random()没有创建它自己的Iterator,而是直接返回被打乱的List中的Iterator

从输出中可以看到,Collections.shuffle()方法没有影响原来的数组,而只是打打乱了shuffled中的引用。之所以这样,只是因为randomized()方法用一个ArrayListArrays.asList()方法的结果包装了起来。如果这个由Arrays.asList()方法产生的List被直接打乱,那么它就会修改底层的数组,就像下面这样:

package com.zjwave.thinkinjava.collection.collection;

import java.util.*;

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

        List<Integer> list2 = Arrays.asList(ia);
        System.out.println("Before shuffling: " + list2);
        Collections.shuffle(list2,random);
        System.out.println("After shuffling: " + list2);
        System.out.println("array: " + Arrays.toString(ia));
    }
}

在第一种情况中,Arrays.asList()的输出被传递给了ArrayList()的构造器,这将创建一个引用ia的元素的ArrayList,因此打乱这些引用不会修改该数组。但是,如果直接使用Arrays.asList(ia)的结果,这种打乱就会修改ia的顺序。意识到Arrays.asList()产生的List对象会使用底层数组作为其物理实现是很重要的。只要你执行的这个操作会修改这个List,并且你不想原来的数组被修改,那么你就应该在另一个容器中创建一个副本。

15.总结

Java提供了大量持有对象的方式:

  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. 新程序中不使用过时的VectorHashtableStack

浏览一下Java容器的简图(不包含抽象类和遗留构件)会大有裨益。这里只包含你在一般情况下会碰到的接口和类。

你可以看到,其实只有四种容器:MapListSetQueue,他们各有两到三个实现版本(Queuejava.util.concurrent实现没有包括在上面这张图中)。常用的容器用黑色粗线框表示。

点线框表示接口,实线框表示普通的(具体的)类。带有空心箭头的点线表示一个特定的类实现了一个接口,实心箭头表示某个类可以生成箭头所指向类的对象。例如,任意的Collection可以生成Iterator,而List可以生成ListIterator(也能生成普通的Iterator,因为List继承自Collection)。

除了TreeSet之外的所有Set都拥有与Collection完全一样的接口。ListCollection存在着明显的不同,尽管List所要求的方法都在Collection中。另一方面,在Queue接口中的方法都是独立的;在创建具有Queue功能的实现时,不需要使用Collection的方法。最后,MapCollection之间的唯一重叠就是Map可以使用entrySet()values()方法来产生Collection

注意,标记接口java.util.RandomAccess附着到了ArrayList上,而没有附着到LinkedList上。这为想要根据所使用的特定的List而动态修改其行为的算法提供了信息。

从面向对象的继承层次关系来看,这种组织结构确实有些奇怪。但是,当你了解了java.util中更多的有关容器的内容后,你就会看到除了继承结构有些奇怪外,还有更多的问题。容器类库一直以来都是设计难题——解决这些难题涉及到要去满足经常彼此之间互为牵制的各方面需求。因此你应该学会中庸之道。

抛开这些问题,Java的容器是每天都会用到的工具,它可以使程序更简洁、更强大、更高效。在适应容器类库的某些方面之前,你确实得费点劲儿,但是我想你很快就会找到自己的路子,去获得和使用这个类库中的类。

 

所有源码均可在https://gitee.com/zjwave/thinkinjava中下载

关联文章:

Thinking in Java——Java异常体系(通过异常处理错误)

Thinking in Java——String及相关类库的使用

Thinking in Java——运行时类型信息(RTTI)以及反射

Thinking in Java——泛型

Thinking in Java——数组

Thinking in Java——集合(容器)深入研究

Thinking in Java——Java I/O系统

Thinking in Java——枚举

Thinking in Java——注解

Thinking in Java——并发

转载请注明原文链接:ZJ-Wave

Top