大公司最喜歡問的Java集合類面試題

看了一些所謂大公司的java面試問題，發現對于java集合類的使用都比較看重似的，而自己在這方面還真的是所真甚少，抽空也學習學習吧。

java.util包中包含了一系列重要的集合類，而對于集合類，主要需要掌握的就是它的内部結構，以及周遊集合的疊代模式。

collection是最基本的集合接口，一個collection代表一組object，即collection的元素（elements）。一些collection允許相同的元素而另一些不行。一些能排序而另一些不行。java sdk不提供直接繼承自collection的類，java sdk提供的類都是繼承自collection的“子接口”如list和set。

所有實作collection接口的類都必須提供兩個标準的構造函數：無參數的構造函數用于建立一個空的collection，有一個collection參數的構造函數用于建立一個新的collection，這個新的collection與傳入的collection有相同的元素。後一個構造函數允許使用者複制一個collection。

主要的一個接口方法：boolean add(ojbect c)

雖然傳回的是boolean，但不是表示添加成功與否，這個傳回值表示的意義是add()執行後，集合的内容是否改變了（就是元素的數量、位置等有無變化）。類似的addall，remove，removeall，remainall也是一樣的。如果你想學習java可以來這個群，首先是二二零，中間是一四二，最後是九零六，裡面有大量的學習資料可以下載下傳。

collection有一個重要的方法：iterator()，傳回一個iterator（疊代器），用于周遊集合的所有元素。iterator模式可以把通路邏輯從不同的集合類中抽象出來，進而避免向用戶端暴露集合的内部結構。典型的用法如下：

不需要維護周遊集合的“指針”，所有的内部狀态都由iterator來維護，而這個iterator由集合類通過工廠方法生成。

每一種集合類傳回的iterator具體類型可能不同，但它們都實作了iterator接口，是以，我們不需要關心到底是哪種iterator，它隻需要獲得這個iterator接口即可，這就是接口的好處，面向對象的威力。

要確定周遊過程順利完成，必須保證周遊過程中不更改集合的内容（iterator的remove()方法除外），是以，確定周遊可靠的原則是：隻在一個線程中使用這個集合，或者在多線程中對周遊代碼進行同步。

由collection接口派生的兩個接口是list和set。

list是有序的collection，使用此接口能夠精确的控制每個元素插入的位置。使用者能夠使用索引（元素在list中的位置，類似于數組下标）來通路list中的元素，這類似于java的數組。和下面要提到的set不同，list允許有相同的元素。

除了具有collection接口必備的iterator()方法外，list還提供一個listiterator()方法，傳回一個listiterator接口，和标準的iterator接口相比，listiterator多了一些add()之類的方法，允許添加，删除，設定元素，還能向前或向後周遊。

實作list接口的常用類有linkedlist，arraylist，vector和stack。

linkedlist實作了list接口，允許null元素。此外linkedlist提供額外的get，remove，insert方法在linkedlist的首部或尾部。這些操作使linkedlist可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。

注意linkedlist沒有同步方法。如果多個線程同時通路一個list，則必須自己實作通路同步。一種解決方法是在建立list時構造一個同步的list：

list list = collections.synchronizedlist(new linkedlist(…));

arraylist實作了可變大小的數組。它允許所有元素，包括null。arraylist沒有同步。

size，isempty，get，set方法運作時間為常數。但是add方法開銷為分攤的常數，添加n個元素需要o(n)的時間。其他的方法運作時間為線性。

每個arraylist執行個體都有一個容量（capacity），即用于存儲元素的數組的大小。這個容量可随着不斷添加新元素而自動增加，但是增長算法并沒有定義。當需要插入大量元素時，在插入前可以調用ensurecapacity方法來增加arraylist的容量以提高插入效率。

和linkedlist一樣，arraylist也是非同步的（unsynchronized）。

vector非常類似arraylist，但是vector是同步的。由vector建立的iterator，雖然和arraylist建立的iterator是同一接口，但是，因為vector是同步的，當一個iterator被建立而且正在被使用，另一個線程改變了vector的狀态（例如，添加或删除了一些元素），這時調用iterator的方法時将抛出concurrentmodificationexception，是以必須捕獲該異常。

