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

焰火！成为一名程序员并不容易。你需要不断学习，总是学习新的东西。但是，与任何其他业务一样，最困难的事情是开始，朝着目标迈出第一步。既然您坐在这个网站上并阅读这篇文章，您就已经完成了第一步。这意味着现在你需要有目的地朝着你的目标前进，而不是一路放慢速度或停下来。如果我理解正确的话，您的目标是成为一名 Java 开发人员或增强您的知识（如果您是一名 Java 开发人员）。如果是这样，那么您来对地方了，因为我们将继续分析 250 多个 Java 开发人员面试问题的广泛列表。 让我们继续吧！

收藏

84.告诉我们迭代器及其用途

集合是任何 Java 开发人员面试中最喜欢的话题之一，在谈论集合层次结构时，应试者经常说它是从Collection接口开始的。但这不是真的，因为在这个接口之上还有另一个接口 - Iterable。该接口代表iterator()方法，它允许您为当前集合调用Iterator对象。这个Iterator对象到底是什么？ 迭代器是一个对象，它提供了在集合中移动并迭代元素的能力，而用户无需知道特定集合的实现。也就是说，这是某种指向集合元素的指针，可以说，它查看集合中的某个位置。迭代器有以下方法：

• hasNext() - 如果指针后面有一个元素，则返回true（此方法允许您查明是否已到达集合末尾）；
• next() - 返回指针后的下一个元素。如果没有，则抛出NoSuchElementException。也就是说，在使用此方法之前，最好确保该元素存在 - 使用hasNext()；
• remove() - 使用next()方法删除从集合中接收到的最后一个元素。如果在调用remove ()之前从未调用过next ()，则会抛出异常 - IllegalStateException；
• forEachRemaining(<Consumer>) - 对集合中的每个元素执行传递的操作（该方法出现在 Java 8 中）。

下面是一个使用所讨论的迭代器方法迭代列表并删除其所有元素的小示例：

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

控制台将显示： 这意味着删除元素成功。一旦我们有了迭代器，我们就可以使用一种方法将所有元素打印到屏幕上：

iterator.forEachRemaining(x -> System.out.print(x));

但在此之后，迭代器将不再适合进一步使用，因为它将遍历整个列表，并且常规迭代器没有回溯方法。这里我们逐渐接近LinkedList，即它的listIterator()方法，它返回一个现代化类型的迭代器 - ListIterator。除了常规（标准）迭代器方法之外，该方法还有其他方法：

• add(<Element>) - 将新元素插入列表中；
• hasPrevious() -如果有一个元素位于指针之前（无论是否有前一个元素），则返回true ；
• nextIndex() - 返回指针之后下一个元素在列表中的索引；
• previous() - 返回前一个元素（直到指针）；
• previousIndex() - 返回前一个元素的索引；
• set(<Element>) - 替换next()或previous()方法返回的最后一个元素。

正如您所看到的，这个迭代器的功能更加有趣：它允许您在两个方向上移动，并在处理元素时释放您的双手。此外，当人们谈论迭代器时，他们有时指的是模式本身。为了避免陷入麻烦并令人信服地谈论它，请阅读这篇关于迭代器模式的文章。

85. Java Collection Framework 中的集合层次结构是什么？

Java 中有两种集合层次结构。 第一个层次结构是Collection层次结构本身，具有以下结构： 它又分为以下子集合：

• Set是一个接口，它将这样的数据结构描述为包含无序唯一（非重复）元素的集合。该接口具有标准实现 - TreeSet、HashSet和LinkedHashSet。
• 列表是一个接口，描述存储有序对象序列的数据结构。列表中包含的实例可以通过其在此集合中的索引进行插入和删除（类似于数组，但可以动态调整大小）。该接口有标准实现 - ArrayList、Vector（被认为已过时且未实际使用）和LinkedList。
• 队列是一个接口，它描述了一种以队列形式存储元素的数据结构，遵循FIFO 先进先出规则。该接口具有以下标准实现：LinkedList（是的，它也实现了Queue）和PriotityQueue。

