Core Java Tutorial -- Collections Framework

系统管理员 2022-05-28 21:09 182阅读 0赞

Java 集合几乎在每个应用中都有被使用。Java 集合框架是 Java 编程语言的核心部分之一。Java 集合教程细致地解析了 Java 集合框架。

1.  What is Java Collections Framework?  
    
    
     *  Benefits of Java Collections Framework
2.  Java Collections Interfaces  
    
    
     *  Collection Interface
     *  Iterator Interface
     *  Set Interface
     *  List Interface
     *  Queue Interface
     *  Dequeue Interface
     *  Map Interface
     *  ListIterator Interface
     *  SortedSet Interface
     *  SortedMap Interface
3.  Java Collections Classes  
    
    
     *  HashSet Class
     *  TreeSet Class
     *  ArrayList Class
     *  LinkedList Class
     *  HashMap Class
     *  TreeMap Class
     *  PriorityQueue Class
     *  Collections class
4.  Synchronized Wrappers
5.  Unmodifiable wrappers
6.  Thread Safe Collections
7.  Collections API Algorithms  
    
    
     *  Sorting
     *  Shuffling
     *  Searching
     *  Composition
     *  Min and Max values
8.  Java 8 Collections API Features
9.  Collection classes in a Nutshell

# 1. What is Java Collections Framework - 什么是 Java 集合框架? #

集合就像在一个单元中将多个物品分组的容器。栗如：一罐巧克力，名字列表等。集合几乎在所有的编程语言中都有被使用。Java 也有一些 Collection 类：`Vector`、`Stack`、`Hashtable`、`Array`。Java 1.2 提供了集合框架，它是一种体系结构，以标准方式表示和操作 Java 中的集合。Java 集合框架由以下部分组成：

