java面試題-集合類

1、集合類概述

java.util包中就包含了一系列重要的集合類,而對於集合類,主要需要掌握的就是它的內部結構,以及遍歷集合的迭代模式.

Java2的集合框架,抽其核心,主要有三種：List、Set和Map.如下圖所示：

Collection

├List

│├LinkedList

│├ArrayList

│└Vector

│　└Stack

└Set

Map

├Hashtable

├HashMap

└WeakHashMap

2.集合類特性

（1）幾個常用類的區別

ArrayList: 元素單個,效率高,多用於查詢

Vector: 元素單個,線程安全,多用於查詢

LinkedList:元素單個,多用於插入和刪除

HashMap: 元素成對,元素可為空

HashTable: 元素成對,線程安全,元素不可為空

3.介面

（1）List介面

List是有序的Collection,使用此介面能夠精確的控制每個元素插入的位置.用戶能夠使用索引（元素在List中的位置,類似於數組下標）來訪問List中的元素,這類似於Java的數組.List允許有相同的元素.

除了具有Collection介面必備的iterator（）方法外,List還提供一個listIterator（）方法,返回一個ListIterator介面,和標準的Iterator介面相比,ListIterator多了一些add（）之類的方法,允許添加,刪除,設定元素,還能向前或向後遍歷.

實現List介面的常用類有LinkedList,ArrayList,Vector和Stack.

LinkedList類

LinkedList實現了List介面,允許null元素.此外LinkedList提供額外的get,remove,insert方法在LinkedList的首部或尾部.這些操作使LinkedList可被用作堆棧（stack）,隊列（queue）或雙向隊列（deque）.

注意LinkedList沒有同步方法.如果多個線程同時訪問一個List,則必須自己實現訪問同步.一種解決方法是在創建List時構造一個同步的List：

List list = Collections.synchronizedList（new LinkedList（…））；

ArrayList類

ArrayList實現了可變大小的數組.它允許所有元素,包括null.ArrayList沒有同步.

size,isEmpty,get,set方法運行時間為常數.但是add方法開銷為分攤的常數,添加n個元素需要O（n）的時間.其他的方法運行時間為線性.

每個ArrayList實例都有一個容量（Capacity）,即用於存儲元素的數組的大小.這個容量可隨著不斷添加新元素而自動增加,但是增長演算法並沒有定義.當需要插入大量元素時,在插入前可以調用ensureCapacity方法來增加ArrayList的容量以提高插入效率.

和LinkedList一樣,ArrayList也是非同步的（unsynchronized）.

Vector類

Vector非常類似ArrayList,但是Vector是同步的.由Vector創建的Iterator,雖然和ArrayList創建的Iterator是同一介面,但是,Vector是同步的,當一個Iterator被創建正在被使用,另一個線程改變了Vector的狀態（例如,添加或刪除了一些元素）,這時調用Iterator的方法時將拋出ConcurrentModificationException,因此必須捕獲該異常.

Stack 類

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

（2）Set介面

Set是一種不包含重複的元素的Collection,即任意的兩個元素e1和e2都有e1.equals（e2）=false,Set最多有一個null元素.

很明顯,Set的構造函數有一個約束條件,傳入的Collection參數不能包含重複的元素.

請注意：必須小心操作可變對象（Mutable Object）.如果一個Set中的可變元素改變了自身狀態導致Object.equals（Object）=true將導致一些問題.

（3）Map介面

請注意,Map沒有繼承Collection介面,Map提供key到value的映射.一個Map中不能包含相同的key,每個key只能映射一個value.Map介面提供3種集合的視圖,Map的內容可以被當作一組key集合,一組value集合,或者一組key-value映射.

Hashtable類

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是同步的.

HashMap類

HashMap和Hashtable類似,不同之處在於HashMap是非同步的,並且允許null,即null value和null key.,但是將HashMap視為Collection時（values（）方法可返回Collection）,其迭代子操作時間開銷和HashMap的容量成比例.因此,如果迭代操作的性能相當重要的話,不要將HashMap的初始化容量設得過高,或者load factor過低.

WeakHashMap類

WeakHashMap是一種改進的HashMap,它對key實行「弱引用」,如果一個key不再被外部所引用,那麼該key可以被GC回收.

4.collections 和collection

Collection是集合類的上級介面,繼承與他的介面主要有Set 和List.

Collections是針對集合類的一個幫助類,他提供一系列靜態方法實現對各種集合的搜索、排序、線程安全化等操作.