1 简介

集合框架图

集合框架要满足的目标
- 该框架必须是高性能的。基本集合（动态数组，链表，树，哈希表）的实现也必须是高效的。
- 该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性

为此，整个集合框架就围绕一组标准接口而设计

集合框架的设计思想
- 集合类库将接口与实现分离
- 通常使用接口类型存放集合引用，这样做就可以轻松地改变集合的实现（不同的集合实现具有不同的特点），因为我们只需要改变调用集合构造器一个地方
- 集合框架中会有一组抽象类，这些类是为类库实现者设计的，如果我们要实现自己的集合类，会发现扩展这些抽象类比实现接口中的所有方法要轻松很多
集合框架的特点
- Java集合框架位于java.util包下
- 集合框架包括两种基本接口：**Collection**、**Map**

Collection用于存储一种类型的元素集合；Map用于存储键/值对映射

集合框架中的所有接口都是泛型接口，因此集合可以容纳任何引用类型

2 Collection接口

1 概述

Collection接口的特点
- Collection是最基本的集合接口，一个Collection代表一组同一类型的Object
- Collection接口存储一组不唯一、无序的对象

Collection接口中定义的方法

public interface Collection<E> extends Iterable<E> {
  // 返回集合中存储的元素个数
  int size();
  // 将一个元素e/集合c中的全部元素添加到集合中，如果添加了元素则返回true
  boolean add(E e);
  boolean addAll(Collection<? extends E> c);
  // 将集合中元素等于o的元素/在c中存在的元素删除，如果删除了元素则返回true
  boolean remove(Object o);
  boolean removeAll(Collection<?> c);
  // 如果集合中包含与o相等的元素/包含c中的所有元素，则返回true
  boolean contains(Object o);
  boolean containsAll(Collection<?> c);
  // 返回集合的数组形式
  // 可以向该方法中传入一个数组实例a
  // 如果a的容量够大，则将集合中的所有元素填入a中，否则填入一个与a元素类型相同的新数组
  Object[] toArray();
  <T> T[] toArray(T[] a);
  // 删除集合中与c中元素不同的元素，如果删除了元素则返回true
  boolean retainAll(Collection<?> c);
  // 如果集合中没有元素则返回true
  boolean isEmpty();
  // 返回一个用于访问集合中各个元素的迭代器
  Iterator<E> iterator();
  // 删除集合中的所有元素
  void clear();
  // 实现集合与集合之间的值比较
  boolean equals(Object o);
  int hashCode();
}

Collection接口声明了很多方法，所有的实现类都必须提供这些方法
为了让实现类更容易地实现这些接口，集合框架提供了一个AbstractCollection类，其实现了一些例行方法，这样一来具体类可以扩展AbstractCollection类

2 List接口

List接口概述
- List接口相比于Collection的特点是有序、不唯一，因此List支持随机访问

随机访问即支持通过索引的方式精准的访问List中的元素

List和数组的特性很类似，不同的是List支持动态增长，可以根据实际存储元素的数量自动增加容量

RandomAccess接口
- 虽然List接口支持随机访问，但是我们可以发现List实现类的底层有数组和链表
- 数组可以很好地支持随机访问，而链表虽然是有序的，但是随机访问很慢，最好使用迭代器遍历
- 为了尽量避免对链表执行随机访问操作，JDK1.4引入了一个标记接口RandomAccess，该接口不包含任何方法，不过其标记了一个特定的集合是否支持高效的随机访问

List接口提供的方法（相比于Collection接口新增的部分方法）

public interface List<E> extends Collection<E> {
  @SuppressWarnings({"unchecked", "rawtypes"})
  default void sort(Comparator<? super E> c) {...}
  // 对指定索引位置进行增删改查
  E get(int index);
  E set(int index, E element);
  void add(int index, E element);
  E remove(int index);
  // ListIterator是Iterator的子接口，其可以实现前后两个方向的遍历
  ListIterator<E> listIterator();
  int indexOf(Object o);
  int lastIndexOf(Object o);
  List<E> subList(int fromIndex, int toIndex);
}

由于List有序性的特点，因此其定义了很多与索引有关的方法

List接口的实现类包括

ArrayList、LinkedList、Vector等

1 ArrayList、Vector和Stack

ArrayList和Vector的共同特点
- ArrayList和Vector的底层数据结构都是Object[]数组，因此可以很好地支持快速随机访问（被RandomAccess接口标识）
- ArrayList和Vector都支持动态再分配数组，即可以根据需要自动扩充数组的容量，这也是ArrayList和Vector与普通数组相比最大的区别
- 常常将ArrayList称为动态数组
ArrayList和Vector的不同点
- Vector的所有方法都是同步方法，因此Vector是线程安全的，而ArrayList并不是线程安全的

