Java集合框架（例如基本的數(shù)據(jù)結(jié)構(gòu)）里包含了最常見的Java常見面試問題。很好地理解集合框架，可以幫助你理解和利用Java的一些高級特性。下面是面試Java核心技術(shù)的一些很實用的問題。
Q：最常見的數(shù)據(jù)結(jié)構(gòu)有哪些，在哪些場景下應用它們？
A. 大部分人都會遺漏樹和圖這兩種數(shù)據(jù)結(jié)構(gòu)。樹和圖都是很有用的數(shù)據(jù)結(jié)構(gòu)。如果你在回答中提及到它們的話，面試者可能會對你進行進一步進行的考核。
Q:你如何自己實現(xiàn)List，Set和Map?
A:雖然Java已經(jīng)提供了這些接口的經(jīng)過實踐證明和測試過的實現(xiàn)，但是面試者還是喜歡這樣問，來測試你對數(shù)據(jù)結(jié)構(gòu)的理解。我寫的《Core Java Career Essentials》一書中通過圖例和代碼詳細地講解了這些內(nèi)容。
常見的數(shù)據(jù)結(jié)構(gòu)
數(shù)組是最常用的數(shù)據(jù)結(jié)構(gòu)。數(shù)組的特點是長度固定，可以用下標索引，并且所有的元素的類型都是一致的。數(shù)組常用的場景有把：從數(shù)據(jù)庫里讀取雇員的信息存儲為EmployeeDetail[]，把一個字符串轉(zhuǎn)換并存儲到一個字節(jié)數(shù)組中便于操作和處理，等等。盡量把數(shù)組封裝在一個類里，防止數(shù)據(jù)被錯誤的操作弄亂。另外，這一點也適合其他的數(shù)據(jù)結(jié)構(gòu)。
列表和數(shù)組很相似，只不過它的大小可以改變。列表一般都是通過一個固定大小的數(shù)組來實現(xiàn)的，并且會在需要的時候自動調(diào)整大小。列表里可以包含重復的元素。常用的場景有，添加一行新的項到訂單列表里，把所有過期的商品移出商品列表，等等。一般會把列表初始化成一個合適的大小，以減少調(diào)整大小的次數(shù)。
集合和列表很相似，不過它不能放重復的元素。當你需要存儲不同的元素時，你可以使用集合。
堆棧只允許對最后插入的元素進行操作（也就是后進先出，Last In First Out – LIFO）。如果你移除了棧頂?shù)脑兀敲茨憧梢圆僮鞯箶?shù)第二個元素，依次類推。這種后進先出的方式是通過僅有的peek(),push()和pop()這幾個方法的強制性限制達到的。這種結(jié)構(gòu)在很多場景下都非常實用，例如解析像(4+2)*3這樣的數(shù)學表達式，把源碼中的方法和異常按照他們出現(xiàn)的順序放到堆棧中，檢查你的代碼看看小括號和花括號是不是匹配的，等等。
這種用堆棧來實現(xiàn)的后進先出（LIFO)的機制在很多地方都非常實用。例如，表達式求值和語法解析，校驗和解析XML，文本編輯器里的撤銷動作，瀏覽器里的瀏覽記錄，等等。這里是一些關(guān)于堆棧的一些Java面試題。
隊列和堆棧有些相似，不同之處在于在隊列里第一個插入的元素也是第一個被刪除的元素（即是先進先出）。這種先進先出的結(jié)構(gòu)是通過只提供peek()，offer()和poll()這幾個方法來訪問數(shù)據(jù)進行限制來達到的。例如，排隊等待公交車，銀行或者超市里的等待列隊等等，都是可以用隊列來表示。
這里是一個用多線程來訪問阻塞隊列的例子。
鏈表是一種由多個節(jié)點組成的數(shù)據(jù)結(jié)構(gòu)，并且每個節(jié)點包含有數(shù)據(jù)以及指向下一個節(jié)點的引用，在雙向鏈表里，還會有一個指向前一個節(jié)點的引用。例如，可以用單向鏈表和雙向鏈表來實現(xiàn)堆棧和隊列，因為鏈表的兩端都是可以進行插入和刪除的動作的。當然，也會有在鏈表的中間頻繁插入和刪除節(jié)點的場景。Apache的類庫里提供了一個TreeList的實現(xiàn)，它是鏈表的一個很好的替代，因為它只多占用了一點內(nèi)存，但是性能比鏈表好很多。也就是說，從這點來看鏈表其實不是一個很好的選擇。
ArrayList是列表的一個很好的實現(xiàn)。相比較TreeList而言，ArrayList在除了在列表中間插入或者刪除元素的情況，其他操作都比TreeList快很多。TreeList的實現(xiàn)是在內(nèi)部使用了一個樹形的結(jié)構(gòu)來保證所有的插入和刪除動作的復雜度都是O(log n)的。這種實現(xiàn)方式使得TreeList在頻繁插入和刪除元素的時候的性能遠遠高于ArrayList和LinkedList。
classLink {
???privateintid;??????????????????? // data
???privateString name;?????????????? // data
???privateLink next;???????????????? // reference to next link
}
HashMap的訪問時間接近穩(wěn)定，它是一種鍵值對映射的數(shù)據(jù)結(jié)構(gòu)。這個數(shù)據(jù)結(jié)構(gòu)是通過數(shù)組來實現(xiàn)的。它通過hash函數(shù)來給元素定位，并且用沖突檢測算法來處理被hash到同一位置的值。例如，保存雇員的信息可以用雇員的id來作為key，對從properties文件里讀入的屬性-屬性值可以用key/value對來保存，等等。HashMap在初始化的時候，給定一個合適的大小可以減少調(diào)整大小的次數(shù)。
樹是一種由節(jié)點組成的數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點都包含數(shù)據(jù)元素，并且有一個或多個子節(jié)點，每個子節(jié)點指向一個父節(jié)點（譯者注：除了根節(jié)點）可以表示層級關(guān)系或者數(shù)據(jù)元素的順序關(guān)系。常用的場景有表示一個組織里的雇員層級關(guān)系，XML元素的層級關(guān)系，等等。如果樹的每個子節(jié)點最多有兩個葉子節(jié)點，那么這種樹被稱為二叉樹。二叉樹是一種非常常用的樹形結(jié)構(gòu)， 因為它的這種結(jié)構(gòu)使得節(jié)點的插入和刪除都非常高效。樹的邊表示從一個節(jié)點到另外一個節(jié)點的快捷路徑。
Java里面沒有直接提供樹的實現(xiàn)，但是它很容易通過下面的方式來實現(xiàn)。只需要創(chuàng)建一個Node對象，里面包含一個指向葉子節(jié)點的ArrayList。
packagebigo;
importjava.util.ArrayList;
importjava.util.List;
publicclassNode {
????privateString name;
????privateList<node> children = newArrayList<node>( );
????privateNode parent;
????publicNode getParent( ) {
????????returnparent;
????}
????publicvoidsetParent(Node parent) {
????????this.parent = parent;
????}
????publicNode(String name) {
????????this.name = name;
????}
????publicvoidaddChild(Node child) {
????????children.add(child);
????}
????publicvoidremoveChild(Node child) {
????????children.remove(child);
????}
????publicString toString( ) {
????????returnname;
????}
?}
只要數(shù)據(jù)元素的關(guān)系可以表示成節(jié)點和邊的網(wǎng)狀結(jié)構(gòu)的話，就可以用圖來表示。樹是一種特殊的圖，它的所有節(jié)點都只能有一個父節(jié)點。和樹不同的是，圖的形狀是由實際問題或者問題的抽象來決定的。例如，圖中節(jié)點（或者頂點）可以表示不同的城市，而圖的邊則可以表示兩個城市之間的航線。
在Java里構(gòu)造一個圖，你需要解決數(shù)據(jù)通過什么方式保存和訪問的問題。在圖里面也會用到上面提到的數(shù)據(jù)結(jié)構(gòu)。Java的API里沒有提供圖的實現(xiàn)。不過有很多第三方庫里提供了，例如JUNG，JGraphT，以及JDSL（不過好像不支持泛型）?！禖ore Java Career Essential》一書包含了用Java實現(xiàn)的可用示例。
Q:你對大O這個符號有什么了解呢，你是否可以根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)舉出一些列子來？
A：大O符號可以表示一個算法的效率，也可以用來描述當數(shù)據(jù)元素增加時，最壞情況下的算法的性能。大O符號也可以用來衡量的性能，例如內(nèi)存消耗量。有時候你可能會為了減少內(nèi)存使用量而選擇一個比較慢的算法。大O符號可以表示在大量數(shù)據(jù)的情況下程序的性能。不過，對于程序在大量數(shù)據(jù)量下的性能的測量，唯一比較實際的方式是行用較大的數(shù)據(jù)集來進行性能基準測試，這樣可以把一些在大O復雜度分析里沒有考慮到的情況包含進去，例如在虛擬內(nèi)存使用比較多的時候系統(tǒng)會發(fā)生換頁的情況。雖然基準測試比大O符號表示的結(jié)果更加實際，但是它不適用于設(shè)計階段，所以在這個這時候大O復雜度分析是最合適的選擇。
各種數(shù)據(jù)結(jié)構(gòu)在搜索，插入和刪除算法上的性能都可以用下面方式表示：常量復雜度O(1)，線性復雜度O(n)，對數(shù)復雜度O(log n)，指數(shù)復雜度O(c^n)，多項式復雜度O(n^c)，平方復雜度O(n^2)以及階乘復雜度O(n!)，這里面的n都指的是數(shù)據(jù)結(jié)構(gòu)里的元素的數(shù)量。性能和內(nèi)存占用是可以相互權(quán)衡的。下面是一些示例。
示例1：在HashMap里查找一個元素的的時間復雜度是常量的，也即是O(1)。這是因為查找元素使用的是哈希函數(shù)，并且計算一個哈希值的時間是不受HashMap里的元素的個數(shù)的影響的。
示例2：線性搜索一個數(shù)組，列表以及鏈表都是的復雜度線性的，也即是O(n)，這是查找的時候需要遍歷整個列表。也就是說，如果一個列表的長度是原來的兩倍，那么搜索所花的時間也是原來的兩倍。
示例3：一個需要比較數(shù)組里的所有元素的排序算法的復雜度是多項式的，即是O(n^2)。這是因為一個嵌套的for循環(huán)的復雜度是O(n^2)。在搜素算法里有這樣的例子。
示例4：二分搜索一個數(shù)組或者數(shù)組列表的復雜度是對數(shù)的，即是O(log n)。在鏈表里查詢一個節(jié)點的復雜度一般是O(n)。相比較數(shù)組鏈表和數(shù)組的O(log n)的性能而言，隨著元素數(shù)量的增長，鏈表的O(n)的復雜度的性能就比較差了。對數(shù)的時間復雜度就是如果10個元素花費的時間是x單位的話，100個元素最多花費2x單位的時間，而10000個元素最多花費4x個單位的時間。如果你在一個平面坐標上畫出圖形的話，你會發(fā)現(xiàn)時間的增長沒有n（元素的個數(shù)）快。
Q：HashMap和TreeMap在性能上有什么樣的差別呢？你比較傾向于使用哪一個?
A：一個平衡樹的性能是O(logn)。Java里的TreeMap用一個紅黑樹來保證key/value的排序。紅黑樹是平衡二叉樹。保證二叉樹的平衡性，使得插入，刪除和查找都比較快，時間復雜度都是O(log n)。不過它沒有HashMap快，HashMap的時間復雜度是O(1)，但是TreeMap的優(yōu)點在于它里面鍵值是排過序的，這樣就提供了一些其他的很有用的功能。
Q：怎么去選擇該使用哪一個呢？
A:使用無序的HashSet和HashMap，還是使用有序的TreeSet和TreeMap，主要取決于你的實際使用場景，一定程度上還和數(shù)據(jù)的大小以及運行環(huán)境有關(guān)。比較實際的一個原因是，如果插入和更新都比較頻繁的話，那么保證元素的有序可以提高快速和頻繁查找的性能。如果對于排序操作（例如產(chǎn)生一個報表合作者運行一個批處理程序）的要求不是很頻繁的話，那么把數(shù)據(jù)以無序的方式存儲，然后在需要排序的時候用Collections.sort(…)來進行排序，會比用有序的方式來存儲可能會更加高效。這個只是一種可選的方式，沒人能給你一個確切的答案。即使是復雜度的理論，例如O(n)，成立的前提也是在n足夠大的情況下。只要在n足夠小的情況下，就算是O(n)的算法也可能會比O（log n)的算法更加高效。另外，一個算法可能在AMD處理器上的速度比在Intel處理器上快。如果你的系統(tǒng)有交換區(qū)的話，那么你還要考慮磁盤的性能。唯一可以確定的性能測試途徑是用大小合適的數(shù)據(jù)來測試和衡量程序的性能和內(nèi)存使用量。在你所選擇的硬件上來測試這兩種指標，是最合適的方法。
Q：如何權(quán)衡是用無序的數(shù)組還是有序的數(shù)組呢？
A：有序數(shù)組最大的優(yōu)點在于n比較大的時候，搜索元素所花的時間O(log n)比無序素組所需要的時間O(n)要少很多。有序數(shù)組的缺點在于插入的時間開銷比較大（一般是O(n))，因為所有比插入元素大的值都要往后移動。而無序數(shù)組的插入時間開銷是常量時間，也就是說，插入的速度和元素的數(shù)量無關(guān)。下面的代碼片段展示了向有序數(shù)組和無序數(shù)組插入元素。
插入元素到一個無序的數(shù)組里
packagebigo;
importjava.util.Arrays;
publicclassInsertingElementsToArray {
????publicstaticvoidinsertUnsortedArray(String toInsert) {
????????String[ ] unsortedArray = { "A", "D", "C"};
????????String[ ] newUnsortedArray = newString[unsortedArray.length + 1];
????????System.arraycopy(unsortedArray, 0, newUnsortedArray, 0, 3);
????????newUnsortedArray[newUnsortedArray.length - 1] = toInsert;
????????System.out.println(Arrays.toString(newUnsortedArray));
????}
????publicstaticvoidmain(String[ ] args) {
????????insertUnsortedArray("B");
????}
}
插入元素到一個有序數(shù)組
packagebigo;
importjava.util.Arrays;
publicclassInsertingElementsToArray {
????publicstaticvoidinsertSortedArray(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.
?????????*/
????????intindex = 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
????????????intinsertIndex = -index - 1;
????????????String[ ] newSortedArray = newString[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));
????????}
????}
????publicstaticvoidmain(String[ ] args) {
????????insertSortedArray("B");
????}
}
所以，如何去選擇還是取決于實際的使用情況。你需要考慮下面幾個問題。你的程序是插入/刪除的操作多，還是查找的操作多？數(shù)組里最多可能存儲多少元素？排序的頻率是多少？以及你的性能基準測試的結(jié)果是怎樣的？
Q：怎么實現(xiàn)一個不可變集合？
A：這個功能在Collections類里實現(xiàn)了，它通過裝飾模式實現(xiàn)了對一般集合的封裝。
publicclassReadOnlyExample {
????publicstaticvoidmain(String args[ ]) {
????????Set<string> set = newHashSet<string>( );
????????set.add("Java");
????????set.add("JEE");
????????set.add("Spring");
????????set.add("Hibernate");
????????set = Collections.unmodifiableSet(set);
????????set.add("Ajax");?????????????????????????????????????????? // not allowed.
??}
}
Q：下面的代碼的功能是什么呢？其中的LinkedHashSet能用HashSet來取代嗎？
importjava.util.ArrayList;
importjava.util.LinkedHashSet;
importjava.util.List;
publicclassCollectionFunction {
????public<e> List<e> function (List <e> list) {
??????????returnnewArrayList<e>(newLinkedHashSet<e>(list));
????}
}
A：上面的代碼代碼通過把原有列表傳入一個LinkedHashSet來去除重復的元素。在這個情況里，LinkedHashSet可以保持元素原來的順序。如果這個順序是不需要的話，那么上面的LinkedHashSet可以用HashSet來替換。
Q：Java集合框架都有哪些最佳實踐呢？
A：根據(jù)實際的使用情況選擇合適的數(shù)據(jù)結(jié)構(gòu)，例如固定大小的還是需要增加大小的，有重復元素的還是沒有的，需要保持有序還是不需要，遍歷是正向的還是雙向的，插入是在末尾的還是任意位置的，更多的插入還是更多的讀取，是否需要并行訪問，是否允許修改，元素類型是相同的還是不同的，等等。另外，還需要盡早考慮多線程，原子性，內(nèi)存使用量以及性能等因素。
不要假設(shè)你的集合里元素的數(shù)量一直會保持較小，它也有可能隨著時間增長。所以，你的集合最好能夠給定一個合適的大小。
針對接口編程優(yōu)于針對實現(xiàn)編程。例如，可能在某些情況下，LinkedList是最佳的選擇，但是后來ArrayList可能因為性能的原因變得更加合適
?不好的方式:
1ArrayList list = newArrayList(100);
好的方式:
// program to interface so that the implementation can change
List list = newArrayList(100);
List list2 = newLinkedList(100);
List emptyList = Collections.emptyList( );
Set emptySet = Collections.emptySet( );
在取得列表的時候，如果返回的結(jié)果是空的話，最好返回一個長度為0的集合或者數(shù)組，而不要返回null。因為，返回null的話可能能會導致程序錯誤。調(diào)用你的方法的開發(fā)人員可能會忘記對返回為null的情況進行處理。
封裝好集合：一般來說，集合都是不可變的對象。所以盡量不要把集合的成員變量暴露給調(diào)用者。因為他們的操作一般都不會進行必要的校驗。
歡迎學Java和大數(shù)據(jù)的朋友們加入java架構(gòu)交流： 855835163
群內(nèi)提供免費的架構(gòu)資料還有：Java工程化、高性能及分布式、高性能、深入淺出。高架構(gòu)。性能調(diào)優(yōu)、Spring，MyBatis，Netty源碼分析和大數(shù)據(jù)等多個知識點高級進階干貨的免費直播講解? 可以進來一起學習交流哦
