第 6章 容器类简介
程序就是算法加数据结构,Java程序中的的数据结构的实现利用到了各种各样的容器类 (Java
Collection)，容器以其操作灵活性、功能强大成为是构建程序数据结构的重要选择。本章就对
Java中的形形色色的容器类进行简介，读者会通过本章对容器类形成初步的认识，将会学习到什么是容器、容器的继承关系、容器的分类、容器的实现、容器的应用。
6.1 容器的简介
容器类 (Collection)对于新的开发者是最强大的工具之一，可以大幅提高编程能力。容器是一个将多个元素组合到一个单元的对象，是代表一组对象的对象，容器中的对象成为它的元素。容器适用于处理各种类型的对象的聚集，例如存储、
获取、操纵聚合数据，以及聚合数据的通信。所以容器只保存 Object型的引用，这是所有类的基类，因此容器可以保存任何类型的对象。
6.1.1 容器框架
要想深入理解“容器”的概念需要我们首先理解“容器”的宏观框架 —— 容器框架。容器框架从宏观角度为我们描述了一个“容器”的世界，告诉我们在 Java的容器世界中有哪些,容器”、它们之间的关系如何、它们是什么样子、它们如何使用。总之，容器框架就是一个用于表示操作集合的统一的体系结构，容器框架包含以下元素：
接口 —— 它们代表容器类型的抽象数据类型。整个 Java容器类的基础后来是容器接口（例如 Collection,Map等接口），而不是类。
使用接口的最大好处在于将容器的实现与容器的接口分开，这就意味着你可以使用相同的方法访问容器而不用关心容器是由什么样的数据结构实现的，即接口允许操作容器和不涉及容器所代表的细节。在面向对象的语言中，这些接口一般组成一个层次结构。
实现 —— 它们是容器接口的具体实现。
算法 —— 它们是在实现集合接口对象上执行运算的方法，如搜索和排序。这些算法被称为多态的，也就是说，相同的方法可以用于处理某种接口的许多种不同的实现，算法就是可重用的功能。
6.1.2 Java容器框架的优势与劣势
Java容器框架的优势体现在以下几个方面：
1．减少编程工作量
2．提高程序的运行速度和质量
3．允许无关的 API之间的互操作
4．减少学时和使用新 API的难度
5．减少设计新 API的工作量
6．促进软件重用
6.2 容器接口的分类
正如图 6.2所示，根据容器所包含的对象的不同可以容器接口可以分为 Collection 和 Map两大类，
实现 Collection接口的容器实现是一个包含孤立元素的对象集合，而实现 Map接口的容器实现是一个包含成对元素的对象集合。
6.2.1 Collection接口定义与应用
Collection代表一组对象，这些对象称为它的元素。 Collection
是容器继承树中的顶层接口，作为接口它定义了 15个方法，但没有提供具体实现。 Collection接口如下所示：
6.2.2 Map接口定义与应用
Map是一个将键映射到值的对象，映射不能包含重复的键，即每个键最多可以映射到一个值，这种映射类似于数学中的函数。 Map接口如下所示：
6.3 集合容器 — Set
Set是不包含重复元素的 Collection,Set模拟数学上集合（ set）的概念，具有与 Collection完全一样的接口，因此没有任何额外的功能。 Set对于包含非重复，且无排序要求的数据结构非常合适。
6.3.1 Set接口定义与应用
Set接口只包含从 Collection继承的方法，并添加了禁止重复元素这一限制。 Set还在 equals和 hashcode操作上添加了更强的约束，这允许对 Set实例进行有意义的比较 —— 如果两个 Set对象包含相同元素，那么它们是相等的。 Set接口如下所示：
6.3.2 Set实现
Set实现被分为通用实现和专用实现。通用实现包括 HashSet,TreeSet和 LinkedSet,这三个实现包含在图 6.1中；专用实现包括 EnumSet和
CopyonWriteArraySet。
1,HashSet
2,TreeSet
3,LinkedHashSet
4,EnumSet
5,CopyOnWriteArraySet
6.4 列表容器 — List
List是一个有序的 Collection接口，它有时被称为序列，次序是 List最重要的特点，它确保维护元素特定的顺序。 List非常适合实现有顺序要求的数据结构，例如堆栈和队列。
6.4.1 List接口定义与应用
List为 Collection添加了许多新方法，使能够向 List中间插入与移除元素。一个 List可以生成 ListIterator，使用它可以从两个方向遍历
List，也可以从 List中间插入和删除元素。 List接口如下所示：
1 public interface List<E> extends Collection<E>{
2 E get(int index); // 取特定元素
3 E set(int index);
4 boolean add(E elements);
5 boolean add(int index,E elements);
6 E remove(int index);
7 boolean addAll(int index Collection<? extend E > c);
8 int indexOf(Object o); //查找 h
9 int LastIndexOf(Object o);
10 ListIterator<E> Listiterator(); //迭代器
11 ListIterator<E> Listiterator(int index);
12 List<E>subList(int from,int to); //范围视图
13 }
6.4.2 List实现
List实现分为通用实现和专用实现。有两个通用的 List实现 —— ArrayList和
LinkedList，这两个实现包含在图 6.1中，一个专用的 List实现是
CopyOnWriteArrayList。
1,ArrayList:ArrayList是由数组实现的 List，是最常用的 List实现。它提供常量时间的位置访问，而且速度很快，它不必为 List中的每个元素分配一个节点对象，而且在同时移动多个元素是它可以利用 System.arrayCopy，可以把
ArrayList看作没有同步开销的 Vector。但是向 List中间插入与移除元素的速度很慢,ListIterator只应该用来由后向前遍历 ArrayList，而不是用来插入和移除元素，因为那比 LinkedList开销要大很多。
ArrayList有一个调优参数 —— 初始容量，它是指在 ArrayList 被迫增长之前其可以容纳的元素数量。
2,LinkedList,如果我们采用的数据结构是经常需要将元素添加到 List开头，
或者迭代 List以便从其内部删除元素，那么 LinkedList是首要考虑的选择，因为这些操作在 LinkedList上需要常量时间，而在 ArrayList中需要线性时间。而位置操作而在 LinkedList中需要线性时间，在 ArrayList上需要常量时间。
LinkedList没有用于调优的参数，但它有 7个可选方法，分别是 Clone、
addFirst,getFirst,removeFirst,addLast,getLast和 removeLast。
3,CopyOnWriteArrayList:CopyOnWriteArrayList是通过复制数组支持的 List，
这个实现在性质上和 CopyOnWrite- ArraySet类似，不必进行同步，并且确保迭代器不抛出 ConcurrentModificationexception异常。这个实现非常适合这样的情况：遍历很频繁，而且可能很消耗时间。
6.4.3 使用 List的实现堆栈和队列
堆栈和队列是常用的两种数据结构，本节介绍如何使用 List容器实现堆栈和队列，这样读者可以通过实现过程清除地理解堆栈和队列的构成原理，更清晰地理解堆栈和队列的内部工作机制。
1．堆栈,堆栈（ stack）又名堆叠，是一种简单的数据结构，它是用后进先出的方式来描述数据 LIFO(last in first out)的存取方式。在此我们给出堆栈的定义：限定只能在固定一端进行插入和删除操作的线性表，允许进行插入和删除操作的一端称为栈顶，
另一端称为栈底。向栈中插入数据的操作称为压入 (Push)，从栈中删除数据称为弹出 (Pop)。
2．队列,队列作为另一种数据结构，有点类似堆栈，只是它是用先进先出的方式来描述数据 FIFO(first in first out)的存取方式。在此我们给出堆栈的定义：只能在表的一端进行插入操作，
在表的另一端进行删除操作的线性表。堆栈中的插入和移除数据项方法的命名是很标准，称为 push和 pop，而队列的方法至个没有标服化的命名,,插入,可以称作 put,add或 enque，而,删除,
可以叫 delete,get或 deque，在此我们使用 如下名称,insert、
remove,head和 tail。
6.5 Map容器
Map是将一个键值映射值的对象，而且键不能相同，
不能包含重复的键：每个键最多映射到一个值，
所以 Map看起来比较像由映射组成的 Set。映射模拟数学单值函数的概念，将自变量（键）映射到因变量（值）上。
6.5.1 Map实现
Map接口在 6.2.2节进行了介绍。针对 Map接口，标准的 Java
类库中提供了通用实现、专用实现。通用实现包括 HashMap、
TreeMap,LinkedHashMap，专用实现包括,EnumMap、
WeakHashMap,IdentityHashMap。它们的行为、效率、排序策略、保存对象的生命周期和判定“键”等价的策略等各不相同。其中通用实现包含在图中。
1,HashMap
2,TreeMap
3,LinkedHashMap
4,EnumMap
5,WeakHashMap
6,IdentityHashMap
6.5.2 正确认识 hashCode方法
在容器类的，尤其是 Map的应用过程中，经常会使用到 hashCode方法。它通过一定的散列算法，决定了容器中对象的存储顺序，从而可以快速地检索容器中的对象。因此在本节我们初步学习
hashCode方法。
1．散列码
2,Java中的 hashCode方法
3．重载 hashCode的常用散列算法
6.6 迭代器
迭代器（ Iterator）是一个对象，它的工作是遍历并选择序列中的对象，它提供一种方法访问一个容器（ container）对象中各个元素，而又不需暴露该对象的内部细节。此外迭代器通常被称为
“轻量级”对象：创建它的代价小。因此经常可以见到对迭代器有些限制。例如，某些迭代器只能单向移动。
6.6.1 迭代器接口
迭代器是为容器而,生,的,其实在前文的代码实例中我们已经应用到了迭代器 。 如图 1所示,Java中提供了一个基本的迭代器接口 （ Iterator） 和一个扩展的迭代器接口 （ List
Iterator）,
1 //定义接口
2 public interface Iterator {
3 boolean hasNext();
4 E next();
5 void remove();
6 }。
7 //定义一个扩展的接口
8 public interface ListIterator Extends Iterator{
9 //声明接口中的方法
10 boolean hasNext();
11 E next();
12 boolean hasPrevious();
13 Int nextIndex();
14 Int previous();
15 void remove();
16 void set(E e);
17 void add(E e);
18 }
6.6.2 迭代器的使用
对于基本的使用 Iterator其使用方法如下：
使用方法 iterator()容器返回一个 Iterator对象。第一次调用 Iterator 的 next()方法时，它返回序列的第一个元素。
用 next()获得序列中的下一个元素，并将游标（ Cursor）
向后移动。
使用 hasNext()检查序列中是否还有元素。
使用 remove()将上一次返回的元素从迭代器中移除。
ListIterator从 Iterator继承了 next,hasnext和 remove三个方法,hasPrevious和 previous模拟了 hasnext和 next，
只是方向不同。 hasnext和 next指向游标之后的元素，而
hasPrevious和 previous指向游标之前的元素。
6.7 练习
（ 1）什么是容器类，容器框架由哪几部分构成？
（ 2）容器类间具有怎样的继承关系？
（ 3）容器接口分为哪几类？
（ 4）集合容器（ Set）的有哪几种实现方式？
（ 5）列表容器（ List）的有哪几种实现方式？
（ 6） Map容器的有哪几种实现方式？
（ 7）集合容器（ Set）和列表容器（ List）的区别有那些？
（ 8）利用列表容器实现一个双向队列。
（ 9）在利用 equals() 方法比较两个对象时，比较的内容是什么？
提示：比较对象是否是同一个引用还是比较对象是否具有相同内容。
（ 10） equals() 方法和等值比较（ ==）有什么区别？
（ 11）容器类是否可以容纳任意多的元素？
（ 12）容器类中的元素是对象本身还是对象的引用？
（ 13） hashCode()方法是否是容器类所特有的方法？
（ 14） hashCode()方法返回值是什么类型的，它一般是怎样得到的？
（ 15）什么是迭代器？迭代器一般用来进行那些操作？
程序就是算法加数据结构,Java程序中的的数据结构的实现利用到了各种各样的容器类 (Java
Collection)，容器以其操作灵活性、功能强大成为是构建程序数据结构的重要选择。本章就对
Java中的形形色色的容器类进行简介，读者会通过本章对容器类形成初步的认识，将会学习到什么是容器、容器的继承关系、容器的分类、容器的实现、容器的应用。
6.1 容器的简介
容器类 (Collection)对于新的开发者是最强大的工具之一，可以大幅提高编程能力。容器是一个将多个元素组合到一个单元的对象，是代表一组对象的对象，容器中的对象成为它的元素。容器适用于处理各种类型的对象的聚集，例如存储、
获取、操纵聚合数据，以及聚合数据的通信。所以容器只保存 Object型的引用，这是所有类的基类，因此容器可以保存任何类型的对象。
6.1.1 容器框架
要想深入理解“容器”的概念需要我们首先理解“容器”的宏观框架 —— 容器框架。容器框架从宏观角度为我们描述了一个“容器”的世界，告诉我们在 Java的容器世界中有哪些,容器”、它们之间的关系如何、它们是什么样子、它们如何使用。总之，容器框架就是一个用于表示操作集合的统一的体系结构，容器框架包含以下元素：
接口 —— 它们代表容器类型的抽象数据类型。整个 Java容器类的基础后来是容器接口（例如 Collection,Map等接口），而不是类。
使用接口的最大好处在于将容器的实现与容器的接口分开，这就意味着你可以使用相同的方法访问容器而不用关心容器是由什么样的数据结构实现的，即接口允许操作容器和不涉及容器所代表的细节。在面向对象的语言中，这些接口一般组成一个层次结构。
实现 —— 它们是容器接口的具体实现。
算法 —— 它们是在实现集合接口对象上执行运算的方法，如搜索和排序。这些算法被称为多态的，也就是说，相同的方法可以用于处理某种接口的许多种不同的实现，算法就是可重用的功能。
6.1.2 Java容器框架的优势与劣势
Java容器框架的优势体现在以下几个方面：
1．减少编程工作量
2．提高程序的运行速度和质量
3．允许无关的 API之间的互操作
4．减少学时和使用新 API的难度
5．减少设计新 API的工作量
6．促进软件重用
6.2 容器接口的分类
正如图 6.2所示，根据容器所包含的对象的不同可以容器接口可以分为 Collection 和 Map两大类，
实现 Collection接口的容器实现是一个包含孤立元素的对象集合，而实现 Map接口的容器实现是一个包含成对元素的对象集合。
6.2.1 Collection接口定义与应用
Collection代表一组对象，这些对象称为它的元素。 Collection
是容器继承树中的顶层接口，作为接口它定义了 15个方法，但没有提供具体实现。 Collection接口如下所示：
6.2.2 Map接口定义与应用
Map是一个将键映射到值的对象，映射不能包含重复的键，即每个键最多可以映射到一个值，这种映射类似于数学中的函数。 Map接口如下所示：
6.3 集合容器 — Set
Set是不包含重复元素的 Collection,Set模拟数学上集合（ set）的概念，具有与 Collection完全一样的接口，因此没有任何额外的功能。 Set对于包含非重复，且无排序要求的数据结构非常合适。
6.3.1 Set接口定义与应用
Set接口只包含从 Collection继承的方法，并添加了禁止重复元素这一限制。 Set还在 equals和 hashcode操作上添加了更强的约束，这允许对 Set实例进行有意义的比较 —— 如果两个 Set对象包含相同元素，那么它们是相等的。 Set接口如下所示：
6.3.2 Set实现
Set实现被分为通用实现和专用实现。通用实现包括 HashSet,TreeSet和 LinkedSet,这三个实现包含在图 6.1中；专用实现包括 EnumSet和
CopyonWriteArraySet。
1,HashSet
2,TreeSet
3,LinkedHashSet
4,EnumSet
5,CopyOnWriteArraySet
6.4 列表容器 — List
List是一个有序的 Collection接口，它有时被称为序列，次序是 List最重要的特点，它确保维护元素特定的顺序。 List非常适合实现有顺序要求的数据结构，例如堆栈和队列。
6.4.1 List接口定义与应用
List为 Collection添加了许多新方法，使能够向 List中间插入与移除元素。一个 List可以生成 ListIterator，使用它可以从两个方向遍历
List，也可以从 List中间插入和删除元素。 List接口如下所示：
1 public interface List<E> extends Collection<E>{
2 E get(int index); // 取特定元素
3 E set(int index);
4 boolean add(E elements);
5 boolean add(int index,E elements);
6 E remove(int index);
7 boolean addAll(int index Collection<? extend E > c);
8 int indexOf(Object o); //查找 h
9 int LastIndexOf(Object o);
10 ListIterator<E> Listiterator(); //迭代器
11 ListIterator<E> Listiterator(int index);
12 List<E>subList(int from,int to); //范围视图
13 }
6.4.2 List实现
List实现分为通用实现和专用实现。有两个通用的 List实现 —— ArrayList和
LinkedList，这两个实现包含在图 6.1中，一个专用的 List实现是
CopyOnWriteArrayList。
1,ArrayList:ArrayList是由数组实现的 List，是最常用的 List实现。它提供常量时间的位置访问，而且速度很快，它不必为 List中的每个元素分配一个节点对象，而且在同时移动多个元素是它可以利用 System.arrayCopy，可以把
ArrayList看作没有同步开销的 Vector。但是向 List中间插入与移除元素的速度很慢,ListIterator只应该用来由后向前遍历 ArrayList，而不是用来插入和移除元素，因为那比 LinkedList开销要大很多。
ArrayList有一个调优参数 —— 初始容量，它是指在 ArrayList 被迫增长之前其可以容纳的元素数量。
2,LinkedList,如果我们采用的数据结构是经常需要将元素添加到 List开头，
或者迭代 List以便从其内部删除元素，那么 LinkedList是首要考虑的选择，因为这些操作在 LinkedList上需要常量时间，而在 ArrayList中需要线性时间。而位置操作而在 LinkedList中需要线性时间，在 ArrayList上需要常量时间。
LinkedList没有用于调优的参数，但它有 7个可选方法，分别是 Clone、
addFirst,getFirst,removeFirst,addLast,getLast和 removeLast。
3,CopyOnWriteArrayList:CopyOnWriteArrayList是通过复制数组支持的 List，
这个实现在性质上和 CopyOnWrite- ArraySet类似，不必进行同步，并且确保迭代器不抛出 ConcurrentModificationexception异常。这个实现非常适合这样的情况：遍历很频繁，而且可能很消耗时间。
6.4.3 使用 List的实现堆栈和队列
堆栈和队列是常用的两种数据结构，本节介绍如何使用 List容器实现堆栈和队列，这样读者可以通过实现过程清除地理解堆栈和队列的构成原理，更清晰地理解堆栈和队列的内部工作机制。
1．堆栈,堆栈（ stack）又名堆叠，是一种简单的数据结构，它是用后进先出的方式来描述数据 LIFO(last in first out)的存取方式。在此我们给出堆栈的定义：限定只能在固定一端进行插入和删除操作的线性表，允许进行插入和删除操作的一端称为栈顶，
另一端称为栈底。向栈中插入数据的操作称为压入 (Push)，从栈中删除数据称为弹出 (Pop)。
2．队列,队列作为另一种数据结构，有点类似堆栈，只是它是用先进先出的方式来描述数据 FIFO(first in first out)的存取方式。在此我们给出堆栈的定义：只能在表的一端进行插入操作，
在表的另一端进行删除操作的线性表。堆栈中的插入和移除数据项方法的命名是很标准，称为 push和 pop，而队列的方法至个没有标服化的命名,,插入,可以称作 put,add或 enque，而,删除,
可以叫 delete,get或 deque，在此我们使用 如下名称,insert、
remove,head和 tail。
6.5 Map容器
Map是将一个键值映射值的对象，而且键不能相同，
不能包含重复的键：每个键最多映射到一个值，
所以 Map看起来比较像由映射组成的 Set。映射模拟数学单值函数的概念，将自变量（键）映射到因变量（值）上。
6.5.1 Map实现
Map接口在 6.2.2节进行了介绍。针对 Map接口，标准的 Java
类库中提供了通用实现、专用实现。通用实现包括 HashMap、
TreeMap,LinkedHashMap，专用实现包括,EnumMap、
WeakHashMap,IdentityHashMap。它们的行为、效率、排序策略、保存对象的生命周期和判定“键”等价的策略等各不相同。其中通用实现包含在图中。
1,HashMap
2,TreeMap
3,LinkedHashMap
4,EnumMap
5,WeakHashMap
6,IdentityHashMap
6.5.2 正确认识 hashCode方法
在容器类的，尤其是 Map的应用过程中，经常会使用到 hashCode方法。它通过一定的散列算法，决定了容器中对象的存储顺序，从而可以快速地检索容器中的对象。因此在本节我们初步学习
hashCode方法。
1．散列码
2,Java中的 hashCode方法
3．重载 hashCode的常用散列算法
6.6 迭代器
迭代器（ Iterator）是一个对象，它的工作是遍历并选择序列中的对象，它提供一种方法访问一个容器（ container）对象中各个元素，而又不需暴露该对象的内部细节。此外迭代器通常被称为
“轻量级”对象：创建它的代价小。因此经常可以见到对迭代器有些限制。例如，某些迭代器只能单向移动。
6.6.1 迭代器接口
迭代器是为容器而,生,的,其实在前文的代码实例中我们已经应用到了迭代器 。 如图 1所示,Java中提供了一个基本的迭代器接口 （ Iterator） 和一个扩展的迭代器接口 （ List
Iterator）,
1 //定义接口
2 public interface Iterator {
3 boolean hasNext();
4 E next();
5 void remove();
6 }。
7 //定义一个扩展的接口
8 public interface ListIterator Extends Iterator{
9 //声明接口中的方法
10 boolean hasNext();
11 E next();
12 boolean hasPrevious();
13 Int nextIndex();
14 Int previous();
15 void remove();
16 void set(E e);
17 void add(E e);
18 }
6.6.2 迭代器的使用
对于基本的使用 Iterator其使用方法如下：
使用方法 iterator()容器返回一个 Iterator对象。第一次调用 Iterator 的 next()方法时，它返回序列的第一个元素。
用 next()获得序列中的下一个元素，并将游标（ Cursor）
向后移动。
使用 hasNext()检查序列中是否还有元素。
使用 remove()将上一次返回的元素从迭代器中移除。
ListIterator从 Iterator继承了 next,hasnext和 remove三个方法,hasPrevious和 previous模拟了 hasnext和 next，
只是方向不同。 hasnext和 next指向游标之后的元素，而
hasPrevious和 previous指向游标之前的元素。
6.7 练习
（ 1）什么是容器类，容器框架由哪几部分构成？
（ 2）容器类间具有怎样的继承关系？
（ 3）容器接口分为哪几类？
（ 4）集合容器（ Set）的有哪几种实现方式？
（ 5）列表容器（ List）的有哪几种实现方式？
（ 6） Map容器的有哪几种实现方式？
（ 7）集合容器（ Set）和列表容器（ List）的区别有那些？
（ 8）利用列表容器实现一个双向队列。
（ 9）在利用 equals() 方法比较两个对象时，比较的内容是什么？
提示：比较对象是否是同一个引用还是比较对象是否具有相同内容。
（ 10） equals() 方法和等值比较（ ==）有什么区别？
（ 11）容器类是否可以容纳任意多的元素？
（ 12）容器类中的元素是对象本身还是对象的引用？
（ 13） hashCode()方法是否是容器类所特有的方法？
（ 14） hashCode()方法返回值是什么类型的，它一般是怎样得到的？
（ 15）什么是迭代器？迭代器一般用来进行那些操作？