建议在不需要同步的时候使用ArrayList，在需要同步的时候使用Vector

ArrayList类默认初始容量为10，当数组大小不足时增长率为当前长度的50%

Vector类允许设置容量增长长度，默认增长方式是当前长度的2倍

Stack的特点
- Stack是Vector的子类，同样是线程安全的
- Stack与Vector相比，Stack新增了几个与栈操作相关的方法，便于进行栈操作，如push()、pop()、peek()。

2 LinkedList

LinkedList特点
- LinkedList的底层数据结构是双向链表，这也决定了它的特点，即支持快速地在链表中间位置插入和删除元素、不支持快速随机访问
- 当需要按整数索引访问元素时，通常不选用LinkedList作为List的实现类

当然如果需要对集合的元素频繁地进行增减操作，则应该选用LinkedList

LinkedList与索引相关的操作
- 虽然List接口提供了很多与整数索引相关的方法（如get(int index)），但是这些方法的快速执行依赖于快速随机访问

对于LinkedList来说调用这些方法的效率非常低，因为每次查找一个元素都要从链表的头部重新开始搜索，LinkedList并没有缓存位置信息

由于迭代器描述了集合中的位置，因此对于LinkedList来说依赖于位置的操作应该由迭代器负责，应该避免使用与整数索引相关的方法
对LinkedList头尾元素进行操作时并不需要依赖迭代器，这是显而易见的

3 Queue接口

