成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【Java】jdk1.8集合類特性綜述及橫向比較

沈儉 / 1412人閱讀

摘要：前置知識基礎(chǔ)集合類基礎(chǔ)字典該接口不基于比較繼承父接口父類數(shù)據(jù)存儲底層結(jié)構(gòu)數(shù)組鏈表紅黑樹同雙向鏈表紅黑樹復(fù)雜度插入同刪除同查找同有序性迭代順序插入順序訪問順序自然序自定義支持否同是哈希哈希函數(shù)基于高低位同桶定位法位運算同沖突處理轉(zhuǎn)換成鏈表紅黑

前置知識: Java基礎(chǔ) 集合類基礎(chǔ)(jdk1.8)

Map(字典)

該接口不基于Collection

HashMap/LinkedHashMap/TreeMap比較
HashMap LinkedHashMap TreeMap
繼承 父接口 Map Map NavigableMap1
父類 AbstractMap HashMap AbstractMap
數(shù)據(jù)存儲 底層結(jié)構(gòu) 數(shù)組+(鏈表/紅黑樹) 同HashMap+雙向鏈表 紅黑樹
復(fù)雜度 插入 O(1) 同HashMap O(lgN)
刪除 O(1) 同HashMap O(lgN)
查找 O(1) 同HashMap O(lgN)
有序性 迭代順序 / 插入順序/訪問順序 自然序/自定義
支持Navigate 否 同HashMap 是
哈希 哈希函數(shù) 基于HashCode()高/低位2 同HashMap /
桶定位法 位運算3 同HashMap /
沖突處理 轉(zhuǎn)換成鏈表/紅黑樹4 同HashMap /
擴容機制 初始容量 163 同HashMap /
最大容量 1 << 30(2^31 ) 同HashMap /
負(fù)載因子 0.755 同HashMap /
擴容策略 2倍3 同HashMap /
擴容時機 插入后6 同HashMap /
具體操作 在新數(shù)組中重排所有元素 同HashMap /
保持迭代順序 否7 同HashMap /
序列化 典型優(yōu)化 跳過數(shù)組null位置 同HashMap8 /
transient9 size/modCount10; table/entrySet; 同HashMap; head/tail8; size/modCount; root11;
同步 線程安全 否 同HashMap 否
final Entry.hash/key 同HashMap 無
Set(集合)

該接口基于Collection

HashSet/LinkedHashSet/TreeSet比較

Set實現(xiàn)內(nèi)部使用了Map實現(xiàn),所以其特性和Map對應(yīng)項類似

List(列表)

該接口基于Collection

ArrayList/LinkedList/Vector比較
ArrayList LinkedList Vector
繼承 父接口 List/RandonAccess List/Deque List/RandonAccess
父類 AbstractList AbstractSequentialList AbstractList
數(shù)據(jù)存儲 底層結(jié)構(gòu) 數(shù)組 雙向鏈表12 數(shù)組
復(fù)雜度 插入 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倍 / 默認(rèn)為2倍
主要耗時點 拷貝數(shù)組13 / 拷貝數(shù)組
同步 線程安全 無 無 是(synchronized)
序列化 優(yōu)化策略 跳過數(shù)組空白的尾部 / 無
transient elementData; size; first/last; 無14
Queue/Deque(隊列/雙端隊列)

該接口基于Collection

LinkedList/PriorityQueue/ArrayDeque比較
LinkedList PriorityQueue ArrayDeque
繼承 父接口 List/Deque Queue Deque
父類 AbstractSequentialList AbstractQueue AbstractCollection
數(shù)據(jù)存儲 數(shù)據(jù)結(jié)構(gòu) 列表/雙端隊列 優(yōu)先隊列 雙端隊列
底層結(jié)構(gòu) 雙向鏈表 最小堆/最大堆15(數(shù)組) 循環(huán)數(shù)組
Usage 插入null元素 支持 不支持16 不支持17
有序性 出隊有序性 / 自然序/自定義 /
迭代有序性 / 無 /
復(fù)雜度 插入 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倍
序列化 優(yōu)化策略 / 刪除空白位置,但size不小于2 刪除空白位置
transient size; first/last; queue; modCount; elements; head/tail;
同步 線程安全 否 否 否
Reference

