当前位置：首页 > news >正文

CPT204-Advanced OO Programming: Lists, Stacks, Queues, and Priority Queues

news 2025/6/28 6:54:57

1.Java 集合框架层次结构Java Collection Framework hierarchy

1.1Java 集合框架描述：

1.2数据结构Data structures

1.3 Java 集合框架支持两种类型的容器（数据结构）：

1.4 Java 集合框架的设计

2.Collection

2.1 Collection接口

2.1.1具体方法

2.1.2迭代器 Iterators

2.2 AbstractCollection类

3.列表List

3.1列表接口 The List Interface

3.1.1具体方法

3.1.2 迭代器ListIterator

3.2 ArrayList 和 LinkedList

3.2.1 java.util.ArrayList

3.2.2 java.util.LinkedList

3.2.3 ArrayList 与LinkedList 区别

3.2.4使用 ArrayList 和 LinkedList

3.3Vector及其拓展得到的Stack类

3.3.1向量类The Vector Class

3.3.2栈类The Stack Class

4.队列 Queues

4.1队列接口The Queue Interface

4.2双端队列接口（Deque）

4.3优先队列 --> java.util.PriorityQueue

4.4 LinkedList

5.集合Set

5.1基础概念

5.2 HashSet

5.2.1 : 创建Creation

5.2.2 方法

5.2.2.1add()：向集合中添加元素 Adding elementsto set

5.2.2.2 增强型for循环 Enhanced for loop

5.2.2.3其它方法：

- retainAll()：保留两个集合的交集

5.3 LinkedHashSet：

5.4 SortedSet

5.5 NavigableSet

5.6TreeSet：

5.6.1创建：

5.6.2 add()方法

5.7总结

6.地图 map

6.1基础概念

6.2三种类型

6.3创建

6.4特征

6.5方法：

7. 列表和集合的静态方法Static Methods for Lists and Collections

7.1集合类中用于列表的静态方法

8.集合和列表的表现

9.比较器接口 The Comparator Interface

10.案例研究：表达式求值 Case Study: Evaluating Expressions

10.1算法示例

1.Java 集合框架层次结构Java Collection Framework hierarchy

1.1Java 集合框架描述：

- Java 提供了多种数据结构，可用于高效地组织和操作数据，通常被称为 Java 集合框架。Java provides several data structures that can be used to organize and manipulate data efficiently, commonly known as Java Collections Framework

- Java 集合框架中定义的所有接口和类都被归类在 `java.util` 包中。All the interfaces and classes defined in the Java Collections Framework are grouped in the java.util package

1.2数据结构Data structures

- 数据结构或集合是一种以某种方式组织起来的数据的集合。

A data structure or collection is a collection of data organized in some fashion

·它不仅存储数据，还支持用于访问和操作数据的操作。not only stores data but also supports operations for accessing and manipulating the data

>为特定任务选择最佳的数据结构和算法是开发高性能软件的关键之一。Choosing the best data structures and algorithms for a particular task is one of the keys to developing high-performance software

- 在面向对象的思维方式中，数据结构也被称为容器，是一种存储其他对象（称为元素）的对象。In object-oriented thinking, a data structure, also known as a container, is an object that stores other objects, referred to as elements

1.3 Java 集合框架支持两种类型的容器（数据结构）：

The Java Collections Framework supports two types of containers:

- 一种用于存储元素集合，简单称为集合collection：

One for storing a collection of elements, simply called a collection

·列表（Lists）存储有序的元素集合。Lists store an ordered collection of elements

·集合（Sets）存储一组无重复的元素。Sets store a group of nonduplicate elements

·栈（Stacks）存储以“后进先出”方式处理的对象。Stacks store objects that are processed in a last-in, first-out fashion

·队列（Queues）存储以“先进先出”方式处理的对象。Queues store objects that are processed in a first-in, first-out fashion

·优先队列（PriorityQueues）存储按优先级顺序处理的对象。PriorityQueues store objects that are processed in the order of their priorities

- 另一种用于存储键值对，称为映射。One for storing key/value pairs, called a map

- 注意：在 Python 中，这被称为字典。Note: this is called a dictionary in Python

1.4 Java 集合框架的设计

- 接口定义了框架/通用的 API。The interfaces define the framework/general API

- 抽象类提供了部分实现。The abstract classes provide partial implementation

·提供一个部分实现了接口的抽象类，方便用户编写专门容器的代码。Providing an abstract class that partially implements an interface makes it convenient for the user to write the code for the specialized containers

·AbstractCollection是为了方便而提供的（因此它被称为便利抽象类）。AbstractCollection is provided for convenience (for this reason, it is called a convenience abstract class)

- 具体类则通过具体的数据结构来实现接口。

The concrete classes implement the interfaces with concrete data structures