集合的第二个层次结构是Map，它具有以下结构： 在此集合中，没有划分为子集合（因为Map层次结构本身类似于子集合，但分开放置）。标准Map实现是Hashtable（已被弃用）、LinkedHashMap和TreeMap。实际上，当被问及Collection时，通常意味着这两种层次结构。

86.ArrayList的内部结构是什么？

ArrayList类似于数组，但具有动态扩展的能力。这是什么意思？事实上，ArrayList是在常规数组的基础上工作的，即将元素存储在内部数组中（其默认大小为 10 个单元格）。当内部数组满时，会创建一个新数组，其大小由以下公式确定：

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

也就是说，如果数组的大小为 10，则新数组的大小将为：10 * 3 / 2 + 1 = 16。接下来，使用第一个（旧）数组中的所有值复制到其中原生System.arraycopy ()方法，并且第一个数组被删除。实际上，这就是ArrayList动态扩展性的实现方式。让我们看看最常用的ArrayList方法： 1. add(<Elelement>) - 将一个元素添加到数组末尾（最后一个空单元格），并首先检查该数组中是否有空间。如果不存在，则会创建一个新数组，将元素复制到其中。此操作的对数复杂度为 O(1)。有一个类似的方法 - add(<Index>,<Elelement>)。它不会将元素添加到列表（数组）的末尾，而是添加到具有作为参数的索引的特定单元格。在这种情况下，对数复杂度将根据添加位置的不同而有所不同：

• 如果这大约是列表的开头，则对数复杂度将接近 O(N)，因为位于新元素右侧的所有元素都必须向右移动一个单元格；
• 如果元素插入到中间 - O(N/2) 因为 我们只需将一半的列表元素向右移动一个单元格。

也就是说，该方法的对数复杂度范围从 O(N) 到 O(1)，具体取决于插入元素的位置。2. set(<Index>,<Elelement>) - 将元素写入列表中的指定位置。如果该位置已经有一个元素，则覆盖它。此操作的对数复杂度为 O(1)，因为没有移位：仅通过数组中的索引进行搜索（我们记得，其复杂度为 O(1)），并写入元素。3.remove (<index>) - 通过内部数组中的索引删除元素。删除不在列表末尾的项目时，必须将其右侧的所有项目向左移动一个单元格，以缩小删除该项目后留下的空白。因此，如果元素位于中间，对数复杂度将与add(<Index>,<Elelement>)相同- O(N/2) - 因为您需要将一半元素向左移动一位。因此，如果它在开始处 - O(N)。好吧，如果最后是 O(1)，就不需要移动任何东西。对于那些想要深入研究这个主题的人，我将把这个链接留给一篇分析ArrayList类的文章。

87.LinkedList的内部结构是怎样的？

如果ArrayList包含内部数组中的元素，则LinkedList采用双向链表的形式。这意味着每个元素都包含到前一个元素 ( previous ) 和下一个元素 ( next )的链接。第一个元素没有到前一个元素的链接（它是第一个），但它被认为是列表的头部，并且 LinkedList有一个直接到它的链接。事实上，最后一个元素没有下一个元素，它是列表的尾部，因此 LinkedList 本身有一个到它的直接链接。因此，访问列表头或尾的对数复杂度是 O(1)。 在ArrayList 中，当列表增长时，内部数组也会增加，但这里一切都发生得更简单 - 添加元素时，几个链接只会发生变化。让我们看看一些最常用的LinkedlList方法： 1. add(<Elelement>) - 添加到列表末尾，即 在最后一个元素 (5) 之后，将添加指向新元素的链接作为next。新元素将具有到最后一个元素 (5) 的链接（作为前一个元素）。这种操作的对数复杂度将为 O(1)，因为只需要到最后一个元素的链接，并且您还记得，尾部具有来自LinkedList 的直接链接，并且访问它的对数复杂度是最小的。2. add(<Index>,<Elelement>) - 按索引添加元素。例如，当添加元素到列表的中间时，首先迭代头部和尾部（两侧）的元素，直到找到所需的位置。如果我们想在第三个和第四个元素之间插入一个元素（如上图所示），那么当寻找正确的位置时，第三个元素的下一个链接已经指向新的元素。对于新链接，前一个链接将指向第三个链接。因此，第四个元素（前一个）的链接将已经指向新元素，并且新元素的下一个链接将指向第四个元素： 此方法的对数复杂度将取决于赋予新元素的索引：

