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

好了，這就是我今天的全部內容。我希望讀完這篇文章後，您離自己的夢想更近了——成為一名開發人員。