·Java 集合框架中的所有具体类都实现了 java.lang.Cloneable 和 java.io.Serializable 接口，除了 java.util.PriorityQueue 没有实现 Cloneable 接口。All the concrete classes in the Java Collections Framework implement the java.lang.Cloneable and java.io.Serializable interfaces except that java.util.PriorityQueue does not implement the Cloneable interface

2.Collection

2.1 Collection接口

- Collection 接口是用于操作对象集合的根接口。

The Collection interface is the root interface for manipulating a collection of objects

- Collection接口中的某些方法在具体子类中无法实现（例：只读集合无法添加或删除元素）。

Some of the methods in the Collection interface cannot be implemented in the concrete subclass (e.g., the read-only collections cannot add or remove)

·在这种情况下，该方法会抛出 java.lang.UnsupportedOperationException. In this case, the method would throw java.lang.UnsupportedOperationException, like this:

2.1.1具体方法

2.1.2迭代器 Iterators

- 每个集合都实现了 Iterable 接口。Each collection is Iterable

·迭代器是一种经典的设计模式，用于遍历数据结构，而无需暴露数据在数据结构中的存储细节。Iterator is a classic design pattern for walking through a data structure without having to expose the details of how data is stored in the data structure

>它也用于增强型 `for` 循环，例如：Also used in for-each loops:

- Collection接口扩展了Iterable接口。

The Collection interface extends the Iterable interface

·你可以通过 Iterable接口中的 iterator()方法获取一个集合的迭代器对象，以遍历集合中的所有元素。iterator()方法返回一个 Iterator 的实例。You can obtain a collection Iterator object to traverse all the elements in the collection with the iterator() method in the Iterable interface which returns an instance of Iterator

2.2 AbstractCollection类

- AbstractCollection 类为 Collection 接口提供了部分实现（Collection 中的所有方法，除了 add、size 和 iterator方法）。The AbstractCollection class provides partial implementation for the Collection interface (all the methods in Collection except the add, size, and iterator methods)

3.列表List

3.1列表接口 The List Interface

- 列表集合以顺序方式存储元素，并允许用户指定元素的存储位置。

A list collection stores elements in a sequential order, and allows the user to specify where the element is stored

- 用户还可以通过索引访问元素。The user can also access the elements by index

- List 接口按顺序存储元素，并允许重复。

The List interface stores elements in sequence and permits duplicates

- 在 Java 集合框架中有两个具体的类：ArrayList 和 LinkedList。

Two concrete classes in Java Collections Framework: ArrayList and LinkedList

3.1.1具体方法

- set：替换指定位置上的元素，并返回被替换的元素

3.1.2 迭代器ListIterator

- listIterator() 和 listIterator(startIndex) 方法返回一个ListIterator的实例。

The listIterator() and listIterator(startIndex) methods return an instance of ListIterator

·ListIterator 接口扩展了 Iterator 接口，用于对列表进行双向遍历以及向列表中添加元素。The ListIterator interface extends the Iterator interface for bidirectional traversal of the list and add elements to the list

- 方法nextIndex()返回迭代器中下一个元素的索引，而 previousIndex() 方法返回迭代器中上一个元素的索引。The nextIndex() method returns the index of the next element in the iterator, and the previousIndex() returns the index of the previous element in the iterator

- 方法add(element) 会在 Iterator接口的 next() 方法将要返回的元素之前，将指定的元素插入到列表中。The add(element) method inserts the specified element into the list immediately before the next element that would be returned by the next() method defined in the Iterator interface

3.2 ArrayList 和 LinkedList

- ArrayList 类和 LinkedList 类是 List 接口的具体实现。

The ArrayList class and the LinkedList class are concrete implementations of the List interface

·列表的大小可以动态增长或缩小，而数组一旦创建，其大小就是固定的。

A list can grow or shrink dynamically While an array is fixed once it is created

·如果您的应用程序不需要插入或删除元素，那么数组是最高效的数据结构。If your application does not require insertion or deletion of elements, the most efficient data structure is an array

3.2.1 java.util.ArrayList

- 通过数组实现，例如，在指定索引处插入新元素之前，需要将该索引之后的所有元素向右移动，并将 `ArrayList` 的大小增加 1。Implemented with arrays, e.g., before inserting a new element at a specified index, shift all the elements after the index to the right and increase the ArrayList size by 1

3.2.2 java.util.LinkedList

- 链表中的节点 Nodes in Linked Lists

·链表由节点组成：A linked list consists of nodes:

>每个节点包含一个元素/值，并且每个节点都链接到它的下一个邻居。

Each node contains an element/value, and each node is linked to its next neighbor:

·可以将节点定义为一个类，如下所示：A node can be defined as a class, as follows:

3.2.3 ArrayList 与LinkedList 区别

