Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap
Collection 是最基本的集合接口,一個 Collection 代表一組 Object,即 Collection 的元素(Elements)。一些 Collection 允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK 不提供直接繼承自 Collection 的類,Java SDK 提供的類都是繼承自 Collection的“子接口”如 List 和 Set。 所有實現(xiàn) Collection 接口的類都必須提供兩個標準的構造函數(shù):無參數(shù)的構造函數(shù)用于創(chuàng)建一個空的 Collection,有一個 Collection 參數(shù)的構造函數(shù)用于創(chuàng)建一個新的 Collection,這個新的 Collection 與傳入的 Collection 有相同的元素。后 一個構造函數(shù)允許用戶復制一個Collection。 如何遍歷 Collection 中的每一個元素?不論 Collection 的實際類型如何,它都支持一個iterator()的方法,該方法返回一個迭代子,使用該迭代子即可逐一訪問 Collection 中每一個元素。典型的用法如下:
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個元素
}
由 Collection 接口派生的兩個接口是 List 和 Set。
List 是有序的 Collection,使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引(元素在 List 中的位置,類似于數(shù)組下標)來訪問 List 中的元素,這類似于 Java 的數(shù)組。
和下面要提到的 Set 不同,List 允許有相同的元素。 除了具有 Collection 接口必備的 iterator()方法外,List 還提供一個 listIterator()方法,返回一個 ListIterator 接口,和標準的 Iterator 接口相比,ListIterator 多了一些 add()之類的方法,允許添加,刪除,設定元素, 還能向前或向后遍歷。 實現(xiàn) List 接口的常用類有 LinkedList,ArrayList,Vector 和 Stack。
LinkedList 實現(xiàn)了 List 接口,允許 null 元素。此外 LinkedList 提供額外的 get,remove,insert 方法在 LinkedList 的首部或尾部。這些操作使 LinkedList 可被用作堆棧(stack),隊列(queue)或雙向隊列(deque)。 注意 LinkedList 沒有同步方法。如果多個線程同時訪問一個 List,則必須自己實現(xiàn)訪問同步。一種解決方法是在創(chuàng)建 List 時構造一個同步的 List:
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList 實現(xiàn)了可變大小的數(shù)組。它允許所有元素,包括 null。ArrayList 沒有同步。 size,isEmpty,get,set 方法運行時間為常數(shù)。但是 add 方法開銷為分攤的常數(shù),添加 n 個元素需要 O(n)的時間。其他的方法運行時間為線性。 每個 ArrayList 實例都有一個容量(Capacity),即用于存儲元素的數(shù)組的大小。這個容量可隨著不斷添加新元素而自動增加,但是增長算法 并沒有定義。當需要插入大量元素時,在插入前可以調用 ensureCapacity 方法來增加 ArrayList 的容量以提高插入效率。 和 LinkedList 一樣,ArrayList 也是非同步的(unsynchronized)。
Vector 非常類似 ArrayList,但是 Vector 是同步的。由 Vector 創(chuàng)建的 Iterator,雖然和 ArrayList 創(chuàng)建的 Iterator 是同一接口,但是,因為 Vector 是同步的,當一個 Iterator 被創(chuàng)建而且正在被使用,另一個線程改變了 Vector 的狀態(tài)(例如,添加或刪除了一些元素),這時調用 Iterator 的方法時將拋出 ConcurrentModificationException,因此必須捕獲該異常。
Stack 繼承自 Vector,實現(xiàn)一個后進先出的堆棧。Stack 提供5個額外的方法使得 Vector 得以被當作堆棧使用?;镜?push 和 pop 方法,還有 peek 方法得到棧頂?shù)脑?,empty 方法測試堆棧是否為空,search 方法檢測一個元素在堆棧中的位置。Stack 剛創(chuàng)建后是空棧。
Set 是一種不包含重復的元素的 Collection,即任意的兩個元素 e1 和 e2 都有 e1.equals(e2)=false,Set 最多有一個 null 元素。 很明顯,Set 的構造函數(shù)有一個約束條件,傳入的 Collection 參數(shù)不能包含重復的元素。 請注意:必須小心操作可變對象(Mutable Object)。如果一個 Set 中的可變元素改變了自身狀態(tài)導致 Object.equals(Object)=true 將導致一些問題。
請注意,Map 沒有繼承 Collection 接口,Map 提供 key 到 value 的映射。一個 Map 中不能包含相同的 key,每個 key 只能映射一個 value。Map 接口提供3種集合的視圖,Map 的內容可以被當作一組 key 集合,一組 value 集合,或者一組 key-value 映射。
Hashtable 繼承 Map 接口,實現(xiàn)一個 key-value 映射的哈希表。任何非空(non-null)的對象都可作為 key 或者 value。 添加數(shù)據(jù)使用 put(key, value),取出數(shù)據(jù)使用 get(key),這兩個基本操作的時間開銷為常數(shù)。
Hashtable 通過 initial capacity 和 load factor 兩個參數(shù)調整性能。通常缺省的 load factor 0.75較好地實現(xiàn)了時間和空間的均衡。增大 load factor 可以節(jié)省空間但相應的查找時間將增大,這會影響像 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));
要取出一個數(shù),比如2,用相應的 key:
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作為 key 的對象將通過計算其散列函數(shù)來確定與之對應的 value 的位置,因此任何作為 key的對象都必須實現(xiàn) hashCode 和 equals 方法。hashCode 和 equals 方法繼承自根類 Object,如果你用自定義的類當作 key 的話,要相當小心,按照散列函數(shù)的定義,如果兩個對象相同,即 obj1.equals(obj2)=true,則它們的 hashCode 必須相同,但如果兩個對象不同,則它們的 hashCode 不一定不同,如果兩個不同對象的 hashCode 相同,這種現(xiàn)象稱為沖突,沖突會導致操作哈希表的時間開銷增大,所以盡量定義好的 hashCode()方法,能加快哈希表的操作。 如果相同的對象有不同的 hashCode,對哈希表的操作會出現(xiàn)意想不到的結果(期待的 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 回收。
如果涉及到堆棧,隊列等操作,應該考慮用 List,對于需要快速插入,刪除元素,應該使用LinkedList,如果需要快速隨機訪問元素,應該使用 ArrayList。 如果程序在單線程環(huán)境中,或者訪問僅僅在一個線程中進行,考慮非同步的類,其效率較高,如果多個線程可能同時操作一個類,應該使用同步的類。 要特別注意對哈希表的操作,作為 key 的對象要正確復寫 equals 和 hashCode 方法。 盡量返回接口而非實際的類型,如返回 List 而非 ArrayList,這樣如果以后需要將 ArrayList換成 LinkedList 時,客戶端代碼不用改變。這就是針對抽象編程。
Vector 是同步的。這個類中的一些方法保證了 Vector 中的對象是線程安全的。而 ArrayList 則是異步的,因此 ArrayList 中的對象并不是線程安全的。因為同步的要求會影響執(zhí)行的效率,所以如果你不需要線程安全的集合那么使用 ArrayList 是一個很好的選擇,這樣可以避免由于同步帶來的不必要的性能開銷。
數(shù)據(jù)增長
從內部實現(xiàn)機制來講 ArrayList 和 Vector 都是使用數(shù)組(Array)來控制集合中的對象。當你向這兩種類型中增加元素的時候,如果元素的數(shù)目 超出了內部數(shù)組目前的長度它們都需要擴展內部數(shù)組的長度,Vector 缺省情況下自動增長原來一倍的數(shù)組長度,ArrayList 是原來的50%,所以最 后你獲得的這個集合所占的空間總是比你實際需要的要大。所以如果你要在集合中保存大量的數(shù)據(jù)那么使用 Vector 有一些優(yōu)勢,因為你可以通過設置集合的初 始化大小來避免不必要的資源開銷。
使用模式
在 ArrayList 和 Vector 中,從一個指定的位置(通過索引)查找數(shù)據(jù)或是在集合的末尾增加、移除一個元素所花費的時間是一樣的,這個時間我們用 O(1)表示。但是,如果在集合的其他位置增加或移除元素那么花費的時間會呈線形增長:O(n-i),其中 n 代表集合中元素的個數(shù),i 代表元素增加或移除元素的索引位置。為什么會這樣呢?以為在進行上述操作的時候集合中第 i 和第 i 個元素之后的所有元素都要執(zhí)行位移的操作。這一切意味著什么呢?
這意味著,你只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用 Vector 或ArrayList 都可以。如果是其他操作,你最好選擇其他的集合操作類。比如,LinkList 集合類在增加或移除集合中任何位置的元素所花費的時間都是一樣的?O(1),但它在索引一個元素的使用缺比較慢 -O(i),其中 i 是索引的位置.使用 ArrayList 也很容易,因為你可以簡單的使用索引來代替創(chuàng)建 iterator 對象的操作。LinkList 也會為每個插入的元素創(chuàng)建對象,所有你要明白它也會帶來額外的開銷。
最后,在《Practical Java》一書中 Peter Haggar 建議使用一個簡單的數(shù)組(Array)來代替 Vector 或 ArrayList。尤其是對于執(zhí)行效率要求高的程序更應如此。因為使用數(shù)組 (Array)避免了同步、額外的方法調用和不必要的重新分配空間的操作。
1,vector 是線程同步的,所以它也是線程安全的,而 arraylist 是線程異步的,是不安全的。如果不考慮到線程的安全因素,一般用 arraylist 效率比較高。
2,如果集合中的元素的數(shù)目大于目前集合數(shù)組的長度時,vector 增長率為目前數(shù)組長度的100%,而 arraylist 增長率為目前數(shù)組長度的50%.如過在集合中使用數(shù)據(jù)量比較大的數(shù)據(jù),用 vector 有一定的優(yōu)勢。
3,如果查找一個指定位置的數(shù)據(jù),vector 和 arraylist 使用的時間是相同的,都是0(1),這個時候使用 vector 和 arraylist 都可以。而如果移動一個指定位置的數(shù)據(jù)花費的時間為 0(n-i)n 為總長度,這個時候就應該考慮到使用 linklist,因為它移動一個指定位置的數(shù)據(jù)所花費的時間為 0(1),而查詢一個指定位置的數(shù)據(jù)時花費的時間為 0(i)。
ArrayList 和 Vector 是采用數(shù)組方式存儲數(shù)據(jù),此數(shù)組元素數(shù)大于實際存儲的數(shù)據(jù)以便增加和插入元素,都允許直接序號索引元素,但是插入數(shù)據(jù)要設計到數(shù)組元素移動 等內存操作,所以索引數(shù)據(jù)快插入數(shù)據(jù)慢,Vector 由于使用了 synchronized 方法(線程安全)所以性能上比ArrayList 要差,LinkedList 使用雙向鏈表實現(xiàn)存儲,按序號索引數(shù)據(jù)需要進行向前或向后遍歷,但是插入數(shù)據(jù)時只需要記錄本項的前后項即可,所以插入數(shù)度較快!
1.ArrayList 是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結構,LinkedList 基于鏈表的數(shù)據(jù)結構。 2.對于隨機訪問 get 和 set,ArrayList 覺得優(yōu)于 LinkedList,因為 LinkedList 要移動指針。 3.對于新增和刪除操作 add 和 remove,LinedList 比較占優(yōu)勢,因為 ArrayList 要移動數(shù)據(jù)。 這一點要看實際情況的。若只對單條數(shù)據(jù)插入或刪除,ArrayList 的速度反而優(yōu)于 LinkedList。但若是批量隨機的插入刪除數(shù)據(jù),LinkedList 的速度大大優(yōu)于 ArrayList. 因為 ArrayList 每插入一條數(shù)據(jù),要移動插入點及之后的所有數(shù)據(jù)。
(注) 文章出處:http://www.diybl.com/course/3_program/java/javaxl/200875/130233.html
1、HashMap 通過 hashcode 對其內容進行快速查找,而 TreeMap 中所有的元素都保持著某種固定的順序,如果你需要得到一個有序的結果你就應該使用 TreeMap(HashMap 中元素的排列順序是不固定的)。
HashMap 中元素的排列順序是不固定的)。
2、HashMap 通過 hashcode 對其內容進行快速查找,而 TreeMap 中所有的元素都保持著某種固定的順序,如果你需要得到一個有序的結果你就應該使用 TreeMap(HashMap 中元素的排列順序是不固定的)。集合框架”提供兩種常規(guī)的 Map 實現(xiàn):HashMap 和 TreeMap (TreeMap 實現(xiàn)SortedMap 接口)。
3、在 Map 中插入、刪除和定位元素,HashMap 是最好的選擇。但如果您要按自然順序或自定義順序遍歷鍵,那么 TreeMap 會更好。使用 HashMap 要求添加的鍵類明確定義了 hashCode()和 equals()的實現(xiàn)?! ∵@個 TreeMap 沒有調優(yōu)選項,因為該樹總處于平衡狀態(tài)。
結過研究,在原作者的基礎上我還發(fā)現(xiàn)了一點,二樹 map 一樣,但順序不一樣,導致 hashCode()不一樣。 同樣做測試: 在 hashMap 中,同樣的值的 map,順序不同,equals 時,false; 而在 treeMap 中,同樣的值的 map,順序不同,equals 時,true,說明,treeMap 在 equals()時是整理了順序了的。
一.歷史原因:Hashtable 是基于陳舊的 Dictionary 類的,HashMap 是 Java 1.2 引進的 Map 接口的一個實現(xiàn)
二.同步性:Hashtable 是線程安全的,也就是說是同步的,而 HashMap 是線程序不安全的,不是同步的
三.值:只有 HashMap 可以讓你將空值作為一個表的條目的 key 或 value