跳到主要内容

12、数据结构与算法 - 基础：常用集合简述

1、简介
Java 集合是 Java API 用得最频繁的一类，掌握 Java 集合的原理以及继承结构非常有必要。总的来说，Java 容器可以划分为 4 个部分：
List 集合

  • 列表实现
  • 列表安全实现
  • 链表实现

Set 集合

  • 有序实现
  • 哈希实现

Queue 集合

  • 有序实现
  • 双向实现

Map 集合

  • 哈希实现
  • 有序实现

集合工具类：

1、 Iterator迭代器；
2、 ListIterator迭代器；
3、 Enumeration枚举类；
4、 Arrays；
5、 Collections；

接下来我们先了解一下继承关系。 首先，最顶层的是 Collection 接口。可以看到 Collection 接口定义了最最基本的集合操作，例如：判断集合大小、判断集合是否为空等。List、Set、Queue 都继承了该接口。接着，AbstractCollection 也继承了 Collection 接口。从这个类名可以看出，其是一个抽象类。AbstractCollection 对 Collection 接口中一些通用的方法做了实现。例如：判断是否为空的方法、判断是否包含某个元素的方法等。通过继承AbstractCollection接口，可以少写许多不必要的代码，这是代码抽象设计最常用的思想。AbstractCollection是最为基础的类，其他所有集合的实现都继承了这个抽象类。

 

2、List 集合
List集合存储的元素是有序的（存取有序）, 类结构：一个 List 接口继承了 Collection 接口。一个 AbstractList 抽象类实现了 List 接口、继承了 AbstractCollection 抽象类。 整个 List 集合的实现可以分为三大块:
2.1、列表实现
ArrayList 类是很常用的 List 实现，其底层是用数组实现的。其读取元素的时间复杂度是 O（1），修改写入元素的时间复杂度是 O（N）。我们将会在下面的章节中详细介绍，这里不做深入。

2.2、列表安全实现
Vector 类也是很常用的 List 实现，其底层是用数组实现的。其数据结构与 ArrayList 非常类似。但其与 ArrayList 的一个最大的不同是：Vector 是线程安全的，而 ArrayList 则不是线程安全的。
Stack 类则是在 Vector 的基础上，又实现了一个双向队列。 所以其除了是线程安全的之外，其还是一个先进后出的 List 实现。

2.3、链表结构实现
LinkedList 是一个经典的链表实现。LinkedList 继承了 AbstractSequentialList 抽象类。AbstractSequentialList 抽象类从字面上理解是抽象连续列表。这里的重点是 sequential 这个词，表示其数据结构是连续的（链表）。AbstractSequentialList抽象类做了许多工作，使得后续的链表实现更加简单。从AbstractSequentialList的注释可以看到，如果要实现一个链表，那么只需要实现 listIterator 方法和 size 方法就可以了。

3、Set 集合
Set 集合中存储的元素是不重复的，但是其存储顺序是无序的。 类结构： 与 List 集合类似，都是一个 Set 接口继承了 Collection 接口。一个 AbstractSet 抽象类实现了 Set 接口、继承了 AbstractCollection 抽象类。这部分完全和 List 相同。
Set集合的实现可以分为两大块：
3.1、有序实现
SortedSet 接口继承了 Set 接口，TreeSet 实现了 SortedSet。
我们知道 Set 集合中的元素是无序的，而 SortedSet 接口则是定义了有序 Set 集合的接口。而 TreeSet 则是 SortedSet 的具体实现。

3.2、哈希实现
HashSet 是 Set 接口的经典哈希实现。但 Set 集合中的元素是无序的，为了维护 Set 集合的插入顺序，人们创造出了 LinkedHashSet。LinkedHashSet 在 HashSet 的基础上是用链表维护元素的插入顺序。

4、Queue 集合
队列是一个特殊的线性表，其数据结构特点是先进先出。首先，Queue 接口继承了 Collection 接口。Queue 接口在拥有基本集合操作的基础上，定义了队列这种数据结构的基本操作。可以看到 offer、poll 等方法都是队列独有的操作。接着，AbstractQueue 是对 Queue 接口的抽象实现。针对队列这种数据结构，其添加、删除元素的动作都不一样。在 AbstractQueue 抽象类里将队列的基本操作都实现了一遍。例如 AbstractQueue 中的 add 方法就和 AbstractList 中的 add 方法有着不同的实现。
Queue 集合的实现可以分成两个部分：
4.1、有序实现
PriorityQueue 是 AbstractQueue 抽象类的具体实现。PriorityQueue表示优先级队列，其按照队列元素的大小进行重新排序。当调用peek()或poll()方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列的最小元素。

