概述

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

List 的實(shí)現(xiàn)類(lèi)有：ArrayList、Vector、LinkedList； Set
的實(shí)現(xiàn)類(lèi)有：HashSet、LinkedHashSet、TreeSet； Map
的實(shí)現(xiàn)類(lèi)有：Hashtable、HashMap、ArrayMap、LinkedHashMap、TreeMap。

補(bǔ)充知識(shí)：散列表，也叫哈希表（Hash table），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

一、Collection接口

（1）List列表 —— 有序、值可重復(fù)

1、ArrayList
優(yōu)點(diǎn): 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組Array，查詢(xún)快。增刪慢。
缺點(diǎn): 線(xiàn)程不安全，效率高

2、Vector
優(yōu)點(diǎn): 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組Array，查詢(xún)快。增刪慢。
缺點(diǎn): 線(xiàn)程安全，效率低

*Vector是實(shí)現(xiàn)了 synchronized 的，這也是Vector和ArrayList的唯一的區(qū)別。

3、LinkedList
優(yōu)點(diǎn): 底層數(shù)據(jù)結(jié)構(gòu)是鏈表LinkedList，增刪快。查詢(xún)慢。
缺點(diǎn): 線(xiàn)程不安全，效率高

*鏈表的每一個(gè)節(jié)點(diǎn)（Node）都包含兩方面的內(nèi)容：1.節(jié)點(diǎn)本身的數(shù)據(jù)（data）；2.下一個(gè)節(jié)點(diǎn)的信息（nextNode）。所以當(dāng)對(duì)LinkedList做添加，刪除動(dòng)作的時(shí)候就不用像基于Array的List一樣，必須進(jìn)行大量的數(shù)據(jù)移動(dòng)。只要更改nextNode的相關(guān)信息就可以實(shí)現(xiàn)了。這就是LinkedList的優(yōu)勢(shì)。

（2）Set 集 —— 值不可重復(fù)

1、HashSet
調(diào)用add（）方法向Set中添加對(duì)象，底層數(shù)據(jù)結(jié)構(gòu)是哈希表，無(wú)序。
依賴(lài)兩個(gè)方法來(lái)保證元素唯一性：hashCode()和equals()。使用對(duì)象的值來(lái)計(jì)算hashcode值，對(duì)于兩個(gè)對(duì)象來(lái)說(shuō)hashcode可能相同，所以equals()方法用來(lái)判斷對(duì)象的相等性。

2、LinkedHashSet
底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表和哈希表，有序。
由鏈表保證元素有序，由哈希表保證元素唯一。

3、TreeSet
底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹(shù)，內(nèi)部實(shí)現(xiàn)排序，也可以自定義排序規(guī)則。
自然排序、比較器排序保證元素排序。根據(jù)比較的返回值是否是0來(lái)保證元素唯一性。

4、ArraySet

底層數(shù)據(jù)結(jié)構(gòu)是雙數(shù)組，有序。

Android.util包下的類(lèi)，實(shí)時(shí)擴(kuò)容，節(jié)約內(nèi)存。推薦代替使用HashSet。
ArraySet添加元素的源碼：

    @Override
    public boolean add(@Nullable E value) {
        final int hash;
        int index;
        if (value == null) {//允許key、value有一個(gè)為null
            hash = 0;
            index = indexOfNull();
        } else {
            hash = value.hashCode();//算出hash碼
            index = indexOf(value, hash);//在hash碼數(shù)組中，二分查找拿到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碼數(shù)組
        mArray[index] = value;//存放數(shù)據(jù)
        mSize++;
        return true;
    }

碰撞沖突：如果在第二個(gè)數(shù)組鍵值對(duì)中的key和前面輸入的查詢(xún)key不一致時(shí)產(chǎn)生。

開(kāi)放地址法：以該key為中心點(diǎn)，分別上下展開(kāi)，逐個(gè)去對(duì)比查找，直到找到匹配的值。

擴(kuò)容機(jī)制：在創(chuàng)建時(shí)是嚴(yán)格按照大小創(chuàng)建，如下：

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

在添加、刪除操作方法中都會(huì)調(diào)用如下：

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

小結(jié)：
ArraySet通過(guò)調(diào)用System中提供的一個(gè)native靜態(tài)方法arraycopy()，實(shí)現(xiàn)數(shù)組之間的復(fù)制。采取一種用時(shí)間換取內(nèi)存空間的優(yōu)化思路，其元素?cái)U(kuò)容是時(shí)刻變化的，也就是說(shuō)會(huì)隨時(shí)根據(jù)內(nèi)容動(dòng)態(tài)調(diào)整數(shù)組的大小。

