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

沈儉發布于2019-08-15 10:40 / 1398人閱讀

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

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

Map(字典)

該接口不基于Collection

HashMap/LinkedHashMap/TreeMap比較

		HashMap	LinkedHashMap	TreeMap
繼承	父接口	Map	Map	NavigableMap¹
	父類	AbstractMap	HashMap	AbstractMap
數據存儲	底層結構	數組+(鏈表/紅黑樹)	同HashMap+雙向鏈表	紅黑樹
復雜度	插入	O(1)	同HashMap	O(lgN)
	刪除	O(1)	同HashMap	O(lgN)
	查找	O(1)	同HashMap	O(lgN)
有序性	迭代順序	/	插入順序/訪問順序	自然序/自定義
	支持Navigate	否	同HashMap	是
哈希	哈希函數	基于HashCode()高/低位²	同HashMap	/
	桶定位法	位運算³	同HashMap	/
	沖突處理	轉換成鏈表/紅黑樹⁴	同HashMap	/
擴容機制	初始容量	16³	同HashMap	/
	最大容量	1 << 30(2^31 )	同HashMap	/
	負載因子	0.75⁵	同HashMap	/
	擴容策略	2倍³	同HashMap	/
	擴容時機	插入后⁶	同HashMap	/
	具體操作	在新數組中重排所有元素	同HashMap	/
	保持迭代順序	否⁷	同HashMap	/
序列化	典型優化	跳過數組null位置	同HashMap⁸	/
	transient⁹	size/modCount¹⁰; table/entrySet;	同HashMap; head/tail⁸;	size/modCount; root¹¹;
同步	線程安全	否	同HashMap	否
	final	Entry.hash/key	同HashMap	無

Set(集合)

該接口基于Collection

HashSet/LinkedHashSet/TreeSet比較

Set實現內部使用了Map實現,所以其特性和Map對應項類似

List(列表)

該接口基于Collection

ArrayList/LinkedList/Vector比較

		ArrayList	LinkedList	Vector
繼承	父接口	List/RandonAccess	List/Deque	List/RandonAccess
	父類	AbstractList	AbstractSequentialList	AbstractList
數據存儲	底層結構	數組	雙向鏈表¹²	數組
復雜度	插入	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倍
	主要耗時點	拷貝數組¹³	/	拷貝數組
同步	線程安全	無	無	是(synchronized)
序列化	優化策略	跳過數組空白的尾部	/	無
	transient	elementData;	size; first/last;	無¹⁴

Queue/Deque(隊列/雙端隊列)

該接口基于Collection

LinkedList/PriorityQueue/ArrayDeque比較

		LinkedList	PriorityQueue	ArrayDeque
繼承	父接口	List/Deque	Queue	Deque
	父類	AbstractSequentialList	AbstractQueue	AbstractCollection
數據存儲	數據結構	列表/雙端隊列	優先隊列	雙端隊列
	底層結構	雙向鏈表	最小堆/最大堆¹⁵(數組)	循環數組
Usage	插入null元素	支持	不支持¹⁶	不支持¹⁷
有序性	出隊有序性	/	自然序/自定義	/
	迭代有序性	/	無	/
復雜度	插入	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
	最小容量	/	2¹⁸	8
	時間點	/	插入前	插入后
	判斷條件	/	index >= queue.length	head==tail
	策略	/	新容量<=64為2倍,否則為1.5倍	2倍
序列化	優化策略	/	刪除空白位置,但size不小于2	刪除空白位置
	transient	size; first/last;	queue; modCount;	elements; head/tail;
同步	線程安全	否	否	否

Reference

Java 8系列之重新認識HashMap

深入理解哈希表

Java 核心技術點之集合框架

LinkedHashMap

List 總結

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

JDK中優先級隊列PriorityQueue實現分析

通過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()方法保證,保證樹二叉堆至少有兩層 ?

云服務器 GPU云服務器 JDK1.8 java集合工具類 java集合類詳解、 java集合類詳解

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

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

Java多線程進階（一）—— J.U.C并發包概述

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

anonymoussf 2019-08-16 12:40 評論0 收藏0
java源碼

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

Freeman 2019-08-16 10:59 評論0 收藏0
Java集合總結【面試題+腦圖】，將知識點一網打盡！

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

yearsj 2019-08-15 15:29 評論0 收藏0
通過面試題，讓我們來了解Collection

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

HelKyle 2019-08-16 15:56 評論0 收藏0
java5-8新特性的理解

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

Jinkey 2019-08-19 11:04 評論0 收藏0