知識星球（點選上方公眾號，可快速關註）
來源：ImportNew – 朱偉傑
Java集合框架（例如基本的資料結構）裡包含了最常見的Java常見面試問題。很好地理解集合框架，可以幫助你理解和利用Java的一些高階特性。下麵是面試Java核心技術的一些很實用的問題。
Q：最常見的資料結構有哪些，在哪些場景下應用它們？
A. 大部分人都會遺漏樹和圖這兩種資料結構。樹和圖都是很有用的資料結構。如果你在回答中提及到它們的話，面試者可能會對你進行進一步進行的考核。
Q:你如何自己實現List，Set和Map?
A:雖然Java已經提供了這些介面的經過實踐證明和測試過的實現，但是面試者還是喜歡這樣問，來測試你對資料結構的理解。我寫的《Core Java Career Essentials》一書中透過圖例和程式碼詳細地講解了這些內容。
常見的資料結構
陣列是最常用的資料結構。陣列的特點是長度固定，可以用下標索引，並且所有的元素的型別都是一致的。陣列常用的場景有把：從資料庫裡讀取僱員的資訊儲存為EmployeeDetail[]，把一個字串轉換並儲存到一個位元組陣列中便於操作和處理，等等。儘量把陣列封裝在一個類裡，防止資料被錯誤的操作弄亂。另外，這一點也適合其他的資料結構。
串列和陣列很相似，只不過它的大小可以改變。串列一般都是透過一個固定大小的陣列來實現的，並且會在需要的時候自動調整大小。串列裡可以包含重覆的元素。常用的場景有，新增一行新的項到訂單串列裡，把所有過期的商品移出商品串列，等等。一般會把串列初始化成一個合適的大小，以減少調整大小的次數。
集合和串列很相似，不過它不能放重覆的元素。當你需要儲存不同的元素時，你可以使用集合。
堆疊只允許對最後插入的元素進行操作（也就是後進先出，Last In First Out – LIFO）。如果你移除了棧頂的元素，那麼你可以操作倒數第二個元素，依次類推。這種後進先出的方式是透過僅有的peek(),push()和pop()這幾個方法的強制性限制達到的。這種結構在很多場景下都非常實用，例如解析像(4+2)*3這樣的數學運算式，把原始碼中的方法和異常按照他們出現的順序放到堆疊中，檢查你的程式碼看看小括號和花括號是不是匹配的，等等。
這種用堆疊來實現的後進先出（LIFO)的機制在很多地方都非常實用。例如，運算式求值和語法解析，校驗和解析XML，文字編輯器裡的撤銷動作，瀏覽器裡的瀏覽記錄，等等。這裡是一些關於堆疊的一些Java面試題。
佇列和堆疊有些相似，不同之處在於在佇列裡第一個插入的元素也是第一個被刪除的元素（即是先進先出）。這種先進先出的結構是透過只提供peek()，offer()和poll()這幾個方法來訪問資料進行限制來達到的。例如，排隊等待公交車，銀行或者超市裡的等待列隊等等，都是可以用佇列來表示。
這裡是一個用多執行緒來訪問阻塞佇列的例子。
http://java-success.blogspot.com.au/2012/04/multi-threading-with-blocking-queues.html
連結串列是一種由多個節點組成的資料結構，並且每個節點包含有資料以及指向下一個節點的取用，在雙向連結串列裡，還會有一個指向前一個節點的取用。例如，可以用單向連結串列和雙向連結串列來實現堆疊和佇列，因為連結串列的兩端都是可以進行插入和刪除的動作的。當然，也會有在連結串列的中間頻繁插入和刪除節點的場景。Apache的類庫裡提供了一個TreeList的實現，它是連結串列的一個很好的替代，因為它只多佔用了一點記憶體，但是效能比連結串列好很多。也就是說，從這點來看連結串列其實不是一個很好的選擇。
ArrayList是串列的一個很好的實現。相比較TreeList而言，ArrayList在除了在串列中間插入或者刪除元素的情況，其他操作都比TreeList快很多。TreeList的實現是在內部使用了一個樹形的結構來保證所有的插入和刪除動作的複雜度都是O(log n)的。這種實現方式使得TreeList在頻繁插入和刪除元素的時候的效能遠遠高於ArrayList和LinkedList。
class Link {
private int id; // data
private String name; // data
private Link next; // reference to next link
}
HashMap的訪問時間接近穩定，它是一種鍵值對對映的資料結構。這個資料結構是透過陣列來實現的。它透過hash函式來給元素定位，並且用衝突檢測演演算法來處理被hash到同一位置的值。例如，儲存僱員的資訊可以用僱員的id來作為key，對從properties檔案裡讀入的屬性-屬性值可以用key/value對來儲存，等等。HashMap在初始化的時候，給定一個合適的大小可以減少調整大小的次數。
樹是一種由節點組成的資料結構，每個節點都包含資料元素，並且有一個或多個子節點，每個子節點指向一個父節點（譯者註：除了根節點）可以表示層級關係或者資料元素的順序關係。常用的場景有表示一個組織裡的僱員層級關係，XML元素的層級關係，等等。如果樹的每個子節點最多有兩個葉子節點，那麼這種樹被稱為二叉樹。二叉樹是一種非常常用的樹形結構， 因為它的這種結構使得節點的插入和刪除都非常高效。樹的邊表示從一個節點到另外一個節點的快捷路徑。
Java裡面沒有直接提供樹的實現，但是它很容易透過下麵的方式來實現。只需要建立一個Node物件，裡麵包含一個指向葉子節點的ArrayList。
package bigo;
import java.util.ArrayList;
import java.util.List;
public class Node {
private String name;
private List
children = new ArrayList ( ); private Node parent;
public Node getParent( ) {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node(String name) {
this.name = name;
}
public void addChild(Node child) {
children.add(child);
}
public void removeChild(Node child) {
children.remove(child);
}
public String toString( ) {
return name;
}
}
只要資料元素的關係可以表示成節點和邊的網狀結構的話，就可以用圖來表示。樹是一種特殊的圖，它的所有節點都只能有一個父節點。和樹不同的是，圖的形狀是由實際問題或者問題的抽象來決定的。例如，圖中節點（或者頂點）可以表示不同的城市，而圖的邊則可以表示兩個城市之間的航線。
在Java裡構造一個圖，你需要解決資料透過什麼方式儲存和訪問的問題。在圖裡面也會用到上面提到的資料結構。Java的API裡沒有提供圖的實現。不過有很多第三方庫裡提供了，例如JUNG，JGraphT，以及JDSL（不過好像不支援泛型）。《Core Java Career Essential》一書包含了用Java實現的可用示例。
Q:你對大O這個符號有什麼瞭解呢，你是否可以根據不同的資料結構舉出一些列子來？
A：大O符號可以表示一個演演算法的效率，也可以用來描述當資料元素增加時，最壞情況下的演演算法的效能。大O符號也可以用來衡量的效能，例如記憶體消耗量。有時候你可能會為了減少記憶體使用量而選擇一個比較慢的演演算法。大O符號可以表示在大量資料的情況下程式的效能。不過，對於程式在大量資料量下的效能的測量，唯一比較實際的方式是行用較大的資料集來進行效能基準測試，這樣可以把一些在大O複雜度分析裡沒有考慮到的情況包含進去，例如在虛擬記憶體使用比較多的時候系統會發生換頁的情況。雖然基準測試比大O符號表示的結果更加實際，但是它不適用於設計階段，所以在這個這時候大O複雜度分析是最合適的選擇。
各種資料結構在搜尋，插入和刪除演演算法上的效能都可以用下麵方式表示：常量複雜度O(1)，線性複雜度O(n)，對數複雜度O(log n)，指數複雜度O(c^n)，多項式複雜度O(n^c)，平方複雜度O(n^2)以及階乘複雜度O(n!)，這裡面的n都指的是資料結構裡的元素的數量。效能和記憶體佔用是可以相互權衡的。下麵是一些示例。
示例1：在HashMap裡查詢一個元素的的時間複雜度是常量的，也即是O(1)。這是因為查詢元素使用的是雜湊函式，並且計算一個雜湊值的時間是不受HashMap裡的元素的個數的影響的。
示例2：線性搜尋一個陣列，串列以及連結串列都是的複雜度線性的，也即是O(n)，這是查詢的時候需要遍歷整個串列。也就是說，如果一個串列的長度是原來的兩倍，那麼搜尋所花的時間也是原來的兩倍。
示例3：一個需要比較陣列裡的所有元素的排序演演算法的複雜度是多項式的，即是O(n^2)。這是因為一個巢狀的for迴圈的複雜度是O(n^2)。在搜素演演算法裡有這樣的例子。
示例4：二分搜尋一個陣列或者陣列串列的複雜度是對數的，即是O(log n)。在連結串列裡查詢一個節點的複雜度一般是O(n)。相比較陣列連結串列和陣列的O(log n)的效能而言，隨著元素數量的增長，連結串列的O(n)的複雜度的效能就比較差了。對數的時間複雜度就是如果10個元素花費的時間是x單位的話，100個元素最多花費2x單位的時間，而10000個元素最多花費4x個單位的時間。如果你在一個平面坐標上畫出圖形的話，你會發現時間的增長沒有n（元素的個數）快。
Q：HashMap和TreeMap在效能上有什麼樣的差別呢？你比較傾向於使用哪一個?
A：一個平衡樹的效能是O(logn)。Java裡的TreeMap用一個紅黑樹來保證key/value的排序。紅黑樹是平衡二叉樹。保證二叉樹的平衡性，使得插入，刪除和查詢都比較快，時間複雜度都是O(log n)。不過它沒有HashMap快，HashMap的時間複雜度是O(1)，但是TreeMap的優點在於它裡面鍵值是排過序的，這樣就提供了一些其他的很有用的功能。
Q：怎麼去選擇該使用哪一個呢？
A:使用無序的HashSet和HashMap，還是使用有序的TreeSet和TreeMap，主要取決於你的實際使用場景，一定程度上還和資料的大小以及執行環境有關。比較實際的一個原因是，如果插入和更新都比較頻繁的話，那麼保證元素的有序可以提高快速和頻繁查詢的效能。如果對於排序操作（例如產生一個報表合作者執行一個批處理程式）的要求不是很頻繁的話，那麼把資料以無序的方式儲存，然後在需要排序的時候用Collections.sort(…)來進行排序，會比用有序的方式來儲存可能會更加高效。這個只是一種可選的方式，沒人能給你一個確切的答案。即使是複雜度的理論，例如O(n)，成立的前提也是在n足夠大的情況下。只要在n足夠小的情況下，就算是O(n)的演演算法也可能會比O（log n)的演演算法更加高效。另外，一個演演算法可能在AMD處理器上的速度比在Intel處理器上快。如果你的系統有交換區的話，那麼你還要考慮磁碟的效能。唯一可以確定的效能測試途徑是用大小合適的資料來測試和衡量程式的效能和記憶體使用量。在你所選擇的硬體上來測試這兩種指標，是最合適的方法。
Q：如何權衡是用無序的陣列還是有序的陣列呢？
A：有序陣列最大的優點在於n比較大的時候，搜尋元素所花的時間O(log n)比無序素組所需要的時間O(n)要少很多。有序陣列的缺點在於插入的時間開銷比較大（一般是O(n))，因為所有比插入元素大的值都要往後移動。而無序陣列的插入時間開銷是常量時間，也就是說，插入的速度和元素的數量無關。下麵的程式碼片段展示了向有序陣列和無序陣列插入元素。
插入元素到一個無序的陣列裡
package bigo;
import java.util.Arrays;
public class InsertingElementsToArray {
public static void insertUnsortedArray(String toInsert) {
String[ ] unsortedArray = { “A”, “D”, “C” };
String[ ] newUnsortedArray = new String[unsortedArray.length + 1];
System.arraycopy(unsortedArray, 0, newUnsortedArray, 0, 3);
newUnsortedArray[newUnsortedArray.length – 1] = toInsert;
System.out.println(Arrays.toString(newUnsortedArray));
}
public static void main(String[ ] args) {
insertUnsortedArray(“B”);
}
}
插入元素到一個有序陣列
package bigo;
import java.util.Arrays;
public class InsertingElementsToArray {
public static void insertSortedArray(String toInsert) {
String[ ] sortedArray = { “A”, “C”, “D” };
/*
* Binary search returns the index of the search item
* if found, otherwise returns the minus insertion point. This example
* returns index = -2, which means the elemnt is not found and needs to
* be inserted as a second element.
*/
int index = Arrays.binarySearch(sortedArray, toInsert);
if (index < 0) { // not found.
// array indices are zero based. -2 index means insertion point of
// -(-2)-1 = 1, so insertIndex = 1
int insertIndex = -index – 1;
String[ ] newSortedArray = new String[sortedArray.length + 1];
System.arraycopy(sortedArray, 0, newSortedArray, 0, insertIndex);
System.arraycopy(sortedArray, insertIndex,
newSortedArray, insertIndex + 1, sortedArray.length – insertIndex);
newSortedArray[insertIndex] = toInsert;
System.out.println(Arrays.toString(newSortedArray));
}
}
public static void main(String[ ] args) {
insertSortedArray(“B”);
}
}
所以，如何去選擇還是取決於實際的使用情況。你需要考慮下麵幾個問題。你的程式是插入/刪除的操作多，還是查詢的操作多？陣列裡最多可能儲存多少元素？排序的頻率是多少？以及你的效能基準測試的結果是怎樣的？
Q：怎麼實現一個不可變集合？
A：這個功能在Collections類裡實現了，它透過裝飾樣式實現了對一般集合的封裝。
public class ReadOnlyExample {
public static void main(String args[ ]) {
Set
set = new HashSet ( ); set.add(“Java”);
set.add(“JEE”);
set.add(“Spring”);
set.add(“Hibernate”);
set = Collections.unmodifiableSet(set);
set.add(“Ajax”); // not allowed.
}
}
Q：下麵的程式碼的功能是什麼呢？其中的LinkedHashSet能用HashSet來取代嗎？
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
public class CollectionFunction {
public
List function (List list) { return new ArrayList
(new LinkedHashSet (list)); }
}
A：上面的程式碼程式碼透過把原有串列傳入一個LinkedHashSet來去除重覆的元素。在這個情況裡，LinkedHashSet可以保持元素原來的順序。如果這個順序是不需要的話，那麼上面的LinkedHashSet可以用HashSet來替換。
Q：Java集合框架都有哪些最佳實踐呢？
A：根據實際的使用情況選擇合適的資料結構，例如固定大小的還是需要增加大小的，有重覆元素的還是沒有的，需要保持有序還是不需要，遍歷是正向的還是雙向的，插入是在末尾的還是任意位置的，更多的插入還是更多的讀取，是否需要並行訪問，是否允許修改，元素型別是相同的還是不同的，等等。另外，還需要儘早考慮多執行緒，原子性，記憶體使用量以及效能等因素。
不要假設你的集合裡元素的數量一直會保持較小，它也有可能隨著時間增長。所以，你的集合最好能夠給定一個合適的大小。
針對介面程式設計優於針對實現程式設計。例如，可能在某些情況下，LinkedList是最佳的選擇，但是後來ArrayList可能因為效能的原因變得更加合適
不好的方式:
ArrayList list = new ArrayList(100);
好的方式:
// program to interface so that the implementation can change
List list = new ArrayList(100);
List list2 = new LinkedList(100);
List emptyList = Collections.emptyList( );
Set emptySet = Collections.emptySet( );
在取得串列的時候，如果傳回的結果是空的話，最好傳回一個長度為0的集合或者陣列，而不要傳回null。因為，傳回null的話可能能會導致程式錯誤。呼叫你的方法的開發人員可能會忘記對傳回為null的情況進行處理。
封裝好集合：一般來說，集合都是不可變的物件。所以儘量不要把集合的成員變數暴露給呼叫者。因為他們的操作一般都不會進行必要的校驗。
註：這些Java面試題和答案都是從我的書《Core Java Career Essentials》裡提取出來的。
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