因?yàn)槊看尾僮鞫家獙?shí)現(xiàn)數(shù)組復(fù)制，會(huì)影響到元素操作的效率。理論上來(lái)說(shuō)，在大數(shù)據(jù)量的情況下，更頻繁的數(shù)據(jù)條數(shù)大幅度變化下，效率會(huì)變低。但實(shí)際上，發(fā)現(xiàn)其速度在數(shù)萬(wàn)條數(shù)據(jù)的情況下，相差無(wú)幾。

二、Map接口

Map接口有三個(gè)比較重要的實(shí)現(xiàn)類(lèi)：HashMap、TreeMap、HashTable。

（1）HashMap —— 無(wú)序

如上圖，HashMap是鏈表散列的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。底層是一個(gè)數(shù)組結(jié)構(gòu)，數(shù)組中的每一項(xiàng)元素又是一個(gè)鏈表結(jié)構(gòu)，即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就是數(shù)組中的元素，每個(gè) Map.Entry 其實(shí)就是一個(gè)key-value對(duì)，它持有一個(gè)指向下一個(gè)元素的引用，這就構(gòu)成了鏈表。下面看一下put方法，如下：

public V put(K key, V value) {
    // 當(dāng)key為null時(shí)，調(diào)用putForNullKey方法，將value放置在數(shù)組第一個(gè)位置。
    if (key == null)
        return putForNullKey(value);
    // 根據(jù)key的keyCode重新計(jì)算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在對(duì)應(yīng)table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引處的 Entry 不為 null，通過(guò)循環(huán)不斷遍歷 e 元素的下一個(gè)元素。
    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))) {
            // 如果發(fā)現(xiàn)已有該鍵值，則存儲(chǔ)新的值，并返回原始值
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引處的Entry為null，表明此處還沒(méi)有Entry。
    modCount++;
    // 將key、value添加到i索引處。
    addEntry(hash, key, value, i);
    return null;
}

小結(jié)：

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

工作原理：

通過(guò)put()方法傳遞鍵(key)和值(value)時(shí)，我們先對(duì)鍵調(diào)用hashCode()方法，計(jì)算并返回的hashCode是用于找到Map數(shù)組的位置來(lái)儲(chǔ)存Entry對(duì)象。hashCode()方法中是根據(jù)key的hash值來(lái)求得對(duì)應(yīng)數(shù)組中的位置。因?yàn)镠ashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，如果元素位置盡量的分布均勻些，使得每個(gè)位置上的元素?cái)?shù)量只有一個(gè)，當(dāng)我們用hash算法求得這個(gè)位置的時(shí)候，馬上就可以知道對(duì)應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表。所以，我們首先想到的就是把hashcode對(duì)數(shù)組長(zhǎng)度取模運(yùn)算。

1、取模法

假如數(shù)組的長(zhǎng)度等于5，這時(shí)有一個(gè)數(shù)據(jù)6，我們?nèi)绾伟堰@個(gè)6儲(chǔ)存到長(zhǎng)度只有5的數(shù)組中呢？取余法計(jì)算6%5等于1，即把6這個(gè)數(shù)據(jù)放到數(shù)組下標(biāo)為1的位置。如果再有一個(gè)數(shù)據(jù)需要存儲(chǔ)，取余法計(jì)算后也等于1，就調(diào)用equals()判斷值是否相同，相同的話(huà)就不存儲(chǔ)。但是，問(wèn)題來(lái)了，值不相同就會(huì)造成Hash碰撞沖突了。

2、Hash碰撞沖突

HashCode()的作用就是保證對(duì)象返回唯一hash值對(duì)應(yīng)Map數(shù)組中的bucket存儲(chǔ)位置，但當(dāng)兩個(gè)數(shù)據(jù)計(jì)算后的值一樣時(shí)，這就發(fā)生了碰撞沖突。例如，前面有6%5=1
得到數(shù)組下標(biāo)為1的位置。此時(shí)，有個(gè)數(shù)據(jù)是11，那么11%5=1，但是這個(gè)為1的位置已經(jīng)有了6這個(gè)數(shù)據(jù)了，這就叫Hash沖突。

3、解決Hash沖突

（1）開(kāi)放定址法

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

開(kāi)放定址法分為：線(xiàn)性探查法、二次探查法、偽隨機(jī)探測(cè)法

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

（2）拉鏈法

HashMap、HashSet其實(shí)都是采用的拉鏈法來(lái)解決哈希沖突的。主要是采用鏈表的形式去處理發(fā)生哈希沖突的關(guān)鍵字key。（jdk1.8之后采用鏈表+紅黑樹(shù)）

