NO IMAGE

1、ArrayList<E>

先看其原始碼:

private static final int DEFAULT_CAPACITY = 10; //初始記憶體大小

transient Object[] elementData; //真實資料存放地, 被 transient 修飾的屬性變數不會被序列化(不被網路傳輸、持久化)

實現是基於動態陣列的資料結構,每個元素在記憶體中儲存地址是連續的。每次擴容會固定為1.5倍,所以當你ArrayList達到一定量之後會是一種很大的浪費,並且每次擴容的過程是內部複製陣列到新陣列;對於每個元素的檢索,ArrayList要優於LinkedList。非執行緒安全

淺談JAVA基礎之List與Map

 

ArrayList預設容量是10,如果初始化時一開始指定了容量,或者通過集合作為元素,則容量為指定的大小或引數集合的大小。每次擴容時新容量按老容量1.5倍計算,如果新容量數大於所需最小容量則為新增後所需的最小容量。如果計算後的新容量數超過限制的容量數 MAX_ARRAY_SIZE ( Integer.MAX_VALUE – 8 ),則用所需的最小容量與 MAX_ARRAY_SIZE 進行判斷,超過則指定為 Integer 的最大值,否則指定為限制容量大小。然後通過陣列的複製將原資料複製到一個更大(新的容量大小)的陣列。

Vector與其大致相同,都是基於陣列的資料結構,但是執行緒安全(擴容等方法加了synchronized),vector每次擴容容量是翻倍,即為原來的2倍

剛整理了一套2018最新的0基礎入門和進階教程,無私分享,加Java學習q-u-n :六七八,二四一,五六三 即可獲取,內附:開發工具和安裝包,以及系統學習路線圖

2、LinkedList

transient int size = 0;

LinkedList是採用連結串列的方式來實現List介面的,它本身有自己特定的方法,如: addFirst(),addLast(),getFirst(),removeFirst()等. 由於是採用連結串列實現的,因此在進行 新增 和 刪除 動作時在效率上要比ArrayList要好得多 ! 適合用來實現Stack(堆疊)與Queue(佇列),前者先進後出,後者是先進先出。非執行緒安全

理論上效率好,實際得看新增、刪除位置或者說實際中資料量小,效率差異忽略不計。

3、HashSet

內部也是基於 Hashmap 實現,不允許有重複元素。無序。初始容量16,擴容因子0.75 。在HashSet中,元素都存到HashMap鍵值對的Key上面,而Value時有一個統一的值private static final Object PRESENT = new Object();定義一個虛擬的Object物件作為HashMap的value,將此物件定義為static final。

淺談JAVA基礎之List與Map

 

4、LinkedHashSet

整合 HashSet ,但內部也是基於 LinkedHashMap ,與HashSet 相比無新方法,但元素是有序的。

5、TreeSet

內部基於TreeMap,TreeSet中存放的元素是有序的(不是插入時的順序,是有按關鍵字大小排序的),且元素不能重複。存放自定義物件,需自定義物件實現Comparable 介面,並重寫介面中的compareTo方法,當 compareTo方法

  1. 返回 0 時 只會存一個元素,認為是相同的元素,這時就不再向TreeSet中插入相同的新元素。
  2. 返回負數會倒序儲存,認為新插入的元素比上一個元素小,於是二叉樹儲存時,會存在根的左側,讀取時就是倒序序排列的。
  3. 返回自然數時 認為新插入的元素比上一個元素大,於是二叉樹儲存時,會存在根的右側,讀取時就是正序排列的。

6、HashMap

無序,非執行緒安全,無重複key,允許key和value空值 ,key為空值時其hashCode值定為了0,從而將其存放在雜湊表的第0個bucket中。預設的初始化大小為16,之後每次擴充為原來的2倍。

a. JDK7中HashMap採用的是 陣列(位桶) 連結串列的方式,即我們常說的雜湊連結串列的方式,

transient Entry<K,V>[] table;