stack繼承自vector，實作一個後進先出的堆棧。stack提供5個額外的方法使得vector得以被當作堆棧使用。基本的push和pop方法，還有peek方法得到棧頂的元素，empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。stack剛建立後是空棧。

set是一種不包含重複的元素的collection，即任意的兩個元素e1和e2都有e1.equals(e2)=false，set最多有一個null元素。

很明顯，set的構造函數有一個限制條件，傳入的collection參數不能包含重複的元素。

請注意：必須小心操作可變對象（mutable object）。如果一個set中的可變元素改變了自身狀态導緻object.equals(object)=true将導緻一些問題。

請注意，map沒有繼承collection接口，map提供key到value的映射。一個map中不能包含相同的key，每個key隻能映射一個value。map接口提供3種集合的視圖，map的内容可以被當作一組key集合，一組value集合，或者一組key-value映射。

hashtable繼承map接口，實作一個key-value映射的哈希表。任何非空（non-null）的對象都可作為key或者value。

添加資料使用put(key, value)，取出資料使用get(key)，這兩個基本操作的時間開銷為常數。

hashtable通過initial capacity和load factor兩個參數調整性能。通常預設的load factor 0.75較好地實作了時間和空間的均衡。增大load factor可以節省空間但相應的查找時間将增大，這會影響像get和put這樣的操作。

使用hashtable的簡單示例如下，将1，2，3放到hashtable中，他們的key分别是”one”，”two”，”three”：

hashtable numbers = new hashtable();

numbers.put(“one”, new integer(1));

numbers.put(“two”, new integer(2));

numbers.put(“three”, new integer(3));

要取出一個數，比如2，用相應的key：

integer n = (integer)numbers.get(“two”);

system.out.println(“two = ” + n);

由于作為key的對象将通過計算其散列函數來确定與之對應的value的位置，是以任何作為key的對象都必須實作hashcode和equals方法。hashcode和equals方法繼承自根類object，如果你用自定義的類當作key的話，要相當小心，按照散列函數的定義，如果兩個對象相同，即obj1.equals(obj2)=true，則它們的hashcode必須相同，但如果兩個對象不同，則它們的hashcode不一定不同，如果兩個不同對象的hashcode相同，這種現象稱為沖突，沖突會導緻操作哈希表的時間開銷增大，是以盡量定義好的hashcode()方法，能加快哈希表的操作。

如果相同的對象有不同的hashcode，對哈希表的操作會出現意想不到的結果（期待的get方法傳回null），要避免這種問題，隻需要牢記一條：要同時複寫equals方法和hashcode方法，而不要隻寫其中一個。

hashtable是同步的。

hashmap和hashtable類似，不同之處在于hashmap是非同步的，并且允許null，即null value和null key。，但是将hashmap視為collection時（values()方法可傳回collection），其疊代器操作時間開銷和hashmap的容量成比例。是以，如果疊代操作的性能相當重要的話，不要将hashmap的初始化容量設得過高，或者load factor過低。

weakhashmap是一種改進的hashmap，它對key實行“弱引用”，如果一個key不再被外部所引用，那麼該key可以被gc回收。

如果你想學習java可以來這個群，首先是二二零，中間是一四二，最後是九零六，裡面有大量的學習資料可以下載下傳。

如果涉及到堆棧，隊列等操作，應該考慮用list，對于需要快速插入，删除元素，應該使用linkedlist，如果需要快速随機通路元素，應該使用arraylist。

如果程式在單線程環境中，或者通路僅僅在一個線程中進行，考慮非同步的類，其效率較高，如果多個線程可能同時操作一個類，應該使用同步的類。

要特别注意對哈希表的操作，作為key的對象要正确複寫equals和hashcode方法。

盡量傳回接口而非實際的類型，如傳回list而非arraylist，這樣如果以後需要将arraylist換成linkedlist時，用戶端代碼不用改變。這就是針對抽象程式設計。