【译】Java 集合框架概览
- Java
- 2019-05-29
- 137热度
- 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,这取决于使用的是哪个构造函数。
此实现为基本操作(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 的变化。见原文,此处略。