Java 8系列之重新認(rèn)識HashMap

深入理解哈希表

Java 核心技術(shù)點之集合框架

LinkedHashMap

List 總結(jié)

【集合框架】JDK1.8源碼分析HashSet && LinkedHashSet（八）

JDK中優(yōu)先級隊列PriorityQueue實現(xiàn)分析

通過NavigableMap(擴展自SortedMap)接口,程序可以通過Entry之間的大小順序,訪問某個Entry相鄰的Entry ?

一共兩次哈希:第一次:Object.hashCode()返回32位整數(shù);地二次:對第一次哈希值的低位和高位做乘方運算,保證所有數(shù)字都參與計算,防止Hash聚集現(xiàn)象 ?

定位元素位于哪個bucket中一般使用求模運算index = hash % length,HashMap中使用較之更快的等效位運算index = hash & (length - 1),條件是數(shù)組length必須滿足2^n .受影響參數(shù)包括初始容量/最大容量/擴容策略.使用位運算的代價是:如果length為素數(shù),HashMap不容易產(chǎn)生Hash沖突,但這是一個trade-off ?

since jdk1.8,當(dāng)元素過于集中在一個bucket時,由鏈表轉(zhuǎn)成紅黑樹;反之由紅黑樹轉(zhuǎn)成鏈表 ?

loadFactor>0即可;負(fù)載因子越大,同樣內(nèi)存HashMap能容納元素越多,Hash沖突可能性越大,各個操作的復(fù)雜度越大 ?

插入后檢測擴容比插入前要差,無法避免無謂的擴容(即之后不在put元素的場景) ?

由于resize后各個元素的hash值可能發(fā)生變化,所以無法保證迭代器遍歷的順序,主要體現(xiàn)在在原數(shù)組中靠前的元素在新數(shù)組中靠后,而且如果假設(shè)hash函數(shù)是平均分布的話,該種情況出現(xiàn)的概率為50%(eg.元素hash=31,old_array.length=16,new_array.length=32,元素位置從15變成31).有趣的是,jdk1.8的HashMap利用了這種現(xiàn)象來降低resize時重新計算元素位置的開銷 ?

head/tail為雙向鏈表的頭結(jié)點和尾節(jié)點,由于使用其父類的序列化方法,因此反序列之后需要重新生成雙向鏈表,這是在新建節(jié)點的newNode()中實現(xiàn)的;訪問/插入/刪除方法中對雙向鏈表的操作會通過Override父類的Hook方法實現(xiàn) ?

transient修飾的變量不會被Java默認(rèn)的序列化器處理,需要程序自己OverloadwriteObject()和readObject()方法 ?

modCount記錄結(jié)構(gòu)變化的次數(shù)(eg.插入新元素/刪除老元素) ?

紅黑樹的根節(jié)點 ?

講道理是可以用單向鏈表的,但是由于該類被官方推薦來模擬Stack/Queue/Deque,因此使用了雙向鏈表,該類能夠毫不費力的兼容這些數(shù)據(jù)結(jié)構(gòu) ?

執(zhí)行拷貝數(shù)組的方法是Arrays.copy(),底層native方法是arraycopy(),對數(shù)組元素的拷貝都是淺拷貝.可以用簡單的實驗表明:當(dāng)原數(shù)組的元素數(shù)量超過10^6 時,耗時超過1ms;當(dāng)原數(shù)組元素數(shù)量超過10^7 時,耗時超過5ms ?

由于歷史原因Vector(since jdk1.0)沒有對序列化做優(yōu)化,數(shù)組尾部的空白片段依然會被保留,官方也推薦使用更新的集合類(since jdk1.2)來代替它 ?

默認(rèn)是二叉最小堆(默認(rèn)的comparator來自于SortedSet) ?