- 关键区别在于内部实现方式，这会影响它们的性能。The critical difference between them pertains to internal implementation, which affects their performance.

·如果您需要通过索引支持随机访问，且不需要在列表末尾以外的任何位置插入或删除元素，那么 ArrayList 是最高效的选择。If you need to support random access through an index without inserting or removing elements from any place other than the end, ArrayList offers the most efficient collection

·如果您的应用程序需要在列表的开头插入或删除元素，那么您应该选择 LinkedList。If your application requires the insertion or deletion of elements from at the beginning of the list, you should choose LinkedList

3.2.4使用 ArrayList 和 LinkedList

- 示例演示

·创建了一个填充了数字的 ArrayList，并在列表的指定位置插入新元素。

·从 ArrayList 创建了一个LinkedList，并在列表中插入和删除元素。

·正向和反向遍历列表。

- 对于链表来说，虽然可以使用get(i)方法，但通过索引查找每个元素是一个更耗时的操作。 The get(i) method is available for a linked list, but it is a more time-consuming operation to find each element

·相反，你应该使用迭代器或增强型 `for` 循环（`for-each` 循环） Instead you should use an iterator or for-each loops:

3.3Vector及其拓展得到的Stack类

- 早期数据格式，这些类被重新设计以融入 Java 集合框架，但为了兼容性，它们的旧式方法仍然被保留。These classes were redesigned to fit into the Java Collections Framework, but their old-style methods are retained for compatibility

3.3.1向量类The Vector Class

- 向量类（Vector）与数组列表（ArrayList）类似，区别在于它包含用于访问和修改向量的同步方法。Vector is the same as ArrayList, except that it contains synchronized methods for accessing and modifying the vector

·同步方法可以在多个线程同时访问和修改向量时防止数据损坏。Synchronized methods can prevent data corruption when a vector is accessed and modified by two or more threads concurrently

>到目前为止讨论过的类都不包含同步方法。None of the classes discussed until now are synchronized

·对于许多不需要同步的应用程序，使用数组列表（ArrayList）比使用向量类（Vector）更高效。For many applications that do not require synchronization, using ArrayList is more efficient than using Vector

- 从Java 2版本保留下来的方法：

·addElement(Object element)方法与add(Object element)方法功能相同，区别在于addElement方法是同步的。addElement(Object element) is the same as the add(Object element) method, except that the addElement method is synchronized

- Enumeration 是早期 Java 提供的接口，用于按顺序访问集合中的元素（类似 Iterator）

3.3.2栈类The Stack Class

- 栈类（Stack）表示一个后进先出（LIFO）的对象栈。元素只能从栈顶进行访问。The Stack class represents a last-in-first-out stack of objects. The elements are accessed only from the top of the stack

·你可以通过push(o:E)方法将元素压入栈顶，通过peek()方法查看栈顶元素，通过pop()方法移除栈顶元素。You can insert with push(o:E), retrieve with peek() and remove with pop() (all from the top of the stack)

- 栈是通过扩展向量类（Vector）实现的。Stack is implemented as an extension of Vector

- 从Java 2版本保留下来的方法：

·empty()方法与isEmpty()方法功能相同。empty() method is the same as isEmpty()

4.队列 Queues

- 队列是一种先进先出（FIFO）的数据结构：A queue is a first-in/first-out data structure

·元素被追加到队列的末尾，并从队列的开头移除。Elements are appended to the end of the queue and are removed from the beginning of the queue

>使用offer(o:E)方法将元素添加到队列中。此方法类似于集合接口（Collection interface）中的add方法，但对于队列，更推荐使用offer方法。The offer(o:E) method is used to add an element to the queue .This method is similar to the add method in the Collection interface, but the offer method is preferred for queues

>poll方法和remove方法类似，区别在于当队列为空时，poll()会返回null，而remove()会抛出异常。The poll and remove methods are similar, except that poll() returns null if the queue is empty, whereas remove() throws an exception

>peek方法和element方法类似，区别在于当队列为空时，peek()会返回null，而element()会抛出异常。The peek and element methods are similar, except that peek() returns null if the queue is empty, whereas element() throws an exception

- 在优先队列中，元素会被分配优先级。在访问元素时，优先级最高的元素会最先被移除。In a priority queue, elements are assigned priorities When accessing elements, the element with the highest priority is removed first

4.1队列接口The Queue Interface

- 队列接口扩展了java.util.Collection，增加了额外的插入、提取和检查操作。

Queue interface extends java.util.Collection with additional insertion, extraction, and inspection operations

4.2双端队列接口（Deque）

- 双端队列接口支持在队列的两端插入和移除元素。 Deque interface supports element insertion and removal at both ends

·Deque”是“double-ended queue”（双端队列）的缩写。 The name deque is short for “double-ended queue”

