Java Collections API和泛型

数据结构和算法

学会一门编程语言，你可以写出一些可以工作的代码用计算机来解决一些问题，然而想要优雅而高效的解决问题，就要学习数据结构和算法了。当然对数据结构和算法的理解在开发优秀的软件时是非常重要的，与其同等重要的是在我们的开发工作中应用软件工程中的一些良好准则。邹欣老师(博客,微博,豆瓣)的《现代软件工程讲义》提到三个公式：

• 程序 = 数据结构＋算法
• 软件 = 程序 + 软件工程
• 软件企业 = 软件 + 商业模式

我们学习编写程序是要来解决实际问题的，编程的一般过程：

• 如何用数据形式描述问题?—即由问题抽象出一个适当的数学模型;
• 问题所涉及的数据量大小及数据之间的关系;
• 如何在计算机中存储数据及体现数据之间的关系?
• 处理问题时需要对数据作何种运算?
• 所编写的程序的性能是否良好?

上面所列举的问题基本上要由数据结构和算法来解决了。

邹老师说：

程序是基本功，但是除了程序之外，软件工程决定了软件的命运。

程序基本功除了编程语言外，还有数据结构和算法。

《数据结构与算法》是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

数据结构和算法的研究是计算机科学的重要基石。这是一个富集优雅技术和复杂数学分析结果的领域。一个好的算法或数据结构可能使某个原来需要用成年累月才能完成的问题在分秒之中得到解决。在某些特殊领域，例如密码学，图形学、数据库、语法分析、数值分析和模拟等等，解决问题的能力几乎完全依赖于最新的算法和数据结构

数据结构

计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：

• 信息的表示
• 信息的处理

信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。

日常生活中，人们习惯以松散的方式处理信息：比如板子上的钉子，笔记本中的便条，或者文件夹中的图片。然而，用计算机处理信息需要将数据规则地组织起来。

数据有各种形式和大小，但通常它们可以以相同的方式来组织。

数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。

使用数据结构的三个原因是：效率、抽象和重用性。

• 效率

数据结构组织数据的方式使得算法变得更加高效。例如，考虑一下我们该如何组织数据以对其进行检索。一种简单的方式是将数据存放到数组中，然后遍历其中每一个元素直到找到需要的元素为止。然而这种方式确是低效的，因为在很多情况下需要遍历数组中的每一个元素才行。通过使用另一种数据结构，比如哈希表或者二叉树我们可以显著地提高检索的速度。

• 抽象

数据结构使我们以一种更加容易理解的方式去看待数据。也就是说它们为解决问题提供了一层抽象概念。比如，要把数据存入一个栈，可以把精力集中在可以对栈做什么操作上，例如压栈和出栈，而不是实现每种操作的具体细节上。换句话说，数据结构使我们以不那么“程序化”的方式看待程序。

• 重用性

数据结构是可重用的，因为它们应该是模块化且上下文无关的。它们是模块化的，因为每种数据结构都有各自指定的接口，通过它访问数据结构中存储的数据是受限的。也就是说，只能通过定义接口的操作来访问数据。数据结构是上下文无关的，因为它们能在任意环境或上下文中应用于任意一种类型的数据之上。

数据结构的三个组成部分：

• 逻辑结构： 数据元素之间逻辑关系的描述
• 存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
• 数据操作： 对数据要进行的运算

元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型：

• 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。
• 线性结构（1：1）：结构中的数据元素之间存在一对一的关系。
• 树型结构（1：M）：结构中的数据元素之间存在一对多的关系。
• 图状结构或网状结构（M：N）：结构中的数据元素之间存在多对多的关系。

数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。

元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。

• 顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
• 链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )或引用（reference），用该指针或引用来表示数据元素之间的逻辑结构(关系)。

在Java中，用一维数组表示顺序存储结构；用类来表示链式存储结构。

数据类型(Data Type)指的是一个值的集合和定义在该值集上的一组操作的总称。

数据类型是和数据结构密切相关的一个概念。在Java中数据类型有：基本类型和类类型（引用类型）。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

当面对数据结构时，我们通常会想到特定的行为或者操作，我们通常也希望对它们执行这些操作。例如，给定一个链表，我们会自然地想到插入、移除、遍历和计算元素个数等操作。数据结构加上这些基本操作就称为抽象数据类型（ADT）。一个抽象数据类型的操作就组成它的公共接口。抽象数据类型的公共接口精确地定义了我们可以对它做什么。建立并遵守抽象数据类型的接口是绝对必要的，因为这会使我们能更好地管理程序的数据，使得程序变得更容易理解也更容易维护。

在计算机科学领域中，一些最常用来组织数据的方式有：链表、栈、队列、集合、哈希表、树、堆、优先级队列和图。

算法

