常用的List,Set,Map容器以及比较器

一、简述：

List,Set接口属于集合类容器，Collection接口是它们所有的父接口；
与List,Set接口不同，Map接口是所有Map类容器的父接口，通过键值对（key-value）的映射关系，用键（key）来找值（value）

二、一些常用接口特点：

• Collection接口下：

• List接口：有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。
  • **ArrayList:List **接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。 除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。
    每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。
  • **LinkedList:List **接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
• Set接口：一个不包含重复元素的 collection。更正式地说，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。
  • HashSet:此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。需要重写hashcode()方法和equals()方法。
  • TreeSet:使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator （临时性的）或使元素实现comparable接口进行排序。

• Map接口下：

• HashMap:基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序。

三、常用接口的功能：

• List的功能：List的基本用法相当简单。虽然绝大多数时候，你只是用add()加对象，用get()取对象，用iterator()获取这个序列的Iterator，但List还有一些别的很有用的方法。
  List的最重要的特征就是有序；它会确保以一定的顺序保存元素。List在Collection的基础上添加了大量方法，并使之能在序列中间插入和删除元素（只对LinkedList推荐使用）。
  List可以制造ListIterator对象，你除了能用它在List的中间插入和删除元素之外，还能用它沿两个方法遍历List。

• ArrayList：一个用数组实现的List。能进行快速的随机访问，但是往列表中间插入和删除元素的时候比较慢。ListIterator只能用在反向遍历ArrayList的场合，不要用它来插入和删除元素，因为相比LinkedList，在ArrayList里面用ListIterator的系统开销比较高。
• LinkedList：对顺序访问进行了优化。在List中间插入和删除元素的代价也不高。随机访问的速度相对较慢（这点用ArrayList吧）。此外它还有addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()等方法，你能把它当成栈（stack），队列（queue）或双向队列（deque）来实现后进先出，先进先出。

• Set的功能：加入Set的每个元素必须是唯一的；否则，Set是不会把它加进去的。要想加进Set，Object必须定义equals()，这样才能标明对象的唯一性。
  Set的接口和Collection的一摸一样，Set的接口不保证它会用哪种顺序来存储元素（乱序）。

• HashSet：为优化查询速度而设计的Set。要放进HashSet里面的Object还得定义hashCode()。
• TreeSet：是一个有序的Set，其底层是一颗树。这样你就能从Set里面提取一个有序序列了。
  但是这里的顺序不一定是你想要的顺序。因此，在写自己的类的时候，一定要记住，Set要有一个判断以什么顺序来存储元素的标准，也就是说对象必须实现Comparable接口，并且定义compareTo()方法。
  亦或当你需要一个特定顺序的时候，实现Comparator方法也可以，相对来说，这种方法就比较临时性。

• Map（HashMap）的功能：维持键--值的关系（既pairs），这样就能用键来找值了。提供恒定的插入与查询，put（key，value），get（key）。·

• 用法：

• 在各种Lists中，最好的做法是以ArrayList作为有限选择。当插入、删除频繁时，使用LinkedList()。
• 在各种Sets中，HashSet通常优于TreeSet（插入、查找）。只有当需要产生一个经过排序的序列，才用TreeSet。 TreeSet存在的唯一理由：能够维护其内元素的排序状态。
• 在各种Maps中:HashMap用于快速查找。
• 当元素个数固定，用Array，因为Array效率是最高的。

这些即是最常用的容器。

Comparable和Comparator的区别：

Comparable & Comparator 都是用来实现集合中元素的比较、排序的，只是 Comparable 是在对象内部定义的方法实现的排序，Comparator 是在对象外部实现的排序，所以，如想实现排序，就需要在对象外定义 Comparator 接口的方法或在对象内实现 Comparable 接口的方法。

Collections的sort()方法有两个重载有参方法：

Collections.sort((List<T> list)
Collections.sort((List<T> list, Comparator<? super T> c)```
- #####Comparable：提前做好准备
Comparable 是一个对象本身就已经支持自比较所需要实现的接口
自定义的类要在加入list容器中后能够排序，可以实现Comparable接口，再用```Collections.sort((List<T> list)```方法，此时的顺序就是Comparable接口设定的排序方式。

import java.util.Arrays;
public class User implements Comparable {
private String id;
private int age;
public User(String id, int age) {
this.id = id;
this.age = age;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
//实现Comparable接口需要实现此方法，此例类中比较年龄
public int compareTo(Object o) {
return this.age - ((User) o).getAge();
}
}

List<User> userList=new ArrayList<>();
userList.add(user1);
userList.add(user2);
userList.add(user3);
......
Collection.sort(userList);

- ####Comparator：临时性
 Comparator 是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较。
可以说Comparable是对象自已完成比较，Comparator是外部程序实现比较的而已。

import java.util.Arrays;
import java.util.Comparator;
public class UserComparator implements Comparator {
public int compare(Object o1, Object o2) {
return ((User) o1).getAge() - ((User) o2).getAge();
}
}

当User类没有实现Comparable时

List<User> userList=new ArrayList<>();
userList.add(user1);
userList.add(user2);
userList.add(user3);
......
Collection.sort(userList，new UserComparator());