·双端队列接口扩展了队列接口（Queue），并增加了从队列两端插入和移除元素的额外方法。 The Deque interface extends Queue with additional methods for inserting and removing elements from both ends of the queue

·双端队列接口中定义了以下方法：

>addFirst(e)`：在队列头部插入元素

>`removeFirst()`：移除队列头部的元素

>`addLast(e)`：在队列尾部插入元素

>`removeLast()`：移除队列尾部的元素

>`getFirst()`：获取队列头部的元素

>`getLast()`：获取队列尾部的元素

4.3优先队列 --> java.util.PriorityQueue<T>

- 默认情况下，优先队列根据元素的自然顺序（通过`Comparable`接口）对其元素进行排序。

By default, the priority queue orders its elements according to their natural ordering using Comparable

- 值最小的元素被分配最高的优先级，因此会首先从队列中移除。 The element with the least value is assigned the highest priority and thus is removed from the queue first

- 如果有多个元素具有相同的最高优先级，则会随机打破平局。If there are several elements with the same highest priority, the tie is broken arbitrarily

- 你也可以在构造函数中通过`Comparator`指定排序顺序。You can also specify an ordering using Comparator in the constructor

PriorityQueue(initialCapacity, comparator)

4.4 LinkedList

- LinkedList 是队列的具体实现类，它支持从列表的两端插入和移除元素。LinkedList is the concrete class for queue and it supports inserting and removing elements from both ends of a list

·LinkedList 类实现了 Deque 接口，而 Deque 接口扩展了 Queue 接口。The LinkedList class implements the Deque interface, which extends the Queue interface

5.集合Set

5.1基础概念

- 集合(Set)接口是集合(Collection)接口的子接口。Set interfaceis a sub-interface of Collection

·它扩展了集合(Collection)接口，但没有引入新的方法或常量。It extends the Collection, but does not introduce new methods or constants.

·然而，集合(set)接口规定，集合(set)的实例不能包含重复的元素。However, the Set interface stipulates that an instance of Set contains no duplicate elements

- 可以使用它的三种具体类之一来创建一个集合：HashSet、LinkedHashSet 或 TreeSet。

can create a set using one of its three concrete classes: HashSet, LinkedHashSet, or TreeSet

·实现集合(set)接口的具体类必须确保无法将重复的元素添加到集合中(set)。The concrete classes that implement Set must ensure that no duplicate elements can be added to the set

>HashSet和LinkedHashSet使用：hashCode() + equals()。

>TreeSet使用：compareTo()或Comparable。

5.2 HashSet

- HashSet 类是一个实现了Set接口的具体类。The HashSet class is a concrete class that implements Set

5.2.1 : 创建Creation

- 你可以使用它的无参构造函数来创建一个空的哈希集合。

Set<String> set = new HashSet<>()；

·第一个菱形操作符（“<>”）被称为类型参数或泛型类型。它指定了 HashSet将要存储的元素类型。在这个例子中，HashSet 被指定为存储String 类型的对象。The first diamond operation ("<>") is called a type parameter or generic type. Itspecifiesthe type of elementsthat the HashSet willstore. In this case, the HashSet isspecified to store objects of type String

·在第二个菱形操作符（“<>”）中，编译器会根据上下文推断泛型类型，这通常与第一个菱形操作符中指定的类型相同（仅在简单情况下）。In the 2nd diamond operation ("<>"),the compiler infersthe generic type from the context, which istypically the same asthe type specified in the first diamond operator (Just in simple cases)

·括号（“()”）用于调用HashSet类的构造函数。在这个例子中，它调用了 HashSet 类的无参构造函数，该构造函数创建了一个空的集合。The parentheses("()") is used for calling the constructor of the HashSet class. In this case, it is calling the no- argument constructor of the HashSet class, which creates an empty set.

- 你可以从一个现有的集合(collection)创建一个哈希集合。You can create a hash set from an existing collection

List<String> list = Array.aslist(“apple”)

HashSet<String> hashset = new hashSet<>(list);

·我们有一个字符串列表 We have a List of strings

·<String>，由于列表的类型 <String>, becasue of the list type

·<>，仍然与上面预指定的类型相同。<> ,stillsame asthe pre-specificed type above

·这个列表将被传递到括号中。 the list will be passed to the parentheses

- 你可以创建一个空的 HashSet，并指定其初始容量或初始容量加上加载因子。You can an empty HashSet with the specified initial capacity only or initial capacity plus loadFactor

int initialCapacity =16;

float loadFactor = 0.74f;

HasgSet<String> hashset1 = new HashSet<>(initialCapacity);

HashSet<Strinf> hasgset = new HashSet<>(initialCapacity ,loadFactor );

·默认情况下，初始容量是16，加载因子是0.75。By default, the initial capacity is 16 and the load factor is 0.75

·加载因子的范围是从0.0到1.0，用于衡量集合在容量增加（加倍；×2）之前被允许填充的程度。Loadfactor rangesfrom 0.0 to 1.0, measuring how full the set is allowed to be before its capacity is increased (doubled; x2)

5.2.2 方法

- 接口(Collection)和抽象类(AbstractSet)将由具体类(HashSet、LinkedHashSet、TreeSet）实现或扩展。因此，所有声明的方法（例如，add()、remove()`等）都可以在集合实例中被调用。The interfaces(e.g., Collection) and abstract classes(e.g., AbstractSet) will be implemented/extended by the concrete classes(i.e., HashSet, LinkedHashSet, TreeSet). So, all the declared methods(e.g., add(), remove(), etc) can be called in a set instance