算法是定义良好的用来解决问题的步骤。在计算机科学领域中，算法是必不可少的，因为它们正是计算机完成系统操作所需要的具体步骤。好的算法就如同好的工具一样，以合理的付出完成相应的工作。使用不当的或定义不清的算法就像用台锯去切割一张纸，或者用剪刀去切夹板一样：尽管工作也许能完成，但你不得不考虑完成工作的效率。

算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

算法具有以下五个特性

• 有穷性： 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

• 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

• 可行性： 一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

• 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

• 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。

算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。

评价一个好的算法有以下几个标准

• 正确性(Correctness )：算法应满足具体问题的需求。
• 可读性(Readability)：算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。
• 健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
• 通用性(Generality)： 算法应具有一般性 ，即算法的处理结果对于一般的数据集合都成立。
• 效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。

和数据结构一样，使用算法也有3个原因：效率、抽象和重用性。

• 效率
  
  由于特定类型的问题经常在计算机领域出现，随着时间的推移人们已经找到了高效的方法来解决这类问题。比如，试想一下要对一本书中的索引号排序。因为排序是一项常见的任务，所以对于有许多高效的算法可以完成排序。

• 抽象
  
  在解决问题时，算法能够提供一定程度的抽象，因为很多看似复杂的问题都可以用已存在的著名算法来简化。一旦我们能用简化的眼光去看待复杂的问题，更为复杂的问题就可以看做一个更为简单问题的抽象。例如，试想一下如何找到互联网上两个网关之间数据包的最短路由。一旦我们意识到这个问题不过就是更具一般性的单对最短路径问题的变种时，我们就能够以这种泛化的方式来解决问题。

• 重用性
  
  算法在很多不同场景下能够得到重用。因为很多著名的算法解决的问题都是由复杂的问题抽象而来的，这也是因为很多复杂的问题都能够简化为简单的问题。一些能够有效解决这类特定问题的方法使我们有可能解决更多其他的问题。

算法设计的一般方法

从广义上讲，很多算法解决问题的思路是相同的。因此，为了方便，通常按照算法采用的方法和思路来给它们分类。这样给算法分类的一个原因是：如果我们理解了它采用的一般思路我们常常就能够对该算法获得一些深入的了解。在解决一些没有现成算法求解，但与现有问题类似的问题时，我们从中可以得到一些启发和灵感。当然，有些算法有悖于分类原则，而另一些则是多种方法相结合的产物。这一节将介绍一些常用的方法。

• 随机法

随机法依赖于随机数的统计特性。一个应用随机法的例子是快速排序。

• 分治法

分治法包含3个步骤：分解、求解与合并。在分解阶段，将数据分解为更小、更容易管理的部分。在求解阶段，对每个分解出的部分进行处理。在合并阶段，将每部分处理的结果进行合并。一个分治法的例子是归并排序。

• 动态规划

动态规划同分治法类似，都是将较大的问题分解为子问题最后再将结果合并。然而，它们处理问题的方式与子问题之间的关系有关。在分治法中，每一个子问题都是独立的。为此，我们以递归的方式解决每一个子问题，然后将结果与其他子问题的结果合并。在动态规划中，子问题之间并不是独立的。换句话说，子问题之间可能有关联。这类问题采用动态规划法比分治法更合适。因为若用分治法来解决这类问题会多做很多不必要的工作，有些子问题会重复计算多次。

• 贪心法

贪心法在求解问题时总能够做出在当前的最佳选择。换句话说，不是从整体最优上考虑，而仅仅是在某种意义上的局部最优解。遗憾的是，当前的最优解长远来看却未必是最优的。因此，贪心法并不会一直产生最优结果。然而，在某些方面来说，贪心法确是最佳选择。一个采用贪心法的例子是霍夫曼编码，这是一个数据压缩算法。

• 近似法

近似法并不计算出最优解，相反，它只计算出“足够好”的解。通常利用近似法解决那些计算成本很高又因为其本身十分有价值而不愿放弃的问题。推销员问题是一个通常会用近似法去解决的问题。

算法效率度量

算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：

• 事后统计：

计算机内部进行执行时间和实际占用空间的统计。

问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。

事前分析：求出该算法的一个时间界限函数。

• 事前分析：

求出该算法的一个时间界限函数。

与此相关的因素有：依据算法选用何种策略；问题的规模；程序设计的语言；编译程序所产生的机器代码的质量；机器执行指令的速度；

撇开软硬件等有关因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用n表示），或者说，它是问题规模的函数。

算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作 T(n)=O(f(n))，称作算法的渐近时间复杂度(Asymptotic Time complexity)，简称时间复杂度。

一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。

以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n的平方)<O(n的立方)

指数时间的关系为：O(2的n次方)<O(n!)<O(n的n次方)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。

