Java 開發者訪談問答分析。第9部分

焰火！成為一名程式設計師並不容易。你需要不斷學習，總是學習新的東西。但是，與其他業務一樣，最困難的事情是開始，朝著目標邁出第一步。既然您坐在這個網站上並閱讀這篇文章，您就已經完成了第一步。這意味著現在你需要有目的地朝著你的目標前進，而不是一路放慢速度或停下來。如果我理解正確的話，您的目標是成為 Java 開發人員或增強您的知識（如果您是 Java 開發人員）。如果是這樣，那麼您來對地方了，因為我們將繼續分析 250 多個 Java 開發人員面試問題的廣泛清單。 讓我們繼續吧！

收藏

84.告訴我們迭代器及其用途

集合是任何 Java 開發人員面試中最喜歡的話題之一，在談論集合層次結構時，應試者經常說它是從Collection介面開始的。但這不是真的，因為在這個介面之上還有另一個介面 - Iterable。此介面代表iterator()方法，它允許您為目前集合呼叫Iterator物件。這個Iterator物件到底是什麼？ 迭代器是一個對象，它提供了在集合中移動並迭代元素的能力，而使用者無需知道特定集合的實作。也就是說，這是某種指向集合元素的指針，可以說，它會查看集合中的某個位置。迭代器有以下方法：

• hasNext() - 如果指標後面有一個元素，則傳回true（此方法可讓您找出是否已到達集合末端）；
• next() - 傳回指標後的下一個元素。如果沒有，則拋出NoSuchElementException。也就是說，在使用此方法之前，最好確保該元素存在 - 使用hasNext()；
• remove() - 使用next()方法刪除從集合中接收的最後一個元素。如果在呼叫remove ()之前從未呼叫過next ()，則會拋出異常 - 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 Collection Framework 中的集合層次結構是什麼？

Java 中有兩種集合層次結構。 第一個層次結構是Collection層次結構本身，具有以下結構： 它又分為以下子集合：

• Set是一個接口，它將這樣的資料結構描述為包含無序唯一（非重複）元素的集合。此介面具有標準實作 - TreeSet、HashSet和LinkedHashSet。
• 列表是一個接口，描述儲存有序物件序列的資料結構。清單中包含的實例可以透過其在此集合中的索引進行插入和刪除（類似於數組，但可以動態調整大小）。此介面有標準實作 - ArrayList、Vector（被認為已過時且未實際使用）和LinkedList。
• 佇列是一個接口，它描述了一種以佇列形式儲存元素的資料結構，遵循FIFO 先進先出規則。此介面具有以下標準實作：LinkedList（是的，它也實作了Queue）和PriotityQueue。

集合的第二個層次結構是Map，它具有以下結構： 在此集合中，沒有劃分為子集合（因為Map層次結構本身類似於子集合，但分開放置）。標準Map實作是Hashtable（已被棄用）、LinkedHashMap和TreeMap。實際上，當被問及Collection時，通常意味著這兩種層次結構。

86.ArrayList的內部結構是什麼？

ArrayList類似於數組，但具有動態擴展的能力。這是什麼意思？事實上，ArrayList是在常規數組的基礎上工作的，即將元素存儲在內部數組中（其預設大小為 10 個單元格）。當內部數組滿時，會建立一個新數組，其大小由以下公式決定：

<размерТекущегоМассива> * 3 / 2  + 1

也就是說，如果數組的大小為 10，則新數組的大小將為：10 * 3 / 2 + 1 = 16。接下來，使用第一個（舊）數組中的所有值複製到其中原生System. arraycopy ()方法，並且第一個陣列被刪除。實際上，這就是ArrayList動態擴展性的實作方式。讓我們看看最常用的ArrayList方法： 1. add(<Elelement>) - 將一個元素加入陣列末尾（最後一個空白單元格），並先檢查該陣列中是否有空間。如果不存在，則會建立一個新數組，將元素複製到其中。此操作的對數複雜度為 O(1)。有一個類似的方法 - add(<Index>,<Elelement>)。它不會將元素添加到列表（數組）的末尾，而是添加到具有作為參數的索引的特定單元格。在這種情況下，對數複雜度將根據添加位置的不同而有所不同：

• 如果這大約是清單的開頭，則對數複雜度將接近 O(N)，因為位於新元素右側的所有元素都必須向右移動一個儲存格；
• 如果元素插入到中間 - O(N/2) 因為 我們只需將一半的列表元素向右移動一個單元格。