*  **Interface（接口）：** 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` 包中。
 *  **Implementation Classes（实现类）：** Java 中的集合为集合提供了核心实现类。我们可以用它们在 Java 程序中创建不同类型的集合。一些重要的集合类有：`ArrayList`、`LinkedList`、`HashMap`、`TreeMap`、`HashSet`、`TreeSet`。这些类解决了我们编程中的大部分需求，但是如果我们需要一些特殊集合类，我们可以扩展它们来创建我们的自定义集合类。  
    Java 1.5 带来了线程安全的集合类，允许在迭代它的同时修改集合，其中一些有`CopyOnWriteArrayList`、`ConcurrentHashMap`、`CopyOnWriteArraySet`。这些类在 `java.util.concurrent` 包中。所有的集合类都存在于 `java.util` 和 `java.util.concurrent` 包中。
 *  **Algoithms（算法）：** 算法是提供一些常用功能的有效方法，栗如搜索、排序和洗牌。

下面的类图显示了集合框架层次结构。为了简单期间，我只列出了常用的接口和类。  
![Java-Collection-Framework][]

## Benefits of Java Collections Framework - Java 集合框架的好处 ##

Java 集合框架有以下好处

*  **Reduced Development Effort（减少开发工作）**– 它带有集合所有常见类型的集合以及迭代和操作数据的有用的方法。以致于我们可以更专注于业务逻辑，而不是设计我们的集合 API。
 *  **Increased Quality（提高质量）**\- 使用经过良好测试的核心集合类而不是使用任何自造的数据结构提高了我们的程序质量。
 *  **Reusability and Interoperability（可重用性和互操作性）**
 *  **Reduce effort（减少工作量）**\- 可以使用核心集合 API 来学习任何新的 API

# Java Collections Interfaces - Java 集合接口 #

Java 集合接口是 Java 集合框架的基础。注意所有核心集合接口都是泛型的。栗如 `public interface Collection<E>`。`<E>` 语法适用于`Generics` （泛型），当我们声明 `Collection` 时，我们应该使用它来指定可以包含的 `Object` 类型。它有助于在编译时通过类型检测对象来减少运行时错误。

为了保持集合接口的数量可管理。Java 平台不为每个集合类型的每个变体提供单独的接口。如果调用不受支持的接口，那么集合实现会抛出一个`UnsupportedOperationException` 异常。

## Collection Interface ##

这是集合层次结构的根。一个集合表示一组被称为其元素的对象。Java 平台不提供此接口的任何直接实现。

这个接口有方法告诉你集合中有多少元素（`size`、`isEmpty`），以检查给定对象是否在结合中（`contains`），向集合中添加和删除元素（`add`、`remove`），以及为集合提供迭代器（iterator）。

`Collection` 接口还提供了可用于整个集合批量操作的方法 - `containsAll`、`addAll`、`removeAll`、`retainAll`、`clea`。

`toArray` 方法作为结合和旧 API 之间的桥梁，这些 API 需要输入数组。

## Iterator Interface ##

`Iterator` 接口提供了迭代任何 `Collection` 的方法。我们可以使用 `iterator` 方法从 `Collection` 中获取迭代器实例。迭代器在在 Java 集合框架中取代 `Enumeration` 。迭代器云溪调用者在迭代期间从底层集合中移除元素。集合类中的迭代器是 [Iterator Design Pattern（迭代器设计模式）][Iterator Design Pattern] 的实现。

## Set Interface ##

`Set` 是一个不能包含重复元素的集合。该接口模拟数学集抽象，并用于表示集合，栗如卡片组。

Java 平台包含三个通用 Set 实现：`HashSet`、`TreeSet` 和 `LinkedHashSet` Set 接口不允许对 Collection 中的元素进行随机访问。你可以使用迭代器或者 foreach 循环来遍历一个 Set 的元素。

## List Interface ##

List 是一个有序的集合，可以包含重复的元素。你可以从其银锁访问任何元素。List 更像是具有动态长度的数组。List 是最常用的结合类型之一。`ArrayList` 和 `LinkedList` 是 `List` 接口的实现类。

List 接口提供了在特定索引处添加元素，根据索引移除、替换元素以及使用索引获取子列表的有用方法。

ArrayList 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");

集合类为 List 提供了一些有用的算法 - `sort`、`shuffle`、`reverse`、`binarySearch` 等。

## Queue Interface ##

Queue 是用于按优先保存多个元素来处理的集合。除了基本的 `Collection` 操作外，Queue 还提供额外的插入、提取和检查操作。

队列通常但不一定以 `FIFO`（先进先出）方式排列元素。优先级队列就是例外，它根据提供的比较器或元素的自然排序对元素进行排序。无论使用何种排序，队列的头部都是通过调用来移除或轮询的元素。在 FIFO 队列中，所有新元素都插入队列尾部。

## Deque Interface ##

一个线性集合，它支持两端的元素插入和移除。名字 deque 是 `double ended queue` 的缩写，通常发音 deck。大多数 Deque 实现对它们可能包含的元素的数量是没有固定限制的，但是这个接口支持容量限制的 deques 和没有固定大小限制的 deques。

这个接口定义了访问 deque 两端元素的方法。提供了插入、删除和检查元素的方法。

## Map Interface ##

[Java Map][] 是一个将键映射到值得对象。Map 不能包含重复键：每个键最多只能映射一个值。

Java 平台包含三个通用 Map 实现：`HashMap`、`TreeMap` 和 `LiinkedHashMap`。

Map 的基本操作有 `put`、`get`、`containsKey`、`containsValue`、`size` 和 `isEmpty`。

## ListIterator Interface ##

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

ListIterator 没有当前元素，其游标位置始终位于将要调用 `previous` 所返回的元素于 `next()` 所返回的元素之间。

## SortedSet Interface ##

SortedSet 是一个以升序存储其元素的 Set。提供了几个额外的操作来利用排序。排序集合用于自然排序的集合，栗如担此列表和成员资格卷。

## SortedMap Interface ##

按照升序键维护的 Map。这是 SortedSet 的 Map 类似物。排序映射用于键/值对的自然排序结合，栗如字典和电话簿。

# Java Collections Classes - Java 集合类 #

Java 集合框架带有许多接口的实现类。最常见的实现是 `ArrayList`、`HashMap` 和 `HashSet`。Java 1.5 包含 Concurrent 实现，栗如 `ConcurrentHashMap` 和 `CopyOnWriteArrayList`。通常集合类不是线程安全的，它们的迭代器是夸苏失败的。我们将学习常用的集合类。

## HashSet Class ##

[Java HashSet][] 是由 [HashMap][] 支持的 Set 接口的基本实现。它不保证集合的迭代顺序并允许 null 元素。

这个类为基本操作（`add`、`remove`、`contains` 和 `size`）提供了恒定的时间性能，假设散列函数在桶之间正确分散元素。我们可以设置该集合的初始容量和加载因子。加载因子是衡量哈希映射在其容量自动增加之前获得的满量程的度量。

## TreeSet Class ##

一个基于 TreeMap 的 NavigableSet 实现。这些元素使用它们的自然顺序或者在创建集合时提供的比较器进行排序，具体取决于使用哪个构造函数。

请参考：[Java Comparable Comparator][]

此实现为基本操作（`add`、`remove` 和 `contains`）提供了有保证的 log(n) 时间成本。

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

## ArrayList Class ##

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

`size`、`isEmpty`、`get`、`set`、`iterator` 和 `listIterator` 操作在恒定时间内运行。`add` 操作以分摊的恒定时间运行。即添加 n 个元素需要 O(n) 个时间。所有其他操作都在线性时间内运行（粗略地说）。与 LinkedList 实现相比，常数因子较低。

深入阅读：[Java ArrayList and Iterator][]

## LinkedList Class ##

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

所有这些操作的执行情况可能与双链表相符。索引到列表中的操作将从开始或结束遍历列表，以哪个更接近指定的索引为准。

## HashMap Class ##

基于哈希表的 Map 接口实现。该实现提供了所有可选的映射操作，并允许使用空值和空键。`HashMap` 类与 `Hashtable` 大致相同，只是它不同步并且允许为空。该类不保证映射的顺序。

这个实现为基本操作（`get` 和 `put`）提供了恒定的性能。它提供了构造函数来设置集合的初始容量和加载因子。

深入阅读：[HashMap vs ConcurrentHashMap][]

## TreeMap Class ##

基于红黑数的 NavigableMap 实现。该映射根据其键的自然顺序或在映射创建时提供的比较器进行排序，具体取决于使用哪个构造函数。

此实现为 `containsKey`、`get`、`put` 和 `remove` 操作提供了有保证的 log(n) 时间成本。算法是 Cormen、Leiserson 和 Rivest 的《算法导论》中的算法的改编。

注意！如果此排序映射要正确实现 Map 接口，则树映射维护的排序（如任何有序映射）以及是否提供显式比较器必须与 equals 保持一致。（请参阅 Comparable 或 Comparator 以获得与 equals 一致的精确定义）。这是因为Map接口是根据equals操作定义的，但有序映射使用其 compareTo（或 compare）方法执行所有关键比较，所以两个 从排序映射的角度来看，这种方法认为相同的密钥是相等的。 即使排序与等号不一致，排序映射的行为也是很好定义的。它只是不服从 Map 接口的总体合同。

## PriorityQueue Class ##

队列按照先进先出处理元素，但有时我们希望基于优先级处理元素。在这种情况下我们可以使用 PriorityQueue，我们需要在实例化 PriorityQueue 时提供一个 Comparator 实现。PriorityQueue 不允许空值，它是无界的。有关这方面的更多详细信息，请转到[Java Priority Queue][]，您可以在其中通过示例程序查看它的使用情况。

# 4. Collections class #

该类专门由操作或返回集合的静态方法组成。它包含对集合进行操作的多态废。“包装器”，它返回一个由指定集合支持的新集合，以及其他一些可能性和结果。

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

# 5. Synchronized Wrappers #

同步报装将自动同步（线程安全）添加到任意集合。六个核心集合接口（Collection、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);

每个这些方法都会返回一个由指定集合支持的同步（线程安全）集合。

# 6. Unmodifiable wrappers #

Unmodifiable 包装通过拦截所有修改集合并抛出 `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);

