上面的圖展示了整個集合大家族的成員以及他們之間的關(guān)系。下面就上面的各個接口、基類做一些簡單的介紹(主要介紹各個集合的特點，區(qū)別)。

一、Collection接口：

Collection接口是最基本的集合接口，它不提供直接的實現(xiàn)，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。Collection所代表的是一種規(guī)則，它所包含的元素都必須遵循一條或者多條規(guī)則。如有些允許重復(fù)而有些則不能重復(fù)、有些必須要按照順序插入而有些則是散列，有些支持排序但是有些則不支持。

在Java中所有實現(xiàn)了Collection接口的類都必須提供兩套標準的構(gòu)造函數(shù)，一個是無參，用于創(chuàng)建一個空的Collection，一個是帶有Collection參數(shù)的有參構(gòu)造函數(shù)，用于創(chuàng)建一個新的Collection，這個新的Collection與傳入進來的Collection具備相同的元素。?

?

二、List接口：

List接口為Collection直接接口。List所代表的是有序的Collection，即它用某種特定的插入順序來維護元素順序。用戶可以對列表中每個元素的插入位置進行精確地控制，同時可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素。實現(xiàn)List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

2.1、ArrayList：

（1）ArrayList底層是一個基于數(shù)組的非同步實現(xiàn)，是線程不安全的，它的操作基本上都是基于對數(shù)組的操作。

（2）允許包括null在內(nèi)的所有元素，ArrayList擅長于隨機訪問，所以對元素的查詢快，增刪慢，在ArrayList的中間插入或刪除一個元素，該位置后面的元素都會被移動，查詢的時間復(fù)雜度為O(1)，插入和刪除的時間復(fù)雜度為O(n)。

（3）初始容量為10，數(shù)組擴容時，會將舊數(shù)組中的元素重新拷貝一份到新的數(shù)組中，每次數(shù)組容量增長大約是其容量的1.5倍，這種操作的代價很高。所以如果我們明確所插入元素的多少，最好指定一個初始容量值，避免過多的進行擴容操作而浪費時間、效率。

（4）采用了Fail-Fast機制，面對并發(fā)的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風(fēng)險。

（5）remove方法會讓下標到數(shù)組末尾的元素向前移動一個單位，并把最后一位的值置空，方便GC。

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定時間運行。add 操作以分攤的固定時間運行，也就是說，添加 n 個元素需要 O(n) 時間（由于要考慮到擴容，所以這不只是添加元素會帶來分攤固定時間開銷那樣簡單）。

2.2、LinkedList：

（1）LinkedList是基于雙向鏈表的非同步實現(xiàn)，所以是線程不安全的；

（2）允許包括null在內(nèi)的所有元素。

（3）LinkedList不能隨機訪問，在查找元素的時候，需要從開頭或結(jié)尾遍歷列表（先判斷index是在鏈表的哪一半，然后再去對應(yīng)區(qū)域查找，這樣最多只要遍歷鏈表的一半節(jié)點即可找到）。這樣做的好處就是可以通過較低的代價在List中進行插入和刪除操作。

（4）雖然LinkedList對元素的查詢慢，時間復(fù)雜度為O(n)，但是對元素的增刪快，插入或刪除元素只需要修改元素的指針，時間復(fù)雜度為O(1)

2.3、Vector：

（1）與ArrayList相似，但是Vector是同步的，底層使用synchronized進行加鎖。所以說Vector是線程安全的動態(tài)數(shù)組。它的操作與ArrayList幾乎一樣。

（2）初始容量是10，擴容時，Vector的容量增加capacityIncrement，如果沒有指定capacityIncrement，則將容量增加為原來的兩倍。

2.4、Stack：

（1）Stack繼承自Vector，實現(xiàn)一個后進先出的堆棧。所以用法、線程安全什么的跟Vector都差不多，Stack剛創(chuàng)建后是空棧。

（2）Stack還提供5個額外的方法使得Vector得以被當(dāng)作堆棧使用?；镜膒ush和pop 方法，還有peek方法得到棧頂?shù)脑?#xff0c;empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。

?

三、Map接口：

Map與List、Set接口不同，它是由一系列鍵值對組成的集合，提供了key到Value的映射。同時它也沒有繼承Collection。在Map中它保證了key與value之間的一一對應(yīng)關(guān)系。也就是說一個key對應(yīng)一個value，所以它不能存在相同的key值，當(dāng)然value值可以相同。實現(xiàn)map的有：HashMap、TreeMap、HashTable、Properties、EnumMap。