實(shí)現(xiàn)思想：將所有哈希地址為 i
的元素構(gòu)成一個(gè)稱(chēng)為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行。

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

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

（3）小結(jié)

拉鏈法與開(kāi)放定址法相比

①拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長(zhǎng)度較短；

②由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無(wú)法確定表長(zhǎng)的情況；

③開(kāi)放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；

④在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。

拉鏈法需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，開(kāi)放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來(lái)擴(kuò)大散列表的規(guī)模，可使裝填因子變小，這又減少了開(kāi)放定址法中的沖突，從而提高平均查找速度。

（2）HashTable —— 無(wú)序

散列表，也叫哈希表，存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射；
Hashtable源碼所有 public 方法聲明中都有 synchronized關(guān)鍵字，線(xiàn)程安全，效率低；
不允許null值；（因?yàn)閑qulas()方法需要對(duì)象）
父類(lèi)是Dictionary。

（3）TreeMap —— 有序
父類(lèi)是SortMap接口。能夠把它保存的鍵值對(duì)根據(jù)key排序，基于紅黑樹(shù)，從而保證TreeMap中所有鍵值對(duì)處于有序狀態(tài)。
*紅黑色的見(jiàn)解

1. 每個(gè)節(jié)點(diǎn)非紅即黑
2. 根節(jié)點(diǎn)總是黑色的
3. 如果節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的（反之不一定）
4. 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）
5. 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每條路徑，必須包含相同數(shù)目的黑色節(jié)點(diǎn)（即相同的黑色高度）

（4）ArrayMap——有序

1、概述

Hashmap和HashSet都是Java util包下的類(lèi)，而ArrayMap與ArraySet都是 android.util包下的類(lèi)，是google 在Android平臺(tái)上作出優(yōu)化后的類(lèi)，在Android 源碼中大量地使用了arraymap進(jìn)行內(nèi)存中的數(shù)據(jù)儲(chǔ)存和管理，比如Intent.putExtra、Bundle。二者讀寫(xiě)速度差不多，但是ArrayMap比hashmap減少30%的內(nèi)存消耗。對(duì)于經(jīng)常內(nèi)存空間緊張，可以緩解OOM。

2、實(shí)現(xiàn)原理

當(dāng)調(diào)用 get(key) 方法 獲取某個(gè) value 時(shí)，通過(guò)計(jì)算key得到轉(zhuǎn)換過(guò)后的hash值，再對(duì)（左）hash數(shù)組使用二分查找法尋找到對(duì)應(yīng)的下標(biāo)索引值 index，然后就可以通過(guò)這個(gè) index 在key-value數(shù)組（右）中直接訪(fǎng)問(wèn)到需要的鍵值對(duì)。

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

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

（1）List —— 允許為null

1、可以看到ArrayList可以存儲(chǔ)多個(gè)null，ArrayList底層是數(shù)組，添加null并未對(duì)他的數(shù)據(jù)結(jié)構(gòu)造成影響。

 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 也沒(méi)有問(wèn)題。

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

3、Vector 底層是數(shù)組，所以不會(huì)管你元素的內(nèi)容是什么，可以存儲(chǔ)多個(gè)null。

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

（2）Set

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

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

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

3、TreeSet不能有key為null的元素，會(huì)報(bào)NullPointerException

（3）Map

1、HashMap中只能有一個(gè)key為null的節(jié)點(diǎn)。因?yàn)镸ap的key相同時(shí)，后面的節(jié)點(diǎn)會(huì)替換之前相同key的節(jié)點(diǎn)。

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

2、TreeMap的put方法會(huì)調(diào)用compareTo方法，對(duì)象為null時(shí)，會(huì)報(bào)空指針錯(cuò)。

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

3、HashTable底層為散列表，無(wú)論是key為null，還是value為null，都會(huì)報(bào)錯(cuò)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-707145.html

public void HashTableTest(){
        Hashtable table = new Hashtable();
        table.put(new Object(),null); //Exception
        table.put(null,new Object()); //Exception
        table.put(null,null); //Exception
        Assert.assertEquals(1,table.size());
    }
 
    //hashTable  put函數(shù)源碼
   public synchronized V put(K key, V value) {
        if (value == null) {   //value 需要判空，所以value不可為null
            throw new NullPointerException();
        }
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();     //key需要擁有實(shí)例去調(diào)用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;
    }

到了這里，關(guān)于Map,List,Set 等集合以及底層數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！