他们在面试中可能会问什么：Java 中的数据结构。第2部分

第 1 部分 现在我们正在讨论每个 Java 开发人员都应该了解的基础知识。关于一切开始的经典知识。今天我想谈谈任何面试的基本主题之一——Java中的数据结构。因此，与其拐弯抹角，不如开始吧。了解面试过程中可能会被问到的有关该主题的问题列表的后续内容。

6. 告诉我们有关列表的信息

List是一个接口，表示对象的有序结构，称为列表。这种结构的“技巧”在于，可以通过索引（即List的内部标识符）来插入、修改或删除List中包含的元素。换句话说，索引的意思是：“从列表的开头开始有多少个元素”。第一个List元素的索引为 0，第二个元素的索引为 1，依此类推。所以第五个元素距离列表开头有四个元素。如上所述，将项目添加到列表的顺序很重要。这就是为什么数据结构被称为列表。我们列出了该结构特有的方法，旨在按索引处理元素：

• get - 返回指定位置的元素（按索引值），
• 删除- 删除指定位置的元素，
• set - 用方法中指定的元素替换指定位置的元素。

主要实现是ArrayList和LinkedList。我们稍后会详细讨论它们。 Vector是一个线程安全的列表，因此该类中的每个方法都是同步的。但请记住，如果您想保护某些列表操作，您将同步整个操作序列。而且同步各个操作既不安全，又慢得多。当然，Vector也有锁定开销，即使您不需要锁。因此，该类现在被认为已过时并且不再使用。顺便说一句：ArrayList与Vector类似，但不使用锁定，因此到处都在使用它。 Stack是Vector类的子类，具有一个默认构造函数和Vector类的所有方法，以及它自己的一些方法（我们稍后会讨论它们）。例如，您可以将该过程想象为一堆包含文档的文件夹。您将一个文件夹放在堆栈的顶部，并且只能从顶部开始以相反的顺序取出这些文件夹。实际上，这是一种LIFO类型的机制，即后进先出，最后来的先离开。堆栈实现了自己的方法：

• push - 将传递的元素添加到堆栈顶部；
• peek - 返回堆栈顶部的元素；
• pop - 也返回位于堆栈顶部的元素，但将其删除；
• 空- 检查堆栈是否为空 - true或不 - false；
• search - 在堆栈中搜索给定元素。如果找到一个元素，则返回其相对于堆栈顶部的序列号。如果未找到该元素，则返回值 -1。

目前，由于Stack子类简单且缺乏灵活性，实际上并未使用它，但尽管如此，您可能会遇到它。例如，当您收到一些错误时，您会在控制台中看到一堆有关该错误的消息。您可以在本文中阅读有关堆栈和队列的更多信息。

7. 告诉我们地图

如上所述，Map是一个具有单独的接口结构及其实现的集合。它是分开的，因为这里的值不是一次存储一个，而是存储在“键值”对中。基本地图方法：

• put(K key, V value) - 向 Map 添加一个元素；
• get(Object key) - 按键搜索值；
• containsKey(Object key) — 检查 Map 是否存在该键；
• containsValue(Object value) - 检查 Map 是否存在该值；
• remove(Object key) - 通过键删除值。

正如您所看到的，大多数操作都是通过使用密钥来完成的。通常，选择不可变对象作为键。该对象的典型示例是String。基本地图实现：

1. HashMap - 设计用于以随机顺序存储值，但允许您快速搜索映射元素。允许您使用null关键字指定一个键，但不能多次，因为 具有相同密钥的对被写在彼此的顶部。主要条件是键的唯一性：值可以重复（可能有几个空值）。
2. LinkedHashMap是HashMap 的类似物，它按照添加的顺序存储值。因此，像LinkedList一样，它有一个标头- 双向链表的标头。初始化时，它指向自身。

   LinkedHashMap还有一个 accessOrder，它指定使用迭代器时如何访问元素。如果accessOrder 为false，则将按照插入元素的顺序执行访问。如果为true，则元素将按上次访问的顺序排列（上次访问的元素将放置在末尾）。

