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 源码也是有很好的帮助的。
在接下来的文章里,我们将深入介绍每一个集合的具体实现。