null元素是被刪除的元素留下的空位置/還沒有添加元素的空位置,是個重要的remove()判斷條件,所以不能插入null元素 ?

原因類似PriorityQueue,循環(huán)數(shù)組中中間有一段是null的,null是數(shù)組中的空位置 ?

該最小容量是由序列化writeObject()方法保證,保證樹二叉堆至少有兩層 ?

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67279.html

相關(guān)文章

  • Java多線程進(jìn)階（一）—— J.U.C并發(fā)包概述

    摘要：整個包，按照功能可以大致劃分如下鎖框架原子類框架同步器框架集合框架執(zhí)行器框架本系列將按上述順序分析，分析所基于的源碼為。后，根據(jù)一系列常見的多線程設(shè)計模式，設(shè)計了并發(fā)包，其中包下提供了一系列基礎(chǔ)的鎖工具，用以對等進(jìn)行補充增強。 showImg(https://segmentfault.com/img/remote/1460000016012623); 本文首發(fā)于一世流云專欄：https...

    anonymoussf 評論0 收藏0

  • java源碼

    摘要：集合源碼解析回歸基礎(chǔ)，集合源碼解析系列，持續(xù)更新和源碼分析與是兩個常用的操作字符串的類。這里我們從源碼看下不同狀態(tài)都是怎么處理的。 Java 集合深入理解：ArrayList 回歸基礎(chǔ)，Java 集合深入理解系列，持續(xù)更新~ JVM 源碼分析之 System.currentTimeMillis 及 nanoTime 原理詳解 JVM 源碼分析之 System.currentTimeMi...

    Freeman 評論0 收藏0

  • Java集合總結(jié)【面試題+腦圖】，將知識點一網(wǎng)打盡！

    摘要：而在集合中，值僅僅是一個對象罷了該對象對本身而言是無用的。將這篇文章作為集合的總結(jié)篇，但覺得沒什么好寫就回答一些面試題去了，找了一會面試題又覺得不夠系統(tǒng)。 前言 聲明，本文用的是jdk1.8 花了一個星期，把Java容器核心的知識過了一遍，感覺集合已經(jīng)無所畏懼了！！(哈哈哈....)，現(xiàn)在來總結(jié)一下吧~~ 回顧目錄： Collection總覽 List集合就這么簡單【源碼剖析】 Ma...

    yearsj 評論0 收藏0

  • 通過面試題，讓我們來了解Collection

    摘要：說一說迭代器通過集合對象獲取其對應(yīng)的對象判斷是否存在下一個元素取出該元素并將迭代器對象指向下一個元素取出元素的方式迭代器。對于使用容器者而言，具體的實現(xiàn)不重要，只要通過容器獲取到該實現(xiàn)的迭代器的對象即可，也就是方法。 前言 歡迎關(guān)注微信公眾號：Coder編程獲取最新原創(chuàng)技術(shù)文章和相關(guān)免費學(xué)習(xí)資料，隨時隨地學(xué)習(xí)技術(shù)知識！** 本章主要介紹Collection集合相關(guān)知識，結(jié)合面試中會提到...

    HelKyle 評論0 收藏0

  • java5-8新特性的理解

    摘要：引用特定類型的方法特定類普通方法引用構(gòu)造方法類名稱引用構(gòu)造方法內(nèi)建函數(shù)式接口方法引用操作可能出現(xiàn)的函數(shù)式接口有四類有參數(shù)有返回值有參數(shù)無返回值無參數(shù)有返回值判斷真假。 可變參數(shù) 在java程序中調(diào)用方法時，必須嚴(yán)格按照方法定義的變量進(jìn)行參數(shù)傳遞。但是在開發(fā)過程中可能會出現(xiàn)一種情況：不確定要傳遞的參數(shù)個數(shù)。解決這個問題的思路是將多個參數(shù)封裝為數(shù)組。這是一個打折扣的方法，因為數(shù)組并不代表任...

    Jinkey 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<