探索 Java 开发人员职位面试中的问题和答案。第9部分

成为一名程序员并不容易。总是有新的东西需要学习。而且，与任何其他努力一样，最困难的事情是开始，朝着目标迈出第一步。但既然您已经在这里阅读本文，那么您已经完成了第一步。这意味着现在你需要刻意地朝着你的目标前进，而不是放慢速度或偏离方向。我假设您的目标是成为一名 Java 开发人员，或者如果您已经是一名开发人员，则可以增强您的知识。如果是这样，让我们​​继续解决大量 Java 开发人员面试问题。 让我们继续吧！

收藏

84. 告诉我们关于迭代器及其使用方法

集合是所有 Java 开发人员面试中最喜欢的话题。当回答有关集合层次结构的问题时，考生经常说它是从集合接口开始的。但事实并非如此。上面还有另一个接口：Iterable。该接口由iterator()方法组成，该方法允许您访问当前集合的Iterator对象。这个Iterator对象到底是什么？Iterator对象提供了在集合中移动并迭代其元素的能力，并且用户不需要知道集合的具体实现细节。换句话说，它是一种指向集合元素的指针，就好像它正在窥视其中一个元素一样。迭代器具有以下方法：

• hasNext() —如果迭代有另一个元素，则返回true （此方法让您知道何时到达集合的末尾）；

• next() — 返回迭代中的下一项。如果没有，则抛出NoSuchElementException 。这意味着在使用此方法之前，最好使用hasNext()方法来确保下一个元素存在；

• remove() — 从集合中删除使用next()方法接收到的最后一个元素。如果next()从未被调用过，那么调用remove()将导致抛出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 集合框架中存在什么集合层次结构？

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

• 集合是描述集合的接口，集合是包含无序唯一（非重复）元素的数据结构。该接口有一些标准实现：TreeSet、HashSet和LinkedHashSet。

• 列表是一个描述存储有序对象序列的数据结构的接口。列表中的对象可以通过列表中的索引插入和删除（类似于数组，但可以动态调整大小）。该接口还有一些标准实现：ArrayList、Vector（已弃用且未实际使用）和LinkedList。

• 队列是一个接口，描述将项目存储在先进先出 (FIFO)队列中的数据结构。该接口有以下标准实现：LinkedList（没错，它也实现了Queue）和PriotityQueue。

第二个集合层次结构是Map层次结构，它具有以下结构： 该集合层次结构没有划分为子集合（因为Map层次结构本身就是一个独立的子集合）。标准Map实现是Hashtable（已弃用）、LinkedHashMap和TreeMap。在实践中，当人们询问Collections时，他们通常指的是两个层次结构。

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

ArrayList就像一个数组，但它可以动态扩展。这意味着什么？在底层，ArrayList使用普通数组，即将其元素存储在默认大小为 10 个单元格的内部数组中。一旦内部数组满了，就会创建一个新数组。新数组的大小由以下公式确定：

<size of the current array> * 3 / 2 + 1

因此，如果数组的大小为 10，则新数组的大小将为：10 * 3 / 2 + 1 = 16。然后使用内置函数将原始（旧）数组中的所有值复制到其中System.arraycopy()方法，原数组被删除。简而言之，这就是ArrayList实现动态调整大小的方式。让我们考虑一下最流行的ArrayList方法： 1. add(<Element>) — 在首先检查数组中是否有可用单元之后，将一个元素添加到数组末尾（最后一个空单元中）。如果没有，则创建一个新数组，并将元素复制到其中。该操作的时间复杂度为O(1)。还有一个类似的add(<Index>, <Elelement>)方法。它不会将元素添加到列表（数组）的末尾，而是添加到作为参数传入的索引指示的特定单元格中。在这种情况下，时间复杂度将根据您添加的位置而有所不同：

• 如果添加接近列表的开头，那么时间复杂度将接近 O(N)，因为位于新元素右侧的所有元素都必须向右移动一个单元格；
• 如果将元素插入到中间，那么它将是 O(N/2)，因为我们只需要将一半的​​列表项向右移动一个单元格。