我们还应该区分算法的最坏情况的行为和期望行为。要定义好“期望”的意义非常困难，

因为它依赖于对可能出现的输入有什么假定。另一方面，我们通常能够比较精确

地了解最坏情况，虽然有时它会造成误解。

常见的一些时间复杂度：

Java Collections APIs

如果你正要进入一个新领域去开发程序，那么首先需要弄清楚在这里已经有了些什么，以免无谓地把时间浪费在别人早已做好的东西上。

每个程序都要依靠算法与数据结构，但很少有程序依赖于必须发明一批全新的东西。即使是很复杂的程序，比如在编译器或者网络浏览器里，主要的数据结构也是数组、表、树和散列表等等。如果在一个程序里要求某些更精巧的东西，它多半也是基于这些简单东西构造起来的。因此，对大部分程序员而言，所需要的是知道有哪些合适的、可用的算法和数据结构，知道如何在各种可以互相替代的东西之中做出选择。

候捷老师在《 深入浅出MFC 2e(电子版)》中引用林语堂先生的一句话：

只用一样东西，不明白它的道理，实在不高明

只知道How，不知道Why，出了一点小问题时就无能为力了。我们课上鼓励大家在Linux下学习编程，尽量在命令行中编辑/编译/调试程序，Git的使用，数据库的管理都先会命令方式下使用，这样在IDE中，在GUI界面中出了问题，我们有更好的方法查找。

现在我们遇到另外一个极端，不会用一样东西，却想要明白它的道理，实在太难。比如有的同学连Linux都没用过，却想弄明白Linux内核。

大多数学生学到的第一门语言是语言，用C语言进行《数据结构》的教学好像是顺理成章的事情，

然而由于C语言非常简单，C库也只有100多个函数，C语言没有C++的STL库，Java的Collection API这样的东西，用C语言进行《数据结构》教学有"不会用一样东西，却想要明白它的道理，实在太难"的问题。学完数据结构后，遇到数组进行排序的问题，大多同学的反应是自己写个冒泡排序程序，不知道C语言中有qsort函数，更不用说会用了。

使用Java进行《数据结构》教学有个好处是：我们可以先使用数据结构，就是Java的Collection API，然后现深入实现细节。

在编写面向对象程序的时候，常常需要操作一组对象。我们了解了数组是用来组织相同类型的对象的。遗憾的是，数组缺乏快速开发应用程序所需要的灵活性。例如，数组不能修改其大小。好在Java带有一组接口和类，使得操作成组的对象更为容易。

集合（ collection）是将其他对象组织到一起的一个对象。集合也叫作容器（container），它提供了一种方法来存储、访问和操作其元素。集合帮助 Java 程序员很容易地管理对象。Java程序员应该熟悉集合框架中一些重要的类型，它们在java.util包中。

集合框架中的主要类型，当然是 Collection 接口。 List、 Set 和 Queue 是 Collection 的 3 个主要的子接口。此外，还有一个 Map 接口，它可以用于存储键/值对。 Map 的一个子接口 SortedMap，保证了键按照升序排列。 Map 的其他实现还有 AbstractMap 及其具体的实现 HashMap。其他的接口包括 Iterator 和Comparator。后者使得对象成为可排序和可比较的。

集合框架的大多数接口都带有实现类。有时候，一个实现有两个版本，同步的版本和非同步的版本。例如，java.util.Vector 类和 ArrayList 类实现了 List 接口。Vector 和 ArrayList 都提供了类似的功能，但是 Vector是同步的，而 ArrayLis 是非同步的。

Collection 接口

数据结构的主要运算包括：

• 建立(Create)一个数据结构；
• 消除(Destroy)一个数据结构；
• 从一个数据结构中删除(Delete)一个数据元素；
• 把一个数据元素插入(Insert)到一个数据结构中；
• 对一个数据结构进行访问(Access)；
• 对一个数据结构(中的数据元素)进行修改(Modify)；
• 对一个数据结构进行排序(Sort)；
• 对一个数据结构进行查找(Search)；
• ...

我们看看java的Collection接口：

Collection 接口将对象组织到一起。数组不能调整大小，并且只能组织相同类型的对象，而Collections允许添加任何类型的对象，并且不强迫你指定初始大小。

Collection 带有一些很容易使用的方法:

• 要添加一个元素，使用 add 方法
• 要添加另一个 Collection 的成员，使用 addAll
• 要删除所有的元素，使用 clear 方法
• 要查询 Collection 中的元素的数目，调用其 size 方法
• 要测试一个 Collection 是否包含一个元素，使用 isEmpty 方法
• 要把集合元素放入到一个数组中，使用方法 toArray。

需要注意的重要的一点是， Collection 扩展了 Iterable 接口， Collection 从那里继承了 iterator 方法。该方法返回一个 Iterator对象，可以用来遍历集合的元素。我们还会学习如何使用 for 循环来遍历一个 Collection 的元素。

