Java 集合(1)之 总体架构

Java 提供了一个丰富的集合类，包含了常用的数据结构和算法等。使用 Java 集合的优点部分如下：

• 降低开发的成本：通过提供的核心集合类，使 程序员 更专注地实现程序的核心功能，而不用自己去实现自己的集合类；
• 提高代码的质量：集合框架提供了许多经过严格测试的、高性能、高质量的数据结构和算法，大大提高了程序的质量；
• 促进软件的复用性：只要符合标准集合接口的新数据结构和算法本质上都是可以复用的。

在集合的接口和实现中大量使用了泛型，它为集合提供了一个可以容纳的对象类型，如果添加其他类型的元素，在编译时就会出错，这避免了在运行时出现类型转换异常。泛型也使得代码更加整洁，因为不需要显式地编写类型转换操作，编译器会帮我们实现。

Java 整个集合框架图如下：

可以看到，这个框图主要有两个主干： Collection 和 Map 。

• Collection ：它是一个接口，提供了对集合对象进行基本操作的通用接口方法，有很多具体的实现和继承，它被分为三大分支： List 、 Set 和 Queue 。
• Map ：它是由一系列键值对组成的集合，提供了 key 到 Value 的映射。

除此之外，还有 Iterator 迭代器， Collections 和 Arrays 工具类， Comparator 比较器等。

List

List 是一个有序列表，用特定的插入顺序来维护元素顺序。可以对列表中元素的插入位置进行控制，同时可以根据元素的索引访问元素。实现 List 接口的主要有 ArrayList 、 LinkedList 、 Vector 等。

ArrayList

ArrayList 是一个动态数组，在随机访问元素时性能较高，但插入和删除元素效率较低。 ArrayList 都有一个初始容量，代表了数组的大小，在 ArrayList 快满时，会进行扩容操作，每次增长 1.5 倍大小。但 ArrayList 是非同步的，在多线程场景下不要使用。

LinkedList

LinkedList 是一个双向链表，由于实现方式不同，它不支持随机访问，但很容易在列表中间进行插入和删除操作。与 ArrayList 一样， LinkedList 也是非同步的。

Vector

Vector 与 ArrayList 类似，基于动态数组实现，但 Vector 是同步的。它的操作与 ArrayList 几乎一样。

Map

Map 是由一系列键值对组成的集合，提供了 key 到 Value 的映射。实现 Map 接口的有： HashMap 、 TreeMap 、 HashTable 、 EnumMap 等。

HashMap

HashMap 以哈希表数据结构实现，查询对象时通过哈希函数将元素的哈希地址转换成数组索引，在出现碰撞冲突时，则使用链表的形式存储哈希地址相同的元素，在 JDK8 后，链表过长后会转换为红黑树。 HashMap 存储和查询效率较高，但需要考虑哈希函数、碰撞冲突等问题。

TreeMap

TreeMap 实现了 SortedMap 接口，内部以红黑树数据结构实现，其中键以某种 排序 规则排序，排序规则也可以通过 Comparator 比较器指定。

HashTable

HashTable 也是以哈希表数据结构实现，遇到冲突时采用链表的形式。类似于 HashMap ，但它的同步的。

EnumMap

EnumMap 是将枚举类型作为键值的 Map 。由于键的数量相对固定，所以在内部用一个数组存储对应值。通常来说，效率高于 HashMap 。

Set

Set 是一个不包括重复元素的集合，存入的元素没有顺序。内部通过 Map 实现， Set 里存储的值对应的是 Map 中的键，键对应的值是不变的，指向一个常量。实现 Set 接口的集合有： HashSet 、 TreeSet 、 EnumSet 等。

HashSet

HashSet 底层基于 HashMap 实现，它内部元素的顺序是由哈希码来决定的，所以它不保证 Set 的迭代顺序。可以放入 null ，但只能放入一个。

TreeSet

与 HashSet 类似，它是基于 TreeMap 实现，以某种排序规则排序。它是使用元素的自然顺序排序，或根据创建 Set 时提供的 Comparator 进行排序。但不允许存入 null 值。

EnumSet

EnumSet 基于 EnumMap 实现，是枚举专用的 Set ，其中所有元素都是枚举类型。

Queue

Queue 通常是指先进先出的队列，也不允许随机访问队列中的元素。而 Deque 接口是 Queue 的子接口，它代表一个双端队列。

ArrayDeque

ArrayDeque 是基于有首尾指针的数组（环形缓冲区）实现的双端队列，它只能从首尾取出或插入元素。底层由数组实现，可以指定容量，默认容量为 16 ，并根据添加元素个数，动态扩展。

PriorityQueue

PriorityQueue 是一个优先级队列，它使用自然顺序或者制定的比较器来排序。队列的头是按指定排序方式的最小元素。

Comparator 和 Comparable

Comparator 和 Comparable 是两个接口，都可以用来对对象进行比较。

• Comparable 接口用于当前对象和其他对象进行比较。它有一个 compareTo 方法，该方法只有一个参数。返回值为 int ，大于 0 表示当前对象大于参数对象；小于 0 表示当前对象小于参数对象；等于 0 表示两者相等。
• Comparator 是一个比较器接口，用于对传入的两个对象进行比较。它有一个 compare 方法，该方法有两个参数。

例如，对一组 Student 对象进行排序，分别使用 Comparable 和 Comparator 接口实现功能。

Comparable

Comparable 接口实现在对象类的内部，之后对象就变成了一个可以比较大小的对象，也就可以用来排序了。

首先 Student 类需要实现 Comparable 接口，重写其 compareTo 方法：

public class Student implements Comparable<Student> {

    private String name;
    private int age;
    
    // setter、getter、toString
    
    @Override
    public int compareTo(Student another) {
        int flag = this.name.compareTo(another.name);
        if(flag == 0) {
            flag = this.age - another.age;
        }
        return flag;
    }
}
复制代码

然后利用 List 接口的 sort(Comparator<? super E> c) 默认方法，或者 Collections 工具类的 sort(List<T> list) 方法进行排序：

public static void main(String[] args) {
    List<Student> students = new ArrayList<>();
    students.add(new Student("a", 4));
    students.add(new Student("d", 2));
    students.add(new Student("c", 5));
    students.add(new Student("c", 3));

    students.sort(null);
    // Collections.sort(students);

    for (Student student : students) {
        System.out.println(student);
    }
}
复制代码

Comparator

Comparator 实现在对象类的外部，此时对象类的结构不需要有任何变化。

然后另外定义一个比较器类，实现 Comparator 接口并重写其 compare 方法：

class PersonComparator implements Comparator<Person> {

    @Override
    public int compare(Person o1, Person o2) {
        int flag = o1.getName().compareTo(o2.getName());
        if(flag == 0) {
            flag = o1.getAge() - o2.getAge();
        }
        return flag;
    }
}
复制代码

然后利用 List 接口的 sort(Comparator<? super E> c) 方法，或者 Collections 工具类的 sort(List<T> list, Comparator<? super T> c) 方法进行排序：

public static void main(String[] args) {
    List<Person> persons = new ArrayList<>();
    persons.add(new Person("a", 4));
    persons.add(new Person("d", 2));
    persons.add(new Person("c", 5));
    persons.add(new Person("c", 3));

    persons.sort(new PersonComparator());
    // Collections.sort(persons, new PersonComparator());

    for (Person person : persons) {
        System.out.println(person);
    }
}
复制代码