目錄

概述

一、Collection 接口

（1）List列表 —— 有序、值可重復

（2）Set 集 ?—— 值不可重復

二、Map 接口

（1）HashMap —— ?無序

1、取模法

2、Hash碰撞沖突

3、解決Hash沖突

（2）HashTable —— 無序

（3）TreeMap —— 有序

（4）ArrayMap——有序

三、List、Set、Map的值能否為null？

（1）List —— 允許為null

（2）Set?

（3）Map

---

概述

集合類存放于java.util包中。集合類存放的都是對象的引用，而非對象本身。常見的集合主要有三種——Set(集）、List（列表）和Map（映射）。其中，List和Set 都實現了 Collection?接口，并且List和Set也是接口，而Map 為獨立接口。常見的實現類如下：

• List ?的實現類有：ArrayList、Vector、LinkedList；
• Set ??的實現類有：HashSet、LinkedHashSet、TreeSet；
• Map 的實現類有：Hashtable、HashMap、ArrayMap、LinkedHashMap、TreeMap。

補充知識：散列表，也叫哈希表（Hash table），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

?

一、Collection 接口

（1）List列表 —— 有序、值可重復

1、ArrayList
優點:?底層數據結構是數組Array，查詢快。增刪慢。
缺點:?線程不安全，效率高

2、Vector
優點:?底層數據結構是數組Array，查詢快。增刪慢。
缺點:?線程安全，效率低

*Vector是實現了?synchronized?的，這也是Vector和ArrayList的唯一的區別。

3、LinkedList
優點:?底層數據結構是鏈表LinkedList，增刪快。查詢慢。
缺點:?線程不安全，效率高

*鏈表的每一個節點（Node）都包含兩方面的內容：1.節點本身的數據（data）；2.下一個節點的信息（nextNode）。所以當對LinkedList做添加，刪除動作的時候就不用像基于Array的List一樣，必須進行大量的數據移動。只要更改nextNode的相關信息就可以實現了。這就是LinkedList的優勢。詳細《數據結構與算法》
?

（2）Set 集 ?—— 值不可重復

1、HashSet
調用add（）方法向Set中添加對象，底層數據結構是哈希表，無序。
依賴兩個方法來保證元素唯一性：hashCode()和equals()。使用對象的值來計算hashcode值，對于兩個對象來說hashcode可能相同，所以equals()方法用來判斷對象的相等性。

2、LinkedHashSet
底層數據結構是雙向鏈表和哈希表，有序。
由鏈表保證元素有序，由哈希表保證元素唯一。

3、TreeSet
底層數據結構是紅黑樹，內部實現排序，也可以自定義排序規則。
自然排序、比較器排序保證元素排序。根據比較的返回值是否是0來保證元素唯一性。

4、ArraySet

底層數據結構是雙數組，有序。

Android.util包下的類，實時擴容，節約內存。推薦代替使用HashSet。

ArraySet添加元素的源碼：

@Overridepublic boolean add(@Nullable E value) {final int hash;int index;if (value == null) {//允許key、value有一個為nullhash = 0;index = indexOfNull();} else {hash = value.hashCode();//算出hash碼index = indexOf(value, hash);//在hash碼數組中，二分查找拿到index值}if (index >= 0) {return false;}index = ~index;if (mSize >= mHashes.length) {//安全判斷final int n = mSize >= (BASE_SIZE * 2) ? (mSize + (mSize >> 1)): (mSize >= BASE_SIZE ? (BASE_SIZE * 2) : BASE_SIZE);final int[] ohashes = mHashes;final Object[] oarray = mArray;allocArrays(n);if (mHashes.length > 0) {System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);System.arraycopy(oarray, 0, mArray, 0, oarray.length);}freeArrays(ohashes, oarray, mSize);}if (index < mSize) {System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);System.arraycopy(mArray, index, mArray, index + 1, mSize - index);}mHashes[index] = hash;//hash碼數組mArray[index] = value;//存放數據mSize++;return true;}

碰撞沖突：如果在第二個數組鍵值對中的key和前面輸入的查詢key不一致時產生。

開放地址法：以該key為中心點，分別上下展開，逐個去對比查找，直到找到匹配的值。

擴容機制：在創建時是嚴格按照大小創建，如下：

System.arraycopy(ohashes, 0, mHashes, 0, mSize);System.arraycopy(oarray, 0, mArray, 0, mSize);

在添加、刪除操作方法中都會調用如下：

System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);System.arraycopy(mArray, index, mArray, index + 1, mSize - index);

?小結

ArraySet通過調用System中提供的一個native靜態方法arraycopy()，實現數組之間的復制。采取一種用時間換取內存空間的優化思路，其元素擴容是時刻變化的，也就是說會隨時根據內容動態調整數組的大小。

因為每次操作都要實現數組復制，會影響到元素操作的效率。理論上來說，在大數據量的情況下，更頻繁的數據條數大幅度變化下，效率會變低。但實際上，發現其速度在數萬條數據的情況下，相差無幾。

?

二、Map 接口

Map接口有三個比較重要的實現類：HashMap、TreeMap、HashTable。

（1）HashMap —— ?無序

如上圖，HashMap是鏈表散列的數據結構，即數組和鏈表的結合體。底層是一個數組結構，數組中的每一項元素又是一個鏈表結構，即Entry<K,V>，如下：

transient Entry[] table; static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;final int hash; }

Entry就是數組中的元素，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用，這就構成了鏈表。下面看一下put方法，如下：

public V put(K key, V value) {// 當key為null時，調用putForNullKey方法，將value放置在數組第一個位置。if (key == null)return putForNullKey(value);// 根據key的keyCode重新計算hash值。int hash = hash(key.hashCode());// 搜索指定hash值在對應table中的索引。int i = indexFor(hash, table.length);// 如果 i 索引處的 Entry 不為 null，通過循環不斷遍歷 e 元素的下一個元素。for (Entry<K,V> e = table[i]; e != null; e = e.next) {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;}}// 如果i索引處的Entry為null，表明此處還沒有Entry。modCount++;// 將key、value添加到i索引處。addEntry(hash, key, value, i);return null; }

小結：?

• 如果key相同，則覆蓋原始值；如果key出現沖突，則將當前的key-value放入鏈表。在鏈表中做進一步的對比value。
• 沒有 synchronized關鍵字，即非線程安全，因此效率較高；
• 允許存放null鍵和null值

工作原理：

通過put()方法傳遞鍵(key)和值(value)時，我們先對鍵調用hashCode()方法，計算并返回的hashCode是用于找到Map數組的位置來儲存Entry對象。hashCode()方法中是根據key的hash值來求得對應數組中的位置。因為HashMap的數據結構是數組和鏈表的結合，如果元素位置盡量的分布均勻些，使得每個位置上的元素數量只有一個，當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表。所以，我們首先想到的就是把hashcode對數組長度取模運算。

1、取模法

假如數組的長度等于5，這時有一個數據6，我們如何把這個6儲存到長度只有5的數組中呢？取余法計算6%5等于1，即把6這個數據放到數組下標為1的位置。如果再有一個數據需要存儲，取余法計算后也等于1，就調用equals()判斷值是否相同，相同的話就不存儲。但是，問題來了，值不相同就會造成Hash碰撞沖突了。

2、Hash碰撞沖突

HashCode()的作用就是保證對象返回唯一hash值對應Map數組中的bucket存儲位置，但當兩個數據計算后的值一樣時，這就發生了碰撞沖突。例如，前面有6%5=1 得到數組下標為1的位置。此時，有個數據是11，那么11%5=1，但是這個為1的位置已經有了6這個數據了，這就叫Hash沖突。

3、解決Hash沖突

（1）開放定址法

開放地址法有個非常關鍵的特征，就是所有輸入的元素全部存放在哈希表里。它的實現是，發生哈希沖突，就以當前地址為基準，某種探查技術在散列表中形成一個探查(測)序列，去尋找下一個地址，若發生沖突再去尋找，直至找到一個為空的地址為止。假如關鍵字key的哈希地址（hashCode）的值?p = H（key），此時出現沖突，就以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。所以這種方法又稱為再散列法。

開放定址法分為：線性探查法、二次探查法、偽隨機探測法

• 線性探查：順序查看表中下一單元，直到找出一個空單元或查遍全表；
• 二次探查：在表的左右進行跳躍式探測，比較靈活；
• 偽隨機探測：建立一個偽隨機數序列，如i=(i+p) % m，并給定一個隨機數做起點，每次去加上這個偽隨機數就可以了。

（2）拉鏈法

HashMap、HashSet其實都是采用的拉鏈法來解決哈希沖突的。主要是采用鏈表的形式去處理發生哈希沖突的關鍵字key。（jdk1.8之后采用鏈表+紅黑樹）

實現思想：將所有哈希地址為 i 的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。

①插入操作：在輸入域的關鍵字發生哈希沖突的時候，我們先檢查帶插入元素是否出現在表中。這個查找所用的次數最壞時間復雜度為O(1)。

②刪除操作：在刪除一個元素的時候，需要更改該元素的前驅元素的next指針的屬性，把該元素從鏈表中刪除。這個操作的時間復雜度也是O(1)的。

（3）小結

拉鏈法與開放定址法相比

①拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；

②由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；

③開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；

④在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。

拉鏈法需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

?

（2）HashTable —— 無序

• 散列表，也叫哈希表，存儲的內容是鍵值對(key-value)映射；
• Hashtable源碼所有 public 方法聲明中都有 synchronized關鍵字，線程安全，效率低；
• 不允許null值；（因為equlas()方法需要對象）
• 父類是Dictionary。

（3）TreeMap —— 有序

• 父類是SortMap接口。能夠把它保存的鍵值對根據key排序，基于紅黑樹，從而保證TreeMap中所有鍵值對處于有序狀態。

*紅黑色的見解

1、每個節點非紅即黑

2、根節點總是黑色的

3、如果節點是紅色的，則它的子節點必須是黑色的（反之不一定）

4、每個葉子節點都是黑色的空節點（NIL節點）

5、從根節點到葉節點或空子節點的每條路徑，必須包含相同數目的黑色節點（即相同的黑色高度）

（4）ArrayMap——有序

1、概述

Hashmap和HashSet都是Java util包下的類，而ArrayMap與ArraySet都是?android.util包下的類，是google 在Android平臺上作出優化后的類，在Android 源碼中大量地使用了arraymap進行內存中的數據儲存和管理，比如Intent.putExtra、Bundle。二者讀寫速度差不多，但是ArrayMap比hashmap減少30%的內存消耗。對于經常內存空間緊張，可以緩解OOM。

2、實現原理

當調用?get(key) 方法 獲取某個 value 時，通過計算key得到轉換過后的hash值，再對（左）hash數組使用二分查找法尋找到對應的下標索引值?index，然后就可以通過這個 index 在key-value數組（右）中直接訪問到需要的鍵值對。

源碼和原理基本與ArraySet的相同。此處就不在復制黏貼了。

三、List、Set、Map的值能否為null？

（1）List —— 允許為null

1、可以看到ArrayList可以存儲多個null，ArrayList底層是數組，添加null并未對他的數據結構造成影響。

public void testArrayList(){ArrayList<String> list = new ArrayList<>();list.add(null);list.add(null);Assert.assertEquals(2,list.size()); // success}

2、LinkedList底層為雙向鏈表，node.value = null?也沒有問題。

public void testLinkedList(){LinkedList<String> list = new LinkedList<>();list.add(null);list.add(null);Assert.assertEquals(2,list.size()); // success}

3、Vector 底層是數組，所以不會管你元素的內容是什么，可以存儲多個null。?

public void VectorTest(){Vector box = new Vector();box.add(null);box.add(null);Assert.assertEquals(2,box.size()); //success}//Vector的add函數源碼public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}

（2）Set?

1、HashSet底層是HashMap，可以有1個為null的元素。

public void testHashSet(){HashSet<String> set = new HashSet<>();set.add(null);Assert.assertEquals(1,set.size()); //OK size = 1set.add(null);Assert.assertEquals(2,set.size()); //Error size = 1}

2、LinkHashSet底層也是hashmap，允許存在一個為null的元素。

3、TreeSet不能有key為null的元素，會報NullPointerException

public void testTreeSet(){TreeSet<String> set = new TreeSet<>();set.add(null); //Error NullPointException}

（3）Map

1、HashMap中只能有一個key為null的節點。因為Map的key相同時，后面的節點會替換之前相同key的節點。

public void testHashMap(){HashMap<String,String> map = new HashMap<>();map.put(null,null);Assert.assertEquals(1,map.size()); //OK size = 1map.put(null,null);Assert.assertEquals(2,map.size()); //Error size = 1}

2、TreeMap的put方法會調用compareTo方法，對象為null時，會報空指針錯。

public void testTreeMap(){TreeMap<String,String> map = new TreeMap<>();map.put(null,null);Assert.assertEquals(1,map.size()); //Error NullPointException}

3、HashTable底層為散列表，無論是key為null，還是value為null，都會報錯

public void HashTableTest(){Hashtable table = new Hashtable();table.put(new Object(),null); //Exceptiontable.put(null,new Object()); //Exceptiontable.put(null,null); //ExceptionAssert.assertEquals(1,table.size());}//hashTable put函數源碼public synchronized V put(K key, V value) {if (value == null) { //value 需要判空，所以value不可為nullthrow new NullPointerException();}Entry<?,?> tab[] = table;int hash = key.hashCode(); //key需要擁有實例去調用hashCode方法，所以也不能為空int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)tab[index];for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value;return old;}}addEntry(hash, key, value, index);return null;}

?

結束。

---

歡迎大家入我們的學習交流群，群內成員一篇融洽，節假日紅包不斷發放！還不快到碗里來？😆

歡迎關注個人公眾號，內容豐富，如互聯網動態、技術分享、理財達人等。持續關注每天有超值收獲！

?

參考鏈接

https://blog.csdn.net/zhangqunshuai/article/details/80660974

https://www.jianshu.com/p/c32e192e371d

?

總結

以上是生活随笔為你收集整理的Java 集合List、Set、Map知识结构大全详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。