【译】Java 集合框架概览

桩白墨
Java
2019-05-29
148热度
0评论

原文：https://www.journaldev.com/1260/collections-in-java-tutorial

译者：桩白墨

几乎在每个 Java 应用程序中，都能看到集合的身影。Java 集合框架，是 Java 语言的核心组成部分。本文将对 Java 集合框架（Java Collections Framework）作全面深入的介绍。

1 Java 集合框架是什么？

集合就像容器，可以把多个物品打包到一个独立的单元中。例如，一罐巧克力，一个姓名列表，等等。几乎每一种编程语言，都会用到集合，Java 也不例外。Java 刚诞生时，带有一些基本的集合类：Vector、Stack、Hashtable、Array。随后，Java 1.2 提供了集合框架，使我们得以用一种标准的方式，去表示和操纵 Java 中的集合。Java 集合框架由以下部分组成：

接口：Java 集合框架中的接口，提供了用于表示集合的抽象数据类型。java.util.Collection 是集合框架中最上层的接口，位于继承树的最顶端。它包含了一些每个集合类都必须实现的重要方法，如 size()、iterator()、add()、remove()、clear()。其他重要的接口有：java.util.List、java.util.Set、java.util.Queue 和 java.util.Map。Map 是集合框架中，唯一一个没有继承自 Collection 的接口。所有集合框架的接口，都在 java.util 包中。
实现类：Java 集合框架为集合提供了核心实现类，可以用来创建不同类型的集合。一些重要的集合类：ArrayList、LinkedList、HashMap、TreeMap、HashSet、TreeSet。这些类可以满足我们绝大多数的编程需求，如果我们需要更特殊的集合，可以继承它们，创建自定义集合类。Java 1.5 推出了线程安全的集合类，允许在迭代的时候删除元素。如 CopyOnWriteArrayList、ConcurrentHashMap、CopyOnWriteArraySet。这些类在 java.util.concurrent 包中。所有的集合类都包含在 java.util 和 java.util.concurrent 包中。
算法：算法是一些可以提供通用功能的好用的工具方法，例如查找、排序、洗牌等。

下面的类图，是 Java 集合框架的继承体系。为了简单起见，只画出了常用接口和实现类。

1.1 使用 Java 集合框架的好处

减少开发量——它提供了几乎所有类型的集合，以及迭代和处理数据的实用方法。所以我们可以专注于业务逻辑，而不是耗费时间和精力去设计自己的集合 API。
保障代码质量——相对于自己鼓捣出来的数据结构，使用经过严格测试的集合类，可以提升应用程序的质量。
可重用性和互操作性。
易用——如果使用集合框架中的类，几乎不用学习新的 API。

2 Java 集合接口

Java 集合接口，是 Java 集合框架的基础。注意，所有核心集合接口都是泛化的，例如 public interface Collection<E>。<E> 是泛型的语法，当我们使用集合的时候，应该将它指定为集合所要包含对象的类型。它会在编译时给对象做类型检查，有助于减少运行时错误。

为了控制核心集合接口的数量，Java 平台没有为每一个特殊种类的集合提供单独的接口。如果调用了集合实现类不支持的方法，会抛出 UnsupportedOperationException。

2.1 Collection 接口

这是集合继承树的根节点。一个集合代表了一组对象，这些对象被称为集合的元素。Java 平台没有提供这个接口的直接实现类。

这个接口包含了各种方法，可以告诉我们集合中有多少元素（size、isEmpty），检查一个给定的对象是否在集合中（contains），从集合中增加或删除元素（add、remove），提供一个迭代器（iterator）。

Collection 接口也提供了大量针对整个集合的操作——containsAll、addAll、removeAll、retainAll、clear。

toArray 方法，则在集合类与依赖数组的老式 API 之间架起了一座桥梁。

2.2 Iterator 接口

Iterator 接口提供了迭代任意 Collection 的方法。我们可以使用 iterator 方法，从一个 Collection 中获取迭代器实例。Iterator 取代了 Java 集合框架中的 Enumeration。Iterator 允许调用者在迭代过程中删除元素。集合类中 Iterator，其实是对“迭代器模式”的一种实现。

2.3 Set 接口

Set 是一个不能包含重复元素的集合。这个接口模拟了数学上的“集合”抽象，并用来表示各种数学集合，例如一组不重复的卡片。

Java 平台包含了三个通用的 Set 实现：HashSet、TreeSet 和 LinkedHashSet。Set 接口不支持对集合元素的随机访问。可以使用迭代器或 foreach 循环来遍历一个 Set。

2.4 List 接口

List 是一个有序集合，并且可以包含重复元素。可以使用下标索引访问任意元素。List 很像一个具备动态长度的数组。List 是最常用到的集合类型之一。ArrayList 和 LinkedList 是 List 接口的实现类。

List 接口提供了一些有用的方法：

向指定索引位置添加元素；
根据索引删除/替换元素；
根据索引得到一个子列表。

List strList = new ArrayList<>();

//add at last
strList.add(0, "0");

//add at specified index
strList.add(1, "1");

//replace
strList.set(1, "2");

//remove
strList.remove("1");