List 和 ArrayList

List 是 Collection 最为常用的接口，而 ArrayList 是最为常用的 List 的实现。List 又叫作序列（ sequence），它是一个有序的集合。你可以使用索引来访问其元素，而且可以在确切的位置插入一个元素。一个 List 的索引0引用其第1个元素，索引1引用第 2个元素，依次类推。

继承自 Collection 的 add 方法，将指定的元素添加到列表的末尾。该方法的签名如下：

public boolean add(java.lang.Object element)

如果添加成功，该方法返回 true。否则，它返回 false。 List 的一些实现（如 ArrayList）允许添加空的元素，有些实现则不允许。

List 使用如下的签名添加另一个 add 方法：

public void add(int index, java.lang.Object element)

可以用这个 add 方法在任何位置插入一个元素。

此外，可以分别使用 set 和 remove 方法来替换和删除一个元素。

public java.lang.Object set(int index, java.lang.Object element)

public java.lang.Object remove(int index)

set 方法用 element 来替换 index 所指定的位置的元素，并且返回插入的元素的索引。 remove 方法删除指定的位置的元素，并且返回对删除的元素的一个引用。

要创建一个 List，通常将一个 ArrayList 对象赋值给 List 引用变量。

List myList = new ArrayList();

ArrayList 的无参数构造方法创建了一个ArrayList对象，具有10个元素的初始容量。如果你添加的元素超出其容量，这个大小将会自动增加。如果你知道ArrayList中的元素数目将会大于其容量，可以使用其第 2 个构造方法：

public ArrayList(int initialCapacity)

此方法将会产生一个略微快一些的 ArrayList，因为这个实例不必去增加容量。

List 允许你存储重复的元素，这意味着，可以存储两个或多个指向相同元素的引用。下面代码展

示了 List 及其一些方法的应用：

import java.util.ArrayList;

import java.util.List;

public class ListDemo1 {

    public static void main(String[] args) {

        List myList = new ArrayList();

        String s1 = "Hello";

        String s2 = "Hello";

        myList.add(100);

        myList.add(s1);

        myList.add(s2);

        myList.add(s1);

        myList.add(1);

        myList.add(2, "World");

        myList.set(3, "Yes");

        myList.add(null);

        System.out.println("Size: " + myList.size());

        for (Object object : myList) {

            System.out.println(object);

        }

    }

}

运行程序，这段代码在控制台显示如下的结果。

Size: 7

100

Hello

World

Yes

Hello

1

null

java.util.Arrays 类提供了一个asList方法，它允许你一次向一个List添加数组或任意多个元素。例如，如下的代码段一次添加了多个 String 类型的数据:

List members = Arrays.asList("Chuck", "Harry", "Larry", "Wang");

然而， Arrays.asList 返回具有固定大小的 List， 这意味着，你不能向其添加成员。

List 还增加了方法来搜索集合，即 indexOf 和 lastIndexOf：

public int indexOf(java.lang.Object obj)

public int lastIndexOf(java.lang.Object obj)

indexOf 方法从第一个元素开始使用 equals 方法，以比较 obj 参数及其元素，并且返回第 1 次匹配的索引。 lastIndexOf 做同样的事情，但是，其比较是从最后一个元素到第 1 个元素。如果没有找到匹配， indexOf和 lastIndexOf 方法都返回-1。

java.util. Collections 类是一个辅助类或工具类，它提供了静态方法来操作 List 和其他的 Collection。例如，你可以使用 List 的 sort 方法很容易地对一个 List进行排序，如下面代码所示。

import java.util.Arrays;

import java.util.Collections;

import java.util.List;

public class ListDemo2 {

    public static void main(String[] args) {

        List numbers = Arrays.asList(9, 4, -9, 100);

        Collections.sort(numbers);

        for (Object i : numbers) {

            System.out.println(i);

        }

    }

}

如果运行这个 ListDemo2 类，将会在控制台看到如下内容。

-9

4

9

100

使用 Iterator 和 for 遍历一个Collection

在操作集合的时候，遍历一个Collection是最常见的任务之一。有两种方法可能做到这一点，使用 Iterator或使用 for。

Collection 扩展了 Iterable，后者有一个方法iterator。这个方法返回一个java.util.Iterator，可以用来遍历 Collection。 Iterator 接口有如下的方法：

• hasNext。 Iterator 使用了一个内部指针，其最初指向第1个元素之前的一个位置。如果在指针的后面还有更多的元素，hasNext 返回 true。调用 next 会将这个指针移动到下一个元素。第 1 次在 Iterator上调用 next，会导致其指针指向第 1 个元素。
• next。将内部指针移动到下一个元素并返回该元素。在最后一个元素返回之后调用 next，将会抛出一个 java.util.NoSuchElementException。因此，在调用 next 之前，先调用 hasNext 方法测试是否还有下一个元素，这样做是比较安全的。
• remove。删除内部指针所指向的元素。

