圖解 Java 中的資料結構及原理！-有解無憂

作者：大道方圓
cnblogs.com/xdecode/p/9321848.html

最近在整理資料結構方面的知識, 系統化看了下Java中常用資料結構, 突發奇想用影片來繪制資料流轉程序，

主要基于jdk8, 可能會有些特性與jdk7之前不相同, 例如LinkedList LinkedHashMap中的雙向串列不再是回環的，

HashMap中的單鏈表是尾插, 而不是頭插入等等, 后文不再贅敘這些差異, 本文目錄結構如下：

LinkedList

經典的雙鏈表結構, 適用于亂序插入, 洗掉. 指定序列操作則性能不如ArrayList, 這也是其資料結構決定的.

add(E) / addLast(E)

add(index, E)

這邊有個小的優化, 他會先判斷index是靠近隊頭還是隊尾, 來確定從哪個方向遍歷鏈入.


1         if (index < (size >> 1)) {
2             Node<E> x = first;
3             for (int i = 0; i < index; i++)
4                 x = x.next;
5             return x;
6         } else {
7             Node<E> x = last;
8             for (int i = size - 1; i > index; i--)
9                 x = x.prev;
10             return x;
11         }

靠隊尾

get(index)

也是會先判斷index, 不過性能依然不好, 這也是為什么不推薦用for(int i = 0; i < lengh; i++)的方式遍歷linkedlist, 而是使用iterator的方式遍歷.

remove(E)

ArrayList

底層就是一個陣列, 因此按序查找快, 亂序插入, 洗掉因為涉及到后面元素移位所以性能慢.

add(index, E)

擴容

一般默認容量是10, 擴容后, 會length*1.5.

remove(E)

回圈遍歷陣列, 判斷E是否equals當前元素, 洗掉性能不如LinkedList.

Stack

經典的資料結構, 底層也是陣列, 繼承自Vector, 先進后出FILO, 默認new Stack()容量為10, 超出自動擴容.

push(E)

pop()

后綴運算式

Stack的一個典型應用就是計算運算式如 9 + (3 - 1) * 3 + 10 / 2, 計算機將中綴運算式轉為后綴運算式, 再對后綴運算式進行計算，推薦閱讀：Java 程式員必須掌握的 8 道資料結構面試題，你會幾道？

中綴轉后綴

數字直接輸出
堆疊為空時，遇到運算子，直接入堆疊
遇到左括號, 將其入堆疊
遇到右括號, 執行出堆疊操作，并將出堆疊的元素輸出，直到彈出堆疊的是左括號，左括號不輸出，
遇到運算子(加減乘除)：彈出所有優先級大于或者等于該運算子的堆疊頂元素，然后將該運算子入堆疊
最終將堆疊中的元素依次出堆疊，輸出，

計算后綴表達

遇到數字時，將數字壓入堆疊
遇到運算子時，彈出堆疊頂的兩個數，用運算子對它們做相應的計算, 并將結果入堆疊
重復上述程序直到運算式最右端
運算得出的值即為運算式的結果

佇列

與Stack的區別在于, Stack的洗掉與添加都在隊尾進行, 而Queue洗掉在隊頭, 添加在隊尾.

ArrayBlockingQueue

生產消費者中常用的阻塞有界佇列, FIFO.

put(E)

put(E) 佇列滿了

1         final ReentrantLock lock = this.lock;
2         lock.lockInterruptibly();
3         try {
4             while (count == items.length)
5                 notFull.await();
6             enqueue(e);
7         } finally {
8             lock.unlock();
9         }

take()

當元素被取出后, 并沒有對陣列后面的元素位移, 而是更新takeIndex來指向下一個元素.

takeIndex是一個環形的增長, 當移動到佇列尾部時, 會指向0, 再次回圈.

1     private E dequeue() {
2         // assert lock.getHoldCount() == 1;
3         // assert items\[takeIndex\] != null;
4         final Object\[\] items = this.items;
5         @SuppressWarnings("unchecked")
6         E x = (E) items\[takeIndex\];
7         items\[takeIndex\] = null;
8         if (++takeIndex == items.length)
9             takeIndex = 0;
10         count--;
11         if (itrs != null)
12             itrs.elementDequeued();
13         notFull.signal();
14         return x;
15     }

HashMap

最常用的哈希表, 面試的童鞋必備知識了, 內部通過陣列 + 單鏈表的方式實作. jdk8中引入了紅黑樹對長度 > 8的鏈表進行優化, 我們另外篇幅再講，推薦閱讀：Java 程式員必須掌握的 8 道資料結構面試題，你會幾道？

put(K, V****)

put(K, V) 相同hash值

resize 動態擴容

當map中元素超出設定的閾值后, 會進行resize (length * 2)操作, 擴容程序中對元素一通操作, 并放置到新的位置，推薦閱讀：Java 程式員必須掌握的 8 道資料結構面試題，你會幾道？

具體操作如下:

在jdk7中對所有元素直接rehash, 并放到新的位置.
在jdk8中判斷元素原hash值新增的bit位是0還是1, 0則索引不變, 1則索引變成"原索引 + oldTable.length".

1     //定義兩條鏈
2     //原來的hash值新增的bit為0的鏈，頭部和尾部
3     Node<K,V> loHead = null, loTail = null;
4     //原來的hash值新增的bit為1的鏈，頭部和尾部
5     Node<K,V> hiHead = null, hiTail = null;
6     Node<K,V> next;
7     //回圈遍歷出鏈條鏈
8     do {
9         next = e.next;
10         if ((e.hash & oldCap) == 0) {
11             if (loTail == null)
12                 loHead = e;
13             else
14                 loTail.next = e;
15             loTail = e;
16         }
17         else {
18             if (hiTail == null)
19                 hiHead = e;
20             else
21                 hiTail.next = e;
22             hiTail = e;
23         }
24     } while ((e = next) != null);
25     //擴容前后位置不變的鏈
26     if (loTail != null) {
27         loTail.next = null;
28         newTab\[j\] = loHead;
29     }
30     //擴容后位置加上原陣列長度的鏈
31     if (hiTail != null) {
32         hiTail.next = null;
33         newTab\[j + oldCap\] = hiHead;
34     }