Java-集合类
1 Set
Set接口代表无序不可重复集合。Set集合通常记不住元素的添加顺序，并且Set集合不允许包含相同的元素，向Set中加入相同元素时会失败，即方法返回false。Set接口常用的实现类有：HashSet、TreeSet。
HashSet是Set接口的典型实现，它具有以下特点：
- HashSet不能保证元素的排列顺序；
- HashSet集合元素的值可以是 null；
- HashSet是非线程安全的，多线程环境下须通过代码来保证其同步。
TreeSet可以保证元素的排列顺序，它比HashSet多了一些方法：
- 返回集合中第一个/最后一个元素；
- 返回集合中位于指定元素之前/之后的元素；
- 返回集合中某个限定范围内的元素组成的子集。
TreeSet采用红黑树的数据结构来存储元素，它支持两种排序方式：自然排序、定制排序。
- 自然排序：
- 添加时，调用元素的compareTo方法比较元素的大小，并按照升序排列元素；
- 添加到TreeSet中的对象必须实现Comparable接口，该接口定义了compareTo方法；
- Java提供的很多类型均已经实现了Comparable接口，如包装类、String、Date等。
- 定制排序：
- 创建TreeSet时，传入Comparator接口的实例；
- Comparator接口定义了compare方法，用于比较两个对象的大小；
- TreeSet不再调用compareTo方法，转而调用compare方法比较大小。
2 List
List接口代表有序集合，它提供了根据索引来访问集合的方法：
- 将元素插入到集合中指定的索引处；
- 将指定索引处的元素从集合中删除；
- 从集合中返回指定索引处的元素；
- 返回某个元素在集合中的索引值；
- 从集合中，返回起始索引和结束索引之间的元素所组成的子集。
List还提供了一个listIterator方法，以返回一个ListIterator对象。ListIterator是一个接口，它继承于Iterator接口，并增加了如下的方法：
boolean hasPrevious(); // 判断迭代器指向的元素是否有上一个元素E previous(); // 返回该迭代器所指向的元素的上一个元素boolean hasNext(); // 判断迭代器指向的元素是否有下一个元素E next(); // 返回该迭代器所指向的元素的下一个元素void add(E e); // 在迭代器所指向的元素位置插入一个元素
List接口常用实现类有ArrayList、LinkedList，ArrayList是采用数组实现有序集合，LinkedList是采用链表实现的有序集合。数组和链表的区别在于：
- 数组需要占据连续的内存空间，访问效率高、增删效率低；
- 链表不必占据连续的内存空间，增删效率高、访问效率低，它以指针维护元素的顺序，即上一个元素会指向下一个元素。
3 Queue
Queue接口用于模拟队列，它是一种先进先出（FIFO）的容器，常用的方法见下方表格：
Queue接口包含如下子接口和实现类：
- PriorityQueue是一种不标准的队列实现，它不是按照加入的顺序来保存元素，而是按照元素的大小排序来保存元素；
- Deque接口代表双端队列，它允许你从队列头/尾的任何一端，来进行入队/出队操作，甚至还支持入栈/出栈的操作；
- ArrayDeque、LinkedList是Deque接口的实现类，前者采用数组实现双端队列，而后者采用链表结构实现双端队列。
4 Map
Map接口用于保存具有映射关系的数据（key-value），key和value之间存在单向一对一关系，通过指定的key，总能找到确定的value。Map的key不允许重复，同一个Map的任何两个key通过equals比较总返回false。
如下图，Map接口具有如下实现类，其中较为常用的是HashMap和TreeMap。
HashMap
HashMap是Map接口的典型实现：
- HashMap是非线程安全的，其性能高于Hashtable；
- HashMap允许使用null作为key/value，而Hashtable不允许存入null。
TreeMap
TreeMap是一个红黑树的数据结构，在存储键值对时，它按照key对键值对排序。
- 自然排序：对key进行比较，并根据key按照由小到大的顺序排列键值对。所有的key应该是同一个类型，且必须实现Comparable接口。
- 定制排序：创建TreeMap时，传入一个Comparator类型的对象，该对象负责对所有的key进行比较，此时不要求key实现Comparable接口。
5 Collections
Collections是一个操作集合的工具类，它提供了4类集合操作：
- 强大的排序功能：针对List集合提供了众多排序方法；
- 查找与替换功能：针对Collection提供了众多查找和替换元素的方法；
- 创建不可变集合：提供3类方法（空的/唯一/只读）来创建一个不可变的集合；
- 线程同步的集合：将指定的集合包装成线程同步的集合，以解决线程安全问题。