一个 Iterator 遍历 Collection 的常用方式是使用 while 或 for。假设 myList是你想要遍历的 ArrayList 。如下的代码段使用 while 语句来遍历一个集合，并且打印出集合中的每一个元素。

Iterator iterator = myList.iterator();

while (iterator.hasNext()) {

String element = (String) iterator.next();

System.out.println(element);

}

相同的代码是：

for (Iterator iterator = myList.iterator(); iterator.hasNext(); ) {

    String element = (String) iterator.next();

    System.out.println(element);

}

for 语句可以遍历一个 Collection 而不需要调用 iterator 方法。其语法如下：

for (Type identifier : expression) {

    statement(s)

}

这里的 expression 必须是一个 Iterable。由于 Collection扩展了Iterable，你可以使用增强的 for 来遍历任何 Collection。例如，如下的代码展示了如何使用 for。

for (Object object : myList) {

    System.out.println(object);

}

使用 for 遍历一个集合是使用Iterator的快捷方式。实际上，以上使用for的代码，会被编译器翻译为如下的代码。

for (Iterator iterator = myList.iterator(); iterator.hasNext(); ) {

    String element = (String) iterator.next();

    System.out.println(element);

}

Set 和 HashSet

Set 表示一个数学的集。和 List 不同， Set 不允许重复的内容。假设两个元素， e1 和 e2，如果 e1.equals(e2)的话，它们是不能在 Set中同时存在的。如果试图添加一个重复的元素， Set 的 add 方法会返回 false。例如，如下的代码会打印出“ addition failed”。

Set set = new HashSet();

set.add("Hello");

if (set.add("Hello")) {

    System.out.println("addition successful");

} else {

    System.out.println("addition failed");

}

第 1 次调用 add 的时候，添加了字符串“Hello”。第2次调用的时候，将会失败，因为要添加另一个“ Hello”将会导致 Set 中有重复的元素。

Set 允许最多有一个空元素。有些实现不允许有空元素。例如，Set最流行的实现HashSet，允许最多有一个空元素。当使用 HashSet 的时候，需要注意，并不能保证元素的顺序保持不变。 HashSet 应该是 Set的首选，因为它比 Set 的其他实现（ TreeSet 和 LinkedHashSet）要快.

Queue 和 LinkedList

Queue 通过添加支持按照先进先出（first-in-first-out，FIFO）的方式排序元素的方法，扩展了 Collection。FIFO 意味着，当获取元素的时候，最先添加的元素将会是第一个元素。这和 List 不同，在 List 中，是通过传给其 get 方法一个索引来选择要访问的元素。

Queue 添加了如下的方法。

• offer。这个方法就像 add方法一样用来添加一个元素。但是，如果添加一个元素有可能会失败的话，应该使用 offer。如果添加一个元素失败的话，offer会返回false，并且不会抛出一个异常。如果使用 add 添加失败，会抛出一个异常。

• remove。该方法删除并返回Queue头部的元素。如果Queue为空，该方法抛出一个java.util.NoSuchElementException。

• poll。该方法就像是 remove 方法一样。但是，如果 Queue为空，它将会返回空而不会抛出一个
  
  异常。

• element。该方法返回 Queue 头部的元素但不会删除它。 但是，如果Queue为空，该方法抛出一
  
  个 java.util.NoSuchElementException。

• peek。返回 Queue 头部的元素但不会删除它。 但是，如果 Queue 为空，该方法将会返回空。
  
  当在一个 Queue 上调用 add 或 offer 方法的时候，该元素总是添加在 Queue的末尾。要访问这个元素，可以使用 remove 或 poll 方法。 remove 和 poll 方法总是删除并返回 Queue 头部的元素。

例如，如下的代码创建了一个 LinkedList（这是 Queue 的一个实现）来展示 Queue 的 FIFO 特性。

Queue queue = new LinkedList();

queue.add("one");

queue.add("two");

queue.add("three");

System.out.println(queue.remove());

System.out.println(queue.remove());

System.out.println(queue.remove());

这段代码产生的结果如下：

one

two

three

上面代码展示了 remove 总是删除 Queue 头部的元素。换句话说，你不能在删除“ one”和“ two”之前删除“ three”（ Queue 的第 3 个元素）。

与Queue类似，java.util.Stack类是一个Collection，其行为是后进先出（last-in-first-out，LIFO）的方式。

集合转换

Collection 实现通常有一个构造函数，它接受一个Collection对象。这使得你可以将一个Collection 转换为另一个不同类型的 Collection。如下是这个构造方法的一些实现：