Queue接口概述
- Queue接口与List、Set同一级别，都直接继承于Collection接口
- Queue接口定义了单向队列的相关方法
Deque接口概述
- Deque接口是Queue接口的子接口，前者是双向队列，后者为单向队列
- 由于Deque是双向队列，因此其可以很好地支持队列和栈的操作特性，其也提供了与队列操作和栈操作有关的方法
Deque接口中定义的方法 ```java public interface Deque extends Queue { // 在队列头部/尾部添加元素 // 如果使用容量受限的队列，当容量满时将抛出异常 void addFirst(E e); void addLast(E e); // 删除并返回队列头部/尾部元素，队列为空时将抛出异常 E removeFirst(); E removeLast(); // 返回队列头部/尾部元素，队列为空时将抛出异常 E getFirst(); E getLast();

// 在队列头部/尾部添加元素 // 如果使用容量受限的队列，当容量满时将返回false boolean offerFirst(E e); boolean offerLast(E e); // 删除并返回队列头部/尾部元素，队列为空时将返回null E pollFirst(); E pollLast(); // 返回队列头部/尾部元素，队列为空时将抛返回null E peekFirst(); E peekLast();

/* 队列相关方法 */
// 在队列尾部添加元素，在队列头部删除并返回元素、返回元素
// 当队列容量为空、满时将抛出异常
boolean add(E e);
E remove();
E element();
// 在队列尾部添加元素，在队列头部删除并返回元素、返回元素
// 当队列容量为空、满时将返回false、null
boolean offer(E e);
E poll();
 E peek();
// 将c中所有元素添加到队列中，当队列满时将抛出异常
boolean addAll(Collection<? extends E> c);
/* 栈相关方法 */
// 向栈顶部（队列头部）添加元素，该方法与addFirst()相同
void push(E e);
// 从栈顶部（队列头部）删除并返回元素、返回元素，该方法与removeFirst()相同
E pop();
E peek();

}


<a name="hSDE7"></a>
### 1 LinkedList和ArrayDeque
- **LinkedList**
   - 由于LinkedList支持快速地增删集合中的元素，且队列和栈仅对集合两端进行操作，因此**LinkedList底层数据结构双向链表天然地支持高效地队列操作和栈操作**，因此LinkedList既实现了List接口，还实现了Deque接口
   - **Deque接口窄化了对LinkedList的方法的访问权限（即如果LindList对象的引用类型是Deque时，就完全只能访问Deque接口所定义的方法，而不能直接访问LinkedList的非Deque的方法），以使得只有恰当的方法才可以使用**
<br />
- **ArrayDeque**
   - ArrayDeque是Deque接口的另一个实现类，其底层数据结构是**对象数组**
<a name="ZTjff"></a>
### 2 PriorityQueue
- **PriorityQueue特点**
   - PriorityQueue称为优先队列，其底层数据结构是**堆**且**默认是小根堆**
   - **堆是一颗完全二叉树**，每次插入和删除操作都可以保证根节点是最大值（大根堆）或最小值（小根堆）
   - PriorityQueue与TreeSet的不同之处在于元素次序的不同
PriorityQueue只保证每次插入和删除节点操作后，根节点的值为最大值或最小值，但是迭代时并不是按照有序顺序来访问元素的<br />TreeSet在迭代时可以保证有序访问元素
- **PriorityQueue的使用**
   - 优先队列的使用和队列的使用方法一致
   - 插入操作使用`add()`或`offer()`方法
   - 删除操作使用`remove()`或`poll()`方法
   - 只返回值不删除使用`peek()`方法
<a name="YhxZW"></a>
## 4 Set接口
![image.png](https://cdn.nlark.com/yuque/0/2021/png/1169704/1633324642086-1a4beb0a-0b5b-4296-b62b-62040dc67ad3.png#clientId=u573a997b-c985-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=ubf965380&name=image.png&originHeight=292&originWidth=371&originalType=binary&ratio=1&rotation=0&showTitle=false&size=14004&status=done&style=none&taskId=uebd9d1c4-7180-4a34-88a8-d93fe7781b2&title=)
- **Set接口概述**
   - Set接口相比于Collection接口的特点是**唯一、无序**，因此Set支持**快速查找元素**
   - **Set具有与Collection完全相同的方法**，但是其方法的行为有更严谨的定义，比如add()方法不允许增加重复的元素、只要两个set包含相同的元素equals()就返回true，而不要求这些元素有同样的顺序
- **Set接口的实现类包括**
HashSet、TreeSet等
<a name="EBthJ"></a>
### 1 HashSet
- **HashSet特点**
   - HashSet是**底层数据结构为hash表**的Set接口实现类
   - hash表的特点就是HashSet的特点，即**支持快速查找元素但是无法控制元素出现的次序**
      - HashSet的`add(E e)`方法就对应向hash表中插入元素的操作
      - HashSet的`contains(Object o)`方法就对应从hash表中查找元素的操作
- **遍历HashSet**
   - 使用迭代器遍历HashSet时，将依次访问HashSet的所有桶
   - 由于元素分散在散列表中，所以会以一种**看起来随机的顺序访问元素**
<a name="XZD24"></a>
#### hash表
- **hash表的原理**
   - hash表时一种用于快速查找对象的数据结构
**组成**
   - hash表由**链表数组**实现，每个**链表被称为桶**
**查找元素**<br />要想查找hash表中是否存在某个对象，需要以下两个步骤
   1. 先计算对象的**哈希码**，然后**与桶的总数取余**，**所得到的结果就是保存这个元素的桶的索引**
   1. **遍历桶中的对象**，看桶中的对象与要查找的对象是否相等
> **哈希码**
> - 哈希码是根据对象的信息，以一定规则生成的一个整数
> - 相等的对象，它们的哈希码一定是相等的；不相等的对象，它们的哈希码有可能相等。
> 
**Java中的**`**hashCode()**`**和**`**equals()**`
> - Java中Object的`hashCode()`方法是根据对象的存储地址、对象的字段等生成的哈希码。
> - Java利用`hashCode()`生成的哈希码来找到哈希表中的桶，然后使用`equals()`方法来比较对象。
> - 当我们重写`equals()`方法后，必须重写`hashCode()`方法，使得两个`equals()`为true的对象产生的哈希码相同，否则就会影响哈希表的使用。
**插入元素**
   - 向hash表插入对象时同样需要计算对象的哈希码，通过哈希码找到对象应该插入的桶
   - 桶中可能已经存在对象，此时就发生了哈希冲突，此时需要将新对象与桶中的对象进行比较，如果不存在则将新对象插入到桶中
- **hash表的桶数**
   - **为了更好地控制散列表的性能（在空间利用率和查询成本之间找到平衡），可以指定一个初始的桶数**
   - 如果大致知道最终会有多少个元素要插入到hash表中，就可以设置桶数，通常**将桶数设置为预计元素个数的75% ~ 150%**
   - JDK库使用的**桶数是2的幂**，当提供的初始桶数不是2的幂时，将**自动将桶数提升到2的幂**
   - **桶数的默认值为16**
> **为什么hash桶的个数必须为2的幂次方？**
> 
> hash算法中利用hashcode计算新元素具体应该放在哪个桶里
> - 例如一共有16个桶，新元素的hashcode为18
> - 最简单的方法可以对hashcode取模计算桶，得到2（18%16=2），所以放在第二个桶里
> - 上述计算方法有两个缺点：
>    1. **如果hashcode是负数，得到的也是负数**
>    2. **运算比较慢（相比于位运算）**
> 
> 在JDK中，**计算桶的算法是**`**hashcode&(length - 1)**`** **
> - 例如16个桶可以由四位二进制表示，那么就可以利用1111去和hashcode进行按位与运算，1111与hashcode按位与运算的结果就是桶的位置
>    - 这里1111实际上就是桶数-1的二进制结果
> - 如：01011000111001&1111=1001
> - 如果想使用上述算法，那么桶数就必须为2的幂次方，如果不是2的幂次方，在进行二进制中减一，不会变成全1，比如出现1011，这样在和hashcode取做&运算的时候，就不会出现1111这个桶数，也就是说这个桶肯定是空的
<br />
- **hash表的再散列（rehashed）**
   - 如果hash表太满，就需要再散列
   - 如果要对hash表再散列，就需要创建一个桶数更好的表，并将所有元素插入到这个新表中，然后丢弃原来的表，**新表的桶数是原来的两倍**
**触发再散列的条件**
   1. **装填因子（load factor）可以确定何时对散列表进行再散列，默认值是0.75**，即如果hash表中的元素数量已经超过capacity * 0.75，就会自动再散列
   1. 在JDK8中，**当桶中的对象数量到达8个时，就会尝试将链表转化为红黑树以减少比较次数**
**在转换为红黑树之前会先查看桶的数量，如果桶的数量小于64个时，就会触发再散列而不是将链表转化为红黑树**
<a name="PqhEl"></a>
### 2 TreeSet
- **TreeSet特点**
   - TreeSet的**底层数据结构是红黑树（优化的排序二叉树）**
   - TreeSet的功能与HashSet十分类似，都可以快速地查找元素（TreeSet稍慢），但是由于TreeSet的底层数据结构是红黑树，因此**TreeSet支持自动排序所有元素**
   - 可以按任意顺序将元素插入到TreeSet中，**在对TreeSet进行遍历时，元素将自动地按照排序后的顺序呈现**
- **TreeSet与HashSet的区别**
**功能**
   - 两者都支持快速查询元素，但是TreeSet还支持对元素进行排序
**查询和插入效率**
   - **对于TreeSet来说，每次将一个元素插入到红黑树中或者从红黑树中查询元素时，都需要找到树的正确位置，平均时间复杂度为**![](https://cdn.nlark.com/yuque/__latex/c5b86093c3a81e20e7309f9e6f19d7fb.svg#card=math&code=O%28log_2n%29&id=NPeZQ)
   - **对于HashSet来说，插入和查询操作的时间复杂度几乎为**![](https://cdn.nlark.com/yuque/__latex/5e079a28737d5dd019a3b8f6133ee55e.svg#card=math&code=O%281%29&id=C2uyf)
   - 因此TreeSet的使用效率比HashSet要差
**元素条件**
   - 对于HashSet来说，要插入其中的元素只需要能够计算哈希码即可，这十分容易
   - 对于TreeSet来说，要插入其中的元素必须要可比较，这一条件在某些情况下很难达成，例如比较两个矩形
<a name="eqhCl"></a>
### 3 EnumSet
- EnumSet是一个枚举类型元素集的高效实现，由于枚举类型只有有限个实例，所以EnumSet内部用位序列实现，如果对应的值在集中，则相应的位被置为1
<a name="McPKp"></a>
# 3 Map接口
![](https://cdn.nlark.com/yuque/0/2021/png/1169704/1618986340377-dabeff23-364d-4676-83d5-5d37332fbbaa.png#crop=0&crop=0&crop=1&crop=1&from=url&id=gC0Qc&margin=%5Bobject%20Object%5D&originHeight=518&originWidth=1079&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
<a name="ByAh2"></a>
## 1 概述
- **Map接口的特点**
   - Set允许我们快速地查找现有的元素，但是要查找一个元素需要有所查找的元素的副本
通常，我们只知道某些关键信息，希望查找与之关联的元素，Map（映射）数据结构就是为此设计的
   - Map用来存放键值对，如果提供了键，就能够查找到值，且键是不允许重复的
   - 从功能上就可以看出，Map接口与Set接口很相似，实际上Map接口的实现与Set接口的实现也极其相似
- **Map接口定义的方法**
```java
public interface Map<K, V> {
    // 如果Map中存在指定的key，则返回true
    boolean containsKey(Object key);
    // 如果Map中存在一个或多个key对应的value为指定的value，则返回true
    boolean containsValue(Object value);
    // 返回指定key对应的value
    V get(Object key);
    // 返回指定key对应的value，如果指定key不存在，则返回默认值
    V getOrDefault(Object key, V defaultValue);
    // 向Map中存放指定键值对
    // 如果Map中已经存在相同的key，则把旧value替换为新value
    V put(K key, V value);
    // 删除key对应的键值对
    V remove(Object key);
    // 添加m中所有的键值对
    void putAll(Map<? extends K, ? extends V> m);
    // 返回Map中所有key的集合视图
    // 对该集合的操作会影响到产生它的Map，该集合只支持删除操作，不支持添加操作
    Set<K> keySet();
    // 返回Map中所有value的集合视图
    // 对该集合的操作会影响到产生它的Map，该集合只支持删除操作，不支持添加操作
    Collection<V> values();
    // 返回Map中所有键值对的集合视图
    // 对该集合的操作会影响到产生它的Map，该集合只支持删除操作，不支持添加操作
    Set<Map.Entry<K, V>> entrySet();
    // 该接口表示一个键值对，是entrySet()方法中返回的集合中的元素类型
    interface Entry<K, V> {
        K getKey();
        V getValue();
        V setValue(V value);
        ...
        }
    }
    // 对Map中的所有键值对执行给定的action
    default void forEach(BiConsumer<? super K, ? super V> action) {
        Objects.requireNonNull(action);
        for (Map.Entry<K, V> entry : entrySet()) {
            K k;
            V v;
            try {
                k = entry.getKey();
                v = entry.getValue();
            } catch (IllegalStateException ise) {
                // this usually means the entry is no longer in the map.
                throw new ConcurrentModificationException(ise);
            }
            action.accept(k, v);
        }
    }
    ...
}

