下面這些類圖是通過IDEA生成的邻奠，將一些無用的線刪掉了（比如：LinkedList繼承了AbstractList，并且實現(xiàn)List，其實不用聲明實現(xiàn)List接口罗洗，因為這里AbstractList就是List的實現(xiàn)。這種做法不明白其意思钢猛，網(wǎng)上搜索的答案是因為手誤伙菜，但是也不影響程序，所以就一直保留了命迈。贩绕。）
綠色實線：接口繼承
藍色實現(xiàn)：類繼承
綠色虛線：接口實現(xiàn)
下面是集合的類圖火的，這里只畫出了比較常用的類，并不是java中的全部集合類淑倾，大致可以分為三種類型：List卫玖、Set和 Queue，后面會對每種類型的集合進行詳細解讀踊淳，這里只簡單提一下這三種類型的區(qū)別假瞬。
List：作為
有序可重復(fù)集合的容器，實現(xiàn)方式有數(shù)組（ArrayList）和鏈表（LinkedList）等迂尝。
Set：不能包含重復(fù)元素脱茉，并且元素是無序的，當(dāng)然這里的無序指的是天然無序垄开，并不是沒有辦法讓它有順序琴许，如果不考慮元素的順序，只是判斷元素是否存在于集合中溉躲，使用這種數(shù)據(jù)結(jié)構(gòu)更高效榜田。
Queue：隊列是一種FIFO的數(shù)據(jù)結(jié)構(gòu)，也有雙端隊列锻梳，常用的場景是阻塞隊列實現(xiàn)生產(chǎn)者和消費者箭券。
Collection.png
List
List.png
- ArrayList
底層是用Object類型的數(shù)組（考慮一下為什么不是泛型數(shù)組，為什么沒有泛型數(shù)組）存儲疑枯，適用于索引查找元素辩块，但是對于添加和刪除元素效率較低，這是底層數(shù)組結(jié)構(gòu)決定的荆永，刪除和添加元素需要移動受影響的元素废亭。既然ArrayList是動態(tài)數(shù)組，那么它是如何實現(xiàn)擴容的具钥，請看下面的源代碼
public void add(int index, E element) {
rangeCheckForAdd(index);
//檢查容量
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個空數(shù)組
//初始化數(shù)組大小最小是DEFAULT_CAPACITY
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//修改計數(shù)器豆村，用于迭代器的快速失敗檢查
modCount++;
// overflow-conscious code
//如果容量不夠，進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量是原來容量加1/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新容量比需要的最小容量小骂删，就是用需要的容量作為新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于最大容量（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）
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);
}
//這個方法除了檢查minCapacity是不是負數(shù)之外掌动，后面返回值不知道意義何在，
//如果真是newCapacity - MAX_ARRAY_SIZE>0桃漾，但是MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8坏匪，
//也就是說數(shù)組最大是Integer.MAX_VALUE，為什么不直接將MAX_ARRAY_SIZE 設(shè)置為Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError()撬统；
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//將要添加元素位置以后的所有元素向后移動一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//將要刪除的元素的后面的元素向前移動一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
總結(jié)：
- newCapacity = oldCapacity + oldCapacity / 2 适滓，具體還要根據(jù)minCapacity以及數(shù)組當(dāng)前狀態(tài)確定。
- ArrayList 的最大容量是Integer.MAX_VALUE
- 插入和刪除時需要移動元素
- LinkedList
鏈表存儲恋追，并且實現(xiàn)了雙端隊列接口凭迹，適用于插入和刪除罚屋，但是不適用于通過索引獲取元素，即便是支持的嗅绸，效率很低脾猛。我們看一下插入和刪除操作的源碼
public void add(int index, E element) {
//插入位置檢查： 0<=index<=size
checkPositionIndex(index);
//插入鏈表末尾
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkLast(E e) {
//插入之前末尾節(jié)點
final Node<E> l = last;
//設(shè)置插入節(jié)點的前驅(qū)節(jié)點是之前的末尾節(jié)點，后驅(qū)節(jié)點為空
final Node<E> newNode = new Node<>(l, e, null);
//插入節(jié)點作為新的末尾節(jié)點
last = newNode;
//如果之前的末尾節(jié)點為空鱼鸠，也就是鏈表為空猛拴，新節(jié)點應(yīng)該作為首節(jié)點，
//否則設(shè)置新節(jié)點是之前末尾節(jié)點的后驅(qū)節(jié)點
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//根據(jù)元素的索引查找元素
Node<E> node(int index) {
// assert isElementIndex(index);
//如果索引大于1/2 size蚀狰，從首節(jié)點遍歷愉昆，否則從末節(jié)點遍歷
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
總結(jié)：
1.獲取元素是通過遍歷元素，所以效率不高麻蹋，O(n)
2.向指定的位置添加和刪除元素跛溉，也會涉及到通過索引定位元素，然后修改節(jié)點關(guān)系扮授，也就是LinkedList的插入和刪除效率不一定比ArrayList高芳室，當(dāng)數(shù)據(jù)量比較大哟绊，索引靠近中間位置（遍歷查找元素耗時最多）的時候挂签，ArrayList要比LinkedList的效率高。（可以用20w個元素猖辫，index設(shè)置為10w測試）深夯。但是如果只是在末尾插入元素呢抖格，這個要根據(jù)數(shù)據(jù)量來說，具體可以看一下這篇文章：https://blog.csdn.net/qq_34144916/article/details/81154528
- List總結(jié)
- 在插入或者刪除場景推薦使用 LinkedList
- 在索引查找場景推薦使用 ArrayList
上面的兩點不是絕對的咕晋，要具體根據(jù)元素數(shù)量來說，在元素數(shù)量比較小時適用收奔。
Vector和ArrayList的相同點和不同點
- 相同點：
- 繼承自
AbstractList - 底層使用Object數(shù)組實現(xiàn)
- 實現(xiàn)了RandomAccess掌呜，支持隨機訪問
- 能容納的最大元素數(shù)量相同
- 不同點
- Vector的所有公開方法都是
synchronized的 - 擴容大小不同
//Vector
//capacityIncrement 可以通過構(gòu)造函數(shù)傳入，默認是0
newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity)
//ArrayList
newCapacity = oldCapacity + (oldCapacity >> 1);
雙端隊列以及使用場景
在上面的類圖中我們看到 ArrayDeque 和 LinkedList 都實現(xiàn) Deque 接口坪哄，ArrayDeque 是循環(huán)隊列质蕉，可以使用在隊列和棧場景，雙端隊列主要適用于工作秘場景翩肌，比如爬蟲任務(wù)模暗。在隊列模塊會進行詳細解讀∧罴溃可以參考這篇文章：
https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/4-Stack%20and%20Queue.md
到此List相關(guān)類詳細完畢兑宇，下一節(jié)我們學(xué)習(xí)Set。
Set
Set.png
這里我們著重介紹
HashSet 粱坤、LinkedHashSet和TreeSet
- HashSet
HashSet底層是使用HashMap存儲隶糕，HashMap我們會在后面的章節(jié)介紹到瓷产，那么將HashSet中的元素如何存儲到HashMap中的，HashMap中的鍵是什么枚驻？值是什么濒旦？請看下面的代碼
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
//鍵是元素，值是一個固定的Object再登，而且是靜態(tài)的尔邓，
//也就是所有 `HashSet` 在 `HashMap`中的值是一樣的
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
這里需要注意一點，既然 HashSet 中的元素是作為 HashMap 的鍵锉矢，那么為了保證 HashSet 中元素不能重復(fù)梯嗽，就要重寫元素的 equals 和 hashCode 方法。至于這兩個方法的關(guān)系我們在 Map 章節(jié)介紹
實現(xiàn)很簡單吧沈撞，下面我們再說一下 HashSet 的子類 LinkedHashSet
LinkedHashSet
LinkedHashSet使用LinkedHashMap實現(xiàn)的慷荔，LinkedHashMap是一個比較有意思的Map，Map章節(jié)介紹缠俺，這里知道LinkedHashSet保證元素的遍歷順序和插入順序是相同的就行显晶，其他和HashSet沒有什么區(qū)別，這也是為什么前面我們說Set只是天然無序的壹士，并不是不能做到有序磷雇。TreeSet
TreeSet是使用TreeMap實現(xiàn)
所有要想深入了解Set，必須學(xué)習(xí)對應(yīng)的Map躏救。Set總結(jié)
- Set 使用 Map 實現(xiàn)
- HashSet 是無序的
- LinkedHashSet 是有序的唯笙，順序是元素插入的順序
- TreeSet 可以對元素排序
- 它們都是線程不安全的
Set學(xué)習(xí)至此完畢，下一節(jié)學(xué)習(xí)Queue盒使。
Queue
Queue.png
- 隊列分類
| 阻塞單端隊列 | 非阻塞單端隊列 | 阻塞雙端隊列 | 非阻塞雙端隊列 |
|---|---|---|---|
| BlockingQueue | Queue | BlockingDeque | Deque |
| ArrayBlockingQueue LinkedBlockingQueue SynchronousQueue PriorityBlockingQueue |
PriorityQueue | LinkedBlockingDeque | ArrayDeque/LinkedList |
- 使用場景
在生產(chǎn)者-消費者設(shè)計中崩掘，所有消費者有一個共享的工作隊列，而在工作密取設(shè)計中少办，每個消費者都有各自的雙端隊列苞慢。如果一個消費者完成了自己雙端隊列中的全部工作，那么它可以從其它消費者雙端隊列末尾秘密地獲取工作英妓。
密取工作模式比傳統(tǒng)的生產(chǎn)者-消費者模式具有更高的可伸縮性挽放，這是因為工作者線程不會在單個共享的任務(wù)隊列上發(fā)生競爭。在大多數(shù)時候蔓纠，它們都只是訪問自己的雙端隊列辑畦，從而極大地減少了競爭。當(dāng)工作者線程需要訪問另一個隊列時腿倚，它會從隊列的尾部而不是頭部獲取工作纯出，因此進一步降低了隊列上的競爭程度。
工作密取非常適用于即是消費者也是生產(chǎn)真問題--當(dāng)執(zhí)行某個工作時可能導(dǎo)致出現(xiàn)更多的工作。例如潦刃，在網(wǎng)頁爬蟲程序中處理一個頁面時侮措，通常會發(fā)現(xiàn)有更多的頁面需要處理。類似的還有許多搜索圖的算法乖杠，例如在垃圾回收階段對堆進行標(biāo)記分扎，都可以通過工作密取機制來實現(xiàn)高效并行。當(dāng)一個工作線程找到新的任務(wù)單元時胧洒，它會將其放到自己隊列的末尾（或者在工作共享模式中畏吓，放入其它工作者線程的隊列中）。當(dāng)雙端隊列為空時卫漫，它會在另一個線程的隊列末尾查找新的任務(wù)菲饼，從而確保每個線程都保持忙碌狀態(tài)。
首先我們簡單陳述一下列赎，各種類型隊列的定義：
image.png
關(guān)注一下對于相同操作宏悦，不同方法的操作結(jié)果
| Throws exception | Special value | Blocks | Times out | |
|---|---|---|---|---|
| Insert | add(e) | offer(e) | put(e) | offer(e, time, unit) |
| Remove | remove() | poll() | take() | poll(time, unit) |
| Examine | element() | peek() | not applicable | not applicable |
- ArrayDeque
無界循環(huán)雙端隊列
在閱讀代碼之前，首先應(yīng)該明白一個公式：
a % b == a & (b - 1)包吝，前提是b是2^n饼煞，并且a>0，具體證明可以參考這里：
https://www.codercto.com/a/30894.html
// 第一個元素的索引
private transient int head;
// 下個要添加元素的位置诗越，為末尾元素的索引 + 1
private transient int tail;
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
/*當(dāng)head-1 = -1 時砖瞧，取余得到的是(elements.length - 1)，從而實現(xiàn)了循環(huán)嚷狞，
這也說明了tail為什么不是最后一個元素的位置块促，而是最后一個需要插入元素的位置，如果是最后一個
元素的位置的話床未，當(dāng)：head=0竭翠，tail=elements.length-1 時，就沒有位置從首部插入新的元素*/
elements[head = (head - 1) & (elements.length - 1)] = e;
/*如果head==tail 時進行擴容薇搁，請注意這里的tail是下一個可插入元素的位置逃片，也就是這時候數(shù)組中其實
還有一個空位的*/
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
//這里直接在尾部插入了元素，就是因為tail是下一個可插入元素的位置
elements[tail] = e;
/*更新tail只酥，如果需要擴容
取模，保證數(shù)據(jù)不越界*/
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
/**
* Allocates empty array to hold the given number of elements.
*獲取大于numElements的最小2^n
* @param numElements the number of elements to hold
*/
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
//如果numElements本來就是2^n呀狼，則結(jié)果翻倍裂允，如果想返回原始值，則在計算之前-1
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);//使 n 的前2位為1
initialCapacity |= (initialCapacity >>> 2);//使 n 的前4位為1
initialCapacity |= (initialCapacity >>> 4);//使 n 的前8位為1
initialCapacity |= (initialCapacity >>> 8);//使 n 的前16位為1
initialCapacity |= (initialCapacity >>> 16);//使 n 的前32位為1
initialCapacity++;
//如果大于了最大整數(shù)哥艇，上面的++會導(dǎo)致溢出绝编，結(jié)果變?yōu)樨摂?shù)
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = new Object[initialCapacity];
}
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
那么可以回答下面的問題了
- 如何做到循環(huán)隊列？
通過控制數(shù)組元素個數(shù)為2^n，通過 & 實現(xiàn)循環(huán) - 怎么判斷需要擴容
當(dāng) head==tail 時十饥，說明數(shù)組中只剩tail位置可以插入窟勃，這是進行兩倍的擴容 - 如何做到無界隊列
數(shù)組拷貝擴容
通過上面源碼的學(xué)習(xí)，我們應(yīng)該收獲到
- 實現(xiàn)有界循環(huán)：a & (b-1)
- 計算一個數(shù)的最小2的次冪
- LinkedList
在List章節(jié)已經(jīng)詳細介紹過
關(guān)于上面這兩個雙端隊列性能的比較可以看一下這篇文章：
https://www.zhihu.com/question/33030727
- PriorityQueue
優(yōu)先級隊列逗堵，因為需要排序秉氧，有兩種方式實現(xiàn)排序，要么元素實現(xiàn)Comparable接口蜒秤，要么在給隊列的構(gòu)造函數(shù)提供比較器：Comparator
在學(xué)習(xí)之前我們復(fù)習(xí)一下我們曾經(jīng)學(xué)習(xí)的堆
堆：
- 近似完全二叉樹結(jié)構(gòu)
- 如果用數(shù)組實現(xiàn)堆汁咏，每個節(jié)點的索引滿足下面的公式：
節(jié)點索引是k,那么左右子節(jié)點的索引分別是:2i+1和2i+2 - 有序堆：大頂堆（升序）、小頂堆（降序）作媚，
滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆攘滩，滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆
下面代碼是用小頂堆排序
public static void sort(int[] array) {
//構(gòu)建小頂堆，從最后一個非葉子節(jié)點調(diào)整纸泡，直到堆頂
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, array.length, i);
}
//排序
for (int i = array.length - 1; i >= 0; i--) {
//將頂部元素和最后一個在數(shù)組中（這里請注意漂问，是數(shù)組中）未排序的元素交換
swap(array, 0, i);
//交換以后，調(diào)整由交換引起的可能不滿足小頂堆性質(zhì)的節(jié)點
adjustHeap(array, i, 0);
}
}
private static void adjustHeap(int[] array, int length, int i) {
int temp = array[i];
//從i節(jié)點的左子節(jié)點開始
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
//如果右子節(jié)點比左子節(jié)點的值還小女揭，就用右子節(jié)點與父節(jié)點比較
if (k + 1 < length && array[k] > array[k + 1]) {
//右子節(jié)點
k = k + 1;
}
//如果子節(jié)點的值比父節(jié)點小蚤假，交換
if (temp > array[k]) {
swap(array, i, k);
//交換以后，確保父節(jié)點沉下去以后還是滿足小頂堆性質(zhì)
i=k;
} else {
break;
}
}
}
private static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
好了田绑，如果明白了小頂堆排序勤哗，那么學(xué)習(xí) PriorityQueue 源代碼就簡單多了，它的實現(xiàn)就是：數(shù)組+小頂堆
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
//自動擴容掩驱，grow方法和ArrayList中的grow類似芒划，這里不做過多解釋
if (i >= queue.length)
grow(i + 1);
//更新元素總數(shù)
size = i + 1;
//如果是第一個插入到隊列中的元素，直接放到數(shù)組的0位
if (i == 0)
queue[0] = e;
else
//將i作為子節(jié)點欧穴，調(diào)整它以及它的祖先節(jié)點
siftUp(i, e);
return true;
}
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
//如果要移除的是最后一個元素民逼，直接移除，不用調(diào)整堆
if (s == i) // removed last element
queue[i] = null;
else {
//堆中最后一個元素涮帘，也是最大的元素
E moved = (E) queue[s];
queue[s] = null;
//將最大的元素移動到要移除的元素的位置拼苍，并向下調(diào)整堆
//這里寫的不太好，既然已經(jīng)是小頂堆了调缨，最有可能出現(xiàn)在要刪除位置的元素應(yīng)該是它的子節(jié)點
//這里的moved應(yīng)該用要刪除元素的子節(jié)點感覺更合適一點疮鲫，也有另外一個原因是，不管移動那個
//節(jié)點弦叶，要刪除的元素的所有子節(jié)點都要移動一下
siftDown(i, moved);
//如果沒有向下調(diào)整俊犯，也就是說它比它的子節(jié)點都小，那就要判斷一下是否有向上調(diào)整的必要
//如果queue[i] 伤哺！= moved 說明向下調(diào)整了燕侠，也就是說有子節(jié)點還比它小者祖，所以沒有必要再向上調(diào)整
//了绢彤，因為本來就是有序堆。
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
//向下調(diào)整堆茫舶，也就是將k作為父節(jié)點
private void siftDown(int k, E x) {
//下面的兩個方法的算法是一樣的械巡，只不過比較方式不一樣
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
//還記得父節(jié)點的子節(jié)點的索引關(guān)系嗎？2K+1/2K+2奇适，也就是最大的非葉子節(jié)點的索引應(yīng)該是
//(size-2)/2=size/2-1坟比，所以這里的half可以理解為第一個葉子節(jié)點的索引
int half = size >>> 1; // loop while a non-leaf
//如果是非葉子節(jié)點
while (k < half) {
//左節(jié)點：child=2k+1
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
//右節(jié)點
int right = child + 1;
//如果右節(jié)點比左節(jié)點小，就用右節(jié)點的父節(jié)點比較
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
//繼續(xù)調(diào)整交換以后的子節(jié)點
k = child;
}
queue[k] = key;
}
//類似于：siftDownComparable
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
//向上調(diào)整嚷往，k作為子節(jié)點
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
private void siftUpUsingComparator(int k, E x) {
//直到對頂元素
while (k > 0) {
//parent = (k-1)/2
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//如果比它的父節(jié)點大葛账，就結(jié)束
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
//初始化堆，從第一個非葉子節(jié)點開始（length/2-1）
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
學(xué)習(xí)完源代碼是不是覺得沒有想象中的那么難皮仁？呵呵
使用場景：
那么這個隊列的使用場景是什么籍琳，既然它是優(yōu)先級隊列，那直接想到的就是處理優(yōu)先級高的數(shù)據(jù)贷祈，比如一個電商網(wǎng)站搞特賣或搶購趋急，用戶登錄下單提交后，考慮這個時間段用戶訪問下單提交量很大势誊，通常表單提交到服務(wù)器后端后呜达，后端程序一般不直接進行扣庫存處理，將請求放到隊列粟耻，異步消費處理查近，用普通隊列是FIFO的，這里有個需求是挤忙，用戶會員級別高的霜威，可以優(yōu)先搶購到商品，可能這個時間段的級別較高的會員用戶下單時間在普通用戶之后册烈，這個時候使用優(yōu)先隊列代替普通隊列戈泼，基本能滿足我們的需求。
后面我們學(xué)習(xí)一下阻塞隊列赏僧，一般使用阻塞隊列使用的比較多，因為大多數(shù)涉及到隊列的場景都有高并發(fā)淀零。
突然發(fā)現(xiàn)除了LinkedList其他隊列都不允許元素為空，我想這可能是因為像poll這樣的方法如果沒有獲取到元素會返回null，但是如果允許元素有null，那么就有歧義了巨坊。
- 阻塞隊列是通過
ReentrantLock來保證線程安全的此改，有兩個Condition，分別是：notEmpty占调，notFull - 阻塞隊列新增了幾個中重要的方法：阻塞方法
take/put和超時等待的off /poll
- ArrayBlockingQueue
有界隊列
如果讀懂之前介紹的隊列源代碼究珊，這里的源代碼就很簡單了
int count;
final Object[] items;
//阻塞獲取元素索引
int takeIndex;
//阻塞添加元素索引
int putIndex;
final ReentrantLock lock;
//有數(shù)據(jù)條件
private final Condition notEmpty;
//有空間條件
private final Condition notFull;
//入隊列
private void enqueue(E x) {
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
items[putIndex] = x;
//從頭開始添加纵苛，可以想象成putIndex和takeIndex剛開始都為0攻人，然后takeIndex跟在putIndex后面
//在數(shù)據(jù)中循環(huán)移動
if (++putIndex == items.length)
putIndex = 0;
count++;
notEmpty.signal();
}
//出隊列
private E dequeue() {
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
E x = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();
return x;
}
- LinkedBlockingQueue
可以是有界，也可以是無界
類似于ArrayBlockingQueue瞬浓，不同的是底層使用鏈表蓬坡，并且lock的粒度不同渣窜，新增了takeLock和putLock，計數(shù)使用AtomicInteger
private final AtomicInteger count = new AtomicInteger();
transient Node<E> head;
private transient Node<E> last;
private final ReentrantLock takeLock = new ReentrantLock();
private final Condition notEmpty = takeLock.newCondition();
private final ReentrantLock putLock = new ReentrantLock();
private final Condition notFull = putLock.newCondition();
private void enqueue(Node<E> node) {
// assert putLock.isHeldByCurrentThread();
// assert last.next == null;
last = last.next = node;
}
private E dequeue() {
//這里要明白的是head節(jié)點是個空節(jié)點位迂，移除的是空節(jié)點的next
Node<E> h = head;
Node<E> first = h.next;
h.next = h; // help GC
head = first;
E x = first.item;
first.item = null;
return x;
}
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
// Note: convention in all put/take/etc is to preset local var
// holding count negative to indicate failure unless set.
int c = -1;
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
final AtomicInteger count = this.count;
putLock.lockInterruptibly();
try {
while (count.get() == capacity) {
notFull.await();
}
enqueue(node);
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
}
public E take() throws InterruptedException {
E x;
int c = -1;
final AtomicInteger count = this.count;
final ReentrantLock takeLock = this.takeLock;
takeLock.lockInterruptibly();
try {
while (count.get() == 0) {
notEmpty.await();
}
x = dequeue();
c = count.getAndDecrement();
if (c > 1)
notEmpty.signal();
} finally {
takeLock.unlock();
}
//c是上一次元素數(shù)量掂林，如果上一次容量滿了坝橡，現(xiàn)在移除了一個元素，那么應(yīng)該通知當(dāng)前
//容量非滿锣杂，剛開始看著說有可能發(fā)生多線程掛死，后面才看到signalNotFull方法中又用了
//putLock赖阻，所以不用擔(dān)心
if (c == capacity)
signalNotFull();
return x;
}
private void signalNotFull() {
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
notFull.signal();
} finally {
putLock.unlock();
}
}
private void signalNotEmpty() {
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
notEmpty.signal();
} finally {
takeLock.unlock();
}
}
通過上面的代碼可以看到踱蠢，LinkedBlockingQueue 使用了兩個鎖茎截，在容量滿了或者為空時，用對方的鎖去signal企锌。
所以LinkedBlockingQueue在多線程上實現(xiàn)生產(chǎn)者和消費者應(yīng)該要比ArrayBlockingQueue效率高。
- LinkedBlockingDeque
LinkedBlockingDeque實現(xiàn)上和ArrayBlockingQueue類似哀军，只不過底層使用的是鏈表杉适，并且是雙端隊列柳击。詳細代碼就不用貼了。
通過上面的隊列學(xué)習(xí)蹬叭，我們應(yīng)該知道：
- 循環(huán)雙端隊列 ArrayDeque 是如何實現(xiàn)的状知？
- 阻塞隊列是如何實現(xiàn)的以及
ArrayBlockingQueue和LinkedBlockingQueue有什么區(qū)別？ - 優(yōu)先級隊列的數(shù)據(jù)結(jié)構(gòu)
至此坦喘，Collection的實現(xiàn)類學(xué)習(xí)完畢西设，如果這時候你對Collection類圖了然于胸，并且每個實現(xiàn)類的使用場景以及優(yōu)缺點都整明白了棠笑，那么恭喜你蓖救，對于集合部分的大部分知識你能應(yīng)對了。
下面我們會學(xué)習(xí)常用的映射表藻糖， 它的實現(xiàn)中有很多巧妙的算法，很有意思。
參考文檔：
https://blog.csdn.net/u013309870/article/details/71478120
https://blog.csdn.net/l540675759/article/details/62893335
Map
- equals 和 hashCode
- put 的操作過程
- 如何解決Hash沖突
- HashTable 和 ConcurrentHashMap 在實現(xiàn)高并發(fā)時有什么區(qū)別
Map.png
視圖
迭代器
- fail-fast 和 fail-safe
- Iterator和ListIterator的區(qū)別
- Iterator 和 Enumeration的區(qū)別
并發(fā)集合
建議
LinkedList和ArrayList 的使用場景和區(qū)別洋满？
Iterator 和 ListIterator 的區(qū)別牺勾？
訪問元素的方式阵漏？
列表和集的使用場景？
列表是有序的回还，但是對于不關(guān)心元素順序的場景叹洲，使用集更高效，因為查找相當(dāng)于索引訪問數(shù)組（當(dāng)然這里也要考慮哈希沖突導(dǎo)致的列表查找）隊列類似功能方法區(qū)別蝗柔？
優(yōu)先級隊列的實現(xiàn)
更新一個映射值有那些方式
常見的映射表
視圖
http://www.reibang.com/p/939b8a672070
http://www.reibang.com/p/a53b94b2bcca
https://mp.weixin.qq.com/s?__biz=MzI3NzE0NjcwMg==&mid=2650120877&idx=1&sn=401bb7094d41918f1a6e142b6c66aaac&chksm=f36bbf8cc41c369aa44c319942b06ca0f119758b22e410e8f705ba56b9ac6d4042fe686dbed4&mpshare=1&scene=1&srcid=1010L0NNyoRB5lVoryo00awY#rd
http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
