1.總覽

Java中的集合分List、Set、Queue、Map 4種類型。

List：大多數(shù)實現(xiàn)元素可以為null，可重復(fù)，底層是數(shù)組或鏈表的結(jié)構(gòu)，支持動態(tài)擴容

Set：大多數(shù)實現(xiàn)元素可以為null但只能是1個，不能重復(fù)，

2.List

2.1 ArrayList

ArrayList繼承AbstractList實現(xiàn)List接口，底層是對象數(shù)組，Object[]

可以有多個null，初始大小為10，每次擴容為原容量的1.5倍，

注意：通過下表查找元素效率高，查詢要便利所有、插入、刪除要大量移動元素效率低

2.2 LinkedList

LinkedList繼承AbstractSequentialList實現(xiàn)List、Deque接口，底層是Node鏈表，可以雙向遍歷

可以有多個null，初始化沒有沒有初始任何存儲，當有元素進來時，默認從last節(jié)點插入，構(gòu)造鏈表

注意：通過下標查找元素效率低要遍歷到下標位置，查詢要遍歷所有，插入頭和尾很快，插入和刪除索引位置需要先遍歷到那里再插入和刪除

2.3 Vector(線程安全)

Vector繼承AbstractList實現(xiàn)List接口，底層和ArrayList一樣也是對象數(shù)組，Object[]

它和ArrayList的唯一區(qū)別是： 它是線程安全的，實現(xiàn)的方式是每個有線程安全風險的方法上添加 synchronized 進行同步

2.4 Stack(線程安全)

Stack繼承Vector，是個先進后出的結(jié)構(gòu)，底層和ArrayList一樣也是對象數(shù)組，Object[]

2.5 CopyOnWriteArrayList(線程安全)

CopyOnWriteArrayList實現(xiàn)了List接口，底層和ArrayList一樣也是對象數(shù)組，volatile Object[] array,注意這里用volatile進行了修飾，保證當array引用更改時，所有線程都能獲取到最新的引用。

CopyOnWriteArrayList原理：讀支持多線程并發(fā)讀，寫時復(fù)制原則

set(index, e) 過程：

1. 先加鎖，
2. 獲取原數(shù)組引用，
3. 獲取原值，
4. 原值和新值不同時拷貝新數(shù)組，新數(shù)組值更新，更新array指向，返回舊值
5. 原值和新值相同是，更新array指向(還是原來的)，返回舊值(還是原來的)
6. 解鎖

add(e)過程：

1. 先加鎖，
2. 獲取原數(shù)組引用，
3. 拷貝新數(shù)組，新數(shù)組值更新，更新array指向，返回true，解鎖

3.Set

3.1 HashSet

HashSet繼承AbstractHashSet實現(xiàn)Set接口，底層實際是HashMap或LinkedHashMap，在底層數(shù)據(jù)結(jié)構(gòu)是：Node[]數(shù)組+單鏈表+紅黑樹

可以為null，但只會有一個null，初始大小為16，加載因子是0.75，擴容時是2的倍數(shù)

當調(diào)用HashSet的add方法時，實際是調(diào)用HashMap的put方法，key是add的值，value是一個共享的Object變量。

注意：因為不是線程安全的，調(diào)用size方法，返回的size可能會和真實元素個數(shù)不一致

3.2 LinkedHashSet

LinkedHashSet繼承HashSet，它的代碼很少，因為它借助HashSet的LinkedHashMap為底層實現(xiàn)，完成插入順序的HashSet

其余都和HashSet一致

3.3 TreeSet

TreeSet繼承AbstractSet實現(xiàn)NavigableSet接口，和HashSet相比：

1. 集合種的元素不保證插入排序，默認使用元素自然排序，可以自定義排序器
2. jdk1.8之后，集合中的元素不可以為null

TreeSet使用TreeMap實現(xiàn)，底層用的是紅黑樹。

