對于常用的集合大家都不陌生，但是深入到內(nèi)部原理可能都是一知半解，通過閱讀源碼理解如下。

ArrayList

ArrayList內(nèi)部就是一個默認(rèn)大小為10的動態(tài)對象數(shù)組容器，每當(dāng)add一個新數(shù)據(jù)的時候，如果大于原來的容器大小，則會通過Arrays.copyOf把容器大小增加到原來的1.5倍，以此類推。當(dāng)可以預(yù)知數(shù)據(jù)大小，可以通過initialCapacity來默認(rèn)設(shè)置動態(tài)數(shù)據(jù)的大小，減少擴(kuò)容帶來的資源消耗。

時間復(fù)雜度：

get() - 直接讀取下標(biāo) - O(1)

add(E) - 直接在后面添加 - O(1)

add(idnex, E) - 插入數(shù)據(jù)后需要移動后面的數(shù)據(jù) - O(n)

remove(index) - 刪除后需要移動 - O(n)

LinkedList

LinkedList內(nèi)部是一個雙向鏈表，add新數(shù)據(jù)的時候，其實就是調(diào)用linklast在鏈表尾部插入數(shù)據(jù)。刪除的時候直接找到對應(yīng)數(shù)據(jù)，替換掉鏈表的前后節(jié)點即可。

時間復(fù)雜度：

get() - 需要遍歷 - O(n)

add(E) - 調(diào)用linklast直接添加在最后 - O(1)

add(index, E) - 需要先查找到原來index位置的數(shù)據(jù)，再重新指定鏈表前后的數(shù)據(jù) - O(n)

remove() - 直接調(diào)用removeLast刪除最后數(shù)據(jù) - O(1)

remove(index) - 需要先查找到原來index位置的數(shù)據(jù) - O(n)

HashMap

HashMap內(nèi)部其實是一個數(shù)組，每個數(shù)組下是一個單向鏈表。HashMap中的數(shù)組是一個取名為Entry的類，類包含(key, value, next)這幾個屬性。存放規(guī)則為，數(shù)組下標(biāo)按hash(key)%len獲得，取得數(shù)組后則查找對應(yīng)數(shù)組的值。HashMap還有個負(fù)載因子（默認(rèn)0.75），當(dāng)里面數(shù)組填滿了75%的時候，會進(jìn)行擴(kuò)展到原來大小的2倍。

那么問題來了，如果在put的時候，取到hash(key)%len的值相等時不就沖突了？HashMap的處理方法是：原來有一個Entry[0] = A，此時來一個index也是0的B，則會把Entry[0] = B，B.next = A，又來一個C的時候，則會把Entry[0] = C，C.next = B，以此類推。這樣Entry就會形成一個鏈表，取的時候則是遍歷鏈表取值。

這里需要提到的是，使用hashMap的時候，引入的key對象必須重寫hashCode()和equal()兩個函數(shù)，原因可以參考源碼判斷條件(if (e.hash == hash && ((k = e.key) == key || key.equals(k))))，如果hashCode()沒重寫，則壓根找不到對應(yīng)數(shù)組，如果equal()沒重寫，則無法判斷key值的內(nèi)容是否相等。

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value); //null總是放在數(shù)組的第一個鏈表中  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        //遍歷鏈表  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            //如果key在鏈表中已存在，則替換為新value  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))){  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
}

補(bǔ)充：

在java8之后hashmap進(jìn)行了優(yōu)化：由于單向鏈表的查詢時間復(fù)雜度為O(n)，在極端情況下可能存在性能問題，于是java8針對鏈表長度大于8的情況會使用時間復(fù)雜度為O(log n)的紅黑樹進(jìn)行存儲來提升存儲查詢的效率。

LinkedHashMap

LinkedHashMap內(nèi)部雙向鏈表和HashMap的結(jié)合，支持多種迭代順序，默認(rèn)按插入順序，也可以按訪問順序。 

訪問順序（accessOrder=true）：調(diào)用過get訪問的元素會放到鏈尾，迭代會從鏈?zhǔn)组_始

插入順序（accessOrder=false）：按插入順序迭代出來

TreeMap

TreeMap內(nèi)部是基于紅黑樹實現(xiàn)的，并且默認(rèn)會通過compareTo按照key類型進(jìn)行自然排序。TreeSet的低層是TreeMap。

 

 

來自：http://www.jointforce.com/jfperiodical/article/4192

 

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。