1.總覽

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

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

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

2.List

2.1 ArrayList

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

可以有多個(gè)null，初始大小為10，每次擴(kuò)容為原容量的1.5倍，

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

2.2 LinkedList

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

可以有多個(gè)null，初始化沒(méi)有沒(méi)有初始任何存儲(chǔ)，當(dāng)有元素進(jìn)來(lái)時(shí)，默認(rèn)從last節(jié)點(diǎn)插入，構(gòu)造鏈表

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

2.3 Vector(線程安全)

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

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

2.4 Stack(線程安全)

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

2.5 CopyOnWriteArrayList(線程安全)

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

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

set(index, e) 過(guò)程：

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

add(e)過(guò)程：

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

3.Set

3.1 HashSet

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

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

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

注意：因?yàn)椴皇蔷€程安全的，調(diào)用size方法，返回的size可能會(huì)和真實(shí)元素個(gè)數(shù)不一致

3.2 LinkedHashSet

LinkedHashSet繼承HashSet，它的代碼很少，因?yàn)樗柚鶫ashSet的LinkedHashMap為底層實(shí)現(xiàn)，完成插入順序的HashSet

其余都和HashSet一致

3.3 TreeSet

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

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

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

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

3.4 CopyOnWriteArraySet(線程安全)

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

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

3.5 ConcurrentSkipListSet(線程安全)

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

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

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

4.Queue

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

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

4.1ArrayDeque

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

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

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

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

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

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

4.2 PriorityQueue

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

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

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

重要方法邏輯：

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

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

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

4.3 DelayQueue(線程安全)

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

4.3.1 Thread lead 成員變量的用處

leader來(lái)減少不必要的等待時(shí)間,那么這里我們的DelayQueue是怎么利用leader來(lái)做到這一點(diǎn)的呢:

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

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

如果為空說(shuō)明沒(méi)有其他線程去取這個(gè)節(jié)點(diǎn),設(shè)置leader并等待delay延時(shí)到期,直到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)在延遲隊(duì)列里面有三個(gè)對(duì)象。

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

4.4 ConcurrentLinkedQueue(線程安全)

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

下面以offer方法的注釋來(lái)詳細(xì)說(shuō)明下ConcurrentLinkedQueue

public boolean offer(E e) {// 檢查e是不是null，是的話拋出NullPointerException異常。checkNotNull(e);// 創(chuàng)建新的節(jié)點(diǎn)final Node<E> newNode = new Node<E>(e);// 將“新的節(jié)點(diǎn)”添加到鏈表的末尾。for (Node<E> t = tail, p = t;;) {Node<E> q = p.next;// 情況1：q為空，p是尾節(jié)點(diǎn)插入if (q == null) {// CAS操作：如果“p的下一個(gè)節(jié)點(diǎn)為null”(即p為尾節(jié)點(diǎn))，則設(shè)置p的下一個(gè)節(jié)點(diǎn)為newNode。// 如果該CAS操作成功的話，則比較“p和t”(若p不等于t，則設(shè)置newNode為新的尾節(jié)點(diǎn))，然后返回true。// 如果該CAS操作失敗，這意味著“其它線程對(duì)尾節(jié)點(diǎn)進(jìn)行了修改”，則重新循環(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實(shí)現(xiàn)BlockQueue接口，底層是鏈表，使用ReentrantLock進(jìn)行并發(fā)安全控制。不允許添加null。

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

5.6 ArrayBlockingQueue(線程安全)

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

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

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

5.Map

5.1 HashMap

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

擴(kuò)容：HashMap初始容量是16，默認(rèn)負(fù)載因子是0.75，當(dāng)HashMap中的元素?cái)?shù)量大于 容量*負(fù)載因子則進(jìn)行容量*2的擴(kuò)容操作。

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

5.1.1 put方法

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// 這就是那個(gè)擾動(dòng)函數(shù) 作用：讓key的hash值的高16位也參與路由運(yùn)算(在hash表數(shù)組長(zhǎng)度還不是很大的情況下，讓hash值的高16位也參與進(jìn)來(lái))
// 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: 引用當(dāng)前哈希表的數(shù)組// p: 當(dāng)前哈希表的元素// n: 哈希表數(shù)組的長(zhǎng)度// i: 路由尋址的結(jié)果               Node<K,V>[] tab; Node<K,V> p; int n, i;// 如果當(dāng)前hashmap的數(shù)組為null或數(shù)據(jù)為0， hashmap設(shè)計(jì)為第一次向其插入數(shù)據(jù)的時(shí)候會(huì)初始化(延遲初始化)if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 最簡(jiǎn)單的情況，尋址找到的數(shù)組的位置正好是null，則直接把當(dāng)前k v封裝成node放進(jìn)去    if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else { // 存在和要插入元素相同hash值的元素// e: node臨時(shí)元素// k: 臨時(shí)的一個(gè)keyNode<K,V> e; K k;// 表示數(shù)組中的元素與當(dāng)前要插入的元素 完全一致，表示后續(xù)需要進(jìn)行替換操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// P元素已經(jīng)樹(shù)化了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) { // 當(dāng)前元素是最后一個(gè)元素，// 則將新節(jié)點(diǎn)放到p的后面p.next = newNode(hash, key, value, null);// 判斷后的元素是否達(dá)到  TREEIFY_THRESHOLD(8)if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); // 樹(shù)化操作break;}// 在鏈表中找到一個(gè)key和當(dāng)前要插入元素的key一致的元素if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // 找到了要替換的數(shù)據(jù)， 判斷onlyIfAbsent后進(jìn)行替換數(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方法