注意：與HashSet相比，TreeSet的性能稍低，add、remove、search等操作時間復(fù)雜度為O(log n)，按照順序打印n個元素為O(n)

3.4 CopyOnWriteArraySet(線程安全)

CopyOnWriteArraySet繼承AbstractSet，底層使用的是CopyOnWriteArrayList，

當加入的數(shù)據(jù)不存在時，再添加

3.5 ConcurrentSkipListSet(線程安全)

ConcurrentSkipListSet繼承了AbstractSet實現(xiàn)了NavigableSet接口，底層使用ConcurrentNavigableMap實現(xiàn)，和HashSet使用HashMap實現(xiàn)一致

數(shù)據(jù)不能為null，使用ConcurrentNavigableMap的key存儲值，Boolean.TRUE最為ConcurrentNavigableMap的value

注意：此類線程安全且有序，可以傳遞一個排序器

4.Queue

Queue是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，形如我們現(xiàn)時生活中的排隊，第一個到的排在最前面，后面到的依次向后排，第一個處理完后處理第二個。

Deque是在Queue的基礎(chǔ)上支持從尾部取數(shù)據(jù)的功能，Deque能適合更多的場合

4.1ArrayDeque

ArrayDeque繼承AbstractCollection實現(xiàn)了Deque接口，它底層是一個Object[]數(shù)組，它支持自動擴容，默認初始容量是16，當元素達到隊列的容量后就自動以2的倍數(shù)擴容，元素不能是null。

原理：ArrayDeque里面維護了head和tail兩個指針，兩個指針初始都是0，表示的是Object[]數(shù)組的下標，

正常使用隊列使用的是offer方法，offer調(diào)用的是addLast方法，此方法是先在tail位置放置元素，然后再移動tail指針指向下一個位置，如果下一個位置就是head指針指向的位置則表示數(shù)組已全部放置了數(shù)據(jù)，需要對其進行擴容

addFirst使用的是head指針，head指針向左移動，[head = (head - 1) & (elements.length - 1)] = 15，在數(shù)組的最后一個位置放入元素，如果再addFirst就是向14這個位置放置元素，

總結(jié)：ArrayDeque是一個雙端隊列，內(nèi)部使用head和tail指針進行控制元素的進隊和出隊

注意：數(shù)字在計算機中是以補碼的方式存儲的，正數(shù)的補碼等于自己的原碼，負數(shù)的補碼等于自己的原碼除符號位取反再+1，如1的原碼和補碼都是00000001，-1的原碼是10000001，反碼是11111110，補碼是11111111

4.2 PriorityQueue

PriorityQueue繼承AbstractQueue，它底層是一個Object[]數(shù)組，它支持自動擴容，默認初始容量是11，當元素達到隊列的容量后，它會判斷當前容量是否小于64，小于64的話，容量+2否則容量擴大一倍；元素不能是null。

原理：PriorityQueue其實是一種堆排序結(jié)構(gòu)，默認是小根堆，堆底層使用Object[]數(shù)組實現(xiàn)。

堆：1.堆中的某個節(jié)點總是大于或者不小于其父親節(jié)點的值 2.堆總是一顆完全二叉樹

重要方法邏輯：

插入元素：1.先將元素放入到堆的最后一個節(jié)點的位置(也就是數(shù)組的有效元素的最后的一個位置)注：此時空間不夠時需要進行擴容。 2. 將最后插入的節(jié)點向上調(diào)整，直到滿足堆的性質(zhì)

刪除元素(彈出堆的第一個元素)：1. 將堆頂元素和堆中的最后一個元素進行交換 2.刪除堆的最后一個元素 3.對堆頂元素進行向下調(diào)整

效率：加入一個數(shù)的時間復(fù)雜度是logN;取最大數(shù)且繼續(xù)維持大根堆的時間復(fù)雜度是logN；

4.3 DelayQueue(線程安全)

