探索 Java 開發人員職位面試中的問題和答案。第9部分

成為一名程式設計師並不容易。總是有新的東西要學習。而且，就像其他努力一樣，最困難的事情是開始，朝著目標邁出第一步。但既然您已經在這裡閱讀本文，那麼您已經完成了第一步。這意味著現在你需要刻意地朝著你的目標前進，而不是放慢速度或偏離方向。我假設您的目標是成為 Java 開發人員，或者如果您已經是開發人員，則可以增強您的知識。如果是這樣，讓我們繼續解決大量 Java 開發人員面試問題。 讓我們繼續吧！

收藏

84. 告訴我們關於迭代器及其使用方法

集合是所有 Java 開發人員面試中最喜歡的話題。當回答有關集合層次結構的問題時，考生經常說它是從集合介面開始的。但事實並非如此。上面還有另一個介面：Iterable。此介面由iterator()方法組成，該方法允許您存取目前集合的Iterator物件。這個Iterator物件到底是什麼？Iterator物件提供了在集合中移動並迭代其元素的能力，並且使用者不需要知道集合的具體實作細節。換句話說，它是一種指向集合元素的指針，就好像它正在窺視其中一個元素一樣。迭代器具有以下方法：

• hasNext() —如果迭代有另一個元素，則傳回true （此方法讓您知道何時到達集合的末端）；

• next() — 傳回迭代中的下一項。如果沒有，則拋出NoSuchElementException 。這意味著在使用此方法之前，最好使用hasNext()方法來確保下一個元素存在；

• remove() — 從集合中刪除使用next()方法接收的最後一個元素。如果next()從未被呼叫過，那麼呼叫remove()將導致拋出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 集合框架中存在什麼集合層次結構？

Java 中有兩種集合層次結構。 第一個層次結構是 Collection 層次結構，其結構如下： 它分成以下子集合：

• 集合是描述集合的接口，集合是包含無序唯一（非重複）元素的資料結構。此介面有一些標準實作：TreeSet、HashSet和LinkedHashSet。

• 列表是一個描述儲存有序物件序列的資料結構的介面。清單中的物件可以透過清單中的索引插入和刪除（類似於數組，但可以動態調整大小）。這個介面還有一些標準實作：ArrayList、Vector（已棄用且未實際使用）和LinkedList。

• 佇列是一個接口，描述將專案儲存在先進先出 (FIFO)佇列中的資料結構。這個介面有以下標準實作：LinkedList（沒錯，它也實作了Queue）和PriotityQueue。

第二個集合層次結構是Map層次結構，它有以下結構： 這個集合層次結構沒有分割成子集合（因為Map層次結構本身就是一個獨立的子集合）。標準Map實作是Hashtable（已棄用）、LinkedHashMap和TreeMap。在實踐中，當人們詢問Collections時，他們通常指的是兩個層次結構。

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

ArrayList就像一個數組，但它可以動態擴展。這意味著什麼？在底層，ArrayList使用普通數組，即將其元素儲存在預設大小為 10 個單元格的內部數組中。一旦內部數組滿了，就會建立一個新數組。新數組的大小由以下公式決定：

<size of the current array> * 3 / 2 + 1

因此，如果數組的大小為 10，則新數組的大小將為：10 * 3 / 2 + 1 = 16。然後使用內建函數將原始（舊）數組中的所有值複製到其中System.arraycopy( )方法，原數組被刪除。簡而言之，這就是ArrayList實現動態調整大小的方式。讓我們考慮一下最受歡迎的ArrayList方法： 1. add(<Element>) — 在先檢查陣列中是否有可用單元之後，將一個元素新增至陣列結尾（最後一個空單元）。如果沒有，則建立一個新數組，並將元素複製到其中。此操作的時間複雜度為O(1)。還有一個類似的add(<Index>, <Elelement>)方法。它不會將元素添加到列表（數組）的末尾，而是添加到作為參數傳入的索引指示的特定單元格中。在這種情況下，時間複雜度將根據您添加的位置而有所不同：

• 如果新增接近清單的開頭，那麼時間複雜度將接近 O(N)，因為位於新元素右側的所有元素都必須向右移動一個儲存格；
• 如果將元素插入到中間，那麼它將是 O(N/2)，因為我們只需要將一半的清單項目向右移動一個儲存格。

