【译】Java 集合框架概览

原文: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.Listjava.util.Setjava.util.Queuejava.util.Map。Map 是集合框架中,唯一一个没有继承自 Collection 的接口。所有集合框架的接口,都在 java.util 包中。
  • 实现类:Java 集合框架为集合提供了核心实现类,可以用来创建不同类型的集合。一些重要的集合类:ArrayListLinkedListHashMapTreeMapHashSetTreeSet。这些类可以满足我们绝大多数的编程需求,如果我们需要更特殊的集合,可以继承它们,创建自定义集合类。Java 1.5 推出了线程安全的集合类,允许在迭代的时候删除元素。如 CopyOnWriteArrayListConcurrentHashMapCopyOnWriteArraySet。这些类在 java.util.concurrent 包中。所有的集合类都包含在 java.utiljava.util.concurrent 包中。
  • 算法:算法是一些可以提供通用功能的好用的工具方法,例如查找、排序、洗牌等。

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

1.1 使用 Java 集合框架的好处

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

2 Java 集合接口

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

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

2.1 Collection 接口

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

这个接口包含了各种方法,可以告诉我们集合中有多少元素(sizeisEmpty),检查一个给定的对象是否在集合中(contains),从集合中增加或删除元素(addremove),提供一个迭代器(iterator)。

Collection 接口也提供了大量针对整个集合的操作——containsAlladdAllremoveAllretainAllclear

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

2.2 Iterator 接口

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

2.3 Set 接口

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

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

2.4 List 接口

List 是一个有序集合,并且可以包含重复元素。可以使用下标索引访问任意元素。List 很像一个具备动态长度的数组。List 是最常用到的集合类型之一。ArrayListLinkedList 是 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 提供了一些有用的算法:sortshufflereversebinarySearch 等。

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 实现:HashMapTreeMapLinkedHashMap

对 Map 的基本操作有:putgetcontainsKeycontainsValuesizeisEmpty

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。它不保证集合的迭代顺序,并且允许空元素。

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

3.2 TreeSet 类

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

参考:Java Comparable Comparator

此实现为基本操作(addremovecontains)提供了 log(n) 级别的时间消耗。

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

3.3 ArrayList 类

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

sizeisEmptygetsetiteratorlistIterator 操作都在常数时间完成。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。这个类不保证映射的顺序。

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

深入阅读: HashMap vs ConcurrentHashMap

3.6 TreeMap 类

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

此实现为 containsKeygetputremove 操作保证了 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。其中一些类是 CopyOnWriteArrayListConcurrentHashMapCopyOnWriteArraySet

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

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 组合

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

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

4.3.5 最小值和最大值

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

5 其他

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