DelayQueue繼承AbstractQueue實現(xiàn)BlockingQueue。它底層是PriorityQueue，依賴PriorityQueue的能力來存儲元素。DelayQueue里的元素都有一個延期時間實現(xiàn)Delayed接口，PriorityQueue按照延期時間進行排序。當還未到延期時間，DelayQueue彈出的數(shù)據(jù)為空。DelayQueue的線程安全是使用ReentrantLock進行控制。

4.3.1 Thread lead 成員變量的用處

leader來減少不必要的等待時間,那么這里我們的DelayQueue是怎么利用leader來做到這一點的呢:

這里我們想象著我們有個多個消費者線程用take方法去取,內(nèi)部先加鎖,然后每個線程都去peek第一個節(jié)點.如果leader不為空說明已經(jīng)有線程在取了,設(shè)置當前線程等待

if (leader != null)available.await();

如果為空說明沒有其他線程去取這個節(jié)點,設(shè)置leader并等待delay延時到期,直到poll后結(jié)束循環(huán)

else {Thread thisThread = Thread.currentThread();leader = thisThread;try {available.awaitNanos(delay);} finally {if (leader == thisThread)leader = null;}}

take方法中 為什么釋放first元素

first = null; // don't retain ref while waiting

我們可以看到doug lea后面寫的注釋,那么這段代碼有什么用呢？

　想想假設(shè)現(xiàn)在延遲隊列里面有三個對象。

• 線程A進來獲取first,然后進入 else 的else ,設(shè)置了leader為當前線程A
• 線程B進來獲取first,進入else的阻塞操作,然后無限期等待
• 這時他是持有first引用的
• 如果線程A阻塞完畢,獲取對象成功,出隊,這個對象理應(yīng)被GC回收,但是他還被線程B持有著,GC鏈可達,所以不能回收這個first.
• 假設(shè)還有線程C 、D、E.. 持有對象1引用,那么無限期的不能回收該對象1引用了,那么就會造成內(nèi)存泄露.

4.4 ConcurrentLinkedQueue(線程安全)

ConcurrentLinkedQueue繼承AbstractQueue實現(xiàn)Queue接口。它是一個線程安全的先進先出隊列實現(xiàn)，內(nèi)部維護了head和tail兩個volatile的指針，它底層是鏈表，自定義了Node節(jié)點，Node類中用volatile聲明了item和next變量，并使用CAS的方式設(shè)置節(jié)點的next節(jié)點等，不支持null元素。

下面以offer方法的注釋來詳細說明下ConcurrentLinkedQueue

public boolean offer(E e) {// 檢查e是不是null，是的話拋出NullPointerException異常。checkNotNull(e);// 創(chuàng)建新的節(jié)點final Node<E> newNode = new Node<E>(e);// 將“新的節(jié)點”添加到鏈表的末尾。for (Node<E> t = tail, p = t;;) {Node<E> q = p.next;// 情況1：q為空，p是尾節(jié)點插入if (q == null) {// CAS操作：如果“p的下一個節(jié)點為null”(即p為尾節(jié)點)，則設(shè)置p的下一個節(jié)點為newNode。// 如果該CAS操作成功的話，則比較“p和t”(若p不等于t，則設(shè)置newNode為新的尾節(jié)點)，然后返回true。// 如果該CAS操作失敗，這意味著“其它線程對尾節(jié)點進行了修改”，則重新循環(huán)。if (p.casNext(null, newNode)) {if (p != t) // hop two nodes at a timecasTail(t, newNode);  // Failure is OK.return true;}}// 情況2：p和q相等else if (p == q)p = (t != (t = tail)) ? t : head;// 情況3：其它elsep = (p != t && t != (t = tail)) ? t : q;}
}

5.5 LinkedBlockingQueue(線程安全)

LinkedBlockingQueue繼承AbstractQueue實現(xiàn)BlockQueue接口，底層是鏈表，使用ReentrantLock進行并發(fā)安全控制。不允許添加null。