5.2.2.1add()：向集合中添加元素 Adding elementsto set

- 哈希集合是无序的（因为使用了哈希机制）且不允许重复 A hash set is unordered (because of hashing) and，is non-duplicated

- 哈希集合使用hashCode( )的equals( )方法来检查重复项。（需要实现 equals( )方法才行）

A hash set use hashcode() and equals() to check duplication

·这两个方法是“内置”的，因为它们是 Java 标准 String 类的一部分（与其他来自 Java 标准库的对象，如Integer一样）。These 2 methods are "built-in" in the String object, asthey are part of the standard String classin Java (Same as other objectsfrom the standard Java library like Integer)

5.2.2.2 增强型for循环 Enhanced for loop

- 集合接口扩展了可迭代接口（Iterable interface），因此集合中的元素是可迭代的。

Collection interface extends the Iterable interface , so the elements in a set are iterable

- 方法1：增强型for循环 Enhanced for loop

for (declaration : expression) {

// Statements}

·声明：用于声明一个变量，该变量将保存你正在迭代的数组或集合中的元素。Declaration: the part where you declare a variable that will hold an element of the array or collection you're iterating over

·表达式：你想要迭代的集合或数组；目标。Expression: the collection or array you want to iterate over; the target

·使用增强型for循环是因为哈希集合是无序的，没有索引（没有 [i]）。

Enhanced for loop is used because a hash set is unordered without index (No [i])

- 方法2：forEach()方法

·这是 Iterabl接口中的一个默认方法。A default method in the Iterable interface

Set.forEach(e -> System.out.print(e))`

>’e’是传递给 lambda 表达式的参数。它代表集合中的当前元素。e isthe parameter passed to the lambda expression. It representsthe current element of the set

> ‘->’ 是 lambda 箭头，它将 lambda 表达式的参数与其主体分开。

-> isthe lambda arrow which separatesthe parameters of the lambda expression from its body

5.2.2.3其它方法：

- remove()：从集合中删除一个字符串 Delete a string from set1

- size()：集合的大小the size of the set

- contains()：如果集合包含某个特定的元素，返回真/假 if the set contains a certain element, return T/F

- addAll()：将集合中的元素添加到另一个集合中，不包含重复项！会调用 hashCode()和 equals() 方法add the elements in seti and set2 together. NO DUPILICATION! hashcode() and equals () are called

- removeAll()：从集合中移除另一个集合中的元素removing the elements in set 2 from set1

- retainAll()：保留两个集合的交集

5.3 LinkedHashSet：

- 基础概念

·LinkedHashSet继承自 HashSet,并实现了一个链表,这个链表支持集合中元素的排序LinkedHashSet extends HashSet with a linked list implementation that supports an ordering of the elements in the set

·它与我们之前了解的 HashSet 非常相似（例如，集合的创建和可以调用的方法）都适用于 LinkedHashSet。Very similar to HashSet, those we have acquired previously (e.g., the set creation and the methods can be called) are applicable to LinkedHashSet

·显著的区别：LinkedHashSet 中的元素可以按照它们被插入集合的顺序被检索。Significant Difference: The elements in a LinkedHashSet can be retrieved in the order in which they were inserted into the set

- 示例：

5.4 SortedSet

- 基本概念：SortedSet是 Set 的一个子接口，它保证集合中的元素是排序的。

SortedSet is asub-interface of Set, which guarantees that the elements in the set are sorted

- 常用方法：

·first()：返回集合中的第一个元素。return the first element in the set

·last()：返回集合中的最后一个元素。return the last element in the set

·headSet()：查找小于或等于给定元素 find the elementsthat are lessthan or equal to the given toElement

·tailSet()：查找大于或等于给定元素 find the elementsthat are equal to or bigger than the given toElement

5.5 NavigableSet

- 基本概念:NavigableSet 扩展了 SortedSet，提供了导航方法（例如,lower(e),floor(e)等）

NavigableSet extends SortedSet to provide navigation methods (e.g., lower(e), floor(e),etc)

- 常用方法：

·lower()：返回集合中严格小于给定元素的最大元素。Returns the greatest element in thissetstrictly lessthan the given element

·higher()：返回集合中严格大于给定元素的最小元素。Returnst he least element in thissetstrictly greater than the given element

·floor()：返回集合中小于或等于给定元素的最大元素。Returns the greatest element in thisset lessthan or equal to the given element

·ceiling()：返回集合中大于或等于给定元素的最小元素。Returns the least element in thisset greater than or equal to the given element

·pollFirst()：检索并移除第一个（最小）元素。Retrieves and removesthe first (lowest) element

·pollLast()：检索并移除最后一个（最大）元素。Retrieves and removesthe last (highest) element

5.6TreeSet：

- 基本概念：

TreeSet是一个具体类，实现了SortedSet和NavigableSet接口。TreeSet is a concrete class that implements the SortedSet and NavigableSet interfaces

5.6.1创建：

- 无参数的空TreeSet,其元素将根据元素的自然顺序升序排序.(由于实现了SortedSet接口)

Empty tree set without arguement, which will be sorted in ascending order according to the natural ordering of its elements. (Due to the implementation of SortedSet interface)

TreeSet<String> treeSet = new TreeSet<>();

- 使用其他集合创建的 TreeSet，其元素将根据自然顺序排序。Tree set with other collections, being sorted by the natural ordering.

TreeSet<String> treeSet = new TreeSet<>(list);

- 使用自定义比较器的 TreeSet，其中我们可以定义排序顺序。

Tree set with customized comparator,where we can define the orders

TreeSet<String> treeSet = new TreeSet<>(Comparator.reverseOrder());

- 与指定的已排序集合具有相同元素和相同排序的TreeSet。

Tree set with the same elements and the same ordering asthe specified sorted set

// 如果我们已经有一个根据特定规则排序的集合

SortedSet<String> originalSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);

// 我们可以通过这种方式创建另一个具有相同元素和相同排序的TreeSet

TreeSet<String> copiedSet = new TreeSet<>(originalSet);

5.6.2 add()方法

- 类似于哈希集合，重复的元素不会被添加到树集合中。Similar to a hash set, the duplicted elements would not be added to the tree set

- 这不是因为hashCode()和 equals()方法，而是由于 Java 标准库中 String和 Integer以及其他包装类中“内置”的compareTo() 方法。Instead of hashcode() and equals(), thisis because the “built-in” compareTo() in String and Integer and other wrapper classesin Java'sstandard library.

- 区别在于底层数据结构，哈希集合 -> 哈希，树集合 -> 树The difference is due to the bottomed data structure, hash set -> Hashing , tree set -> Tree

5.7总结

- HashSet、LinkedHashSet 和 TreeSet 都是 Java 中 Set接口的实现，这意味着它们都具有不允许重复元素的基本特性。HashSet, LinkedHashSet, and TreeSet are all implementations of the Set interface in Java, which meansthey all share the fundamental characteristic of not allowing duplicate elements.

- HashSet：

·排序：它不保证任何迭代顺序。Ordering: It does not guarantee any order of iteration

·内部结构：由哈希表支持。Internal Structure: Backed by a hash table

- LinkedHashSet：

·排序：维护一个贯穿其所有条目的双向链表，这定义了迭代顺序，通常是元素被插入到集合中的顺序（插入顺序）。Ordering: Maintains a doubly-linked list running through all its entries, which definesthe iteration ordering, which is normally the order in which elements were inserted into the set (insertion-order).

·内部结构：由带有贯穿它的链表的哈希表支持 Internal Structure: Backed by a hash table with a linked list running through it

- TreeSet：

·排序：保证元素将根据元素的自然顺序或在集合创建时提供的比较器按升序排序。Ordering: Guaranteesthat elements will be sorted in ascending element order, according to the natural ordering of the elements, or by a Comparator provided atset creation time

·内部结构：由树支持。Internal Structure: Backed by a tree

6.地图 map

6.1基础概念

- 地图（Map）是一个容器对象，用于存储键/值对的集合。A map is a container object thatstores a collection of key/value pairs.

- 它可以通过键来快速检索、删除和更新这对键/值。映射存储值的同时也会存储键。It enablesfast retrieval, deletion, and updating of the pair through the key. A map storesthe values along with the keys.

- 在列表（List）中，索引是整数。在地图（Map）中，键可以是任何对象。In List, the indexes are integers. In Map, the keys can be any objects.

·地图不能包含重复的键。A map cannot contain duplicate keys.

·每个键映射到一个值。Each key maps to one value.

6.2三种类型

- 有三种类型的字典：HashMap、LinkedHashMap 和 TreeMap。

·它们仍然确保映射实例通过 hashCode() 和 equals()（对于 HashMap 和 LinkedHashMap）以及 compareTo()/Comparator（对于 TreeMap）来保证键的唯一性。

Still, they ensure the map instances non- duplicated using hashcode() and equals() (for HashMap and LinkedHashMap) as well asthe compareTo()/Comparator (for TreeMap).

● HashMap、LinkedHashMap 和 TreeMap 类是 Map 接口的三种具体实现，其中 TreeMap 还额外实现了 SortedMap 和NavigableMap接口。The HashMap, LinkedHashMap, and TreeMap classes are three concrete implementations of the Map interface, with TreeMap additionally implements SortedMap and NavigableMap

6.3创建

- 我们可以使用带参数（m：Map<? extends K,? extends V>）的方式来创建新的哈希映射（HashMap）、链接哈希映射（LinkedHashMap）或树映射（TreeMap）。We can create new hash/linked hash/tree maps with arguement (m: Map<? extends K,? extends V>)

- 这表明构造函数接受一个 Map<X, Y> 类型的参数，其中 X 是 K 的子类型，Y 是 V 的子类型。

It indicatesthat the constructor accepts a Map <X, Y> (i.e.,smallMap) where X is a subclass of K, and Y is a subclass of V (See figure).

- 当 X 完全等于 K，Y 完全等于 V 时，这种方法同样适用。

It would also work when X is exactly K, and Y is exactly V

·Map<Integer, String> smallMap = new HashMap<>();

·Map<Integer, String> largerMap = new HashMap<>(smallMap);

- 通常，类似于 LinkedHashSet，LinkedHashMap 通过链表实现扩展了 HashMap，支持按插入顺序检索元素。Usually, and similar to LinkedHashSet, LinkedHashMap extends HashMap with a linked-list implementation thatsupportsretreiving elementsin the insertion order.

- 在 LinkedHashMap中，有一个构造函数参数（initialCapacity：int，loadFactor：float，accessOrder：boolean）。In LinkedHashMap, there is a constructor arguement (initialCapacity: int, loadFactor: float, accessOrder: boolean)

- 一旦设置为LinkedHashMap(initialCapacity, loadFactor, true)，创建的 LinkedHashMap将允许我们按照元素最后被访问的顺序来检索它们，从最近最少访问到最近最多访问的顺序（访问顺序）。Once it isset to be LinkedHashMap(initialCapacity, loadFactor, true), the created LinkedHashMap would allow usto retreive elements in the order in which they were last accessed, from least recently to most recently accessed (access order)

6.4特征

- 哈希映射是无序的，类似于哈希集合。A hash map is unordered, similar to a hash set

- 树映射按涉及元素的键排序（在这种情况下是按字母顺序）。

A tree map is ordered by the keys of the involved elements (alphabetically in this case)

- 链接哈希映射可以按插入顺序排序，也可以按访问顺序排序（`accessOrder: true`）。

A linked hash map can be ordered by the insertion order, and by the access order (accessOrder: True)

6.5方法：

- get()：返回指定键映射的值。Returns the value to which the specified key is mapped

- forEach()：对映射中的每个条目执行给定操作，直到所有条目都已处理完毕或操作抛出异常。Performs the given action for each entry in this map until all entries have been processed or the action throws an exception

void forEach(BiConsumer<? super K, ? super V> action)

·不返回任何内容（void），只执行操作。return nothing (void), just perform the action

·K是映射的键，V 是映射的值。K is the map’s key, V is the map’s value

·基本上，forEach((key, value) -> action)。Basically, forEach( (key,value) -> action )

7. 列表和集合的静态方法Static Methods for Lists and Collections

- java.util.Collections类包含用于在集合或列表中执行常见操作的静态方法。The java.util.Collections class contains static methods to perform common operations in a collection or a list

·用于集合的方法包括：max、min、disjoint 和 frequency。

·用于列表的方法包括：sort、binarySearch、reverse、shuffle、copy 和 fill。

- Collections 类的 UML 图

- Collections类其他有用的静态方法：

·rotate(List list, int distance)：将列表中的所有元素按指定距离旋转。

·replaceAll(List list, Object oldVal, Object newVal)：将列表中所有指定值的出现替换为另一个值。

·indexOfSubList(List source, List target)：返回源列表中第一个与目标列表相等的子列表的索引。

·lastIndexOfSubList(List source, List target)：返回源列表中最后一个与目标列表相等的子列表的索引。

·swap(List list, int i, int j)：在指定列表中交换指定位置的元素。

·addAll(Collection<? super T> c, T... )：将指定数组中的所有元素添加到指定集合中。

7.1集合类中用于列表的静态方法

- 排序：Sorting

·增序排序

>输出结果是：`[blue, green, red]`

·降序排序，使用 Collections.reverseOrder()

>输出结果是：`[red, green, blue]`

·声明

>static <T extends Comparable<? super T>> void sort(List<T> list)

使用 Comparable 接口中的 compareTo方法对列表进行排序。uses the compareTo method in the Comparable interface

>static <T> void sort(List<T> list, Comparator<? super T> c)

使用 Comparator 接口中的 compare方法对列表进行排序。uses the compare method in the Comparator interface

- 二分查找Binary search:

·你可以使用 binarySearch 方法在已排序的列表中查找一个键值。You can use the binarySearch method to search for a key in a sorted list

·要使用此方法，列表必须按升序排列。To use this method, the list must be sorted in increasing order

·如果键值不在列表中，该方法会返回 -(键值应插入的点 + 1)。If the key is not in the list, the method returns -(insertion point + 1)

- 反转列表Reverse

·代码输出：[blue, green, red, yellow]

- 随机打乱Shuffle

·你也可以使用 `shuffle(List, Random)` 方法，通过指定的 `Random` 对象随机重新排列列表中的元素。You can also use the shuffle(List, Random) method to randomly reorder the elements in a list with a specified Random object.

·使用指定的 Random 对象随机打乱列表，便于实现可重复的随机打乱或在多线程环境中使用。

- 拷贝：copy(dest, src)：

·将一个源列表中的所有元素复制到目标列表的相同索引位置 copy(dest, src): copy all the elements from a source list to a destination list on the same inde

>list1的输出结果是：[white, black, green, blue]

·copy方法执行的是浅拷贝：仅复制源列表中元素的引用，而不是元素本身的副本。如果源列表和目标列表中的元素是可变对象，那么修改这些对象的内容会影响两个列表中对应的元素。

The copy method performs a shallow copy: only the references of the elements from the source list are copied

·如果目标列表比源列表小，那么我们会遇到一个运行时错误。If the destination list is smaller than the source list then we get a runtime error:

- asList方法

·用于从可变长度的参数列表中创建一个列表。creating a list from a variable-length list of arguments

>返回的是一个由 Arrays 类内部定义的内部类对象的 List 引用：`java.util.Arrays$ArrayList`。它也被称为 `ArrayList`，但实际上只是一个数组的包装器。

returns a List reference of inner class object defined within Arrays : java.util.Arrays$ArrayList, which is also called ArrayList but it is just a wrapper for an array

- nCopies(int n, Object o) 方法

·创建一个不可变的列表，该列表由指定对象的 n个副本组成。create an immutable list that consists of n copies of the specified object

>list1` 是一个包含三个 `Calendar` 对象的列表。

>通过 `nCopies` 方法创建的列表是不可变的，因此你无法在列表中添加或删除元素——所有元素都指向同一个引用！The list created from the nCopies method is immutable, so you cannot add/remove elements in the list ---All the elements have the same reference!

>`list1` 是 `Collections` 类的一个内部类的实例：`java.util.Collections$CopiesList`。

list1 is an instance of an inner class of Collections: class java.util.Collections$CopiesList

- fill(List list, Object o)方法

·将列表中的所有元素替换为指定的元素。replaces all the elements in the list with the specified element

>输出：`[black, black, black]`

- max和min方法

·用于在集合中查找最大和最小的元素。find the maximum and minimum elements in a collection

- disjoint(collection1, collection2)方法

·用于判断两个集合是否没有任何共同的元素。如果没有共同元素，则返回 `true`。

returns true if the two collections have no elements in common

- frequency(collection, element) 方法

·用于查找指定元素在集合中的出现次数。finds the number of occurrences of the element in the collection

·过程中使用的是 .equal 方法

8.集合和列表的表现

- 集合(set)比列表更适合存储无重复元素。Sets are more efficient than lists for storing nonduplicate elements

- 列表通过索引访问元素很有用。Lists are useful for accessing elements through the index

- 集合不支持索引，因为集合中的元素是无序的。Sets do not support indexing because the elements in a set are unordered

- 要遍历集合中的所有元素，可以使用增强型for循环或迭代器。To traverse all elements in a set, use a for-each loop or iterator

9.比较器接口 The Comparator Interface

- 有时，你可能需要比较那些不是 Comparable 类型的实例，或者按照与 Comparable 不同的标准进行比较。Sometimes you want to compare the elements that are not instances of Comparable or by a different criteria than Comparable

- 你可以定义一个比较器（Comparator）来比较这些元素。You can define a Comparator to compare these elements

·定义一个实现了 java.util.Comparator<T> 接口的类。Define a class that implements the java.util.Comparator<T> interface

·Comparator接口包含两个方法：compare 和 equals。The Comparator interface has two methods: compare and equals

public int compare(T element1, T element2)

>如果 `element1` 小于 `element2`，返回负值；

>如果 `element1` 大于 `element2`，返回正值；

>如果两者相等，返回零。

- 例子：