JAVA 常用集合內部機制原理

luqiuwen 發布于2019-08-16 10:28 / 1539人閱讀

摘要：訪問順序調用過訪問的元素會放到鏈尾，迭代會從鏈首開始插入順序按插入順序迭代出來內部是基于紅黑樹實現的，并且默認會通過按照類型進行自然排序。

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

ArrayList

ArrayList內部就是一個默認大小為10的動態對象數組容器，每當add一個新數據的時候，如果大于原來的容器大小，則會通過Arrays.copyOf把容器大小增加到原來的1.5倍，以此類推。當可以預知數據大小，可以通過initialCapacity來默認設置動態數據的大小，減少擴容帶來的資源消耗。

時間復雜度：
get() - 直接讀取下標 - O(1)
add(E) - 直接在后面添加 - O(1)
add(idnex, E) - 插入數據后需要移動后面的數據 - O(n)
remove(index) - 刪除后需要移動 - O(n)

LinkedList

LinkedList內部是一個雙向鏈表，add新數據的時候，其實就是調用linklast在鏈表尾部插入數據。刪除的時候直接找到對應數據，替換掉鏈表的前后節點即可。

時間復雜度：
get() - 需要遍歷 - O(n)
add(E) - 調用linklast直接添加在最后 - O(1)
add(index, E) - 需要先查找到原來index位置的數據，再重新指定鏈表前后的數據 - O(n)
remove() - 直接調用removeLast刪除最后數據 - O(1)
remove(index) - 需要先查找到原來index位置的數據 - O(n)

HashMap

HashMap內部其實是一個數組，每個數組下是一個單向鏈表。HashMap中的數組是一個取名為Entry的類，類包含(key, value, next)這幾個屬性。存放規則為，數組下標按hash(key)%len獲得，取得數組后則查找對應數組的值。HashMap還有個負載因子（默認0.75），當里面數組填滿了75%的時候，會進行擴展到原來大小的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()兩個函數，原因可以參考源碼判斷條件(if (e.hash == hash && ((k = e.key) == key || key.equals(k))))，如果hashCode()沒重寫，則壓根找不到對應數組，如果equal()沒重寫，則無法判斷key值的內容是否相等。

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value); //null總是放在數組的第一個鏈表中  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        //遍歷鏈表  
        for (Entry 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;  
}

補充：
在Java 8之后hashmap進行了優化：由于單向鏈表的查詢時間復雜度為O(n)，在極端情況下(每次都查找)可能存在性能問題，于是Java 8針對鏈表長度大于8的情況會使用時間復雜度為O(log n)的紅黑樹進行存儲來提升存儲查詢的效率，時間復雜度就從原來的O(1)+O(n)變成了O(1)+O(log n)，優化了極端情況導致的性能問題。

LinkedHashMap

LinkedHashMap內部雙向鏈表和HashMap的結合，支持多種迭代順序，默認按插入順序，也可以按訪問順序。
訪問順序（accessOrder=true）：調用過get訪問的元素會放到鏈尾，迭代會從鏈首開始
插入順序（accessOrder=false）：按插入順序迭代出來

TreeMap

TreeMap內部是基于紅黑樹實現的，并且默認會通過compareTo按照key類型進行自然排序。TreeSet的底層是TreeMap。

GPU云服務器云服務器 java集合的原理內部原理 php執行的機制原理 java 集合

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69866.html

金三銀四，2019大廠Android高級工程師面試題整理

摘要：原文地址游客前言金三銀四，很多同學心里大概都準備著年后找工作或者跳槽。最近有很多同學都在交流群里求大廠面試題。最近整理了一波面試題，包括安卓JAVA方面的，目前大廠還是以安卓源碼，算法，以及數據結構為主，有一些中小型公司也會問到混合開發的知識，至于我為什么傾向于混合開發，我的一句話就是走上編程之路，將來你要學不僅僅是這些，豐富自己方能與世接軌，做好全棧的裝備。原文地址：游客kutd...

tracymac7 2019-08-16 16:18 評論0 收藏0
小馬哥Java項目實戰訓練營極客大學

摘要：百度網盤提取碼一面試題熟練掌握是很關鍵的，大公司不僅僅要求你會使用幾個，更多的是要你熟悉源碼實現原理，甚至要你知道有哪些不足，怎么改進，還有一些有關的一些算法，設計模式等等。 ??百度網盤??提取碼：u6C4?一、java面試題熟練掌握java是很關鍵的，大公司不僅僅要求你會使用幾個api，更多的是要你熟悉源碼實現原理，甚...

不知名網友 2021-11-26 11:11 評論0 收藏0
后臺開發常問面試題集錦（問題搬運工，附鏈接）

摘要：基礎問題的的性能及原理之區別詳解備忘筆記深入理解流水線抽象關鍵字修飾符知識點總結必看篇中的關鍵字解析回調機制解讀抽象類與三大特征時間和時間戳的相互轉換為什么要使用內部類對象鎖和類鎖的區別，，優缺點及比較提高篇八詳解內部類單例模式和 Java基礎問題 String的+的性能及原理 java之yield(),sleep(),wait()區別詳解-備忘筆記深入理解Java Stream流水...

spacewander 2019-08-21 17:42 評論0 收藏0
后臺開發常問面試題集錦（問題搬運工，附鏈接）

摘要：基礎問題的的性能及原理之區別詳解備忘筆記深入理解流水線抽象關鍵字修飾符知識點總結必看篇中的關鍵字解析回調機制解讀抽象類與三大特征時間和時間戳的相互轉換為什么要使用內部類對象鎖和類鎖的區別，，優缺點及比較提高篇八詳解內部類單例模式和 Java基礎問題 String的+的性能及原理 java之yield(),sleep(),wait()區別詳解-備忘筆記深入理解Java Stream流水...

xfee 2019-08-15 12:33 評論0 收藏0