2 HashMap和TreeMap

HashMap和TreeMap是Map接口常用的实现类
这两个类与HashSet和TreeSet的实现基本一致，不同的是
- HashMap使用key来计算哈希值，与value无关
- TreeMap将key应用到比较函数，与value无关

3 LinkedHashMap和LinkedHashSet

这两个类在HashMap和HashSet的基础是新增了一个双向链表，这个双向链表可以记录插入元素项的顺序，使得遍历时访问元素的顺序和插入元素的顺序一致

4 算法

1 Collections类

Collections类概述
- Collections类是集合框架的工具类，其提供的方法服务于集合框架中的集合
- Collections包含了排序、二分查找和一些实用算法
- Collections中的方法接收的参数都是泛型接口，这样算法只需要实现一次就可以应用到不同的实现类
- Collections中的方法都是静态方法

1 排序

**Collections.sort()**方法
- Collections提供的sort()方法可以对实现了List接口的集合进行排序
- 注意sort()方法使用的是稳定的排序算法，时间复杂度为
- sort()方法有以下两种形式
```
<T> void sort(List<T> list, Comparator<? super T> c)
<T extends Comparable<? super T>> void sort(List<T> list)
```
  可以提供一个比较器，也可以使用List元素自身的内部比较器
Collections.sort()方法源码分析