public ArrayList(Collection c)

public HashSet(Collection c)

public LinkedList(Collection c)

作为示例，如下的代码把一个 Queue 转换为一个 List。

Queue queue = new LinkedList();

queue.add("Hello");

queue.add("World");

List list = new ArrayList(queue);

如下的代码把一个 List 转换为一个 Set。

List myList = new ArrayList();

myList.add("Hello");

myList.add("World");

myList.add("World");

Set set = new HashSet(myList);

myList 有 3 个元素，其中的两个是重复的。因为Set并不允许重复的元素，因此，只有一个重复的元素会被接受。因此，上面的 Set 只有两个元素。

Map 和 HashMap

Map 保存了键到值的映射。Map中不能有重复的元素，并且每个键最多映射一个值。要给Map添加键/值对，需要用 put 方法。其签名如下所示：

public void put(java.lang.Object key, java.lang.Object value)

注意，键和值都不能是基本类型。但是，在如下的代码中，为键和值都传递基本类型是合法的，因为在调用 put 方法之前会先执行装箱操作。

map.put(1, 3000);

此外，也可以使用 putAll 方法并传入一个 Map 参数。

public void putAll(Map map)

可以通过给 remove 方法传递键来删除一个映射。

public void remove(java.lang.Object key)

要删除所有的映射，可以使用 clear方法。要得到映射的数目，可以使用size方法。此外，如果有 0个映射的话， isEmpty 方法会返回 true。

要获取一个值，给 get 方法传入一个键：

public java.lang.Object get(java.lang.Object key)

除了目前为止所讨论的方法，还有 3 个无参数方法，能够提供查看 Map 的功能。

• keySet。返回包含 Map 中的所有键的一个 Set。
• values。返回包含 Map 中的所有值的一个 Collection。
• entrySet。返回包含了Map.Entry对象的一个Set，其中每个Map.Entry对象表示一个键/值对。Map.Entry接口提供了 getKey 方法，它能够返回键的部分；还有 getValue 方法，能够返回值的部分。

java.util 包中有 Map 的几个实现,最常使用的是HashMap和Hashtable。HashMap是非同步的，Hashtable是同步的。因此， HashMap 是二者中更快的一个。

如下的代码展示了 Map 和 HashMap 的用法。

Map map = new HashMap();

map.put("1", "one");

map.put("2", "two");

System.out.println(map.size()); //prints 2

System.out.println(map.get("1")); //prints "one"

Set keys = map.keySet();

// print the keys

for (Object object : keys) {

    System.out.println(object);

}

使得对象可比较和可排序

在现实世界中，当我们说“我的汽车和你的汽车一样”的时候，我的意思是说，我的车和你的车是同

样的型号，一样的新，具有相同的颜色等。

在 Java 中，我们使用引用对象的变量来操作对象。引用变量并不包含对象，而是包含了对象在内存中的地址，因此，当你比较两个引用变量 a 和 b 的时候，可以使用下面的代码。

if (a == b)

实际上，你是在询问 a 和 b 是否引用同一个变量，而不是说 a 和 b 引用的对象是否是相同的。

考虑如下的示例。

Object a = new Object();

Object b = new Object();

a 引用的对象的类型和 b 引用的对象的类型相同。

但是， a 和 b 引用了两个不同的实例，而且 a 和 b 包含了不同的内存地址。因此，（ a == b）返回 false。

这种比较对象引用的方式很难有用，因为大多数时候，我们更关心对象，而不是对象的地址。如果你想要比较对象，需要找到该类所提供的专门比较对象的方法。例如，要比较两个 String 对象，可以调用其equals方法。能否比较两个对象，取决于该对象的类是否支持比较。一个类可以通过实现它从 java.lang.Object继承而来的 equals 和 hashCode 方法来支持对象的比较。

此外，可以通过实现 java.lang.Comparable和java.util.Comparator接口让对象成为可比较的。

使用 java.lang.Comparable

java.util.Arrays 类提供了静态的方法 sort，它可以排序对象的一个数组。该方法的签名如下。

public static void sort(java.lang.Object[]a)

由于所有的 Java 类都派生自 java.lang.Object，所有的 Java 对象都是 java.lang.Object 类型的。这意味着，可以将任何对象的数组传递给 sort 方法。

和数组类似， java.util.Collections 类也有一个 sort 方法用来排序 List。

sort 方法怎么知道如何去排序任意的对象呢？排序数字或字符串很容易，但是，如何排序 Elephant 对象的一个数组呢？

首先，看一下如下代码中的 Elephant 类。

public class Elephant {

    public float weight;

    public int age;

    public float tuskLength; // in centimeters

}

作为 Elephant 类的编写者，由你来决定想要让Elephant对象如何排序。假设你想要根据其体重和年龄来排序。现在，如何告诉 Arrays.sort 或 Collections.sort 你的决定呢？

