使用集合的技巧

一、藏品清单

您可能还记得，Java 有集合——一种用于存储相同类型对象的便捷工具。

让我们试着回忆一下与集合相关的主要接口：

列表、集合、映射和队列。

像往常一样，工具不一定好或坏——重要的是您是否将它们用于预期目的。为此，我们必须彻底了解它们的具体功能，以便知道何时使用哪个集合。

1.清单

让我们从最常用的集合开始。

列出尽可能接近普通的旧数组。

这个集合让我们可以方便地存储相同类型的对象列表，而不用担心集合本身的大小，如果我们使用数组就必须担心。集合的元素通过索引访问。如果我们确切地知道一个对象在哪里并且需要经常访问它而不需要经常添加或删除元素，那么 List是理想的选择。

2.设置

Set具有完全不同的结构。

当我们需要存储唯一的对象时， Set是最合适的。例如，图书馆中的一组作者，其中每个作者都是唯一的。但是我们不能只是去从中获取任何特定的作者。Set让我们可以快速检查特定作者是否存在于我们的图书馆中，即我们可以检查Set中是否存在唯一对象。我们还可以遍历整个集合，访问每个元素，但这样做并不是最优的。

换句话说，对于我们的图书馆，一个Set可以代表所有唯一作者的集合，以快速检查是否存在任何特定作者。

3. 地图

地图更像是一个文件柜，每个文件都经过签名，可以存储单个对象或整个结构。在我们需要维护从一个值到另一个值的映射的情况下，应该使用Map 。

对于Map，这些关系称为键值对。

我们可以在我们的图书馆中使用这种结构，方法是将作者对象用作键，将书籍的列表（List对象）用作值。因此，在检查Set以查看图书馆中是否存在作者对象之后，我们可以使用相同的作者对象从Map中获取他或她的书籍的列表。

4.队列

Queue是一个集合——惊喜！— 实现队列的行为。队列可以是LIFO（后进先出）或FIFO（先进先出）。更重要的是，队列可以是双向的，或“双端”。

当添加到类中的对象需要按接收顺序使用时，此结构很有用。以我们的图书馆为例。

我们可以将新来的访客添加到队列中，并依次为他们服务，发放他们来找的书。

正如我们所看到的，如果用于其预期目的，这些结构中的每一个都是好的。我们在一个库示例中发现了所有四种类型的集合的良好用途。

2. 复杂性

如前所述，我们上面考虑的集合是接口，这意味着它们必须有实现才能让我们使用它们。

就像用显微镜敲钉子不是最好的主意一样，并非每个集合的实施都适合所有情况。

在为一项工作选择合适的工具时，我们通常会考虑两个特征：

• 该工具与工作的匹配程度如何？
• 它完成工作的速度有多快？

我们花了一些时间弄清楚如何为工作选择合适的工具，但它的速度是新事物。

在计算中，工具的速度通常用时间复杂度表示，并用大写字母 O 表示。

时间复杂度到底是什么？

简单来说，时间复杂度表示集合中的算法执行特定操作（添加/删除元素、搜索元素）所需的时间。

ArrayList 与 LinkedList

让我们使用List接口的两个实现 - ArrayList和LinkedList来看一下。

对于外观，使用这些集合是相似的：

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

如您所见，对于这两种集合类型，添加、获取和删除元素看起来是一样的。这是因为它们是同一接口上的实现。但这就是相似之处结束的地方。

由于它们对List接口的不同实现，这两个结构比其他结构更有效地执行不同的操作。

考虑删除和添加一个元素。

如果我们需要从ArrayList的中间删除一个元素，我们必须覆盖列表中我们删除的元素后面的任何部分。

假设我们有一个包含 5 个元素的列表，我们想要删除第 3 个元素。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

在这种情况下，移除释放了一个单元格，因此我们需要将第 4 个元素写入第 3 个元素，将第 5 个元素写入第 4 个元素。

这是非常低效的。

将元素添加到列表中间时也会发生同样的情况。

LinkedList 的结构不同。添加或删除元素很快，因为我们只需要更改前一个和下一个元素中的引用，从而从元素链中排除我们要删除的对象。

回到同样包含 5 个元素的列表示例，在删除第 3 个元素之后，我们需要做的只是将第 2 个元素的引用更改为下一个元素，将第 4 个元素的引用更改为前一个元素。

当一个元素被添加到列表中时，同样的过程发生，但相反。

请注意，与ArrayList相比，我们在LinkedList中需要做的工作要少得多。这只是 5 个元素。如果我们的列表有 100 个或更多元素， LinkedList的优越性将变得更加明显。

但是如果我们通过索引访问一个元素，情况会发生什么变化呢？

这里的一切都恰恰相反。

由于 ArrayList 的结构与普通数组相同，因此通过索引获取任何元素对我们来说都非常容易。我们只需将指针移动到某个地方，然后从相应的单元格中获取元素。

但是LinkedList根本不能那样工作。我们必须遍历列表的所有元素才能找到具有特定索引的元素。

我们是否应该尝试用大 O 来表达所有这些？

让我们从按索引访问元素开始。

在ArrayList中，无论元素在列表中的位置如何，这一步都会发生。无论是在结尾还是开头。

在这种情况下，时间复杂度将为O(1)。

在LinkedList中，我们必须遍历等于所需索引值的多个元素。

这种操作的时间复杂度为O(n)，其中 n 是我们需要的元素的索引。

在这里，您会看到我们放在大 O 括号中的数字对应于执行的操作数。

我们返回删除和添加的外壳？

让我们从链表开始。

因为我们不需要做大量的操作来添加或删除一个元素，而且这个操作的速度不以任何方式依赖于元素所在的位置，所以它的复杂度表示为 O(1)并表示保持不变。

ArrayList的这个操作的时间复杂度也是O(n)，我们称之为线性复杂度。

在具有线性复杂度的算法中，运行时间直接取决于要处理的元素数量。它还可能取决于元素的位置，是在列表的开头还是接近结尾。

时间复杂度也可以是对数的。这表示为O(log n)。

例如，考虑一个由 10 个数字组成的排序TreeSet 。我们想找到数字 2。

由于列表已排序并且不包含重复项，我们可以将其分成两半并检查哪一半包含所需的数字，丢弃不相关的部分然后重复此过程直到我们到达所需的元素。最终，我们将找到（或找不到）处理 log(n) 个元素后的数字。

下表总结了其余集合的时间复杂度。

现在我们有了一张显示流行集合的时间复杂度的表格，我们可以回答为什么在这么多集合中我们最常使用ArrayList、HashSet和HashMap的问题。

只是它们对于大多数任务来说是最有效的 :)