注意：如果不傳入?yún)?shù)則默認大小是Integer.max，如果傳入?yún)?shù)則大小就是傳入的數(shù)值，當queue中元素達到最大值時，put 添加元素操作會被阻塞，等queue中不滿時才能繼續(xù)插入，使用Condition notEmpty進行await和signal進行等待和喚醒

5.6 ArrayBlockingQueue(線程安全)

ArrayBlockingQueue繼承AbstractQueue實現(xiàn)BlockingQueue，底層是數(shù)組，使用ReentrantLock進行并發(fā)安全控制。不允許添加null。

原理：使用takeIndex和putIndex對取出和放入的位置進行控制，當take時，取taskIndex的位置元素，當put時put putIndex位置的元素，take和put后，判斷takeIndex和putIndex是否等于數(shù)組的長度，等于的話從0繼續(xù)開始

注意：傳入?yún)?shù)就是底層數(shù)組的大小，當queue中元素達到最大值時，put 添加元素操作會被阻塞，等queue中不滿時才能繼續(xù)插入，使用Condition notEmpty notFull兩個進行控制

5.Map

5.1 HashMap

HashMap繼承AbstractMap實現(xiàn)Map接口。底層是數(shù)組+鏈表+紅黑樹。允許key和value為null

擴容：HashMap初始容量是16，默認負載因子是0.75，當HashMap中的元素數(shù)量大于 容量*負載因子則進行容量*2的擴容操作。

引入紅黑樹的原因：降低查找相同hash值節(jié)點的速度，紅黑樹也是一種平衡二叉樹，當節(jié)點數(shù)量大于等于8且HashMap中的元素大于等于64的時候才會將鏈表轉(zhuǎn)化成紅黑樹，當節(jié)點數(shù)量小于等于6的時候紅黑樹退化成鏈表

5.1.1 put方法

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// 這就是那個擾動函數(shù) 作用：讓key的hash值的高16位也參與路由運算(在hash表數(shù)組長度還不是很大的情況下，讓hash值的高16位也參與進來)
// key如果是null則就放到 數(shù)組的0位置
// h      = 0010 1100 1010 0011 1000 0101 1101 1100
// ^
// h>>>16 = 0000 0000 0000 0000 0010 1100 1010 0011
//        = 0010 1100 1010 0011 1010 1001 0111 1111       
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// tab: 引用當前哈希表的數(shù)組// p: 當前哈希表的元素// n: 哈希表數(shù)組的長度// i: 路由尋址的結(jié)果               Node<K,V>[] tab; Node<K,V> p; int n, i;// 如果當前hashmap的數(shù)組為null或數(shù)據(jù)為0， hashmap設(shè)計為第一次向其插入數(shù)據(jù)的時候會初始化(延遲初始化)if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 最簡單的情況，尋址找到的數(shù)組的位置正好是null，則直接把當前k v封裝成node放進去    if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else { // 存在和要插入元素相同hash值的元素// e: node臨時元素// k: 臨時的一個keyNode<K,V> e; K k;// 表示數(shù)組中的元素與當前要插入的元素 完全一致，表示后續(xù)需要進行替換操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// P元素已經(jīng)樹化了else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 還是鏈表結(jié)構(gòu)，且鏈表的頭元素和要插入的元素的key不一致for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) { // 當前元素是最后一個元素，// 則將新節(jié)點放到p的后面p.next = newNode(hash, key, value, null);// 判斷后的元素是否達到  TREEIFY_THRESHOLD(8)if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); // 樹化操作break;}// 在鏈表中找到一個key和當前要插入元素的key一致的元素if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // 找到了要替換的數(shù)據(jù)， 判斷onlyIfAbsent后進行替換數(shù)據(jù)操作V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

5.1.2 resize方法