• 如果它靠近头部或尾部，它将接近 O(1)，因为实际上不需要迭代元素；
• 如果靠近中间，则 O(N/2) - 将同时对头部和尾部的元素进行排序，直到找到所需的元素。

3. set(<Index>,<Elelement>) - 将元素写入列表中的指定位置。此操作的对数复杂度范围从 O(1) 到 O(N/2)，同样取决于元素距离头部、尾部或中间的距离。4.remove (<index>) - 从列表中删除一个元素，本质上是使被删除的元素之前的元素 ( previous ) 引用被删除的元素之后的元素 ( next )。反之亦然：这样被删除元素之后的元素就引用被删除元素之前的元素： 结果是与按索引添加相反的过程（add(<Index>,<Elelement>)）。对于那些希望了解更多关于LinkedList 内部结构的人，我建议阅读这篇文章。

88. HashMap的内部结构是什么？

也许是面试 Java 开发人员时最常见的问题之一。 HashMap v 使用键值对。它们如何存储在HashMapv本身中？HashMap内部有一个节点数组：

Node<K,V>[] table

默认情况下，数组的大小为 16，并且每次填充元素时都会加倍（当达到LOAD_FACTOR时- 一定的填充百分比，默认情况下为0.75）。每个节点存储键的散列、一个键、一个值以及到下一个元素的链接： 实际上，“到下一个元素的链接”意味着我们正在处理一个单链表，其中每个元素都包含一个到下一个元素的链接。下一个。也就是说，HashMap将数据存储在单链表数组中。但我会立即注意到：当表数组的一个单元格链接到由多个元素组成的类似单链表时，这并不好。这种现象称为碰撞。但首先要说的是。让我们看看如何使用put方法保存新的对。首先，获取密钥的hach​​Code() 。因此，为了使hashmap正常工作，您需要将重写此方法的类作为键。然后在内部方法hash()中使用该哈希码来确定表数组大小内的数字。接下来，使用接收到的数字来访问表数组的特定单元。这里我们有两种情况：

1. 该单元格为空 - 新的 节点值存储在其中。
2. 单元格不为空 - 比较键的值。 如果它们相等，则新的Node值将覆盖旧的 Node 值，如果它们不相等，则访问下一个元素并与其键进行比较...依此类推，直到新值覆盖旧值或到达该值的末尾单链表，并将作为最后一个元素存储在那里。

当通过键（ get(<key>)方法）搜索元素时，会计算键的hashCode ，然后使用hash()在数组中计算其值，并使用结果数找到表数组的单元格，其中已经通过枚举节点并将所需节点的键与当前节点的键进行比较来执行搜索。理想情况下， Map中的操作的算法复杂度为 O(1)，因为它们访问的是数组，并且正如您所记得的，无论元素数量有多少，数组上的操作的复杂度都是 O(1)。但这是理想的。当使用的数组单元不为空 (2) 并且那里已经有一些节点时，算法复杂度变成线性 O(N)，因为现在需要迭代元素才能找到正确的位置。我不能不提一下：从Java 8开始，如果单链表节点有超过8个元素（碰撞），它就会变成二叉树。在这种情况下，算法复杂度将不再是 O(N)，而是 O(log(N)) - 这是另一回事，不是吗？ HashMap是一个很大的话题，人们喜欢在面试中问有关它的问题。因此，我建议您详细了解它（以便它从您的牙齿上弹开）。就我个人而言，我没有面试过没有HashMap问题的面试。您可以在本文中深入了解HashMap。今天就到这里了，未完待续……