这两个 sort 方法都定义了它们自身和需要排序的对象之间的一个协议。这个协议的形式是java.lang.Comparable 接口。

package java.lang;

public interface Comparable {

    public int compareTo(Object obj);

}

需要通过 Arrays.sort 或 Collections.sort 来支持排序的任何类，都必须实现 Comparable 接口。在上面代码中， compareTo方法中的参数obj引用了需要和该对象进行比较的对象。如果该对象比参数对象大，在实现类中，实现该方法的代码必须返回一个正值；如果两个对象相等，这个方法返回 0；如果该对象比参数对象小，该方法返回一个负值。

下面代码给出了一个修改了的 Elephant 类，它实现了 Comparable。

public class Elephant implements Comparable {

    public float weight;

    public int age;

    public float tuskLength;

    public int compareTo(Object obj) {

        Elephant anotherElephant = (Elephant) obj;

        if (this.weight > anotherElephant.weight) {

            return 1;

        } else if (this.weight < anotherElephant.weight) {

            return -1;

        } else {

            // both elephants have the same weight, now

            // compare their age

            return (this.age - anotherElephant.age);

        }

    }

}

既然 Elephant 实现了 Comparable 接口，可以使用 Arrays.sort 或 Collections.sort 来排序 Elephant 对象的一个数组或 list。 sort 方法会将Elephant对象当作一个Comparable对象（因为 Elephant 实现了 Comparable，一个Elephant对象可以被认为是Comparable类型的），并且在该对象上调用 compareTo 方法。sort方法重复这一过程，直到数组中的Elephant对象都已经按照其体重和年龄正确地组织好了。

下面代码提供了一个类来测试 Elephant 对象上的 sort 方法。

import java.util.Arrays;

public class ElephantTest {

public static void main(String[] args) {

Elephant elephant1 = new Elephant();

elephant1.weight = 100.12F;

elephant1.age = 20;

Elephant elephant2 = new Elephant();

elephant2.weight = 120.12F;

elephant2.age = 20;

Elephant elephant3 = new Elephant();

elephant3.weight = 100.12F;

elephant3.age = 25;

Elephant[] elephants = new Elephant[3];

elephants[0] = elephant1;

elephants[1] = elephant2;

elephants[2] = elephant3;

System.out.println("Before sorting");

for (Elephant elephant : elephants) {

System.out.println(elephant.weight + ":" +

elephant.age);

}

Arrays.sort(elephants);

System.out.println("After sorting");

for (Elephant elephant : elephants) {

System.out.println(elephant.weight + ":" +

elephant.age);

}

}

}

如果运行 ElephantTest 类，将会在控制台看到如下内容。

Before sorting

100.12:20

120.12:20

100.12:25

After sorting

100.12:20

100.12:25

120.12:20

像 java.lang.String、 java.util.Date 这样的类，以及基本类型的包装器类，都实现了 java.lang.Comparable。

这就说明了能够排序它们的原因。

使用 Comparator

实现 java.lang.Comparable接口使得你可以定义一种方式来比较类的实例。但是，对象有时候需要以更多的方式进行比较。例如，两个Person对象可能需要按照年龄、姓氏和名字进行比较。对于类似这样的情况，你需要创建一个Comparator实例，它定义了应该如何比较两个对象。要让对象可以按照两种方式比较，就需要两个Comparator 实例。有了Comparator，我们就可以比较两个对象，即便它们的类没有实现 Comparable 接口。

要创建一个 Comparator 对象，编写一个实现了 Comparator 接口的类。然后，提供其 compare 方法的实现。该方法签名如下：

public int compare(java.lang.Object o1, java.lang.Object o2)

如果 o1 和 o2 相等，compare返回0；如果o1小于o2，它返回一个负整数；如果o1大于o2，返回一个正整数。

下面示例实现了 Comparable接口，展示了Person对象的两个Comparator（按照姓氏比较和按照名字比较）。

实现了 Comparable 的 Person 类

public class Person implements Comparable {

    private String firstName;

    private String lastName;

    private int age;

    public String getFirstName() {

        return firstName;

    }

    public void setFirstName(String firstName) {

        this.firstName = firstName;

    }

    public String getLastName()

        return lastName;

    }

    public void setLastName(String lastName) {

        this.lastName = lastName;

    }

    public int getAge() {

        return age;

    }

    public void setAge(int age) {

        this.age = age;

    }

    public int compareTo(Object anotherPerson throws ClassCastException {

    if (!(anotherPerson instanceof Person)) {

        throw new ClassCastException("A Person object expected.");

    }

    int anotherPersonAge = ((Person) anotherPerson).getAge();

    return this.age - anotherPersonAge;

    }

}

LastNameComparator 类

