Java集合架構底層原理

Java集合架構

• Java集合架構
• List集合
• • ArrayList底層實作原理
  • • ArrayList數組擴容技術（數組拷貝）
    • 擴容大小
    • 查詢和删除
    • 集合中的泛型
  • LinkedList
  • Vector 線程安全
  • LinkedList和ArrayList差別
• Map集合
• • HashMap底層實作原理
  • • 連結清單存放的都是那些資料？
    • 數組初始化
    • HashMap的擴容機制
• ConcurrentHashMap底層原理
• • JDK1.7 HashMap在多線程下線程不安全
  • • 如何判斷單連結清單有環無環
  • HashTable與ConcurrentHashMap
  • Segment
  • JDK1.8版本ConcurrentHashMap
  • • 相比于 1.7 版本，它做了兩個改進
  • CAS （compare and swap比較交換）
  • Node連結清單和紅黑樹的切換

Java集合架構

所有集合類都位于java.util包下。Java的集合類主要由兩個接口派生而出：Collection和Map，Collection和Map是Java集合架構的根接口。

集合特點：

1、所有集合底層基本都是數組（除了LinkedList）

2、集合中可以存放無限大小的資料=>采用數組擴容

集合的關系：

Set 接口繼承 Collection，集合元素不重複。

List 接口繼承 Collection，允許重複，維護元素插入順序

Map接口是鍵－值對象，與Collection接口沒有什麼關系。

List集合是有序集合，集合中的元素可以重複，通路集合中的元素可以根據元素的索引來通路。

Set集合是無序集合，集合中的元素不可以重複，通路集合中的元素隻能根據元素本身來通路

List集合

List集合繼承Collection，重點說一下ArrayList和LinkedList，簡要說一下Vector。

ArrayList底層實作原理

1.Arraylist底層基于數組實作

2.Arraylist底層預設數組初始化大小為10個object數組

public ExtArraylist() throws Exception {
		this(10);
	}
	public ExtArraylist(int initialCapacity) throws Exception {
		if (initialCapacity < 0) {
			throw new IllegalArgumentException("初始容量不能小于0 " + initialCapacity);
		}
		elementData = new Object[initialCapacity];
	}
           

3.添加元素後大于目前數組的長度，則進行擴容,将數組的長度增加原來數組的一半。

// 增大數組空間
	private void grow(int minCapacity) {
		// overflow-conscious code
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + (oldCapacity >> 1); // 在原來容量的基礎上加上
														// oldCapacity/2
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity; // 最少保證容量和minCapacity一樣
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity); // 最多不能超過最大容量
	// minCapacity is usually close to size, so this is a win:
	elementData = Arrays.copyOf(elementData, newCapacity);
	}
           

ArrayList數組擴容技術（數組拷貝）

eg：

Object[] arr = {1,2};
Object[] copyNew = Arrays.copy(arr,10);//原來數組arr,擴容加10，并保證原來資料不變。
/* 
System.arraycopy方法：如果是數組比較大，那麼使用System.arraycopy會比較有優勢，因為其使用的是記憶體複制，省去了大量的數組尋址通路等時間
*/
           

ArrayList正是采用System.arraycopy進行擴容。System.arraycopy是一個Native修飾的方法，由C語言寫的，本地是找不到的。

數組資料量不大的時候，System.arraycopy和Arrays.copy差别不大。但數組資料變大時，System.arraycopy效率優于Arrays.copy。

是以，從JDK1.6開始，Arrays.copy底層也使用了System.arraycopy來實作。

ArrayList底層采用數組實作，數組的名稱叫“ElementData”。

ArrayList底層預設數組的大小為10.

JDK1.6初始化預設大小數組在構造器中，JDK1.7之後數組初始化是放在了add()方法中。是以，在定義ArrayList的時候，數組是沒有初始化的。

擴容大小

擴容是在add()方法中，先判斷大小，如果size=elementData.length。即實際元素個數超過數組容量，就會擴容。

ArrayList擴容是原來的1.5倍。源碼如下：

int oldCapacity = elementData.length.
int newCapacity = oldCapacity + (oldCapacity>>1);//右移1位相當于除以2
           

如果ArrayList的初始容量為1，那麼擴容後的容量為多少？

答案：仍然是1（錯誤）

應該是2（正确）

因為JDK由保證最小擴容容量的代碼，如下：

ensureCapacity(size + 1) //minCapacity = size + 1;是以值等于2

if(newCapacity - minCapacity < 0){
	newCapacity = minCapacity;//minCapacity值是2
}
           

查詢和删除

get(index) 使用數組下标進行查詢（查之前對index是否越界進行判斷）

remove(index) 删除原理：

元素：A B C D E

下标：0 1 2 3 4

删除後:

元素：A B D E null

下标：0 1 2 3 4

代碼如下：

System.arrayCopy(elementData,index+1,elementData,index,numMoved)
//如果删除的是最後一個元素，就直接将最後以一個元素置空
           

集合中的泛型

Java的反射機制有個缺點：不能擷取泛型類型。因為泛型是在編譯之後是沒有的。

泛型是運作時才确定類型，（通過位元組碼技術可以擷取到泛型）

LinkedList

LinkedList是雙向連結清單，可以雙向周遊查詢。

Vector 線程安全

Vector相當于線程安全的ArrayList，裡面用了大量的鎖。内部實作和ArrayList幾乎一樣。

LinkedList和ArrayList差別

首先，LinkedList底層删除和新增的時候，不會移動元素，隻會維護内部節點的關系。

ArrayList删除的時候，将目前元素後面資料往前移動移位。這時會用到擴容技術，這種方式效率比較低。