Collections.sort()源码

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}
@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

可以看到调用的实际上是List接口的**sort()**方法

**List::sort()**源码

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();    // List转为对象数组
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

常见的排序方法都需要基于随机访问方式，不过对于链表来说则难以支持

因此List::sort()会将List中的所有元素都转入一个数组（无论是否是链表），使用Arrays类提供的sort()方法对数组进行排序，然后再将排序后的数组复制回List
**Arrays.sort()**源码

public static void sort(Object[] a) {
    // 如果用户要求使用传统的归并排序
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);    // 使用JDK1.5中的归并排序算法
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);    // 使用改进后的归并排序算法
}
public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);    // 如果没有转入比较器，则调用sort(Object[] a)方法
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

这里主要关注sort(Object[] a)方法，该方法采用元素自身的比较器进行比较
可以看到该方法中会根据需要调用传统的归并排序算法和改良后的归并排序算法（TimSort）

1 传统的归并排序

legacyMergeSort(a)
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
b7d817994686a3403c289263295b7308_1024555-20161218163120151-452283750.png

2 优化的归并排序

TimSort

2 二分查找

**Collections.binarySearch()**方法
- binarySearch()方法可以对实现了List接口的有序集合执行二分查找
- 集合必须是有序的，否则该方法将返回一个错误的答案
查找失败
- 当集合中不存在目标值时，**Collections.binarySearch()**方法将返回一个负值，表示查询失败
- 返回的负值并不是毫无意义的，如果返回的值是**i**，则**-i-1**就表示目标值应该插入的位置（或者说如果目标值存在，其下标为**-i-1**）
传入链表

