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

你好！不管你怎么看，如果没有成功通过技术面试，你就无法成为一名开发人员。 Java相关的技术有很多，不可能全部学会。通常，只有当他们正在寻找对项目重要的框架具有丰富经验的开发人员时，才会在面试时询问一些具体问题。如果是这样的话，你就会被这个框架全速追赶，对此你毫不怀疑。但现在我们谈论的是每个 Java 开发人员都应该了解的基础知识。关于一切开始的经典知识。今天我想谈谈任何面试的基本主题之一——Java中的数据结构。因此，与其拐弯抹角，不如开始吧。查找在面试过程中可能会被问到的有关该主题的问题列表。

1. 告诉我们一些关于数据结构的知识

数据结构是包含以某种方式结构化的信息的数据存储。这些结构是为了高效执行某些操作而设计的。数据结构的典型例子有：

• 数组，
• 堆栈，
• 队列，
• 相关列表，
• 图表，
• 树木，
• 前缀树，
• 哈希表。

您可以在此处和此处了解有关它们的更多信息。数据是程序中的关键组成部分，结构允许这些数据以特定的、结构清晰的形式存储。无论您的应用程序做什么，这方面都将始终存在于其中：如果它是网络商店，则将存储有关产品的信息，如果它是社交网络，则将存储有关用户和文件的数据等等。

2.你对数组了解多少？

数组是存储相同类型值的容器，其数量已预先指定。使用字符串值创建数组的示例：

String[] strArray = {"Java","is","the","best","language"};

创建数组时，会为其所有元素分配内存：最初指定的元素单元越多，分配的内存就越多。如果创建具有一定数量单元格的空数组，则该数组的所有元素都将被分配默认值。例如：

int[] arr = new int[10];

因此，对于具有boolean 类型元素的数组，初始（默认）值为false，对于具有数值 - 0 的数组，具有char类型元素的数组- \u0000。对于类类型（对象）的数组 - null（不是空字符串 - “” 但特别是null）。也就是说，在上面的例子中，arr数组的所有值都将是0，直到直接指定为止。与集合不同，数组不是动态的。一旦声明了特定大小的数组，大小本身就无法更改。要向数组添加新元素，您需要创建一个更大的新数组，并将旧数组中的所有元素复制到其中（这就是 ArrayList 的工作原理）。有一点并不是每个人都知道，但你可以很好地抓住这一点。Java 中有两种类型的变量 -简单类型和对成熟对象的引用。其中哪些是数组？例如，这里：

int[] arr = new int[10];

看起来一切都很简单——这就是 10 个int元素。那么，我们可以说这是一个简单类型吗？不管怎样。 在Java中，数组是对象，是动态创建的并且可以分配给Object类型的变量。 可以在数组上调用 Object 类的所有方法。所以我们甚至可以写：

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

输出到控制台时，您可能会得到类似以下内容的信息： 在这篇关于 Java Array 的文章 中了解有关 Java 中数组功能的更多信息。为了巩固你的知识，你可以解决这个集合中的几个问题。

3. 解释集合的层次结构

集合用于在处理数据时需要灵活性的情况。集合可以添加元素、删除元素以及执行许多其他操作。Java中有很多不同的实现，我们只需要根据当前情况选择合适的集合即可。通常，当您提到Collection接口时，系统会要求您列出它的一些实现及其与Map的关系。好吧，让我们找出答案。因此，Collection和Map是数据结构的两种不同层次结构。Collection层次结构是什么样的：Collection接口是具有一系列基本方法的关键顶层链接，三种基本类型的数据结构均源于此 - Set、List、Queue。 Set<T>是一个接口，表示对象的集合，其中每个对象都是唯一的。 List<T>是一个接口，表示对象的有序序列（称为列表）。 Queue<T>是一个接口，负责组织为队列（元素的顺序存储）的结构。如前所述，Map是一个单独的层次结构：Map<K, V>是一个表示字典的接口，其中元素以键值对的形式包含。此外，所有键 (K) 在Map对象中都是唯一的。如果我们知道键（对象的唯一标识符），这种类型的集合就可以更轻松地查找元素。

4.你对赛特了解多少？

如前所述，该系列具有许多独特的元素。换句话说，同一个对象在 Java Set中不能出现多次。我还想指出，我们无法通过数字（索引）从Set中提取元素- 只能通过暴力。重要的是不同的Set实现有不同的数据结构方式。具体实施我们会进一步考虑。因此， Set的主要实现： HashSet是一个基于哈希表的集合，这反过来又有助于搜索。使用哈希函数可以提高查找和插入期间的性能。无论元素数量有多少，插入和搜索（有时是删除）通常都会在接近恒定的时间内执行 - O(1)。稍后我们将更详细地了解哈希函数。我还想指出，HashSet包含一个 HashMap，这就是所有魔法发生的地方。这里有一篇关于Java中HashSet的详细文章。 LinkedHashSet - 此类扩展了HashSet，而不添加任何新方法。与LinkedList类似，此类按照插入顺序维护集合元素的链接列表。这允许您在给定的Set实现中组织必要的顺序。TreeSet类创建一个基于红黑树的集合来组织存储元素的结构。换句话说，在给定的集合中，我们可以按升序对元素进行排序。如果我们使用“盒子”中的一些标准对象，例如Integer，那么我们不需要做任何事情来按升序排列 Integers 集合：

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

在控制台中我们将得到输出： 也就是说，在这个集合中，数字以排序的形式存储。如果我们在TreeSet中使用String元素，它们将按字母顺序排序。好吧，如果我们有一些标准（自定义）类怎么办？此类的对象将如何构造TreeSet？如果我们尝试将任意对象分配给此Set：

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

我们将收到ClassCastException，因为TreeSet不知道如何对这种类型的对象进行排序。在这种情况下，我们需要自定义对象来实现Comparable接口及其compareTo方法：

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

正如您所注意到的，compareTo方法返回一个 int：

• 1 如果当前（这个）对象被认为很大；
• 如果当前对象被认为小于作为参数传入的对象，则为 -1；
• 如果对象相等则为 0（在本例中我们不使用它）。

在这种情况下，我们的TreeSet将正常工作并显示结果： 另一种方法是创建一个单独的排序类来实现比较器接口及其比较方法：

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

在这种情况下，要使用它，我们必须将此类的对象设置为TreeSet构造函数：

TreeSet set = new TreeSet<>(new CatComparator());

此后，TreeSet中包含的Cat类的所有对象都将使用Cat Comparator类进行排序。您可以从本文中了解有关Java 中的Comparator和Comparable 的更多信息。

5. 告诉我们有关队列的信息

队列是一个接口，负责组织为队列的结构 - 一种按顺序存储元素的数据结构。例如，在排队的人中，第一个进去的人就是比其他人早到的人，最后一个进来的人就是比其他人都晚到的人。这种方法称为FIFO，即先进先出。独特的队列方法专注于处理第一个或最后一个元素，例如：

• 添加和提供- 在队列末尾插入一个元素，
• 删除- 检索并删除此队列的标头，
• peek - 检索但不删除队列头。

第2部分