3.1 Collections框架

容器在Java语言开发中有着非常重要的作用，Java提供了多种类型的容器来满足开发的需要，容器不仅在面试笔试中也是非常重要的一个知识点，在实际开发的过程中也是经常会用到。因此，对容器的掌握是非常有必要也是非常重要的。Java中的容器可以被分为两类：

（1）Collection

Collection用来存储独立的元素，其中包括List、Set和Queue。其中List是按照插入的顺序保存元素，Set中不能有重复的元素，而Queue按照排队规则来处理容器中的元素。它们之间的关系如图3-1所示。

图3-1 Collection类图

（2）Map

Map用来存储<键，值>对，这个容器允许通过键来查找值。Map也有多种实现类，如图3-2所示。

Java Collections框架中包含了大量集合接口以及这些接口的实现类和操作它们的算法（例如排序、查找、反转、替换、复制、取最小元素、取最大元素等），具体而言，主要提供了List（列表）、Queue（队列）、Set（集合）、Stack（栈）和Map（映射表，用于存放键值对）等数据结构。其中List、Queue、Set、Stack都继承自Collection接口。

图3-2 Map类图

Collection是整个集合框架的基础，它里面存储一组对象，表示不同类型的Collections，它的作用只是提供维护一组对象的基本接口而已。

下面分别介绍List，Set和Map三个接口。

1）Set表示数学意义上的集合概念，最主要的特点是集合中的元素不能重复，因此存入Set的每个元素都必须定义equals()方法来确保对象的唯一性。该结构有两个比较常用的实现类：HashSet和TreeSet。其中TreeSet实现了SortedSet接口，因此TreeSet容器中的元素是有序的。

2）List又称为有序的Collection，它按对象进入的顺序保存对象，所以它能对列表中的每个元素的插入和删除位置进行精确控制。同时，它可以保存重复的对象。LinkedList、ArrayList和Vector都实现了List接口。

3）Map提供了一个从键映射到值的数据结构。它用于保存键值对，其中值可以重复，但键是唯一的，不能重复。Java类库中有多个实现该接口的类：HashMap、TreeMap、LinkedHashMap、WeakHashMap和IdentityHashMap。虽然它们都实现了相同的接口，但执行效率却不是完全相同的。具体而言，HashMap是基于哈希表实现的，采用对象的hashCode可以进行快速查询。LinkedHashMap采用列表来维护内部的顺序。TreeMap基于红黑树的数据结构来实现，内部元素是按需排列的。