import java.util.Comparator;

public class LastNameComparator implements Comparator {

    public int compare(Object person, Object anotherPerson) {

        String lastName1 = ((Person)

            person).getLastName().toUpperCase();

        String firstName1 =

            ((Person) person).getFirstName().toUpperCase();

        String lastName2 = ((Person)

            anotherPerson).getLastName().toUpperCase();

        String firstName2 = ((Person) anotherPerson).getFirstName()

        .toUpperCase();

        if (lastName1.equals(lastName2)) {

            return firstName1.compareTo(firstName2);

        } else {

            return lastName1.compareTo(lastName2);

        }

    }

}

FirstNameComparator 类

import java.util.Comparator;

public class FirstNameComparator implements Comparator {

    public int compare(Object person, Object anotherPerson) {

        String lastName1 = ((Person)

            person).getLastName().toUpperCase();

        String firstName1 = ((Person)

            person).getFirstName().toUpperCase();

        String lastName2 = ((Person)

            anotherPerson).getLastName().toUpperCase();

        String firstName2 = ((Person) anotherPerson).getFirstName()

            .toUpperCase();

        if (firstName1.equals(firstName2)) {

            return lastName1.compareTo(lastName2);

        } else {

            return firstName1.compareTo(firstName2);

        }

    }

}

PersonTest 类

import java.util.Arrays;

public class PersonTest {

    public static void main(String[] args) {

        Person[] persons = new Person[4];

        persons[0] = new Person();

        persons[0].setFirstName("Elvis");

        persons[0].setLastName("Goodyear");

        persons[0].setAge(56);

        persons[1] = new Person();

        persons[1].setFirstName("Stanley");

        persons[1].setLastName("Clark");

        persons[1].setAge(8);

        persons[2] = new Person();

        persons[2].setFirstName("Jane");

        persons[2].setLastName("Graff");

        persons[2].setAge(16);

        persons[3] = new Person();

        persons[3].setFirstName("Nancy");

        persons[3].setLastName("Goodyear");

        persons[3].setAge(69);

        System.out.println("Natural Order");

        for (int i = 0; i < 4; i++) {

            Person person = persons[i];

            String lastName = person.getLastName();

            String firstName = person.getFirstName();

            int age = person.getAge();

            System.out.println(lastName + ", " + firstName +

            ". Age:" + age);

        }

        Arrays.sort(persons, new LastNameComparator());

        System.out.println();

        System.out.println("Sorted by last name");

        for (int i = 0; i < 4; i++) {

            Person person = persons[i];

            String lastName = person.getLastName();

            String firstName = person.getFirstName();

            int age = person.getAge();

            System.out.println(lastName + ", " + firstName +

            ". Age:" + age);

        }

        Arrays.sort(persons, new FirstNameComparator());

        System.out.println();

        System.out.println("Sorted by first name");

        for (int i = 0; i < 4; i++) {

            Person person = persons[i];

            String lastName = person.getLastName();

            String firstName = person.getFirstName();

            int age = person.getAge();

            System.out.println(lastName + ", " + firstN

            ". Age:" + age);

        }

        Arrays.sort(persons);

        System.out.println();

        System.out.println("Sorted by age");

        for (int i = 0; i < 4; i++) {

            Person person = persons[i];

            String lastName = person.getLastName();

            String firstName = person.getFirstName();

            int age = person.getAge();

            System.out.println(lastName + ", " + firstN

            ". Age:" + age);

        }

    }

}

如果运行 PersonTest 类，将会得到如下的结果。

Natural Order

Goodyear, Elvis. Age:56

Clark, Stanley. Age:8

Graff, Jane. Age:16

Goodyear, Nancy. Age:69

Sorted by last name

Clark, Stanley. Age:8

Goodyear, Elvis. Age:56

Goodyear, Nancy. Age:69

Graff, Jane. Age:16

Sorted by first name

Goodyear, Elvis. Age:56

Graff, Jane. Age:16

Goodyear, Nancy. Age:69

Clark, Stanley. Age:8

Sorted by age

Clark, Stanley. Age:8

Graff, Jane. Age:16

Goodyear, Elvis. Age:56

Goodyear, Nancy. Age:69

Java 泛型

参考资料

• 算法精解(电子版,Mastering Algorithms with C)
• 构建之法(电子版)
• 数据结构(严蔚敏)

---

欢迎关注“rocedu”微信公众号(手机上长按二维码)

做中教，做中学，实践*同进步！

---

• 原文地址：http://www.cnblogs.com/rocedu/p/java-collections-generic.html

• 推荐网站：博客园、新浪微博、扇贝背单词、DKY背单词小组、有道云笔记、豆瓣读书

• 版权声明：*转载-非商用-非衍生-保持署名| Creative Commons BY-NC-ND 3.0

---