只有采用随机访问，二分查找才有意义，因此如果向**binarySearch()**方法传入一个链表，则自动退化为线性查找

3 其他算法

2 集合与对象数组的转换

对象数组转集合
```
String[] strs = {"崔奕宸", "邱雪静"};
List<String> list = new ArrayList<>(Arrays.asList(strs));
Set<String> set = new HashSet<>(Arrays.asList(strs));
```
- 基本上所有的集合实现类的构造器都可以接收一个实现了Collections接口的集合，因此只需要利用Arrays.asList()方法将数组转为List，即可将其传给任何集合实现类
集合转数组
```
Set<String> set = new HashSet<>();
String[] strs = (String[])set.toArray();    //错误的，无法通过编译
String[] strs = set.toArray(new String[0]);
```
注意这里需要给toArray()方法传入一个数组实例，否则该方法将返回一个Object数组，而且无法直接利用强制类型转换将Object数组转为其它类型数组

5 比较器

**Comparable**和**Comparator**概述
- **Comparable**和**Comparator**都是用来实现类的自定义比较的，进而实现集合的排序
- Comparable接口出自java.lang包，它有一个compareTo(Object obj)方法用来排序
- Comparator接口出自java.util包，它有一个compare(Object obj1, Object obj2)方法用来排序
内部比较器：**Comparable**接口

Comparable是一个对象本身支持自比较所需要实现的接口，如String、Integer自己就可以完成比较大小操作，因为它们已经实现了Comparable接口）

外部比较器：**Comparator**接口
- Comparator是一个外部的比较器，当某个对象不支持自比较或者自比较函数不能满足要求时，可以写一个比较器来完成两个对象之间大小的比较或者用于制定一个比较规则，可以作为参数传给方法
- 应用

Collections.sort()（如果不指定比较器，则使用类内部实现的compareTo()作为比较规则）、构造函数TreeMap()等

两种方式实现自定义比较
1. 需要比较的类实现Comparable接口，在类内部重写compareTo()方法实现自定义比较
2. 定义一个比较类，实现Comparator接口，在比较类内部重写compare()方法实现一个排序规则
实例

分别采用重写compareTo()和重写compare()的方式对Person对象进行排序

class Person implements Comparable<Person> {
    private String name;
    private int age;
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public int getAge() { return age; }
    public String getName() { return name; }
    //内部比较规则：按Person的age降序排列
    @Override
    public int compareTo(Person person) {
        if (age < person.age) return 1;
        else return -1;
    }
}
class AgeComparator implements Comparator<Person> {
    //外部比较规则：按Person的name升序排列
    @Override
    public int compare(Person o1, Person o2) {
        if (o1.getName().compareTo(o2.getName()) > 0) return 1;
        else return -1;
    }
}
public class MyClass<T> {
    public static void main(String args[]) {
        Person p1 = new Person("崔奕宸", 20);
        Person p2 = new Person("邱雪静", 19);
        Person p3 = new Person("崔伟", 52);
        Person p4 = new Person("陈彦文", 50);
        ArrayList arrayList = new ArrayList();
        arrayList.add(p1);
        arrayList.add(p2);
        arrayList.add(p3);
        arrayList.add(p4);
        System.out.println("根据Person内部比较规则进行排序：");
        Collections.sort(arrayList);
        printPersons(arrayList);
        System.out.println("根据外部比较器规定的规则进行排序：");
        Collections.sort(arrayList, new AgeComparator());
        printPersons(arrayList);
    }
    public static void printPersons(ArrayList arrayList){
        for (Object obj : arrayList) {
            Person person = (Person) obj;
            System.out.print("姓名：" + person.getName() + " 年龄：" + person.getAge() + "\n");
        }
        System.out.println();
    }
}

上述代码输出为

根据Person内部比较规则进行排序：
姓名：崔伟 年龄：52
姓名：陈彦文 年龄：50
姓名：崔奕宸 年龄：20
姓名：邱雪静 年龄：19
根据外部比较器规定的规则进行排序：
姓名：崔伟 年龄：52
姓名：崔奕宸 年龄：20
姓名：邱雪静 年龄：19
姓名：陈彦文 年龄：50