Java 开发人员访谈问答分析。第10部分

你好！成为某件事的大师需要多少小时？我经常听到这样的话：“要成为任何事情的大师，你需要花费一万个小时。” 一个可怕的数字，不是吗？ 不过，我想知道这是真的吗？我不断地试图弄清楚我已经投入了多少时间来掌握编程艺术。而当我跨过那珍贵的一万小时，成为大师时，我会感受到这种差异吗？还是我早已在不知不觉中跨过了它们？无论如何，要成为一名程序员，你不需要投入如此大量的时间。最重要的是明智地使用它。您的首要目标是通过面试。而且新人面试的时候，首先问的就是理论，所以你一定要很强。实际上，在准备面试时，你的任务就是发现自己在 Java 开发人员基础理论方面的所有差距，并用知识来弥补它们。今天我将在这件事上帮助你，因为我在这里继续分析最热门的问题。那么让我们继续吧！

89.ArrayList与LinkedList有何不同？

这是与HashMap内部结构问题一起最常见的问题之一。如果没有它，任何一次采访都是不完整的，因此它的答案应该是“从你的牙齿上弹下来”。除了明显的名称不同之外，它们的内部结构也有所不同。前面我们已经研究了ArrayList和LinkedList的内部结构，因此我不会详细介绍它们的实现细节。顺便提醒一下，ArrayList是基于内部数组实现的，根据需要根据公式增加：

<размерТекущегоМассива> * 3 / 2  + 1

同时，LinkedList是基于内部双向链表实现的，即每个元素都有一个到上一个和下一个的链接，不包括作为列表开头/结尾的值。人们喜欢以这样的形式问这个问题：“ ArrayList和LinkedList哪个更好？”，希望能抓住你。毕竟，如果你指出其中之一作为答案，那将是错误的答案。 相反，您应该澄清您所讨论的具体情况 - 索引访问或插入列表中间。根据答案，您将能够解释您的选择。我之前已经描述过ArrayList和LinkedList在某种情况下如何工作。让我们通过将它们放在同一页面上进行比较来总结这一点： 添加元素（add）

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

底线：在LinkedList 中，算法复杂度范围从O(1)到O(n/2)。也就是说，插入越接近列表的末尾或开头，速度就越快。同时，对于ArrayList来说，其范围从O(1)到O(n)：插入越接近列表末尾，速度越快。 设置元素 (set) 此操作将一个元素写入列表中的指定位置，覆盖前一个元素（如果有）。在LinkedList中，这个操作将类似于添加，因为 这里最大的困难是找到元素。重写元素将通过重写一对链接来进行，因此这里算法复杂度也将从O(1)到O(n/2)不等，具体取决于位置与列表末尾或开头的距离。此时，会在ArrayList中找到本次索引操作所需的单元格，并写入一个新元素。与此操作一样，索引搜索的算法复杂度为O(1)。 按索引获取元素 (get) 在LinkedList 中，获取元素将按照与搜索其他操作相同的原理进行 - 取决于距结束或开始的距离，即 从O(1)到O(n/2)。在ArrayList中，正如我之前所说，通过索引在数组中查找元素的复杂度为O(1)。 通过索引删除一个元素（remove） 对于LinkedList 来说，它的操作原理也适用于此：首先找到该元素，然后覆盖链接——该元素的邻居开始互相引用，失去对该元素的引用，这随后将被垃圾收集器删除。也就是说，算法复杂度仍然相同 - 从O(1)到O(n/2)。对于ArrayList来说，这个操作更类似于添加新元素（add）的操作。首先，找到所需的元素 - O(1)，然后将其删除，并将其右侧的所有元素向左移动一个单位以缩小产生的间隙。删除操作将具有与添加操作相同的算法复杂度 - 从O(1)到O(n)。删除越接近列表末尾，算法复杂度就越小。其实主要的操作就这些了。我提醒您：在比较这两个列表时，您需要明确我们正在谈论的具体情况，然后您才能明确地回答提出的问题。

90.ArrayList与HashSet有何不同？

如果ArrayList和LinkedList可以在操作方面进行比较——哪个更好——那么将ArrayList与HashSet进行比较就不那么容易了，因为它们是完全不同的集合。你可以将一种甜食与另一种进行比较，但它可以与荤菜进行比较——它们太不同了。不过，我会尝试给出它们之间的一些区别：

• ArrayList实现了List接口，而HashSet实现了Set接口；

• 在ArrayList中，通过元素索引来访问：获取操作的算法复杂度为O(1)，而在HashSet中，需要通过暴力破解来获取所需元素，这是从O(1)到O(n) ;

• ArrayList允许重复元素。在HashSet 中，所有元素都是唯一的：向集合中已存在类似元素的HashSet添加元素将不起作用（使用哈希码检查重复项，因此该集合的名称）；

• ArrayList是使用内部数组实现的，HashSet是使用内部HashMap实现的；

• ArrayList维护元素的插入顺序，而HashSet是无序集合，不维护元素的顺序；