3. TreeMap是一个按键值对元素进行排序的 Map。与TreeSet类似，但用于基于键值的对。要设置TreeMap排序规则，键必须实现Comparable接口。否则，应该有一个面向键的比较器（在TreeMap构造函数中指定的比较器），一个 TreeSet - 用内部的 TreeMap 对象实现，事实上，所有的魔法都发生在其中。

   您可以在有关 TreeMap 功能的文章中阅读有关使用红黑树在 TreeMap 中进行排序的更多信息。

4. Hashtable与HashMap类似，但不允许将null存储为键或值。从多线程的角度来看，它是仔细同步的，这反过来又意味着从多线程的角度来看它是安全的。但这种实现方式已经过时且缓慢，所以现在你或多或少不会在新项目中看到Hashtable 。

8. ArrayList 与 LinkedList。最好使用哪一种？

这个问题可能是数据结构中最流行的问题，并且存在一些陷阱。在回答这个问题之前，我们先来了解一下这些数据结构。 ArrayList实现List接口并在根据需要扩展的内部数组上进行操作。当内部数组完全填满，并且需要插入新元素时，将创建一个大小为 (oldSize * 1.5) +1 的新数组。之后，旧数组中的所有数据都会复制到新+新元素中，旧数组将被垃圾收集器删除。add方法将一个元素添加到数组的最后一个空单元格中。也就是说，如果我们已经有 3 个元素，它会将下一个元素添加到第 4 个单元格。我们来看看基本方法的性能：

• get(int index) - 通过索引获取数组中的元素是O(1)中最快的；
• add(Object obj) - 如果内部数组中有足够的空间容纳新元素，则正常插入将花费O(1)时间，因为添加是在最后一个单元格中故意完成的。

  如果我们需要创建一个新数组并将内容复制到其中，那么我们的时间将与数组中元素的数量成正比O(n)；

• remove(int index) - 当删除一个元素时，例如，从中间删除一个元素，我们将获得 O(n/2) 时间，因为我们需要将元素向右移动一个单元格。因此，如果从列表的开头删除，则 O(n)，从末尾 - O(1)；
• add(int index, Object obj) - 类似于删除的情况：添加到中间时，我们需要将右侧的元素向前移动一个单元格，因此时间为 O(n/2)。当然，从开始 - O(n)，从结束 - O(1)；
• set(int index, Object obj) - 这里的情况有所不同，因为你只需要找到所需的元素并覆盖它，而不移动其余的，所以 O(1)。

在本文中阅读有关ArrayList 的更多信息。 LinkedList同时实现两个接口 - List和Queue，因此具有这两个数据结构固有的属性和方法。从 List 中，他通过索引访问元素，从 Queue 中访问元素——“头”和“尾”的存在。在内部，它被实现为表示双向链表的数据结构。也就是说，除了“尾部”和“头部”之外，每个元素都具有到下一个和前一个元素的链接。

• get(int index) - 当搜索列表中间的元素时，它开始按顺序搜索所有元素，直到找到所需的元素。从逻辑上讲，搜索应该花费O(n/2)，但 LinkedList 也有尾部，因此搜索是从两侧同时进行的。因此，时间减少到O(n/4)。

  如果元素接近列表的开头或结尾，则时间将为O(1)；

• add(Object obj) - 添加新元素时，“tail”元素将具有指向添加的下一个元素的链接，新元素将收到指向前一个元素的链接并成为新的“tail”。因此，时间将为O(1)；
• remove(int index) - 逻辑类似于get(int index)方法。要从列表中间删除元素，必须首先找到它。这又是O(n/4)，而删除本身实际上什么都不做，因为它只改变了相邻对象的指针（它们开始互相引用）。如果元素位于开头或结尾，则同样 - O(1)；
• add(int index, Object obj)和set(int index, Object obj) - 这些方法的时间复杂度与 get(int index)相同，因为大部分时间都花在搜索元素上。因此，对于列表的中间 - O(n/4)，对于开头 - O(1) 。

本文介绍了有关使用LinkedList的更多信息。让我们在表格中看看所有这些： 正如您可能已经了解的那样，不可能明确地回答这个问题。毕竟，在不同的情况下，它们的工作速度是不同的。因此，当你被问到这样的问题时，你应该立即询问这个列表将重点关注什么以及最常执行哪些操作。从这里开始，给出一个答案，但要解释为什么会这样。让我们总结一下我们的比较： ArrayList：