Collections 类为 List 提供了一些有用的算法：sort、shuffle、reverse、binarySearch 等。

2.5 Queue 接口

Queue 是一个用于保存多个待处理元素的集合。除了基本的集合操作之外，Queue 还提供插入、提取和检查操作。

一般而言，队列会用“先进先出”（FIFO）的方式对内部元素排序。优先队列是个例外，它会根据提供的 Comparator 或元素的自然顺序排序。无论使用什么顺序，调用 remove 或 poll 时，总会移除队列头部的元素。

在一个 FIFO 队列中，所有新元素都插入在队列的尾部。

2.6 Deque 接口

这是一个线性集合，支持从两端插入或删除元素。名称 deque 是 “double-ended queue” 的缩写，发音是 “deck”。大多数 Deque 的实现对包含的元素数量没有限制，但是这个接口支持容量受限的 deque 以及没有固定大小限制的 deque。

这个接口定义了访问 deque 两端元素的方法，可以插入、删除或检查元素。

2.7 Map 接口

Java Map 是一个将键映射到值的对象。map 不能包含重复的键：每个键至多能映射到一个值。

Java 平台包含了三个通用的 Map 实现：HashMap、TreeMap 和 LinkedHashMap。

对 Map 的基本操作有：put、get、containsKey、containsValue、size、isEmpty。

2.8 ListIterator 接口

它是列表的迭代器，允许程序员沿任一方向遍历列表，在迭代期间修改列表，并获取迭代器在列表中的当前位置。

Java ListIterator 没有当前元素的概念。它的指针位置总是在元素之间，可以调用 previous() 和 next() 访问指针位置之前和之后的元素。

2.9 SortedSet 接口

SortedSet 是一个维持内部元素升序排列的 Set。它提供了几个额外操作以更好地利用有序性。

SortedSet 用于存在自然顺序的集合，如单词列表和成员名册。

2.10 SortedMap 接口

以键的升序顺序来维护其映射的 Map。这是 Map 版的 SortedSet。SortedMap 用于存在自然顺序的键值对的集合，例如字典和电话簿。

3 Java 集合类

Java集合框架带有许多接口的实现类。最常见的实现类是 ArrayList、HashMap 和 HashSet。Java 1.5 包含了并发实现，如 ConcurrentHashMap 和 CopyOnWriteArrayList。通常，集合类不是线程安全的，它们的迭代器会快速失败（fail-fast）。在本节中，我们将了解常用的集合类。

3.1 HashSet 类

Java HashSet 是 Set 接口的基本实现，内部是 HashMap。它不保证集合的迭代顺序，并且允许空元素。

这个类为基本操作（add、remove、contains 和 size）提供了常数时间的性能，前提是散列函数在存储桶中正确地分散元素。我们可以为集合设置初始容量和负载系数（load factor）。负载系数是对 HashMap 自动扩容之前它所允许的饱满程度的度量。

3.2 TreeSet 类

基于 TreeMap 的 NavigableSet 的实现。元素使用他们的自然顺序来排序，或者用对象创建时提供的 Comparator，这取决于使用的是哪个构造函数。

参考：Java Comparable Comparator

此实现为基本操作（add、remove、contains）提供了 log(n) 级别的时间消耗。

注意，如果要正确实现集合接口，集合维护的顺序（无论是否提供显式比较器）必须与equals一致。（请参阅 Comparable 或 Comparator 的文档，以获得与 equals 保持一致的精确定义。）这是因为 Set 接口是根据 equals 操作定义的，但 TreeSet 实例使用其 compareTo（或 compare）方法执行所有元素比较，因此从集合的角度看，被此方法视为相等的两个元素一定是 equal 的。

3.3 ArrayList 类

Java ArrayList 是 List 接口的变长数组的实现。实现所有可选的列表操作，并允许所有元素（包括 null）。除了实现列表接口之外，这个类还提供了一些方法来操作用于存储列表的内部数组的大小。（这个类大致相当于 Vector，只是它不同步。）

size、isEmpty、get、set、iterator 和 listIterator 操作都在常数时间完成。add 操作以均摊常数时间完成，即添加 n 个元素需要 O(n) 时间。所有其他操作，大致上都是线性时间。与 LinkedList 的实现相比，常量系数较小。

深入阅读：Java ArrayList and Iterator

3.4 LinkedList 类

对 List 和 Deque 接口的双向链表实现。实现所有可选的列表操作，并允许所有元素（包括null）。

支持双向链表能支持的所有操作。涉及索引的操作，会从头到尾遍历链表，直至找到索引位置的元素。

3.5 HashMap 类

Map 接口的基于哈希表的实现。此实现提供所有可选的 Map 操作，并允许 null 值和 null 键。HashMap 大致相当于 Hashtable，只是它不同步并且允许 null。这个类不保证映射的顺序。

此实现为基本操作（get 和 put）提供常数时间的性能。它提供构造函数来设置集合的初始容量和负载系数。

深入阅读： HashMap vs ConcurrentHashMap

3.6 TreeMap 类

基于红黑树的 NavigableMap 实现。映射是根据键的自然顺序，或创建时提供的 Comparator 排序的，这取决于使用的是哪个构造函数。