4.2、双向实现
首先，我们会看到 Deque 接口。Deque（double ended queue）是双向队列的意思，它能在头部或尾部进行元素操作。最后，我们看到 LinkedList 和 ArrayDeque 都是 Deque 接口的具体实现。LinkedList 我们之前说过了，是一个链表，但它还是一个双向队列。因此LinkedList具有List和Queue的双重特性。ArrayDeque则是一个双向循环队列，其底层是用数组实现。更多内容，我们将在队列章节讲解。

5、Map 集合

Map集合与List、Set、Queue有较大不同，其实类似于key value的数据结构。首先，Map接口是最顶层的接口。与List、Set、Queue类似，Map接口定义的是哈希表数据结构的操作。例如我们常用的 put、get、keySet 等。接着，有 AbstractMap 抽象类。和 List 等类似，AbstractMap 是 Map 接口的抽象实现。

Map集合的实现分成两块。

5.1、哈希实现
AbstractMap 有具体的实现类 HashMap。HashMap 是 AbstractMap 基于哈希算法的具体实现。
接着，LinkedHashMap 和 WeakedHashMap 继承了 HashMap。LinkedHashMap 是 HashMap 的进一步实现，其用链表保存了插入 HashMap 中的元素顺序。WeakedHashMap 是 HashMap 的进一步实现，与 HashMap不同的是：WeakedHashMap 中的引用是弱引用，如果太久没用，则会被自动回收。

5.2、有序实现
首先，SortedMap 接口继承了 Map 接口。与 Set 一样，Map 中的元素是没有顺序的，SortedMap 就是有序 Map 的接口定义。接着，NavigableMap 继承了 SortedMap 接口。NavigableMap 接口定义了一些查找逻辑，方便后续实现。最后，TreeMap 则是 NavigableMap 接口的具体实现。其实 TreeMap 是基于红黑树的 Map 实现。

6、工具类
集合的工具类有：Iterator 迭代器、ListIterator 迭代器、Enumeration 枚举类、Arrays 和 Collections 类。

6.1、Iterator 迭代器
Iterator 迭代器是一个用来遍历并选择序列中的对象。Java 的 Iterator 只能单向移动。可以看到在 ArrayList、WeakHashMap 等集合类都实现了该接口，从而实现不同类型集合的遍历。

6.2、ListIterator 迭代器
ListIterator 继承了 Iterator 接口，所以其有更强大的功能，即它能够实现双向移动。但从其名字也可以看出，其只能适用于 List 集合的遍历。

6.3、Enumeration 枚举类
它是JDK1.0引入的接口。作用和Iterator一样，也是遍历集合。但是Enumeration的功能要比Iterator少。Enumeration只能在Hashtable,Vector,Stack中使用。这种传统接口已被迭代器取代，虽然 Enumeration 还未被遗弃，但在代码中已经被很少使用了。官方也在文档中推荐使用 Iterator 接口来替代 Enumeration 接口。

6.4、Arrays
Java.util.Arrays类能方便地操作数组，它提供的所有方法都是静态的。

6.5、Collections
java.util.Collections 是一个包含各种有关集合操作的静态多态方法的工具类，服务于 Java 的 Collection 框架。常用的如下：

  • Collections.sort(List<> list): 集合的自然排序；
  • Collections.binarySearch(List<> list ,T key) : 集合的二分查找；
  • Collections.max() : 获取最大值；
  • Collections .reverse() : 元素反转；
  • Collections .shuffle() : 元素位置随机置换；
  • Collections.synchronizedList(new ArrayList<>()): 创建线程安全的集合。

7、总结

我们花费了大量的篇幅讲解了 List 集合、Set 集合、Map 集合、Queue 集合以及 Iterator 等工具类。我们对这集合的类结构进行了详细的解析，从而更加了解他们之间的关系。

有时候我们会想，了解这么多有啥用呢。我有个朋友只用了常见的 ArrayList、HashMap 就可以了啊。对于这个问题，我想分享几个收获。

第一，让你更加熟悉类之间的差异。 如果我们只会用一两个类，那么我们就不知道在什么时候用什么类。例如：什么时候用 HashMap，什么时候用 Hashtable？Iterator 接口有什么作用？JDK源码的命名有什么特点？

第二，方便对源码进行扩展。 当我们深入研究了集合的实现之后，我们知道了原来 List 接口就是 List 这种数据类型的定义，而 AbstractList 是 List 的抽象实现。那么如果我们要实现一个自定义的 List 结构，那么我们就可以直接继承 AbstractList 类，从而达到快速实现的目的。但如果你没有深入研究呢？你或许只能从头写起，这样得浪费多大的精力啊。你学会了这种方式，那么对于你扩展 Spring 源码也是有很好的帮助的。
在接下来的文章里，我们将深入介绍每一个集合的具体实现。