• 如果最频繁的操作是搜索元素、覆盖元素，则最好的选择；
• 如果是在开头中间进行插入和删除操作，这是最差的选择，因为会发生右侧元素的移位操作。

链表：

• 如果我们频繁的操作是在开头中间插入和删除，那么最好的选择；
• 如果最常见的操作是搜索，则是最差的选择。

9. HashMap 中元素是如何存储的？

HashMap集合包含一个内部数组Node[] table，其单元格也称为存储桶。 节点包含：

• key - 链接到密钥，
• value — 对值的引用，
• 散列- 散列值，
• next - 指向下一个Node 的链接。

table[]数组的一个单元格可能包含对Node对象的引用，并具有到下一个Node元素的链接，并且它可能具有到另一个 Node 元素的链接，依此类推...因此，这些Node元素可以形成一个单链表，其中的元素具有指向下一个的链接。这种情况下，同一条链的元素的哈希值是相同的。简短的题外话之后，让我们看看元素是如何存储在HashMap中的：

1. 检查该键是否为null。如果为null，则 key 将存储在table[0]单元格中，因为 null 的哈希码始终为 0。
2. 如果键不为null，则调用键对象的hashcode()方法，该方法将返回其哈希码。该哈希码用于确定存储 Node 对象的数组单元。
3. 接下来，这个哈希码被放置在内部hash()方法中，该方法计算哈希码，但在table[]数组的大小之内。
4. 接下来，根据哈希值，将 Node 放置在table[]数组中的特定单元格中。
5. 如果用于保存当前Node元素的table[]单元格不为空，但已经有一些元素，则Node元素将迭代下一个值，直到到达最后一个元素。也就是说，下一个字段为null 的字段。

   在此搜索过程中，受保护Node对象的键与正在搜索的 Node 对象的键进行比较：

   • 如果找到匹配，则搜索结束，新的Node将覆盖找到匹配的Node （仅覆盖其value字段）；
   • 如果没有找到关键匹配，则新节点将成为此列表中的最后一个节点，而前一个节点将有一个指向它的下一个链接。

面试时经常出现这样的问题：什么是冲突？当table[]数组的一个单元格存储的不是一个元素，而是两个或多个元素的链时，这种情况称为冲突。在正常情况下，单个table[]单元中仅存储一个元素，访问HashMap的元素具有恒定的O(1)时间复杂度。但是，当具有所需元素的单元格包含元素链（碰撞）时，则O(n)，因为在这种情况下，时间与要排序的元素数量成正比。

10.解释迭代器

在上面的Collection层次结构映射图中，Collection接口是整个层次结构的开始位置，但实际上并非如此。Collection 继承自具有iterator()方法的接口，该方法返回实现Iterator<E>接口的对象。迭代器接口如下所示：

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - 通过调用此方法，您可以获得下一个元素。 hasNext() - 允许您查明是否存在下一个元素，以及是否已到达集合末尾。当仍有元素时，hasNext()将返回true。通常，hasNext()在next()方法之前调用，因为next()在到达集合末尾时将抛出NoSuchElementException。 remove() - 删除上次调用next()检索到的元素。Iterator 的目的是迭代元素。例如：

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

实际上，for-each 循环是使用迭代器在底层实现的。您可以在此处阅读有关此内容的更多信息。 List提供了它自己的迭代器版本，但是一个更酷、更复杂的迭代器 - ListIterator。该接口扩展了Iterator并具有附加方法：

• 如果集合中存在前一个元素，hasPrevious将返回 true，否则返回 false；
• previous返回当前元素并移至上一个元素；如果没有，则抛出 NoSuchElementException；
• add将在下一次调用next()返回的元素之前插入传递的对象；
• set为当前元素分配对传递对象的引用；
• nextIndex返回下一个元素的索引。如果不存在，则返回列表的大小；
• previousIndex返回前一个元素的索引。如果没有，则返回数字-1。

好了，这就是我今天的全部内容。我希望读完这篇文章后，您离自己的梦想更近了——成为一名开发人员。