HashMap 在底層將 key-value 當成一個整體進行處理,這個整體就是一個 Entry 物件。HashMap 底層採用一個 Entry[] 陣列來儲存所有的 key-value 對,當需要儲存一個 Entry 物件時,會根據hash演算法來決定其在陣列中的儲存位置,在根據equals方法決定其在該陣列位置上的連結串列中的儲存位置;當需要取出一個Entry時,也會根據hash演算法找到其在陣列中的儲存位置,再根據equals方法從該位置上的連結串列中取出該Entry。

HashMap的resize(rehash)

當HashMap中的元素越來越多的時候,hash衝突的機率也就越來越高,因為陣列的長度是固定的。所以為了提高查詢的效率,就要對HashMap的陣列進行擴容,陣列擴容這個操作也會出現在ArrayList中,這是一個常用的操作,而在HashMap陣列擴容之後,最消耗效能的點就出現了:原陣列中的資料必須重新計算其在新陣列中的位置,並放進去,這就是resize。

那麼HashMap什麼時候進行擴容呢?當HashMap中的元素個數超過陣列大小loadFactor時,就會進行陣列擴容,loadFactor的預設值為0.75,這是一個折中的取值。也就是說,預設情況下,陣列大小為16,那麼當HashMap中元素個數超過160.75=12的時候,就把陣列的大小擴充套件為 2*16=32,即擴大一倍,然後重新計算每個元素在陣列中的位置,而這是一個非常消耗效能的操作,所以如果我們已經預知HashMap中元素的個數,那麼預設元素的個數能夠有效的提高HashMap的效能。

HashMap的效能引數

HashMap 包含如下幾個構造器:

  1. HashMap():構建一個初始容量為 16,負載因子為 0.75 的 HashMap。
  2. ashMap(int initialCapacity):構建一個初始容量為 initialCapacity,負載因子為 0.75 的 HashMap。
  3. HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的負載因子建立一個 HashMap。

HashMap的基礎構造器HashMap(int initialCapacity, float loadFactor)帶有兩個引數,它們是初始容量initialCapacity和負載因子loadFactor。

負載因子loadFactor衡量的是一個雜湊表的空間的使用程度,負載因子越大表示雜湊表的裝填程度越高,反之愈小。對於使用連結串列法的雜湊表來說,查詢一個元素的平均時間是O(1 a),因此如果負載因子越大,對空間的利用更充分,然而後果是查詢效率的降低;如果負載因子太小,那麼雜湊表的資料將過於稀疏,對空間造成嚴重浪費。

HashMap的實現中,通過threshold欄位來判斷HashMap的最大容量:

threshold = (int)(capacity * loadFactor);

結合負載因子的定義公式可知,threshold就是在此loadFactor和capacity對應下允許的最大元素數目,超過這個數目就重新resize,以降低實際的負載因子。預設的的負載因子0.75是對空間和時間效率的一個平衡選擇。當容量超出此最大容量時, resize後的HashMap容量是容量的兩倍。

b、JDK8中採用的是陣列(位桶) 連結串列/紅黑樹(有關紅黑樹請檢視紅黑樹)的方式,也是非執行緒安全的。當某個位桶的連結串列的長度達到某個閥值的時候,這個連結串列就將轉換成紅黑樹。當同一個hash值的節點數不小於8時,將不再以單連結串列的形式儲存了,會被調整成一顆紅黑樹。這就是JDK7與JDK8中HashMap實現的最大區別。

transient Node<K,V>[] table;

R-B Tree,全稱是Red-Black Tree,又稱為“紅黑樹”,它一種特殊的二叉查詢樹。紅黑樹的每個節點上都有儲存位表示節點的顏色,可以是紅(Red)或黑(Black)。

7、HashTable

