在編寫 Java 程序中,我們最常用的除了八種基本數據類型,String 對象外還有一個集合類,在我們的的程序中到處充斥著集合類的身影!Java 中集合大家族的成員實在是太豐富了,有常用的 ArrayList、HashMap、HashSet,也有不常用的 Stack、Queue,有線程安全的 Vector、HashTable,也有線程不安全的 LinkedList、TreeMap 等等!
上面的圖展示了整個集合大家族的成員以及他們之間的關系。下面就上面的各個接口、基類做一些簡單的介紹(主要介紹各個集合的特點。區別),更加詳細的介紹會在不久的將來一一講解。
Collection 接口是最基本的集合接口,它不提供直接的實現,Java SDK提供的類都是繼承自 Collection 的“子接口”如 List 和 Set。Collection 所代表的是一種規則,它所包含的元素都必須遵循一條或者多條規則。如有些允許重復而有些則不能重復、有些必須要按照順序插入而有些則是散列,有些支持排序但是有些則不支持。
在 Java 中所有實現了 Collection 接口的類都必須提供兩套標准的構造函數,一個是無參,用於創建一個空的 Collection,一個是帶有 Collection 參數的有參構造函數,用於創建一個新的 Collection,這個新的 Collection 與傳入進來的 Collection 具備相同的元素。
List 接口為 Collection 直接接口。List 所代表的是有序的 Collection,即它用某種特定的插入順序來維護元素順序。用戶可以對列表中每個元素的插入位置進行精確地控制,同時可以根據元素的整數索引(在列表中的位置)訪問元素,並搜索列表中的元素。實現 List 接口的集合主要有:ArrayList、LinkedList、Vector、Stack。
ArrayList 是一個動態數組,也是我們最常用的集合。它允許任何符合規則的元素插入甚至包括 null。每一個 ArrayList 都有一個初始容量(10),該容量代表了數組的大小。隨著容器中的元素不斷增加,容器的大小也會隨著增加。在每次向容器中增加元素的同時都會進行容量檢查,當快溢出時,就會進行擴容操作。所以如果我們明確所插入元素的多少,最好指定一個初始容量值,避免過多的進行擴容操作而浪費時間、效率。
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定時間運行。add 操作以分攤的固定時間運行,也就是說,添加 n 個元素需要 O(n) 時間(由於要考慮到擴容,所以這不只是添加元素會帶來分攤固定時間開銷那樣簡單)。
ArrayList 擅長於隨機訪問。同時 ArrayList 是非同步的。
同樣實現 List 接口的 LinkedList 與 ArrayList 不同,ArrayList是一個動態數組,而 LinkedList 是一個雙向鏈表。所以它除了有 ArrayList 的基本操作方法外還額外提供了 get,remove,insert 方法在 LinkedList 的首部或尾部。
由於實現的方式不同,LinkedList 不能隨機訪問,它所有的操作都是要按照雙重鏈表的需要執行。在列表中索引的操作將從開頭或結尾遍歷列表(從靠近指定索引的一端)。這樣做的好處就是可以通過較低的代價在 List 中進行插入和刪除操作。
與 ArrayList 一樣,LinkedList 也是非同步的。如果多個線程同時訪問一個 List,則必須自己實現訪問同步。一種解決方法是在創建 List 時構造一個同步的 List:
List list = Collections.synchronizedList(new LinkedList(…));
與 ArrayList 相似,但是 Vector 是同步的。所以說 Vector 是線程安全的動態數組。它的操作與 ArrayList 幾乎一樣。
Stack 繼承自 Vector,實現一個後進先出的堆棧。Stack 提供 5 個額外的方法使得 Vector 得以被當作堆棧使用。基本的 push 和 pop 方法,還有 peek 方法得到棧頂的元素,empty 方法測試堆棧是否為空,search 方法檢測一個元素在堆棧中的位置。Stack 剛創建後是空棧。
Set 是一種不包括重復元素的 Collection。它維持它自己的內部排序,所以隨機訪問沒有任何意義。與 List 一樣,它同樣運行 null 的存在但是僅有一個。由於 Set 接口的特殊性,所有傳入 Set 集合中的元素都必須不同,同時要注意任何可變對象,如果在對集合中元素進行操作時,導致e1.equals(e2)==true,則必定會產生某些問題。實現了 Set 接口的集合有:EnumSet、HashSet、TreeSet。
是枚舉的專用 Set。所有的元素都是枚舉類型。
HashSet 堪稱查詢速度最快的集合,因為其內部是以 HashCode 來實現的。它內部元素的順序是由哈希碼來決定的,所以它不保證 set 的迭代順序;特別是它不保證該順序恆久不變。
基於 TreeMap,生成一個總是處於排序狀態的 set,內部以 TreeMap 來實現。它是使用元素的自然順序對元素進行排序,或者根據創建 Set 時提供的 Comparator
進行排序,具體取決於使用的構造方法。
Map 與 List、Set 接口不同,它是由一系列鍵值對組成的集合,提供了 key 到 Value 的映射。同時它也沒有繼承 Collection。在 Map 中它保證了 key 與 value 之間的一一對應關系。也就是說一個 key 對應一個 value,所以它不能存在相同的 key 值,當然 value 值可以相同。實現 map 的有:HashMap、TreeMap、HashTable、Properties、EnumMap。
以哈希表數據結構實現,查找對象時通過哈希函數計算其位置,它是為快速查詢而設計的,其內部定義了一個 hash 表數組(Entry[] table),元素會通過哈希轉換函數將元素的哈希地址轉換成數組中存放的索引,如果有沖突,則使用散列鏈表的形式將所有相同哈希地址的元素串起來,可能通過查看 HashMap.Entry 的源碼它是一個單鏈表結構。
鍵以某種排序規則排序,內部以 red-black(紅-黑)樹數據結構實現,實現了 SortedMap 接口
也是以哈希表數據結構實現的,解決沖突時與 HashMap 也一樣也是采用了散列鏈表的形式,不過性能比 HashMap 要低
WeakHashMap是一種改進的HashMap,它對key實行“弱引用”,如果一個key不再被外部所引用,那麼該key可以被GC回收。
隊列,它主要分為兩大類,一類是阻塞式隊列,隊列滿了以後再插入元素則會拋出異常,主要包括 ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。另一種隊列則是雙端隊列,支持在頭、尾兩端插入和移除元素,主要包括:ArrayDeque、LinkedBlockingDeque、LinkedList。
1,vector 是線程同步的,所以它也是線程安全的,而 arraylist 是線程異步的,是不安全的。如果不考慮到線程的安全因素,一般用 arraylist 效率比較高。
2,如果集合中的元素的數目大於目前集合數組的長度時,vector 增長率為目前數組長度的 100%,而 arraylist 增長率為目前數組長度的 50%.如過在集合中使用數據量比較大的數據,用 vector 有一定的優勢。
3,如果查找一個指定位置的數據,vector 和 arraylist 使用的時間是相同的,都是 0(1),這個時候使用 vector 和 arraylist 都可以。而如果移動一個指定位置的數據花費的時間為 0(n-i)n 為總長度,這個時候就應該考慮到使用 linklist,因為它移動一個指定位置的數據所花費的時間為 0(1),而查詢一個指定位置的數據時花費的時間為 0(i)。
ArrayList 和 Vector 是采用數組方式存儲數據,此數組元素數大於實際存儲的數據以便增加和插入元素,都允許直接序號索引元素,但是插入數據要設計到數組元素移動等內存操作,所以索引數據快插入數據慢,Vector 由於使用了 synchronized 方法(線程安全)所以性能上比 ArrayList 要差,LinkedList 使用雙向鏈表實現存儲,按序號索引數據需要進行向前或向後遍歷,但是插入數據時只需要記錄本項的前後項即可,所以插入數度較快!
1.ArrayList 是實現了基於動態數組的數據結構,LinkedList 基於鏈表的數據結構。
2.對於隨機訪問 get 和 set,ArrayList 覺得優於 LinkedList,因為 LinkedList 要移動指針。
3.對於新增和刪除操作 add 和 remove,LinedList 比較占優勢,因為 ArrayList 要移動數據。
這一點要看實際情況的。若只對單條數據插入或刪除,ArrayList 的速度反而優於 LinkedList。但若是批量隨機的插入刪除數據,LinkedList 的速度大大優於 ArrayList. 因為 ArrayList 每插入一條數據,要移動插入點及之後的所有數據。
1、HashMap 通過 hashcode 對其內容進行快速查找,而 TreeMap 中所有的元素都保持著某種固定的順序,如果你需要得到一個有序的結果你就應該使用 TreeMap(HashMap 中元素的排列順序是不固定的)。HashMap 中元素的排列順序是不固定的)。
2、HashMap 通過 hashcode 對其內容進行快速查找,而 TreeMap 中所有的元素都保持著某種固定的順序,如果你需要得到一個有序的結果你就應該使用 TreeMap(HashMap 中元素的排列順序是不固定的)。集合框架”提供兩種常規的 Map 實現:HashMap 和 TreeMap (TreeMap 實現 SortedMap 接口)。
3、在 Map 中插入、刪除和定位元素,HashMap 是最好的選擇。但如果您要按自然順序或自定義順序遍歷鍵,那麼 TreeMap 會更好。使用 HashMap 要求添加的鍵類明確定義了 hashCode() 和 equals() 的實現。 這個 TreeMap 沒有調優選項,因為該樹總處於平衡狀態。
1、歷史原因:Hashtable 是基於陳舊的 Dictionary 類的,HashMap 是Java 1.2 引進的 Map 接口的一個實現 。
2、同步性:Hashtable 是線程安全的,也就是說是同步的,而 HashMap 是線程序不安全的,不是同步的 。
3、值:只有 HashMap 可以讓你將空值作為一個表的條目的 key 或value。
1、對於隨機查詢與迭代遍歷操作,數組比所有的容器都要快。所以在隨機訪問中一般使用 ArrayList
2、LinkedList 使用雙���鏈表對元素的增加和刪除提供了非常好的支持,而 ArrayList 執行增加和刪除元素需要進行元素位移。
3、對於 Vector 而已,我們一般都是避免使用。
4、將 ArrayList 當做首選,畢竟對於集合元素而已我們都是進行遍歷,只有當程序的性能因為 List 的頻繁插入和刪除而降低時,再考慮 LinkedList。
1、HashSet 由於使用 HashCode 實現,所以在某種程度上來說它的性能永遠比 TreeSet 要好,尤其是進行增加和查找操作。
3、雖然 TreeSet 沒有 HashSet 性能好,但是由於它可以維持元素的排序,所以它還是存在用武之地的。
1、HashMap 與 HashSet 同樣,支持快速查詢。雖然 HashTable 速度的速度也不慢,但是在 HashMap 面前還是稍微慢了些,所以 HashMap 在查詢方面可以取代 HashTable。
2、由於 TreeMap 需要維持內部元素的順序,所以它通常要比 HashMap 和 HashTable 慢。