// 為什么需要擴容：為了解決哈希沖突導致的鏈化影響查詢效率的問題，通過擴容來緩解
final Node<K,V>[] resize() {// oldTab:擴容前的哈希表Node<K,V>[] oldTab = table;// oldCap:擴容之前的table數(shù)組的長度int oldCap = (oldTab == null) ? 0 : oldTab.length;// oldThr:擴容之前的擴容閾值，觸發(fā)本次擴容的閾值int oldThr = threshold;// newCap:擴容之后哈希數(shù)組的大小// newThr:擴容之后，下次再次觸發(fā)擴容的條件int newCap, newThr = 0;// 下面if  else 就是計算本次擴容之后 數(shù)組的大小newCap, 以及下次再次觸發(fā)擴容的大小newThr      if (oldCap > 0) {// 哈希表已經(jīng)初始化過了，這是一次正常擴容if (oldCap >= MAXIMUM_CAPACITY) { // 擴容之前的哈希數(shù)組大小已經(jīng)達到最大閾值了，則不擴容，且設(shè)置擴容條件為threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 容量翻倍newThr = oldThr << 1; }else if (oldThr > 0) // 哈希表還是null，如下情況：1.new HashMap(initCapacity, loadFatory) 2.new HashMap(initCapacity) 3.new HashMap(map)newCap = oldThr;else {// 哈希表還是null，且 只有 new HashMap()時newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//newThr為0時，通過newCap和loadFactory計算出一個newThrif (newThr == 0) { float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 創(chuàng)建一個更大的數(shù)組table = newTab;if (oldTab != null) { // 說明擴容之前，哈希里面已經(jīng)有數(shù)據(jù)了for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) { // 當前哈希數(shù)組位置有數(shù)據(jù)oldTab[j] = null; // 置空，方便JVM回收內(nèi)存if (e.next == null) // 當前元素沒有和任何數(shù)據(jù)發(fā)生碰撞， 最簡單情況newTab[e.hash & (newCap - 1)] = e; // 新計算哈希表的索引將值放進去就行else if (e instanceof TreeNode) // 當前節(jié)點已樹化((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 鏈表情況// 低位鏈表：存放在擴容之后的數(shù)組的下標位置，與當前數(shù)組的下標位置一致Node<K,V> loHead = null, loTail = null;// 高位鏈表：存放在擴容之后的數(shù)組的下標位置為當前數(shù)組的下標位置 + 擴容之前數(shù)組的長度Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// hash -> ... 0 1111// oldCap->000 1 0000//       ->000 0 0000   這樣就巧妙的分出 loHead和hiHead了if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) { // 低位鏈表有數(shù)據(jù), 處理鏈表指向loTail.next = null;newTab[j] = loHead;}if (hiTail != null) { // 高位鏈表有數(shù)據(jù), 處理鏈表指向hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

5.1.3 get方法

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {// tab:當前哈希表的數(shù)組// first:哈希表數(shù)組桶位的頭元素// e:臨時node元素// n:哈希表的數(shù)組的長度Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { // 哈希表不等于空，且要取的數(shù)據(jù)的key的哈希值在哈希表中存在if (first.hash == hash && // 哈希表數(shù)組中的頭元素就是需要查找的數(shù)據(jù)，則直接返回((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) { // 當前桶位不止一個元素，可能樹、可能鏈表if (first instanceof TreeNode) // 樹return ((TreeNode<K,V>)first).getTreeNode(hash, key);do { // 循環(huán)每個節(jié)點判斷是否相等，是則返回if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

5.1.4 remove方法

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {//tab:引用哈希表中的數(shù)組//p:當前Node元素//n:哈希表的長度//index:尋址結(jié)果Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) { // 哈希有數(shù)據(jù)，且路由到的數(shù)組索引也是有數(shù)據(jù)的，需要進行查找操作并且刪除// node:查找到的結(jié)果// e:當前node的下一個節(jié)點Node<K,V> node = null, e; K k; V v;if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 第一種情況 當前數(shù)組索引中的元素就是你要刪除的元素node = p;else if ((e = p.next) != null) { // 當前數(shù)組索引不是你要刪除的元素，且數(shù)組索引的頭節(jié)點后續(xù)還有節(jié)點，不是樹就是鏈表if (p instanceof TreeNode) // 第二種情況 是樹node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else { // 第三種情況 鏈表do {// 循環(huán)鏈表查詢if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode) // 樹 情況刪除節(jié)點((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p) // 數(shù)組頭節(jié)點是要刪除的元素tab[index] = node.next;else // 鏈表元素刪除 node是p.nextp.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}public boolean remove(Object key, Object value) {return removeNode(hash(key), key, value, true, true) != null;
}

5.1.5?replace方法

// key和oldValue都相同 替換value
public boolean replace(K key, V oldValue, V newValue) {Node<K,V> e; V v;if ((e = getNode(hash(key), key)) != null &&((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {e.value = newValue;afterNodeAccess(e);return true;}return false;
}// key相同，替換value
public V replace(K key, V value) {Node<K,V> e;if ((e = getNode(hash(key), key)) != null) {V oldValue = e.value;e.value = value;afterNodeAccess(e);return oldValue;}return null;
}

5.2 TreeMap

TreeMap繼承AbstractMap實現(xiàn)NavigableMap接口，底層是紅黑樹結(jié)構(gòu)

可以傳一個自定義排序器，對元素進行排序，元素的key不能為null

5.3 LinkedHashMap

LinkedHashMap繼承HashMap實現(xiàn)Map接口，底層使用哈希表與雙向鏈表來保存所有元素，哈希表使用的是HashMap，雙向鏈表實現(xiàn)是LinkedHashMap重新定義了哈希表的數(shù)組中保存元素的Entry，它除了保存當前對象的引用外，還保存了其上一個元素-before和下一個元素-after的引用，從而在哈希標的基礎(chǔ)上又構(gòu)建了雙向鏈表。

• put方法

當用戶調(diào)用put方法時，實際時調(diào)用HashMap的put方法，LinkedHashMap沒有重寫put方法，但是重寫了put方法中的newNode方法，此方法會生成一個LinkedHashMap的Entry并構(gòu)建好鏈表結(jié)構(gòu)后返回

• remove方法

當用戶調(diào)用remove方法，實際還是調(diào)用HashMap的remove方法，在remove方法最后，會調(diào)用afterNodeRemove方法，此方法LinkedHashMap進行了重寫，在這個方法里，LinkedHashMap重新維護的雙向鏈表結(jié)構(gòu)

LinkedHashMap支持insert排序和訪問排序，默認insert排序。

支持key和value都為null

5.4 ConcurrentHashMap(線程安全)

ConcurrentHashMap繼承AbstractMap實現(xiàn)ConcurrentMap接口，jdk1.8采用了更細粒度的鎖，采用Node+Synchronized+CAS算法實現(xiàn)，降低了鎖粒度，并發(fā)性能更好，并且結(jié)構(gòu)上與HashMap更加一致

key和value都不允許為null，

• size方法：

size方法并不簡單返回一個計數(shù)器的值，每次調(diào)用它，它都會調(diào)用sumCount()方法進行計算，baseCount+countCells數(shù)組存儲的值，baseCount會在每次修改Map影響個數(shù)的時候修改，如果CAS的方式修改失敗，修改數(shù)放入countCells。

5.5 ConcurrentSkipListMap(線程安全)

ConcurrentSkipListMap繼承AbstractMap實現(xiàn)了ConcurrentNavigableMap接口，底層是一個跳表的并發(fā)Map集合，沒有使用哈希表。

其元素可以通過自定義排序器進行排序，不允許key和value的值為null

原理：

• 底層結(jié)構(gòu)：HeadIndex、Index、Node

Node：key value和指向下一個Node節(jié)點的next，單向鏈表

Index：SkipList的索引節(jié)點。內(nèi)部2個指針，down：指向下一層，right：指向右邊的index，還有一個代表當前節(jié)點的node

HeadIndex：index的子類，多了一個level屬性，只在頭部使用