Java Collections面試問題
本文是系列文章的一部分：
•Java Collections面試問題 （當前文章）
•Java類型系統面試問題
•Java並發麵試問題（+答案）
•Java類結構和初始化面試問題
•Java 8面試題（+答案）
•Java面試問題中的內存管理（+答案）
•Java泛型面試問題（+答案）
•Java流控制面試問題（+答案）
•Java異常面試問題（+答案）
•Java註釋面試問題（+答案）
•熱門Spring Framework面試問題
1.簡介
Java集合是Java開發人員經常在技術訪談中提到的主題。本文回顧了一些最常問到的重要問題，這些問題可能很難弄清。
2.問題
Q1。描述集合類型層次結構。主要接口是什麼，它們之間有什麼區別？
Iterable接口表示可以使用for-each循環進行迭代的任何集合。 Collection接口繼承自Iterable，並添加了通用方法來檢查元素是否在集合中，從集合中添加和刪除元素，確定其大小等。
List ， Set和**Queue**接口繼承自Collection接口。
List是一個有序的集合，其元素可以通過列表中的索引進行訪問。
Set是具有不同元素的無序集合，類似於集合的數學概念。
隊列是一個集合，其中包含用於添加，刪除和檢查元素的其他方法，這些方法對於在處理之前保存元素很有用。
Map接口也是collection框架的一部分，但是沒有擴展Collection 。這是設計使然，以強調集合和映射之間的差異，這些差異在通用抽像下很難收集。 Map接口表示具有唯一鍵的鍵值數據結構，每個鍵的值不超過一個。
Q2。描述Map接口的各種實現及其用例差異。
HashMap是Map接口最常用的實現之一。它是一種典型的哈希映射數據結構，它允許在恆定時間內訪問元素，即O（1），但不保留順序，也不是線程安全的。
要保留元素的插入順序，可以使用**LinkedHashMap**類，該類擴展了HashMap並另外將這些元素綁定到一個鍊錶中，並且具有可預見的開銷。
TreeMap類將其元素存儲在紅黑樹結構中，該結構允許以對數時間或O（log（n））訪問元素。在大多數情況下，它比HashMap慢，但是根據某些Comparator ，它可以使元素保持有序。
ConcurrentHashMap是哈希映射的線程安全實現。它提供了檢索的完全並發性（因為get操作不需要鎖定）和更新的高並發性。
從1.0版開始， Hashtable類就已在Java中使用。它不被棄用，但通常被認為已過時。它是一個線程安全的哈希映射，但是與ConcurrentHashMap不同，它的所有方法都是簡單同步的，這意味著對該映射塊的所有操作，甚至是獨立值的檢索。
Q3。解釋Linkedlist和Arraylist之間的區別。
ArrayList是基於數組的List接口的實現。添加或刪除元素時， ArrayList在內部處理此數組的大小調整。您可以通過數組中的索引在恆定時間內訪問其元素。但是，插入或刪除元素會導致所有後續元素發生移位，如果數組很大並且插入或刪除的元素接近列表的開頭，則可能會很慢。
LinkedList的是一個雙向鍊錶：單元素放入該有一個和下一個節點引用Node對象。如果您在列表的不同部分中有很多插入或刪除操作，特別是如果列表很大，則此實現可能比ArrayList效率更高。
但是，在大多數情況下， ArrayList優於LinkedList 。即使是ArrayList中的元素（雖然是O（n）操作），也可以通過非常快的System.arraycopy（）調用來實現。它的出現甚至比LinkedList的O（1）插入要快，後者需要實例化Node對象並在後台更新多個引用。由於創建了多個小型Node對象， LinkedList也可能具有較大的內存開銷。
Q4。哈希集和樹集有什麼區別？
HashSet和**TreeSet**類均實現Set接口並表示不同元素的集合。此外， TreeSet實現了NavigableSet接口。該接口定義了利用元素順序的方法。
HashSet在內部基於HashMap ，並且TreeSet由TreeMap實例支持，該實例定義了它們的屬性： HashSet不會以任何特定順序保留元素。對HashSet中的元素進行迭代會以隨機順序生成它們。另一方面， TreeSet根據一些預定義的Comparator順序生成元素。
Q5。如何在Java中實現Hashmap？它的實現如何使用哈希碼和對象的相等方法？從這樣的結構中放置和獲取元素的時間複雜度是多少？
HashMap類代表具有某些設計選擇的典型哈希圖數據結構。
HashMap由可調整大小的數組支持，該數組的大小為2的冪。將元素添加到HashMap時，首先將計算其hashCode （一個int值）。然後將此值的一定數量的低位用作數組索引。該索引直接指向應放置此鍵值對的數組單元（稱為存儲桶）。通過元素在數組中的索引訪問元素是非常快速的O（1）操作，這是哈希映射結構的主要特徵。
hashCode不是唯一的，即使對於不同的hashCode ，我們也可能會收到相同的數組位置。這稱為碰撞。解決哈希映射數據結構中衝突的方法不止一種。在Java的HashMap中，每個存儲桶實際上不是指向單個對象，而是指向該存儲桶中所有對象的一棵紅黑樹（在Java 8之前，這是一個鍊錶）。
因此，當HashMap確定了鍵的存儲桶時，它必須遍歷此樹以將鍵值對放置在其位置。如果存儲桶中已存在具有此類密鑰的一對，則將其替換為新密鑰。
為了通過其鍵檢索對象， HashMap再次必須計算鍵的hashCode ，找到相應的存儲桶，遍歷樹，在樹中的鍵上調用equals並找到匹配的鍵。
HashMap具有放置元素和獲取元素的O（1）複雜度或恆定時間複雜度。當然，在所有情況下，當所有元素都位於單個存儲桶中時，大量衝突可能會使性能降低到O（log（n））時間複雜度。通常可以通過提供具有均勻分佈的良好哈希函數來解決此問題。
當HashMap內部數組被填充時（在下一個問題中將對此進行詳細說明），它會自動調整為兩倍大。此操作會導致重新哈希處理（內部數據結構的重建），這很昂貴，因此您應事先計劃HashMap的大小。
Q6。 Hashmap的初始容量和負載因子參數的目的是什麼？它們的默認值是多少？
HashMap中構造函數的參數：initialCapacity參數會影響HashMap中的內部數據結構的大小，但推理關於地圖的實際大小是有點麻煩。 HashMap的內部數據結構是一個具有2的冪的數組。因此， initialCapacity參數值將增加到下一個2的冪（例如，如果將其設置為10，則內部數組的實際大小將為16）。
HashMap的負載因子是元素計數除以存儲區計數（即內部數組大小）的比率。例如，如果一個16桶的HashMap包含12個元素，則其負載係數為12/16 = 0.75。高負載係數意味著發生大量碰撞，這又意味著應將地圖調整為下一個2的冪。因此loadFactor參數是映射的負載因子的最大值。當映射達到此負載因子時，它將其內部數組的大小調整為下一個2的冪。
默認情況下， initialCapacity為16，默認情況下，loadFactor為0.75，因此您可以將12個元素放入使用默認構造函數實例化的HashMap中，並且不會調整大小。 HashSet也是如此，它由內部的HashMap實例支持。
因此，提供滿足您需求的initialCapacity並非易事。這就是為什麼Guava庫具有Maps.newHashMapWithExpectedSize（）和Sets.newHashSetWithExpectedSize（）方法的原因，這些方法使您可以構建HashMap或HashSet來容納期望數量的元素而無需調整大小。
Q7。描述枚舉的特殊收藏。與常規館藏相比，實施它們有什麼好處？
EnumSet和**EnumMap**分別是Set和Map接口的特殊實現。在處理枚舉時，應始終使用這些實現，因為它們非常有效。
EnumSet只是一個位向量，其位置與集合中存在的枚舉的有序值相對應的位置為“ 1”。為了檢查枚舉值是否在集合中，實現僅需檢查向量中的對應位是否為“ 1”，這是非常簡單的操作。同樣， EnumMap是一個以枚舉的序數值作為索引訪問的數組。對於EnumMap ，無需計算哈希碼或解決衝突。
Q8。故障快速迭代器和故障安全迭代器之間有什麼區別？
不同集合的迭代器是快速失敗或故障安全的，具體取決於它們對並行修改的反應。並發修改不僅是來自另一個線程的集合的修改，而且是來自同一線程的修改，而是使用另一個迭代器或直接修改集合。
快速失敗的迭代器（由HashMap ， ArrayList和其他非線程安全的集合返回的迭代器）遍歷集合的內部數據結構，並在檢測到並發修改時立即拋出ConcurrentModificationException 。
故障安全迭代器（由線程安全的集合（例如ConcurrentHashMap ， CopyOnWriteArrayList返回）創建它們所迭代的結構的副本。它們保證並發修改的安全性。它們的缺點包括過多的內存消耗以及在修改集合的情況下對可能過時的數據進行迭代。
Q9。如何使用可比較和比較器接口對集合進行排序？
可比較接口是對象的接口，可以根據某些順序進行比較。它的單個方法是compareTo ，它對兩個值進行操作：對象本身和相同類型的參數對象。例如， Integer ， Long和其他數字類型實現此接口。 String還實現了此接口，並且其compareTo方法按字典順序比較字符串。
Comparable接口允許使用Collections.sort（）方法對相應對象的列表進行排序，並支持實現SortedSet和SortedMap的集合中的迭代順序。如果可以使用某些邏輯對對象進行排序，則它們應實現Comparable接口。
可比接口通常使用元素的自然順序來實現。例如，所有整數編號從較小的值到較大的值排序。但是有時您可能想要實現另一種排序，例如，以降序對數字進行排序。比較器界面可以在這裡提供幫助。
您要排序的對象的類不需要實現此接口。您只需創建一個實現類並定義比較方法即可接收兩個對象並決定如何對它們進行排序。然後，您可以使用此類的實例來覆蓋Collections.sort（）方法或SortedSet和SortedMap實例的自然順序。
由於Comparator接口是功能接口，因此可以使用lambda表達式替換它，如以下示例所示。它顯示了使用自然排序（ Integer的Comparable接口）和使用自定義迭代器（ *Comparator
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1);
assertEquals(new Integer(1), list1.get(0));
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1, (a, b) -> b - a);
assertEquals(new Integer(5), list1.get(0));