3.1、HashMap（JDK1.8及以上）：

（1）HashMap是基于哈希表的Map接口的非同步實現(xiàn)，允許使用null值和null鍵，但不保證映射的順序，它是為快速查詢而設(shè)計的。

（2）數(shù)據(jù)結(jié)構(gòu)可以看成數(shù)組+鏈表+紅黑樹。底層使用數(shù)組實現(xiàn)，數(shù)組中每一項是個單向鏈表，即數(shù)組和鏈表的結(jié)合體；當(dāng)鏈表長度大于一定閾值時，鏈表轉(zhuǎn)換為紅黑樹，這樣減少鏈表查詢時間。

（3）HashMap在底層將key-value當(dāng)成一個整體進行處理，這個整體就是一個Node對象。HashMap底層采用一個Node[]數(shù)組來保存所有的key-value對，當(dāng)需要存儲一個Node對象時，會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當(dāng)需要取出一個Node時，也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置，再根據(jù)equals方法從該位置上的鏈表中取出該Node。

（4）HashMap進行數(shù)組擴容需要重新計算擴容后每個元素在數(shù)組中的位置，很耗性能。

HashMap的擴容代價非常大，要生成一個新的桶數(shù)組，然后要把所有元素都重新Hash落桶一次，幾乎等于重新執(zhí)行了一次所有元素的put。所以如果我們對Map的大小有一個范圍的話，可以在構(gòu)造時給定大小，一般大小設(shè)置為：(int) ((float) expectedSize / 0.75F + 1.0F)。

（5）采用了Fail-Fast機制，通過一個modCount值記錄修改次數(shù)，對HashMap內(nèi)容的修改都將增加這個值。迭代器初始化過程中會將這個值賦給迭代器的expectedModCount，在迭代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map，馬上拋出異常。

3.2、Hashtable：

（1）Hashtable是基于哈希表的Map接口的同步實現(xiàn)，使用synchronized實現(xiàn)線程安全，即每次鎖住整張表讓線程獨占。

（2）底層使用數(shù)組實現(xiàn)，數(shù)組中每一項是個單鏈表，即數(shù)組和鏈表的結(jié)合體，采用鏈表法解決哈希沖突；

（3）不允許使用null值和null鍵；

（4）Hashtable在底層將key-value當(dāng)成一個整體進行處理，這個整體就是一個Entry對象。Hashtable底層采用一個Entry[]數(shù)組來保存所有的key-value對，當(dāng)需要存儲一個Entry對象時，會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當(dāng)需要取出一個Entry時，也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置，再根據(jù)equals方法從該位置上的鏈表中取出該Entry。

3.3、ConcurrentHashMap（JDK1.7版本）：

（1）ConcurrentHashMap允許多個修改操作并發(fā)進行，其關(guān)鍵在于使用了鎖分離技術(shù)。它使用了多個鎖來控制對hash表的不同段進行的修改，每個段其實就是一個小的hashtable，它們有各自的鎖。只要多個并發(fā)發(fā)生在不同的段上，它們就可以并發(fā)進行。

（2）與HashMap不同的是，ConcurrentHashMap使用多個子Hash表，也就是段(Segment)，ConcurrentHashMap完全允許多個讀操作并發(fā)進行，讀操作并不需要加鎖，但在HashMap中的實現(xiàn)中，因為允許可以在hash鏈的中間添加或刪除元素，讀操作不加鎖將得到不一致的數(shù)據(jù)。ConcurrentHashMap實現(xiàn)技術(shù)是保證HashEntry幾乎是不可變的。

（3）ConcurrentHashMap在底層將key-value當(dāng)成一個整體進行處理，這個整體就是一個Entry對象。Hashtable底層采用一個Entry[]數(shù)組來保存所有的key-value對，當(dāng)需要存儲一個Entry對象時，會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當(dāng)需要取出一個Entry時，也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置，再根據(jù)equals方法從該位置上的鏈表中取出該Entry。

（4）在JDK1.8之后的版本中，拋棄了Segment鎖分段的概念，而是才贏CAS算法，保存并發(fā)安全性，同時底層數(shù)據(jù)結(jié)構(gòu)可以看成“數(shù)組+鏈表+紅黑樹”。

3.4、TreeMap：

鍵以某種排序規(guī)則排序，內(nèi)部以red-black（紅-黑）樹數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，實現(xiàn)了SortedMap接口。

3.5 LinkedHashMap：