其次，LinkedList查詢慢。因為連結清單沒有下标，需要一個個周遊查詢。（從first開始查詢）

ArrayList查詢非常快，可以直接使用下标查詢。

Map集合

HashMap底層實作原理

HashMap在JDK1.7中使用數組+連結清單，在JDK1.8中使用數組+紅黑樹來實作的。官方說1.8比1.7性能提升15%.

HashMap底層擴容技術：采用負載因子（0.75）

HashMap沖突（碰撞）：采用連結清單（1.7）、紅黑樹（1.8）來處理沖突。

連結清單處理的時候，是把之前的Node作為新沖突Node的下一個節點。

連結清單存放的都是那些資料？

hash值相同，類型都是Entry。Entry包含key、value、next三個屬性。

數組初始化

預設數組初始化大小為：16

HashMap和ArrayList一樣預設都是懶加載，初始化的數組大小都是null，隻有在put(key,value)、add(element)時候才會初始化數組大小。

HashMap的擴容機制

為什麼要擴容？

1、資料一旦滿了的話無法存儲。

2、資料一多連結清單查詢效率低，影響HashMap的性能。

擴容之後，有什麼影響？

需要重新計算hash值。

HashMap從什麼時候開始擴容？

有個負載因子0.75，hash初始化容量大小是16.當資料size>=12時候開始擴容。

HashMap數組擴容，一次擴容多少？

擴容為之前數組的兩倍。

ConcurrentHashMap底層原理

JDK1.7 HashMap在多線程下線程不安全

JDK7 HashMap在并發執行put()方法時候會引起死循環。是因為多線程會導緻HashMap的Entry連結清單形成環形資料，讓連結清單有環，查找時會陷入死循環。

如何判斷單連結清單有環無環

方法1：單連結清單有環，周遊會陷入死循環。（最簡單，但這種方式不靠譜）

方法2：每周遊1個節點就比較之前周遊的節點，如果重複，就表示有環。

方法3：有2個快慢指針slow和fast同時指向頭結點。slow每次周遊1個節點，fast每次周遊2個節點。如果單連結清單無環slow永遠追不上fast，否則slow能追上fast。

HashTable與ConcurrentHashMap

使用synchronized同步鎖，保障了線程安全，但是效率不高。

synchronized關鍵字對put()等方法加鎖，而synchronized是對整個對象加鎖。put()方法在并發修改資料時候，鎖住了整個Hash散清單。故HashTable效率低下。

JDK1.7 ConcurrentHashMap的做法：

JDK1.7ConcurrentHashMap對象儲存了一個Segment數組，即将Hash分為16段。每個Segment元素即相當于一個HashTable。

執行put方法時，根據Hash算法定位到哪個Segment，然後對Segment加鎖。第二次Hash定位到元素頭部連結清單位置。

是以ConcurrentHashMap可以在多線程下實作put操作。

Segment

Segment繼承了ReetrantLock，表示Segment是一個重入鎖。是以ConcurrentHashMap可以通過重入鎖對每個分段加鎖。

預設情況下，初始化數組的大小是16，Segment數組長度也是16，負載因子也是0.75。

ConcurrentHashMap的get方法是不加鎖的，用volatile保證。

ConcurrentHashMap規定key和value均不能為null，否則會抛出空指針異常。（因為會産生線程安全問題）

JDK1.8版本ConcurrentHashMap

JDK1.8版本ConcurrentHashMap采用數組+連結清單+紅黑樹來實作。加鎖使用CAS和synchronized實作。

相比于 1.7 版本，它做了兩個改進

1. 取消了 segment 分段設計，直接使用 Node 數組來儲存資料，并且采用 Node 數組元素作為鎖來實作每一行資料進行加鎖來進一步減少并發沖突的機率

2. 将原本數組+單向連結清單的資料結構變更為了數組+單向連結清單+紅黑樹的結構。為什麼要引入紅黑樹呢?

   在正常情況下，key hash 之後如果能夠很均勻的分散在數組中，那麼 table 數 組中的每個隊列的長度主要為 0 或者 1.但是實際情況下，還是會存在一些隊列長度過長的 情況。如果還采用單向清單方式，那麼查詢某個節點的時間複雜度就變為 O(n);

   是以對于 隊列長度超過 8 的清單，JDK1.8 采用了紅黑樹的結構，那麼查詢的時間複雜度就會降低到 O(logN),可以提升查找的性能;

   

   這個結構和 JDK1.8 版本中的 Hashmap 的實作結構基本一緻，但是為了保證線程安全性， ConcurrentHashMap 的實作會稍微複雜一下

CAS （compare and swap比較交換）

CAS有3個操作數，記憶體值V，預期值A，要修改的值B，當且僅當V=A時，才會将V改為B，否則什麼都不做。

Java中CAS是通過本地方法JNI實作的。

CAS的缺點：

1、存在ABA問題，其解決思路是使用版本号。

2、循環時間長，開銷大

3、隻能保證一個共享變量的原子操作。

Java解決ABA問題，有下面2個原子類：

1、AtomicStampedReference類

帶有一個時間戳的對象引用。

2、AtomicMarkableRefrence類

維護一個Boolean值辨別，處于true和false的切換。這樣做隻能減少ABA發生的機率，并不能杜絕。

Node連結清單和紅黑樹的切換

JDK1.8版本ConcurrentHashMap，加鎖是加在Node頭部結點上，鎖粒度更細，效率更高，大大提升了性能。擴容時阻塞所有讀寫操作，并發擴容。

如果連結清單節點超過8個，則會觸發連結清單轉化為紅黑樹。

當紅黑樹節點小于6個，則紅黑樹會轉化為連結清單。