• ArrayList允许任意数量的空值（null），一个HashSet中只能插入一个空值（毕竟元素的唯一性）。

91. 为什么Java中有如此多种动态数组的实现？

嗯，这更像是一个哲学问题。那么，为什么他们会想出这么多不同的新技术呢？为了舒适。实际上，大量动态数组的实现也是如此。他们都不能被称为最好或理想的。每个人在某些特定情况下都有优势。我们的任务是了解它们的差异、优点/缺点：以便能够在正确的情况下使用最合适的。

92. 为什么Java中有如此多种键值存储实现？

这里的情况与动态数组实现相同。没有最好的人：每个人都有优点和缺点。当然，我们必须充分利用我们的优势。 例子： concurrent包，包含了很多多线程技术，有自己的Concurrent集合。与常规HashMap相比，相同的ConcurrentHashMap在多线程处理数据的安全性方面具有优势，但在非多线程环境中它会损失速度。好吧，在任何情况下都不是最强的实现逐渐被停止使用。 示例：Hashtable最初旨在成为线程安全的HashMap，但ConcurrentHashMap在多线程环境中优于它，Hashtable最终被遗忘并不再使用。

93. 如何对元素集合进行排序？

首先要说的是集合元素类必须实现Comparable接口及其compareTo方法。或者您需要一个使用其比较器方法实现Comaprator 的类。您可以在这篇文章中阅读有关它们的更多信息。两种方法都指定应如何比较给定类型的对象。排序时，这一点至关重要，因为您需要了解比较元素的原理。主要方法是实现Comparable，直接在要排序的类中实现。同时，Comparator的使用也不太常见。假设您正在使用某个库中的类，该类没有Comparable实现，但您需要以某种方式对其进行排序。在无法更改此类的代码（除非扩展它）的情况下，您可以编写Comparator的实现，在其中指示您想要根据什么原则来比较此类的对象。还有一个例子。假设您需要不同的原则来对同一类型的对象进行排序，因此您编写了多个在不同情况下使用的比较器。通常，许多开箱即用的类已经实现了Comparable接口- 相同的String。其实，在使用它们的时候，你不必担心如何比较它们。你只需拿起它们并使用它们。 第一种也是最明显的方法是使用TreeSet或TreeMap类型的集合，它根据元素类比较器按已排序的顺序存储元素。请记住，TreeMap对键进行排序，但不对值进行排序。如果您使用Comparator实现而不是Comparable，则需要在创建时将其对象传递给集合构造函数：

TreeSet treeSet = new TreeSet(customComparator);

但是如果您有不同类型的集合怎么办？怎么排序呢？在这种情况下，Collections实用程序类的第二种方法是合适的- sort()方法。它是静态的，因此您所需要的只是类的名称和向其传递所需列表的方法。例如：

Collections.sort(someList);

如果您不使用Comparable ，而是使用Comparator 的实现，则需要将其作为第二个参数传递：

Collections.sort(someList, customComparator);

结果，传递的列表元素的内部顺序将发生变化：它将根据元素比较器进行排序。我注意到传输的元素列表必须是可变的，即 可变的，否则该方法将无法工作并会抛出UnsupportedOperationException。作为第三种方法，您可以使用Stream排序操作，如果使用Comparable实现，它会对集合的元素进行排序：

someList = someList.stream().sorted().collect(Collectors.toList());

如果比较器：

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

您可以在本文中阅读有关Stream 的更多信息。 第四种方法是手动实现排序，例如冒泡排序或归并排序。

类对象。等于和哈希码

94.简述Java中的类对象

在第二部分的分析中，我们已经讲了Object类的方法，这里我要提醒大家，Object类是Java中所有类的鼻祖。它有 11 个方法，相应地，所有类都继承这些方法。 有关所有 11 种方法的信息可以在讨论的 第二部分中找到。

95. Java 中 Equals 和 HashCode 的用途是什么？

hashCode()是Object类的一个方法，被所有类继承。它的任务是生成一些代表特定对象的数字。使用此方法的一个示例是在键对象上的HashMap中使用它来进一步确定本地哈希码，这将确定存储该对的内部数组（桶）的单元格。我们在分析的第 9 部分中详细讨论了HashMap的工作，因此我们不再过多赘述。 此外，通常，此方法在equals()方法中使用，作为确定对象身份的主要工具之一。 equals()是Object类的一个方法，其作用是比较对象并确定它们是否相等。凡是我们需要比较对象的地方都会用到这个方法，因为通常使用==的比较并不适合对象，因为 仅比较它们的链接。

96.请告诉我们Java中Equals和HashCode之间的约定？

我要说的第一件事是，为了使equals()和hashCode()方法正常工作，需要正确重写它们。此后他们必须遵守规则：

• 通过equals比较返回true 的相同对象必须具有相同的哈希码；
• 具有相同哈希码的对象可能并不总是相等。

到这里我们就暂停一下，等待下一部分的分析！