# 7. Thread Safe Collections - 线程安全集合 #

Java 1.5 Concurrent 包（`java.util.concurrent`）包含线程安全的集合类，允许在迭代时修改集合。 通过设计迭代器快速失败并引发 `ConcurrentModificationException`。 其中一些类有：`CopyOnWriteArrayList`、`ConcurrentHashMap`、`CopyOnWriteArraySet`。

阅读这些文章可以更详细地了解它们

*  [Avoid ConcurrentModificationException][]
 *  [CopyOnWriteArrayList Example][Java ArrayList and Iterator]
 *  [HashMap vs ConcurrentHashMap][]

# 8. Collections API Algorithms - 集合 API 算法 #

Java 集合框架提供了常用地算法实现，如排序和搜索。集合类包含这些方法的实现。大多数这些算法都适用于 List，但其中一些适用于各种集合。

## Sorting ##

排序算法对 List 进行重新排序，以便其元素根据排序关系以升序排序。提供了两种形式的操作。简单的形式需要一个 List，并根据其元素的自然顺序对它进行排序。排序的第二种形式除了 List 之外还有一个而比较器，并使用比较器对元素进行排序。

## Shuffling ##

洗牌算法破坏列表中可能存在的任何顺序轨迹。也就是说，这个算法基于来自随机源的输入对 List 进行重新排序，以便假设公平的随机来源，所有可能的置换都以相等的可能性发生。这个算法在实现机会游戏中很有用。

