動圖詳解：常用數據結構及其設計原理
最近在整理數據結構方面的知識，系統化看了下Java中常用數據結構，突發奇想用動畫來繪制數據流轉過程。
主要基于jdk8，可能會有些特性與jdk7之前不相同，例如LinkedList LinkedHashMap中的雙向列表不再是回環的。HashMap中的單鏈表是尾插，而不是頭插入等等，后文不再贅敘這些差異，本文目錄結構如下：
1. LinkedList
LinkedList經典的雙鏈表結構，適用于亂序插入，刪除。指定序列操作則性能不如ArrayList，這也是其數據結構決定的。
add(E) / addLast(E)
add(index, E)
這邊有個小的優化，他會先判斷index是靠近隊頭還是隊尾，來確定從哪個方向遍歷鏈入。
- 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;
- }
靠隊尾
get(index)
也是會先判斷index，不過性能依然不好，這也是為什么不推薦用for(int i = 0; i < lengh; i++)的方式遍歷linkedlist，而是使用iterator的方式遍歷。
remove(E)
2. ArrayList
ArrayList底層就是一個數組，因此按序查找快，亂序插入，刪除因為涉及到后面元素移位所以性能慢。
add(index, E)
擴容
一般默認容量是10，擴容后，會length*1.5。
remove(E)
循環遍歷數組，判斷E是否equals當前元素，刪除性能不如LinkedList。
3. Stack
Stack是經典的數據結構，底層也是數組，繼承自Vector，先進后出FILO，默認new Stack()容量為10，超出自動擴容。
push(E)
pop()
4. 后綴表達式
Stack的一個典型應用就是計算表達式如 9 + (3 - 1) * 3 + 10 / 2，計算機將中綴表達式轉為后綴表達式，再對后綴表達式進行計算。
中綴轉后綴
- 數字直接輸出
- 棧為空時，遇到運算符，直接入棧
- 遇到左括號, 將其入棧
- 遇到右括號, 執行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號，左括號不輸出。
- 遇到運算符(加減乘除)：彈出所有優先級大于或者等于該運算符的棧頂元素，然后將該運算符入棧
- 最終將棧中的元素依次出棧，輸出。
計算后綴表達
- 遇到數字時，將數字壓入堆棧
- 遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算, 并將結果入棧
- 重復上述過程直到表達式最右端
- 運算得出的值即為表達式的結果
5. 隊列
與Stack的區別在于：Stack的刪除與添加都在隊尾進行，而Queue刪除在隊頭，添加在隊尾。
ArrayBlockingQueue
生產消費者中常用的阻塞有界隊列，FIFO。
put(E)
put(E) 隊列滿了
- final ReentrantLock lock = this.lock;
- lock.lockInterruptibly();
- try {
- while (count == items.length)
- notFull.await();
- enqueue(e);
- } finally {
- lock.unlock();
- }
take()
當元素被取出后，并沒有對數組后面的元素位移，而是更新takeIndex來指向下一個元素。
takeIndex是一個環形的增長，當移動到隊列尾部時，會指向0，再次循環。
- private E dequeue() {
- // assert lock.getHoldCount() == 1;
- // assert items[takeIndex] != null;
- final Object[] items = this.items;
- @SuppressWarnings("unchecked")
- E x = (E) items[takeIndex];
- items[takeIndex] = null;
- if (++takeIndex == items.length)
- takeIndex = 0;
- count--;
- if (itrs != null)
- itrs.elementDequeued();
- notFull.signal();
- return x;
- }
6. HashMap
最常用的哈希表，面試的童鞋必備知識了，內部通過數組 + 單鏈表的方式實現。dk8中引入了紅黑樹對長度 > 8的鏈表進行優化，我們另外篇幅再講。
put(K, V)
put(K, V) 相同hash值
resize 動態擴容
當map中元素超出設定的閾值后，會進行resize (length * 2)操作，擴容過程中對元素一通操作，并放置到新的位置。
具體操作如下：
- 在jdk7中對所有元素直接rehash, 并放到新的位置.
- 在jdk8中判斷元素原hash值新增的bit位是0還是1, 0則索引不變, 1則索引變成"原索引 + oldTable.length".
- //定義兩條鏈
- //原來的hash值新增的bit為0的鏈，頭部和尾部
- Node<K,V> loHead = null, loTail = null;
- //原來的hash值新增的bit為1的鏈，頭部和尾部
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- //循環遍歷出鏈條鏈
- do {
- next = e.next;
- if ((e.hash & oldCap) == 0) {
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- //擴容前后位置不變的鏈
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;
- }
- //擴容后位置加上原數組長度的鏈
- if (hiTail != null) {
- 32 hiTail.next = null;
- 33 newTab[j + oldCap] = hiHead;
- 34 }
7. LinkedHashMap
繼承自HashMap，底層額外維護了一個雙向鏈表來維持數據有序。可以通過設置accessOrder來實現FIFO(插入有序)或者LRU(訪問有序)緩存。
put(K, V)
get(K)
accessOrder為false的時候，直接返回元素就行了，不需要調整位置。
accessOrder為true的時候，需要將最近訪問的元素，放置到隊尾。
removeEldestEntry 刪除最老的元素