也就是說，該方法的時間複雜度範圍從 O(1) 到 O(N)，取決於插入元素的位置。2. set(<Index>, <Element>) — 將元素寫入清單中的指定位置。如果某個元素已存在於該位置，則該方法將覆寫它。這個運算的時間複雜度是O(1)，因為它不涉及任何移位運算：我們只是使用索引計算出儲存格在陣列中的位址，複雜度為O(1)，然後寫入新元素。3.remove (<index>) — 以內部陣列中的索引刪除元素。刪除不在清單末端的項目時，已刪除項目右側的所有項目都必須向左移動一個儲存格，以縮小因刪除而產生的間隙。因此，當在中間加入元素時，時間複雜度將與add(<Index>, <Element>)相同：O(N/2)。畢竟，您需要將一半元素向左移動一個單元格。如果我們談論的是開始，那麼 O(N)。或如果在最後，則 O(1)，因為您不需要移動任何東西。

87. LinkedList的內部結構是什麼？

ArrayList包含內部陣列中的元素，而LinkedList將它們儲存在雙向鍊錶中。這意味著每個元素都包含到前一個元素和下一個元素的連結。第一個元素不連結到前一個元素（畢竟，它是第一個）。它也被認為是列表的頭部，並且LinkedList物件可以直接引用它。同樣，最後一個元素沒有下一個元素，因為它是列表的尾部。LinkedList物件也直接引用它。這意味著存取清單的頭或尾的時間複雜度是 O(1)。 在ArrayList中，如果清單成長，則內部陣列也會成長。在這裡一切都變得更容易：添加引用就像更改幾個連結一樣簡單。讓我們來看看一些最常用的LinkedList方法： 1. add(<Element>) — 將一個元素加入到列表末尾，即在最後一個元素 (5) 之後，將新增指向新元素的連結作為下一個元素。新元素中的前一個引用將指向列表中現在位於其先前的元素 (5)。此操作的時間複雜度為 O(1)，因為我們只需要連結到最後一個元素，並且您會記得，LinkedList 物件具有對尾部的直接引用，並且存取它具有最小的常數時間複雜度。2. add(<Index>, <Element>) — 依索引新增元素。假設在清單中間新增元素時，此方法首先從頭部和尾部（兩個方向）迭代元素，直到找到所需的位置。如果我們在第三個和第四個元素之間添加一個元素（如上圖所示），那麼第三個元素的下一個連結將指向新元素。新加入的元素的前一個將指向第三個。反過來，舊的第四個元素的前一個連結現在將指向新元素，新元素的下一個連結將指向新的第四個元素： 此方法的時間複雜度取決於新元素的索引：

• 如果它靠近頭部或尾部，則操作將接近 O(1)，因為實際上不需要迭代元素；
• 如果靠近中間，那麼我們的時間複雜度為 O(N/2)，因為方法將同時從頭部和尾部搜索，直到找到所需的元素。

3. set(<Index>, <Element>) — 將元素寫入清單中的指定位置。此操作的時間複雜度範圍從 O(1) 到 O(N/2)，同樣取決於新元素距離頭部、尾部或中間的距離。4.remove (<index>) — 從清單中刪除一個元素，使刪除的元素之前的元素（前一個）現在引用刪除的元素之後的元素（下一個）。反之亦然，即被刪除的元素後面的元素現在引用被刪除的元素之前的元素： 此程序與按索引添加（ add(<Index>, <Element>) ）相反。

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

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

Node<K,V>[] table

預設情況下，數組的大小為 16，並且每次填充元素時都會加倍（即，當達到LOAD_FACTOR時；它指定數組可以達到的滿閾值 - 預設為0.75） 。每個節點都儲存鍵的雜湊值、鍵、值以及對下一個元素的引用：在 這種情況下，「對下一個元素的引用」意味著我們正在處理一個單鍊錶，其中每個元素都包含到下一個元素的連結。換句話說，HashMap將其資料儲存在單鍊錶數組中。但我馬上要說的是，當表數組的一個單元格具有由多個元素組成的單鍊錶時，這是不好的。這種現象稱為碰撞。但首先要說的是。讓我們看看如何使用put方法儲存新的對。首先，此方法取得金鑰的hashCode()。這意味著為了使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問題的面試。這就是今天的全部內容。待續...