## Searching ##

binarySearch 算法搜索以排序列表中的指定元素。该算法有两种形式。第一个需要一个 List 和一个元素来搜索（“搜索键”）。这种形式嘉定 List 按照其元素的自然顺序以升序排列。第二种形式除了 List 和搜索关键字之外还有一个比较器，并且假定 List 根据指定的比较器按升序排序。在调用 binarySearch 之前，可以使用排序算法对 List 进行排序。

## Composition ##

频率和不相交算法测试一个或多个集合的组成的某个方面。

*  **frequency（频率）：** 计算指定集合中指定元素出现的次数
 *  **disjoint（不相交）：**确定两个集合是否不相交：也就是说，它们是否不包含任何共同的元素。

## Min and Max values ##

min 和 max 算法分别返回指定 Collection 中包含的最小和最大元素。这两种操作都有两种形式。简单形式只接受一个 Collection，并根据元素的自然顺序返回最小（或最大）元素。第二种形式除 Collection 之外还有一个Comparator，并根据指定的比较器返回最小（或最大）元素。

# 8. Java 8 Collections API Features #

Java 8 与集合 API 有关的最大的变化。一些重要的改变和改进有：

*  Stream API 的引入用于顺序以及并行处理，您应该阅读 [Java Stream API Tutorial][] 以了解更多细节。
 *  使用forEach（）默认方法对 Iterable 接口进行了扩展，以迭代集合。
 *  Lambda 表达式和函数接口对 Collection API 类最有利。

# 9. Collection classes in a Nutshell #

下表提供了常用集合类的基本细节。

<table> 
 <thead> 
  <tr> 
   <th>Collection</th> 
   <th>Ordering</th> 
   <th>Random Access</th> 
   <th>Key-Value</th> 
   <th>DuplicateElements</th> 
   <th>Null Element</th> 
   <th>Thread Safety</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ArrayList</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td>LinkedList</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td>HashSet</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td>TreeSet</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td>HashMap</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td>TreeMap</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td>Vector</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>Hashtable</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>No</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>Properties</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>No</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>Stack</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>CopyOnWriteArrayList</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>ConcurrentHashMap</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
   <td>No</td> 
   <td>No</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>CopyOnWriteArraySet</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
   <td>No</td> 
   <td>Yes</td> 
   <td>Yes</td> 
  </tr> 
 </tbody> 
</table>

我希望本教程能够解释 Java 集合框架中的大部分主题，请分享您的意见和评论。

[Java-Collection-Framework]: 
[Iterator Design Pattern]: https://www.journaldev.com/1716/iterator-design-pattern-java
[Java Map]: https://www.journaldev.com/11641/java-map
[Java HashSet]: https://www.journaldev.com/11627/java-hashset
[HashMap]: https://www.journaldev.com/11560/java-hashmap
[Java Comparable Comparator]: https://www.journaldev.com/780/comparable-and-comparator-in-java-example
[Java ArrayList]: https://www.journaldev.com/11404/java-arraylist
[Java ArrayList and Iterator]: https://www.journaldev.com/1289/copyonwritearraylist-java
[HashMap vs ConcurrentHashMap]: https://www.journaldev.com/122/java-concurrenthashmap-example-iterator
[Java Priority Queue]: https://www.journaldev.com/1642/java-priority-queue-priorityqueue-example
[Avoid ConcurrentModificationException]: https://www.journaldev.com/378/java-util-concurrentmodificationexception
[Java Stream API Tutorial]: https://www.journaldev.com/2774/java-8-stream