他們在面試中可能會問什麼：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部分