// 為什么需要擴(kuò)容：為了解決哈希沖突導(dǎo)致的鏈化影響查詢效率的問(wèn)題，通過(guò)擴(kuò)容來(lái)緩解
final Node<K,V>[] resize() {// oldTab:擴(kuò)容前的哈希表Node<K,V>[] oldTab = table;// oldCap:擴(kuò)容之前的table數(shù)組的長(zhǎng)度int oldCap = (oldTab == null) ? 0 : oldTab.length;// oldThr:擴(kuò)容之前的擴(kuò)容閾值，觸發(fā)本次擴(kuò)容的閾值int oldThr = threshold;// newCap:擴(kuò)容之后哈希數(shù)組的大小// newThr:擴(kuò)容之后，下次再次觸發(fā)擴(kuò)容的條件int newCap, newThr = 0;// 下面if  else 就是計(jì)算本次擴(kuò)容之后 數(shù)組的大小newCap, 以及下次再次觸發(fā)擴(kuò)容的大小newThr      if (oldCap > 0) {// 哈希表已經(jīng)初始化過(guò)了，這是一次正常擴(kuò)容if (oldCap >= MAXIMUM_CAPACITY) { // 擴(kuò)容之前的哈希數(shù)組大小已經(jīng)達(dá)到最大閾值了，則不擴(kuò)容，且設(shè)置擴(kuò)容條件為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()時(shí)newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//newThr為0時(shí)，通過(guò)newCap和loadFactory計(jì)算出一個(gè)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)建一個(gè)更大的數(shù)組table = newTab;if (oldTab != null) { // 說(shuō)明擴(kuò)容之前，哈希里面已經(jīng)有數(shù)據(jù)了for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) { // 當(dāng)前哈希數(shù)組位置有數(shù)據(jù)oldTab[j] = null; // 置空，方便JVM回收內(nèi)存if (e.next == null) // 當(dāng)前元素沒(méi)有和任何數(shù)據(jù)發(fā)生碰撞， 最簡(jiǎn)單情況newTab[e.hash & (newCap - 1)] = e; // 新計(jì)算哈希表的索引將值放進(jìn)去就行else if (e instanceof TreeNode) // 當(dāng)前節(jié)點(diǎn)已樹(shù)化((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 鏈表情況// 低位鏈表：存放在擴(kuò)容之后的數(shù)組的下標(biāo)位置，與當(dāng)前數(shù)組的下標(biāo)位置一致Node<K,V> loHead = null, loTail = null;// 高位鏈表：存放在擴(kuò)容之后的數(shù)組的下標(biāo)位置為當(dāng)前數(shù)組的下標(biāo)位置 + 擴(kuò)容之前數(shù)組的長(zhǎng)度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:當(dāng)前哈希表的數(shù)組// first:哈希表數(shù)組桶位的頭元素// e:臨時(shí)node元素// n:哈希表的數(shù)組的長(zhǎng)度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) { // 當(dāng)前桶位不止一個(gè)元素，可能樹(shù)、可能鏈表if (first instanceof TreeNode) // 樹(shù)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do { // 循環(huán)每個(gè)節(jié)點(diǎn)判斷是否相等，是則返回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:當(dāng)前Node元素//n:哈希表的長(zhǎng)度//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ù)的，需要進(jìn)行查找操作并且刪除// node:查找到的結(jié)果// e:當(dāng)前node的下一個(gè)節(jié)點(diǎn)Node<K,V> node = null, e; K k; V v;if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 第一種情況 當(dāng)前數(shù)組索引中的元素就是你要?jiǎng)h除的元素node = p;else if ((e = p.next) != null) { // 當(dāng)前數(shù)組索引不是你要?jiǎng)h除的元素，且數(shù)組索引的頭節(jié)點(diǎn)后續(xù)還有節(jié)點(diǎn)，不是樹(shù)就是鏈表if (p instanceof TreeNode) // 第二種情況 是樹(shù)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) // 樹(shù) 情況刪除節(jié)點(diǎn)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p) // 數(shù)組頭節(jié)點(diǎn)是要?jiǎng)h除的元素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實(shí)現(xiàn)NavigableMap接口，底層是紅黑樹(shù)結(jié)構(gòu)

可以傳一個(gè)自定義排序器，對(duì)元素進(jìn)行排序，元素的key不能為null

5.3 LinkedHashMap

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

• put方法

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

• remove方法

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

LinkedHashMap支持insert排序和訪問(wèn)排序，默認(rèn)insert排序。

支持key和value都為null

5.4 ConcurrentHashMap(線程安全)

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

key和value都不允許為null，

• size方法：

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

5.5 ConcurrentSkipListMap(線程安全)

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

其元素可以通過(guò)自定義排序器進(jìn)行排序，不允許key和value的值為null

原理：

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

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

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

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