也就是说，该方法的时间复杂度范围从 O(1) 到 O(N)，具体取决于插入元素的位置。2. set(<Index>, <Element>) — 将元素写入列表中的指定位置。如果某个元素已存在于该位置，则该方法将覆盖它。这个操作的时间复杂度是O(1)，因为它不涉及任何移位操作：我们只是使用索引计算出单元格在数组中的地址，复杂度为O(1)，然后写入新元素。3.remove (<index>) — 按内部数组中的索引删除元素。删除不在列表末尾的项目时，已删除项目右侧的所有项目都必须向左移动一个单元格，以缩小因删除而产生的间隙。因此，当在中间添加元素时，时间复杂度将与add(<Index>, <Element>)相同：O(N/2)。毕竟，您需要将一半元素向左移动一个单元格。如果我们谈论的是开始，那么 O(N)。或者如果在最后，则 O(1)，因为您不需要移动任何东西。

87. LinkedList的内部结构是什么？

ArrayList包含内部数组中的元素，而LinkedList将它们存储在双向链表中。这意味着每个元素都包含到前一个元素和下一个元素的链接。第一个元素不链接到前一个元素（毕竟，它是第一个）。它也被认为是列表的头部，并且LinkedList对象可以直接引用它。同样，最后一个元素没有下一个元素，因为它是列表的尾部。LinkedList对象也直接引用它。这意味着访问列表的头或尾的时间复杂度是 O(1)。 在ArrayList中，如果列表增长，则内部数组也会增长。在这里一切都变得更容易：添加引用就像更改几个链接一样简单。让我们看看一些最常用的LinkedList方法： 1. add(<Element>) — 将一个元素添加到列表末尾，即在最后一个元素 (5) 之后，将添加指向新元素的链接作为下一个元素。新元素中的前一个引用将指向列表中现在位于其之前的元素 (5)。此操作的时间复杂度为 O(1)，因为我们只需要链接到最后一个元素，并且您会记得，LinkedList 对象具有对尾部的直接引用，并且访问它具有最小的常量时间复杂度。2. add(<Index>, <Element>) — 按索引添加元素。假设在列表中间添加元素时，此方法首先从头部和尾部（两个方向）迭代元素，直到找到所需的位置。如果我们在第三个和第四个元素之间添加一个元素（如上图所示），那么第三个元素的下一个链接将指向新元素。新添加的元素的前一个将指向第三个。反过来，旧的第四个元素的前一个链接现在将指向新元素，新元素的下一个链接将指向新的第四个元素： 此方法的时间复杂度取决于新元素的索引：

• 如果它靠近头部或尾部，则操作将接近 O(1)，因为实际上不需要迭代元素；
• 如果靠近中间，那么我们的时间复杂度为 O(N/2)，因为该方法将同时从头部和尾部搜索，直到找到所需的元素。

3. set(<Index>, <Element>) — 将元素写入列表中的指定位置。此操作的时间复杂度范围从 O(1) 到 O(N/2)，同样取决于新元素距离头部、尾部或中间的距离。4.remove (<index>) — 从列表中删除一个元素，使删除的元素之前的元素（前一个）现在引用删除的元素之后的元素（下一个）。反之亦然，即被删除的元素后面的元素现在引用被删除的元素之前的元素： 此过程与按索引添加（ add(<Index>, <Element>) ）相反。

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

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

Node<K,V>[] table

默认情况下，数组的大小为 16，并且每次填充元素时都会加倍（即，当达到LOAD_FACTOR时；它指定数组可以达到的满阈值 - 默认情况下为0.75） 。每个节点都存储键的哈希值、键、值以及对下一个元素的引用： 在这种情况下，“对下一个元素的引用”意味着我们正在处理一个单链表，其中每个元素都包含到下一个元素的链接。换句话说，HashMap将其数据存储在单链表数组中。但我马上要说的是，当表数组的一个单元格具有由多个元素组成的单链表时，这是不好的。这种现象称为碰撞。但首先要说的是。让我们看看如何使用put方法保存新的对。首先，该方法获取密钥的hashCode()。这意味着为了使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问题的面试。这就是今天的全部内容。待续...