此实现为 containsKey、get、put、remove 操作保证了 log(n) 的时间开销。其中用到的算法，修改自《算法导论》中的相关算法。

注意，与任何一个有序映射（sorted map）一样，要想正确实现 Map 接口，不论是否提供显式比较器，TreeMap 维护的顺序都必须要与 equals 一致。（请参阅 Comparable 或 Comparator 的文档，以获得与 equals 保持一致的精确定义。）这是因为 Map 接口是根据 equals 操作定义的，但有序映射是使用 compareTo（或 compare）方法执行所有键的比较，因此从有序映射的角度来看，此方法判定为相等的两个 key，必定是 equal 的。另外，即使有序映射的顺序与 equals 不一致，也不影响它的正常使用；它只是不遵守 Map 接口的一般约定。

3.7 PriorityQueue 类

队列通常按 FIFO 的顺序处理元素，但有时我们希望根据元素的优先级处理元素。在这种情况下，我们可以使用 PriorityQueue，并且需要在实例化 PriorityQueue 时提供一个 Comparator 实现。PriorityQueue 不允许空值，并且没有边界（unbounded）。更多细节请看：Java Priority Queue

3.8 线程安全的集合

Java 1.5 Concurrent 包（java.util.concurrent）包含了线程安全的集合类，允许在迭代的同时修改集合。而按照原来的设计，迭代器会快速失败，并抛出 ConcurrentModificationException。其中一些类是 CopyOnWriteArrayList、ConcurrentHashMap、CopyOnWriteArraySet。

详细了解请阅读以下文章：

4 Collections 类

Java Collections 类只包含操作或返回集合的静态方法。有操作集合的多种算法；“包装器”：将指定集合包装为一个新集合并返回；以及其他一些零碎的小功能。

此类包含用于集合框架算法的方法，如二分查找、排序、洗牌、反转等。

4.1 同步包装器

同步包装器向任意集合添加自动同步（线程安全）功能。六大核心集合接口 —— Collections、Set、List、Map、SortedSet 和 SortedMap —— 都有一个静态工厂方法。

public static  Collection synchronizedCollection(Collection c);
public static  Set synchronizedSet(Set s);
public static  List synchronizedList(List list);
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
public static  SortedSet synchronizedSortedSet(SortedSet s);
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);

上面的每个方法，都根据传入的指定集合，返回一个同步的（线程安全的）集合。

4.2 不可变包装器

不可变包装器会去除集合的可修改性。它会截获所有修改集合的操作，并抛出 UnsupportedOperationException。它的主要用途是：

使集合在创建后不可变。在这种情况下，最好不要维护对原始集合的引用。这样就绝对能保证不可变性。
允许某些客户端以只读方式访问你的数据结构。你保留了对原始集合的引用，并对外提供包装后的引用。这样，你依然保持完全的访问权限，但是客户端只能查看不能修改。

这些方法是：

public static  Collection unmodifiableCollection(Collection<? extends T> c);
public static  Set unmodifiableSet(Set<? extends T> s);
public static  List unmodifiableList(List<? extends T> list);
public static <K,V> Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m);
public static  SortedSet unmodifiableSortedSet(SortedSet<? extends T> s);
public static <K,V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, ? extends V> m);

4.3 集合算法

Java 集合框架提供了常用的算法实现，如排序和查找。Collections 类包含这些方法实现。这些算法大都用于 List，但其中一些适用于所有类型的集合。

4.3.1 排序

sort 算法对 List 重新排序，使其元素根据排序关系按升序排列。提供了两种使用形式。较为简单的形式是，接受一个 List，并根据元素的自然顺序对其排序。第二种形式是，除了 List 之外，额外接受一个 Comparator，并使用 Comparator 对元素排序。

4.3.2 洗牌

shuffle 算法会打破 List 中现有的顺序性。也就是说，该算法根据来自随机源的输入对列表重新排序，以便所有可能的排列能以相同的概率发生，前提是有一个公平的随机源。这个算法在实现拼手气的游戏中很有用。

4.3.3 查找

binarySearch 算法在一个排好序的 List 中查找指定元素。这个算法有两种形式。第一种，接受一个 List 和一个待查找的元素（“搜索键”）。这种形式假定 List 是按照元素自然序的升序排列的。第二种形式，额外接受一个 Comparator，并假定 List 根据 Comparator 按升序排列。在调用 binarySearch 之前，要先调用 sort 方法对 List 排序。

4.3.4 组合

frequency 和 disjoint 算法对一个或多个集合形成的组合的某些方面进行测试。

frequency：统计指定元素在指定集合中出现的次数；
disjoint：确定两个集合是否不相交；也就是说，它们是否不包含共同的元素。

4.3.5 最小值和最大值

min 和 max 算法，分别返回指定集合中最小和最大的元素。这两种操作都有两种形式。较为简单的形式，是只接受一个 Collection 并按自然序返回一个最小（或最大）的元素。第二种形式，额外接受一个 Comparator，并根据指定的 Comparator 返回最小（或最大）的元素。

5 其他

Java 8、10、11 中集合框架 API 的变化。见原文，此处略。