無序,執行緒安全,無重複key,不允許key和value空值,HashTable預設的初始大小為11,之後每次擴充為原來的2n 1。內部是採用synchronized來保證執行緒安全的,但線上程競爭激烈的情況下HashTable的效率下降得很快因為synchronized關鍵字會造成程式碼塊或方法成為為臨界區(對同一個物件加互斥鎖),當一個執行緒訪問臨界區的程式碼時,其他執行緒也訪問同一臨界區時,會進入阻塞或輪詢狀態。究其原因,實際上是有獲取鎖意向的執行緒的數目增加,但是鎖還是隻有單個,導致大量的執行緒處於輪詢或阻塞,導致同一時間段有效執行的執行緒的增量遠不及執行緒總體增量。

8、LinkedHashMap

有序,非執行緒安全,Key和Value都允許空,繼承了HashMap。維護一個額外的雙向連結串列保證了迭代順序。

原始碼內部有Entry<K,V> before, after;next 。next是用於維護HashMap指定table位置上連線的Entry的順序的,before、After是用於維護Entry插入的先後順序的

9、CocurrentHashMap

不允許key、value為null,

利用鎖分段技術增加了鎖的數目,從而使爭奪同一把鎖的執行緒的數目得到控制。 鎖分段技術就是對資料集進行分段,每段競爭一把鎖,不同資料段的資料不存在鎖競爭,從而有效提高 高併發訪問效率。CocurrentHashMap在get方法是無需加鎖的,因為用到的共享變數都採用volatile關鍵字修飾,保證共享變數線上程之間的可見性(每次讀取都先同步快取和記憶體,直接從記憶體中獲取值,雖然不是原子操作,但根據JAVA記憶體模型的happen before原則,對volatile欄位的寫入操作先於讀操作,能夠保證不會髒讀),volatile為了讓變數提供執行緒之間的記憶體可見性,會禁止程式執行結果的重排序(導致快取優化的效果降低)。

實際使用中 Map<String, Integer> count = new ConcurrentHashMap<>();

比較

  1. JDK6,7中的ConcurrentHashmap主要使用Segment來實現減小鎖(ReentrantLock)粒度,把HashMap分割成若干個Segment(分段),在put的時候需要鎖住Segment,get時候不加鎖,使用volatile來保證可見性,當要統計全域性時(比如size),首先會嘗試多次計算modcount 來確定,這幾次嘗試中,是否有其他執行緒進行了修改操作,如果沒有,則直接返回size。如果有,則需要依次鎖住所有的Segment來計算;
  2. jdk7中ConcurrentHashmap中,當長度過長碰撞會很頻繁,連結串列的增改刪查操作都會消耗很長的時間,影響效能,所以jdk8 中完全重寫了concurrentHashmap, 主要設計上的變化有以下幾點:
  • 不採用segment而採用node,鎖住node來實現減小鎖粒度。
  • 設計了MOVED狀態 當resize的中過程中 執行緒2還在put資料,執行緒2會幫助resize。
  • 使用3個CAS操作來確保node的一些操作的原子性,這種方式代替了鎖。
  • sizeCtl的不同值來代表不同含義,起到了控制的作用。

JDK8中使用synchronized而不是ReentrantLock,

10.TreeMap

  1. 有序的key-value集合,它是通過紅黑樹實現的。該對映根據其鍵的自然順序進行排序,預設是升序的,如果我們需要改變排序方式,則需要使用比較器:Comparator ,該方法主要是根據第一個引數o1,小於、等於或者大於o2分別返回負整數、0或者正整數。TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

淺談JAVA基礎之List與Map

 

11 cas原理

CAS:Compare and Swap, 翻譯成比較並交換。 CAS有3個運算元,記憶體值V,舊的預期值A,要修改的新值B。當且僅當預期值A和記憶體值V相同時,將記憶體值V修改為B,否則什麼都不做。

淺談JAVA基礎之List與Map

 

CAS通過呼叫JNI的程式碼實現的。JNI:Java Native Interface為JAVA本地呼叫,允許java呼叫其他語言。

而compareAndSwapInt就是藉助C來呼叫CPU底層指令實現的。

淺談JAVA基礎之List與Map