「Java」jdk1.8集合類特性綜述及橫向比較
知識
07-06
前置知識: Java基礎 集合類基礎(jdk1.8)
Map(字典)
該介面不基於Collection
| HashMap | LinkedHashMap | TreeMap | ||
|---|---|---|---|---|
| 繼承 | 父介面 | Map | Map | NavigableMap1 |
| 父類 | AbstractMap | HashMap | AbstractMap | |
| 數據存儲 | 底層結構 | 數組+(鏈表/紅黑樹) | 同HashMap+雙向鏈表 | 紅黑樹 |
| 複雜度 | 插入 | O(1) | 同HashMap | O(lgN) |
| 刪除 | O(1) | 同HashMap | O(lgN) | |
| 查找 | O(1) | 同HashMap | O(lgN) | |
| 有序性 | 迭代順序 | / | 插入順序/訪問順序 | 自然序/自定義 |
| 支持Navigate | 否 | 同HashMap | 是 | |
| 哈希 | 哈希函數 | 基於HashCode高/低位2 | 同HashMap | / |
| 桶定位法 | 位運算3 | 同HashMap | / | |
| 衝突處理 | 轉換成鏈表/紅黑樹4 | 同HashMap | / | |
| 擴容機制 | 初始容量 | 163 | 同HashMap | / |
| 最大容量 | 1 << 30(2^31 ) | 同HashMap | / | |
| 負載因子 | 0.755 | 同HashMap | / | |
| 擴容策略 | 2倍3 | 同HashMap | / | |
| 擴容時機 | 插入後6 | 同HashMap | / | |
| 具體操作 | 在新數組中重排所有元素 | 同HashMap | / | |
| 保持迭代順序 | 否7 | 同HashMap | / | |
| 序列化 | 典型優化 | 跳過數組null位置 | 同HashMap8 | / |
| transient9 | size/modCount10; table/entrySet; | 同HashMap; head/tail8; | size/modCount; root11; | |
| 同步 | 線程安全 | 否 | 同HashMap | 否 |
| final | Entry.hash/key | 同HashMap | 無 |
Set(集合)
該介面基於Collection
Set實現內部使用了Map實現,所以其特性和Map對應項類似
List(列表)
該介面基於Collection
| ArrayList | LinkedList | Vector | ||
|---|---|---|---|---|
| 繼承 | 父介面 | List/RandonAccess | List/Deque | List/RandonAccess |
| 父類 | AbstractList | AbstractSequentialList | AbstractList | |
| 數據存儲 | 底層結構 | 數組 | 雙向鏈表12 | 數組 |
| 複雜度 | 插入 | O(N) | O(1) | O(N) |
| 刪除 | O(N) | O(1) | O(N) | |
| 查詢 | O(1) | O(N) | O(1) | |
| 容量 | 初始容量 | 10 | 0 | 10 |
| 最大容量 | Integer.Max | Integer.Max | Integer.Max | |
| 擴容 | 時間點 | 插入前 | / | 插入前 |
| 策略 | 1.5倍 | / | 默認為2倍 | |
| 主要耗時點 | 拷貝數組13 | / | 拷貝數組 | |
| 同步 | 線程安全 | 無 | 無 | 是(synchronized) |
| 序列化 | 優化策略 | 跳過數組空白的尾部 | / | 無 |
| transient | elementData; | size; first/last; | 無14 |
Queue/Deque(隊列/雙端隊列)
該介面基於Collection
| LinkedList | PriorityQueue | ArrayDeque | ||
|---|---|---|---|---|
| 繼承 | 父介面 | List/Deque | Queue | Deque |
| 父類 | AbstractSequentialList | AbstractQueue | AbstractCollection | |
| 數據存儲 | 數據結構 | 列表/雙端隊列 | 優先隊列 | 雙端隊列 |
| 底層結構 | 雙向鏈表 | 最小堆/最大堆15(數組) | 循環數組 | |
| Usage | 插入null元素 | 支持 | 不支持16 | 不支持17 |
| 有序性 | 出隊有序性 | / | 自然序/自定義 | / |
| 迭代有序性 | / | 無 | / | |
| 複雜度 | 插入 | O(1) | O(lgN) | O(N) |
| 刪除 | O(1) | O(lgN) | O(N) | |
| 查詢 | O(N) | O(lgN) | O(1) | |
| 入隊 | O(1) | O(lgN) | O(1) | |
| 出隊 | O(1) | O(lgN) | O(1) | |
| 擴容 | 初始容量 | / | 11(1+2+4+4) | 8 |
| 最小容量 | / | 218 | 8 | |
| 時間點 | / | 插入前 | 插入後 | |
| 判斷條件 | / | index >= queue.length | head==tail | |
| 策略 | / | 新容量<=64為2倍,否則為1.5倍 | 2倍 | |
| 序列化 | 優化策略 | / | 刪除空白位置,但size不小於2 | 刪除空白位置 |
| transient | size; first/last; | queue; modCount; | elements; head/tail; | |
| 同步 | 線程安全 | 否 | 否 | 否 |
Reference
- 通過
NavigableMap(擴展自SortedMap)介面,程序可以通過Entry之間的大小順序,訪問某個Entry相鄰的Entry? - 一共兩次哈希:第一次:Object.hashCode返回32位整數;地二次:對第一次哈希值的低位和高位做乘方運算,保證所有數字都參與計算,防止Hash聚集現象 ?
- 定位元素位於哪個bucket中一般使用求模運算
index = hash % length,HashMap中使用較之更快的等效位運算index = hash & (length - 1),條件是數組length必須滿足2^n .受影響參數包括初始容量/最大容量/擴容策略.使用位運算的代價是:如果length為素數,HashMap不容易產生Hash衝突,但這是一個trade-off? - since jdk1.8,當元素過於集中在一個bucket時,由鏈錶轉成紅黑樹;反之由紅黑樹轉成鏈表 ?
loadFactor>0即可;負載因子越大,同樣內存HashMap能容納元素越多,Hash衝突可能性越大,各個操作的複雜度越大?- 插入後檢測擴容比插入前要差,無法避免無謂的擴容(即之後不在put元素的場景) ?
- 由於resize後各個元素的hash值可能發生變化,所以無法保證迭代器遍歷的順序,主要體現在在原數組中靠前的元素在新數組中靠後,而且如果假設hash函數是平均分布的話,該種情況出現的概率為50%(eg.元素hash=31,old_array.length=16,new_array.length=32,元素位置從15變成31).有趣的是,jdk1.8的HashMap利用了這種現象來降低resize時重新計算元素位置的開銷 ?
head/tail為雙向鏈表的頭結點和尾節點,由於使用其父類的序列化方法,因此反序列之後需要重新生成雙向鏈表,這是在新建節點的newNode中實現的;訪問/插入/刪除方法中對雙向鏈表的操作會通過Override父類的Hook方法實現?transient修飾的變數不會被Java默認的序列化器處理,需要程序自己OverloadwriteObject和readObject方法?modCount記錄結構變化的次數(eg.插入新元素/刪除老元素)?- 紅黑樹的根節點 ?
- 講道理是可以用單向鏈表的,但是由於該類被官方推薦來模擬Stack/Queue/Deque,因此使用了雙向鏈表,該類能夠毫不費力的兼容這些數據結構 ?
- 執行拷貝數組的方法是
Arrays.copy,底層native方法是arraycopy,對數組元素的拷貝都是淺拷貝.可以用簡單的實驗表明:當原數組的元素數量超過10^6 時,耗時超過1ms;當原數組元素數量超過10^7 時,耗時超過5ms? - 由於歷史原因
Vector(since jdk1.0)沒有對序列化做優化,數組尾部的空白片段依然會被保留,官方也推薦使用更新的集合類(since jdk1.2)來代替它? - 默認是二叉最小堆(默認的
comparator來自於SortedSet)? - null元素是被刪除的元素留下的空位置/還沒有添加元素的空位置,是個重要的
remove判斷條件,所以不能插入null元素? - 原因類似
PriorityQueue,循環數組中中間有一段是null的,null是數組中的空位置? - 該最小容量是由序列化
writeObject方法保證,保證樹二叉堆至少有兩層?
※kubespray安裝kubernetes完成後kubectl客戶端配置
※Java基礎----jdk1.8 反射實驗
※ASP.NET Core配置環境變數和啟動設置
※10.動態規劃（3）——0-1背包問題
TAG:科技優家 |
您可能感興趣
※Louis Pouzin：互聯網發展歷史綜述及未來展望
※2018諾貝爾經濟學獎得主思想綜述及對中國發展的啟示
※今日3篇必讀論文，英偉達GAN神作、自編碼器綜述及擬人機器人系統
※亞冠綜述及排名，5隊出線上港鎖第1，申花等6隊出局，恆大留懸念
※亞冠綜述及積分榜：權健6球慘敗小組第二！恆大逆轉獲首個三分！
※世界盃F組綜述及出線形勢：德國讀秒絕殺握主動，韓國0分仍存希望
※多發性骨髓瘤的分子譜分析：文獻綜述及其治療策略效果的早期指征
※大數據行業概述及機會分析
※根據2月份氣象評述及3月份天氣預報，看春季的農業生產
※亞冠綜述及積分榜 上港鎖定第一權健提前出線，日本已有兩隊出局
※物聯網概述及發展歷程
※俄羅斯「先鋒」高超聲速 助推滑翔導彈綜述及研判
※家國之間：柏拉圖與亞里士多德的家邦關係論述及其啟示
※市場評述及早盤金士頓報價
※廖孟豪 | 俄羅斯「先鋒」高超聲速助推滑翔導彈綜述及研判
※英國大健康產業概述及經驗借鑒
※鋸切行業概述及鋸切行業現狀
※亞冠綜述及排名，上港權健領跑，李同國兩球導逆轉，日本兩連敗
※理想豐滿但現實骨感：俄羅斯海軍新型航空母艦方案綜述及簡評
※黃氏輯佚韻書概述及研究價值