一.Java的集合
Java集合类是一种特别有用的工具类，可用于存储数量不等的对象，并可以实现常用的数据结构，如
栈、队列等。除此之外，Java集合还可用于保存具有映射关系的关联数组。Java集合大致可分为List、
Set、Queue和Map四种体系，其中List代表有序、重复的集合；Set代表无序、不可重复的集合；而
Map则代表具有映射关系的集合，Java5又增加了Queue体系集合，代表一种队列集合实现。
1.1.Java集合概述
为了保存数量不确定的数据，以及保存具有映射关系的数据（也被称为关联数组），Java提供了集合
类。集合类主要负责保存、盛装其他数据，因此集合类也被称为容器类，所有的集合类都位于 java.util
包下。集合类和数组不一样，数组元素既可以是基本类型的值，也可以是对象（实际上保存的是对象的引用变
量）；而集合里只能保存对象（实际上只是保存对象的引用变量，但通常习惯上认为集合里保存的是对
象）。
Java的集合类主要由两个接口派生而出： Collection和Map， Collection和Map是Java集合框架的根接
口，这两个接口又包含了一些子接口或实现类。如下所示是 Java集合简单结构图
1.2. List集合
List集合代表一个元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。Lst集合允许使用
重复元素，可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引，
例如第一次添加的元素索引为0，第二次添加的元素索引为1…
1、Vector是线程安全的，ArrayList不是线程安全的。
2、ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。
PS:Vector是历史遗留问题，现在已经基本不用
List常用方法
1.3. Comparable和Comparator
一、Comparable简介
Comparable是排序接口。若一个类实现了Comparable接口，就意味着该类支持排序。实现了
Comparable接口的类的对象的列表或数组可以通过Collections.sort或Arrays.sort进行自动排序。
此外，实现此接口的对象可以用作有序映射中的键或有序集合中的集合，无需指定比较器。
此接口只有一个方法compare，比较此对象与指定对象的顺序，如果该对象小于、等于或大于指定
对象，则分别返回负整数、零或正整数。
二、Comparator简介
Comparator是比较接口，我们如果需要控制某个类的次序，而该类本身不支持排序(即没有实现
Comparable接口)，那么我们就可以建立一个“该类的比较器”来进行排序，这个“比较器”只需要实现
Comparator接口即可。也就是说，我们可以通过实现Comparator来新建一个比较器，然后通过这个比
较器对类进行排序。
注意：
若一个类要实现Comparator接口：它一定要实现compare(T o1, T o2) 函数，但可以不实现
equals(Object obj) 函数。
int compare(T o1, T o2) 是“比较o1和o2的大小”。返回“负数”，意味着“o1比o2小”；返回“零”，意
味着“o1等于o2”；返回“正数”，意味着“o1大于o2”。
三、Comparable和Comparator区别比较
Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。
Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
用Comparable简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需
要修改源代码。 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定
义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面
用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重
复劳动了。
1.4. Set集合
Set集合类似于一个罐子，程序可以依次把多个对象“丢进”Set集合，而Set集合通常不能记住元素的
添加顺序。
Set集合不允许包含相同的元素，如果试图把两个相同的元素加入同一个Set集合中，则添加操作失
败，add()方法返回 false，且新元素不会被加入。
Set常用方法
一、HashSet类
HashSet类是Set接口的典型实现类，大多数时候使用Set集合时就是使用这个实现类。 HashSet类
按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。
HashSet类具有以下特点：
不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化。
HashSet不是同步的（不是线程安全的），如果多个线程同时访问一个 HashSet，假设有两个或者
两个以上线程同时修改了 HashSet集合时，则必须通过代码来保证其同步。
集合元素值可以是null，但只能放入一个null。
当向 HashSet集合中存入一个元素时， HashSet会调用该对象的 hashCode()方法来得到该对象的
hashCode值，然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过
equals方法比较返回true，但它们的hashCode()方法返回值不相等， HashSet将会把它们存储在
不同的位置，依然可以添加成功。
HashSet判断元素是否相等的依据：hashCode()相同，equals()方法相同；
- LinkedHashSet类
HashSet类还有一个子类 LinkedHashSet， LinkedHashSet集合也是根据元素的 hashCode值来决
定元素的存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的。
也就是说，当遍历 LinkedhashSet集合里的元素时， LinkedHashSet将会按元素的添加顺序来访问集合
里的元素。
LinkedHashSet需要维护元素的插入顺序，因此性能略低于 HashSet的性能，但在迭代访问Set里的
全部元素时将有很好的性能，因为它以链表来维护内部顺序。
三、TreeSet类
TreeSet是 SortedSet接口的实现类，正如 SortedSet名字所暗示的， TreeSet可以确保集合元素处
于排序状态。与 Set集合相比，TreeSet还提供了如下几个额外的方法。
由于TreeSet是有序的，也支持Comparable和Comparator两种排序方式
四、各Set实现类的选择
HashSet和TreeSet是Set的两个典型实现，如何选择HashSet和TreeSet？
HashSet的性能总是比TreeSet好（特别是最常用的添加、查询元素等操作），因为TreeSet需要额
外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时，才应该使用TreeSet，否则
一般都应该使用HashSet。
HashSet还有一个子类：LinkedHashSet，对于普通的插入、删除操作，LinkedHashSet比HashSet
要略微慢一点，这是由维护链表所带来的额外开销造成的，但由于有了链表，遍历LinkedHashSet会更
快。Set的实现类HashSet、TreeSet都是线程不安全的。如果有多个线程同时访问一个Set集合，并且有
超过一个线程修改了该Set集合，则必须手动保证该Set集合的同步性。通常可以通过Collections工具类
的synchronizedSortedSet方法来“包装”该Set集合。