（1）LinkedHashMap繼承于HashMap，底層使用哈希表和雙向鏈表來保存所有元素，并且它是非同步，允許使用null值和null鍵。

（2）基本操作與父類HashMap相似，通過重寫HashMap相關(guān)方法，重新定義了數(shù)組中保存的元素Entry，來實現(xiàn)自己的鏈接列表特性。該Entry除了保存當(dāng)前對象的引用外，還保存了其上一個元素before和下一個元素after的引用，從而構(gòu)成了雙向鏈接列表。

3.6、WeakHashMap：

WeakHashMap與HashMap的用法基本相同，區(qū)別在于：后者的key保留對象的強引用，即只要HashMap對象不被銷毀，其對象所有key所引用的對象不會被垃圾回收，HashMap也不會自動刪除這些key所對應(yīng)的鍵值對對象。但WeakHashMap的key所引用的對象沒有被其他強引用變量所引用，則這些key所引用的對象可能被回收。WeakHashMap中的每個key對象保存了實際對象的弱引用，當(dāng)回收了該key所對應(yīng)的實際對象后，WeakHashMap會自動刪除該key所對應(yīng)的鍵值對。

3.7、IdentifyHashMap：

IdentityHashMap與HashMap基本相似，只是當(dāng)兩個key嚴格相等時，即key1==key2時，它才認為兩個key是相等的 。IdentityHashMap也允許使用null，但不保證鍵值對之間的順序。

?

四、Set接口：

Set是一種不包括重復(fù)元素的Collection。它維持它自己的內(nèi)部排序，所以隨機訪問沒有任何意義。與List一樣，它同樣運行null的存在但是僅有一個。由于Set接口的特殊性，所有傳入Set集合中的元素都必須不同，同時要注意任何可變對象，如果在對集合中元素進行操作時，導(dǎo)致e1.equals(e2)==true，則必定會產(chǎn)生某些問題。實現(xiàn)了Set接口的集合有：EnumSet、HashSet、TreeSet。

3.1、HashSet：

（1）HashSet基于HashMap實現(xiàn)，API也是對HashMap的行為進行了封裝。

（2）HashSet堪稱查詢速度最快的集合，因為其內(nèi)部是以HashCode來實現(xiàn)的。它內(nèi)部元素的順序是由哈希碼來決定的，所以它不保證set 的迭代順序，特別是它不保證該順序恒久不變，并允許使用null元素。

3.2、LinkedHashSet：

（1）對于LinkedHashSet而言，它繼承與HashSet、又基于LinkedHashMap來實現(xiàn)的。

（2）LinkedHashSet底層使用LinkedHashMap來保存所有元素，它繼承與HashSet，其所有的方法操作上又與HashSet相同。

3.3、TreeSet：

基于TreeMap，生成一個總是處于排序狀態(tài)的set，內(nèi)部以TreeMap來實現(xiàn)。它是使用元素的自然順序?qū)υ剡M行排序，或者根據(jù)創(chuàng)建Set 時提供的?Comparator?進行排序，具體取決于使用的構(gòu)造方法。

3.4、EnumSet：

是枚舉的專用Set。所有的元素都是枚舉類型。

?

五、Queue：

隊列，它主要分為兩大類，一類是阻塞式隊列，隊列滿了以后再插入元素則會拋出異常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。另一種隊列則是雙端隊列，支持在頭、尾兩端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。

?

六、相關(guān)問題：

6.1、Set集合是如何保證對象不重復(fù)的？

Set集合不允許有重復(fù)出現(xiàn)的對象，且最終的判斷是根據(jù)equals()的。其實原理是這樣的：HashSet的底層采用HashMap來存放數(shù)據(jù)，HashMap的put()方法是這樣的：