也就是說，該方法的對數複雜度範圍從 O(N) 到 O(1)，取決於插入元素的位置。2. set(<Index>,<Elelement>) - 將元素寫入清單中的指定位置。如果該位置已經有一個元素，則覆蓋它。此操作的對數複雜度為 O(1)，因為沒有移位：僅透過陣列中的索引進行搜尋（我們記得，其複雜度為 O(1)），然後寫入元素。3.remove (<index>) - 透過內部數組中的索引刪除元素。刪除不在清單末端的項目時，必須將其右側的所有項目向左移動一個儲存格，以縮小刪除該項目後留下的空白。因此，如果元素位於中間，對數複雜度將與add(<Index>,<Elelement>)相同- O(N/2) - 因為您需要將一半元素向左移動一位。因此，如果它在開始處 - O(N)。好吧，如果最後是 O(1)，那你就不需要移動任何東西。對於那些想要深入研究這個主題的人，我將把這個連結留給一篇分析ArrayList類別的文章。

87.LinkedList的內部結構是怎樣的？

如果ArrayList包含內部陣列中的元素，則LinkedList採用雙向鍊錶的形式。這意味著每個元素都包含到前一個元素 ( previous ) 和下一個元素 ( next )的連結。第一個元素沒有到前一個元素的連結（它是第一個），但它被認為是列表的頭部，並且 LinkedList有一個直接到它的連結。事實上，最後一個元素沒有下一個元素，它是列表的尾部，因此 LinkedList 本身有一個到它的直接連結。因此，存取列表頭或尾的對數複雜度是 O(1)。 在ArrayList 中，當清單成長時，內部陣列也會增加，但這裡一切都發生得更簡單 - 添加元素時，幾個連結只會改變。讓我們來看看一些最常用的LinkedlList方法： 1. add(<Elelement>) - 加入到列表末尾，即 在最後一個元素 (5) 之後，將新增指向新元素的連結作為next。新元素將具有到最後一個元素 (5) 的連結（作為前一個元素）。這種操作的對數複雜度將為 O(1)，因為只需要到最後一個元素的鏈接，並且您還記得，尾部具有來自LinkedList 的直接鏈接，並且訪問它的對數複雜度是最小的。2. add(<Index>,<Elelement>) - 依索引新增元素。例如，當將元素新增至清單的中間時，首先迭代頭部和尾部（兩側）的元素，直到找到所需的位置。如果我們想要在第三個和第四個元素之間插入一個元素（如上圖所示），那麼當尋找正確的位置時，第三個元素的下一個連結已經指向新的元素。對於新鏈接，前一個鏈接將指向第三個鏈接。因此，第四個元素（前一個）的連結將已經指向新元素，並且新元素的下一個連結將指向第四個元素： 此方法的對數複雜度將取決於賦予新元素的索引：

• 如果它靠近頭部或尾部，它將接近 O(1)，因為實際上不需要迭代元素；
• 如果靠近中間，則 O(N/2) - 將同時對頭部和尾部的元素進行排序，直到找到所需的元素。

3. set(<Index>,<Elelement>) - 將元素寫入清單中的指定位置。此操作的對數複雜度範圍從 O(1) 到 O(N/2)，同樣取決於元素距離頭部、尾部或中間的距離。4.remove (<index>) - 從清單中刪除一個元素，本質上是使被刪除的元素之前的元素 ( previous ) 引用被刪除的元素之後的元素 ( next )。反之亦然：這樣被刪除元素之後的元素就引用被刪除元素之前的元素： 結果是與按索引添加相反的過程（add(<Index>,<Elelement>)）。對於那些希望了解更多關於LinkedList 內部結構的人，我建議閱讀這篇文章。

88. HashMap的內部結構是什麼？

也許是面試 Java 開發人員時最常見的問題之一。 HashMap v 使用鍵值對。它們如何儲存在HashMapv本身中？HashMap內部有一個節點數組：

Node<K,V>[] table

預設情況下，數組的大小為 16，並且每次填充元素時都會加倍（當達到LOAD_FACTOR時- 一定的填充百分比，預設為0.75）。每個節點儲存鍵的雜湊、一個鍵、一個值以及到下一個元素的連結： 實際上，「到下一個元素的連結」意味著我們正在處理一個單鍊錶，其中每個元素都包含一個到下一個元素的連結。下一個。也就是說，HashMap將資料儲存在單鍊錶數組中。但我會立即註意到：當表數組的一個單元格連結到由多個元素組成的類似單鍊錶時，這並不好。這種現象稱為碰撞。但首先要說的是。讓我們看看如何使用put方法儲存新的對。首先，取得金鑰的hachCode() 。因此，為了使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問題的面試。您可以在本文中深入了解HashMap。今天就到這裡了，未完待續…