路的开始
今天我想谈谈“
Java集合框架”这样一个有趣的话题，或者简单地说，关于集合。代码的大部分工作是以一种或另一种形式处理数据。获取用户列表、获取地址列表等。以某种方式对它们进行排序、执行搜索、比较它们。这就是为什么收藏知识被认为是核心技能的原因。这就是为什么我想谈谈它。此外，Java 开发人员面试中最常见的问题之一是集合。例如，“绘制集合的层次结构”。在线编译器将帮助我们。例如，您可以使用“ Tutorialspoint
Online Java Compiler ”或
Repl.it。了解任何数据结构的路径都是从普通变量（变量）开始的。在 Oracle 网站上，各种主题都表示为“路径”或“踪迹”。因此，了解 Java 的路径称为“
Trail：学习 Java 语言：目录”。语言的基础知识（即语言基础知识）从变量开始。因此，我们来写一段简单的代码：
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
它在所有方面都很好，只是我们知道这段代码只对一个变量来说是好的和漂亮的。如果有多个怎么办？数组的发明是为了存储一种类型的数据。在 Oracle 的同一 Trail 中，有一个单独的部分专门介绍数组。本节称为：“
数组”。使用数组也非常简单：
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
数组解决了在一个地方存储多个值的问题。但它有一个限制：数组大小是恒定的。如示例所示，如果我们说 size = 2，则它等于 2。就这样。如果我们想要更大的数组，我们需要创建一个新实例。另外，对于数组来说，查找元素也是一件棘手的事情。有一个方法
Arrays.binarySearch，但此搜索仅适用于已排序的数组（对于未排序的数组，结果是未定义的或根本不可预测）。也就是说，搜索将迫使我们每次都进行排序。删除也只会清除该值。因此，我们仍然不知道数组中实际有多少数据，我们只知道数组中有多少个单元格。刷新您有关数组的知识：
作为 Java 语言发展的结果，Java Collections Framework 出现在 JDK 1.2 中，我们今天将讨论它。
收藏
从一开始就开始计算成本。为什么要收藏？该术语本身来自“类型理论”和“抽象数据类型”等内容。但如果你不看什么高大上的东西，那么当我们有几个东西的时候，我们就可以称它为“东西的集合”。收集物品的人。一般来说，“收集”一词本身来自拉丁语。collectio “收集，收集”。也就是说，集合是某物的集合，是某些元素的容器。所以我们有一个元素的集合。我们可能想用它做什么：
正如你所看到的，我们可能想要非常合乎逻辑的东西。我们还了解我们可能想要对多个集合执行某些操作：
因此，Java 开发人员编写了java.util.Collection接口来描述所有集合的一般行为。Collection 接口是所有集合的起源处。集合是一种思想，它是所有集合应该如何表现的思想。因此，术语“集合”被表达为接口。当然，接口需要实现。接口
java.util.Collection有一个抽象类
AbstractCollection，即一些“抽象集合”，它代表其他实现的骨架（如类上方的 JavaDoc 中所写
java.util.AbstractCollection）。说到集合，让我们回过头来记住我们想要迭代它们。这意味着我们要逐一迭代元素。这是一个非常重要的概念。因此，该接口
Collection继承自
Iterable. 这非常重要，因为... 首先，所有 Iterable 都必须能够根据其内容返回一个 Iterator。其次，所有 Iterable 都可以在循环中使用
for-each-loop。正是在迭代器的帮助下实现了、、
AbstractCollection等方法。理解集合的路径始于最常见的数据结构之一 - 列表，即 。
containstoArrayremoveList
列表
因此，列表在集合的层次结构中占据着重要的位置：
正如我们所看到的，列表实现了
java.util.List接口。列表表示我们有一个按某种顺序依次排列的元素的集合。每个元素都有一个索引（就像在数组中一样）。通常，列表允许您拥有具有相同值的元素。正如我们上面所说，
List它知道元素的索引。这允许您通过索引获取 (
get) 元素或为特定索引 ( ) 设置值
set。集合方法
add、
addAll、
remove允许您指定执行它们的索引。此外，y
List有自己的迭代器版本，称为
ListIterator。该迭代器知道元素的索引，因此它不仅可以向前迭代，还可以向后迭代。它甚至可以从集合中的特定位置创建。在所有的实现中，最常用的有两种：
ArrayList和
LinkedList。首先，它是一个基于数组（）的
ArrayList列表（）。这允许您实现
对元素的“随机访问”。随机访问是指立即通过索引检索元素的能力，而不是迭代所有元素，直到找到具有所需索引的元素。正是以数组为基础才能实现这一点。相反，它是一个链表。链表中的每个条目都以 形式表示，该形式存储数据本身，以及指向下一个 (next) 和上一个 (previous) 的链接。从而实现“顺序访问
”。很明显，要找到第 5 个元素，我们必须从第一个元素到最后一个元素，因为 我们无法直接访问第五个元素。我们只能从第四个元素访问它。它们概念上的区别如下：
ListArrayLinkedListEntryEntryLinkedList
正如你所理解的，在工作中也存在差异。例如，添加元素。这些
LinkedList元素就像链条中的链接一样简单地连接起来。但
ArrayList它将元素存储在数组中。正如我们所知，数组不能改变它的大小。那么它是如何运作的呢
ArrayList？而且它的工作原理非常简单。当数组空间用完时，它会增加1.5倍。这是缩放代码：
int newCapacity = oldCapacity + (oldCapacity >> 1); 操作上的另一个区别是元素的任何位移。例如，在中间添加或删除元素时。要从
LinkedList元素中删除，只需删除对此元素的引用即可。在 的情况下，
ArrayList我们每次都被迫使用 来移动元素
System.arraycopy。因此，元素越多，必须执行的操作就越多。更详细的描述可以在这些文章中找到：
研究过 ArrayList 后，我们不禁会想起它的“前身”，即
java.util.Vector类。它的不同之处
Vector在于
ArrayList使用集合的方法（添加、删除等）是同步的。也就是说，如果一个线程（
Thread）添加元素，那么其他线程将等待，直到第一个线程完成其工作。由于通常不需要线程安全，因此建议在这种情况下使用该类
ArrayList，如该类的 JavaDoc 中明确指出的那样
Vector。另外，
Vector它的尺寸增加的不是1.5倍，
ArrayList而是2倍。否则，行为是相同的 -
Vector隐藏数组形式的元素存储，并且添加/删除元素具有与 中相同的结果
ArrayList。事实上，
Vector我们记住这一点是有原因的。如果我们查看 Javadoc，我们将在“直接已知子类”中看到诸如
java.util.Stack之类的结构。堆栈是一个有趣的结构，它是一种 LIFO
last-in-first-out（后进先出）结构。Stack从英语翻译过来就是堆栈（比如一摞书）。堆栈实现了附加方法：
peek(look,look)、
pop(push)、
push(push)。该方法
peek翻译为look（例如，
peek inside the bag翻译为“
look inside the bag ”，
peek through the keyhole翻译为“
peek through the keyhole ”）。此方法允许您查看堆栈的“顶部”，即 获取最后一个元素而不将其从堆栈中删除（即不删除）。该方法
push将一个新元素压入（添加）到堆栈中并返回它，而元素方法将
pop压入（删除）并返回被删除的元素。在所有三种情况（即查看、弹出和推送）中，我们仅处理最后一个元素（即“堆栈顶部”）。这是栈结构的主要特点。顺便说一句，在《程序员的职业生涯》（破解编码面试）一书中描述了一个有趣的任务来理解堆栈。有一个有趣的任务，使用“堆栈”结构（LIFO），您需要实现“队列” ” 结构（先进先出）。它应该看起来像这样：
这个任务的分析可以在这里找到：《
Implement A Queue using Stacks - The Queue ADT》（LeetCode 上的“Implement A Queue Using Stacks”）。所以我们顺利地转向一种新的数据结构——队列。
队列
队列是我们生活中熟悉的结构。去商店、去看医生都要排队。谁先到（First In），谁就最先离开队列（First Out）。在 Java 中，队列由
java.util.Queue接口表示。根据队列的Javadoc，队列添加了以下方法：
正如您所看到的，有订单方法（无法执行它们会出现异常）和请求方法（无法执行它们不会导致错误）。也可以获取元素而不删除它（查看或元素）。队列接口还有一个有用的后继者 -
Deque。这就是所谓的“双向队列”。也就是说，这样的队列允许您从头到尾都使用这个结构。文档中说“Deques也可以用作LIFO（后进先出）堆栈。这个接口应该优先于遗留的Stack类使用。”，也就是说，建议使用Deque实现而不是使用堆。Javadoc 显示了 Deque 接口描述的方法：
让我们看看有哪些实现。我们会看到一个有趣的事实——LinkedList已经进入了队列阵营）也就是说，LinkedList同时实现了
List, 和
Deque。但也有“仅限队列”的情况，例如
PriorityQueue。她不常被人们记住，但却是徒劳的。首先，您不能在此队列中使用“不可比较的对象”，即 要么必须指定比较器，要么所有对象都必须具有可比较性。其次，“此实现为入队和出队方法提供了 O(log(n)) 时间”。对数复杂度的存在是有原因的。基于堆实现的PriorityQueue。Javadoc 说：“优先级队列表示为平衡的二进制堆。” 其存储本身是一个常规数组。必要时就会增长。当堆小时，增加2倍。然后是 50%。代码注释：“如果小则加倍；否则增长 50%”。优先级队列和二叉堆是一个单独的主题。因此，欲了解更多信息：
一个实现
java.util.Deque可以是
java.util.ArrayDeque类。即列表可以使用链表和数组来实现，队列也可以使用数组或链表来实现。
Queue和接口
Deque具有代表“阻塞队列”的后代：
BlockingQueue和
BlockingDeque。以下是与常规队列相比的接口变化：
让我们看一些阻塞队列的示例。但它们很有趣。例如，BlockingQueue 的实现方式有：
PriorityBlockingQueue、
SynchronousQueue、 ArrayBlockingQueue 、
DelayQueue、
LinkedBlockingQueue。但
BlockingDeque他们实现了标准集合框架中的所有内容
LinkedBlockingDeque。每个队列都是单独审查的主题。在本次审查的框架内，我们不仅将使用 来描述类层次结构
List，而且还将使用 来描述类层次结构
Queue：
从图中我们可以看出，Java Collections Framework 的接口和类是高度交织的。让我们添加层次结构的另一个分支 -
Set。
放
Set——翻译为“设置”。它与队列和列表的不同之处
Set在于它对元素存储的更大抽象。
Set- 就像一袋物体，我们不知道这些物体是如何定位的以及它们放置的顺序。
在 Java 中，这样的集合由java.util.Set接口表示。正如文档所说，
Set这是一个“不包含重复元素的集合”。有趣的是，接口本身并
Set没有向接口添加新的方法
Collection，而只是澄清了要求（关于哪些内容不应包含重复项）。此外，从前面的描述可以看出，您不能简单地
Set从中获取元素。迭代器用于获取元素。
Set还有几个与之相关的接口。第一个是
SortedSet。顾名思义，
SortedSet它表示这样的集合是有序的，因此元素实现接口
Comparable或被指定
Comparator。此外，
SortedSet它还提供了几种有趣的方法：
此外，还有方法
first（按值最小元素）和
last（按值最大元素）。有
SortedSet一个继承人——
NavigableSet。该界面的目的是描述更准确地识别适当元素所需的导航方法。有趣的是
NavigableSet，它为通常的迭代器（从最小到最大）添加了一个相反顺序的迭代器 -
descendingIterator。此外，
NavigableSet它还允许您使用该方法
descendingSet获取您自己的视图（View），其中的元素顺序相反。之所以这样称呼它，是
View因为通过结果元素，您可以更改原始元素的元素
Set。也就是说，本质上，它是原始数据以不同方式的表示，而不是它的副本。有趣的是
NavigableSet， 和 一样
Queue，可以处理
pollFirst（最小）和
pollLast（最大）元素。也就是说，它获取该元素并将其从集合中删除。有哪些具体的实现方式？首先，最著名的实现是基于哈希码 -
HashSet。另一个同样著名的实现是基于红黑树 -
TreeSet。让我们完成我们的图表：
在藏品中，仍然需要理清隐士的等级制度。乍一看，这是站在一边的 -
java.util.Map。
地图
映射是一种按键存储数据的数据结构。例如，密钥可以是 ID 或城市代码。正是通过这个键来搜索数据。有趣的是，这些卡片是分开展示的。根据开发人员的说法（参见“
Java Collections API Design FAQ ”），键值映射不是一个集合。映射可以更快地被认为是键的集合、值的集合、键值对的集合。这是一种非常有趣的动物。卡片提供哪些方法？让我们看一下 Java API 接口
java.util.Map。因为 由于映射不是集合（它们不继承自集合），因此它们不包含
contains. 这是合乎逻辑的。映射由键和值组成。该方法应该检查其中哪些
contains以及如何避免混淆？因此，该接口
Map有两个不同的版本：（
containsKey包含键）和
containsValue（包含值）。使用它
keySet可以让您获得一组密钥（相同的
Set）。并且使用该方法
values我们可以获取map中的值的集合。映射中的键是唯一的，这是数据结构所强调的
Set。值可以重复，这是Collection数据结构所强调的。另外，使用该方法
entrySet我们可以获得一组键值对。您可以在最详细的分析中阅读有关卡实现的更多信息：
我还想看看与和
HashMap非常相似的内容。它们甚至具有相似的界面：、和。所以我们的最终地图将如下所示：
HashSetTreeMapTreeSetNavigableSetNavigableMapSortedSetSortedMap
我们可以结束一个有趣的事实，集合
Set内部使用
Map，其中添加的值是键，并且值在各处都是相同的。这很有趣，因为它
Map不是一个集合并返回
Set，它是一个集合但实际上是作为 实现的
Map。有点超现实，但结果就是这样）
结论
好消息是这篇评论到这里就结束了。坏消息是这是一篇评论性很强的文章。每个集合的每个实现都值得一篇单独的文章，对于我们看不见的每个算法也是如此。但本次审查的目的是记住它们是什么以及接口之间的连接是什么。我希望经过深思熟虑的阅读后，你能够凭记忆画出集合的图表。
好吧，像往常一样，一些链接：
#维亚切斯拉夫
GO TO FULL VERSION