public V put(K key, V value) {if (key == null)return putForNullKey(value);int hash = hash(key.hashCode());//----------1----------int i = indexFor(hash, table.length);//-----------2---------for (Entry<K,V> e = table[i]; e != null; e = e.next) {//-----------3---------Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//------------------4--------------------modCount++;addEntry(hash, key, value, i);return null;}

當(dāng)向HashMap中添加元素的時候，首先計算元素的hashcode值，然后根據(jù)1處的代碼計算出Hashcode的值，再根據(jù)2處的代碼計算出這個元素的存儲位置，如果這個位置為空，就將元素添加進去；如果不為空，則看3-4的代碼，遍歷索引為i的鏈上的元素，如果key重復(fù)，則替換并返回oldValue值。

6.2、集合類排序問題：

一種情況是集合類本身自帶排序功能，如前面說過的TreeSet、SortedSet、SortedMap等，另一種就是本身不帶排序功能，我們通過為需要排序的類實現(xiàn)Comparable或者Comparator接口來實現(xiàn)。

先來看兩個例子，一個是實現(xiàn)Comparable的，一個是實現(xiàn)Comparator的，為了方便，我將類都寫在了一個文件中。

（1）實現(xiàn)Comparable的：

package com.xtfggef.list.test;import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List;@SuppressWarnings("unchecked") public class ComparableTest {public static void main(String[] args) {// User[] users = { new User("egg", 23), new User("niuniu", 22),// new User("qing", 28) };// Arrays.sort(users);// for (User user : users) {// System.out.println(user.getName() + " " + user.getAge());// }List<User> users = new ArrayList<User>();users.add(new User("egg", 23));users.add(new User("niu", 22));users.add(new User("qing", 28));Collections.sort(users);for (User user : users) {System.out.println(user.getName() + " " + user.getAge());}} }@SuppressWarnings("unchecked") class User implements Comparable {private String name;private int age;public User(String name, int age) {super();this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic int compareTo(Object o) {return this.age - ((User) o).getAge();} }

（2）下面是實現(xiàn)Comparator接口的：

package com.xtfggef.comparator.test;import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List;public class ComparatorTest {public static void main(String[] args) {List<User> users = new ArrayList<User>();users.add(new User("egg", 21));users.add(new User("niu", 22));users.add(new User("gg", 29));UserComparator comparator = new UserComparator();Collections.sort(users, comparator);for (User user : users) {System.out.println(user.getUsername() + " " + user.getAge());}}} class User {private String username;private int age;public User(String username, int age) {super();this.username = username;this.age = age;}public String getUsername() {return username;}public void setUsername(String username) {this.username = username;}public int getAge() {return age;}public void setAge(int age) {this.age = age;} } class UserComparator implements Comparator<User> {@Overridepublic int compare(User user1, User user2) {int age1 = user1.getAge();int age2 = user2.getAge();if (age1 < age2) {return 1;}return 0;} }

通過上面的這兩個小例子，我們可以看出，Comparator和Comparable用于不同的場景，實現(xiàn)對對象的比較從而進行排序。

總結(jié)為：

相同點：二者都可以實現(xiàn)對象的排序，不論用Arrays的方法還是用Collections的sort()方法。

不同點：

（1）實現(xiàn)Comparable接口的類，似乎是預(yù)先知道該類將要進行排序，需要排序的類實現(xiàn)Comparable接口，是一種“靜態(tài)綁定排序”。

（2）實現(xiàn)Comparator的類不需要，設(shè)計者無需事先為需要排序的類實現(xiàn)任何接口。

（3）Comparator接口里有兩個抽象方法compare()和equals()，而Comparable接口里只有一個方法：compareTo()。

（4）Comparator接口無需改變排序類的內(nèi)部，也就是說實現(xiàn)算法和數(shù)據(jù)分離，是一個良好的設(shè)計，是一種“動態(tài)綁定排序”。

（5）Comparator接口可以使用多種排序標準，比如升序、降序等。

6.3、使用for循環(huán)刪除元素陷阱：

先來看看下面這個程序：

public class Test {public static void main(String[] args) {List<String> list = new LinkedList<String>();list.add("A");list.add("B");list.add("C");for(int i=0; i<list.size(); i++){list.remove(i);}for(String item:list){System.out.println(item);}} }

讀者朋友們可以先猜猜這個程序輸出什么？按我們的思路，應(yīng)該是輸不出什么，但是執(zhí)行它，輸出的卻是：B。這是為什么呢？我們分部分析下這個程序，當(dāng)?shù)匾徊絩emove完后，集合內(nèi)還剩2個元素，此時i為1，而list.size()的值為2，從0開始的話，i為1時，正好指向第二個元素，也就是說當(dāng)remove完A后，直接就跳到C，將B漏了。

public class Test {public static void main(String[] args) {List<String> list = new LinkedList<String>();list.add("A");list.add("B");list.add("C");for(int i=0; i<list.size(); i++){list.remove(i);i -= 1;//每次刪除完后，i減少1}for(String item:list){System.out.println(item);}} }

?

參考博客：

https://blog.csdn.net/chenssy/article/details/17732841

https://blog.csdn.net/zhangerqing/article/details/8122075

https://blog.csdn.net/qq_25868207/article/details/55259978

總結(jié)

以上是生活随笔為你收集整理的Java集合篇：集合类介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。