最近在整理數(shù)據(jù)結(jié)構(gòu)方面的知識，系統(tǒng)化看了下Java中常用數(shù)據(jù)結(jié)構(gòu)，突發(fā)奇想用動畫來繪制數(shù)據(jù)流轉(zhuǎn)過程。

[[277055]]

主要基于jdk8，可能會有些特性與jdk7之前不相同，例如LinkedList LinkedHashMap中的雙向列表不再是回環(huán)的。HashMap中的單鏈表是尾插，而不是頭插入等等，后文不再贅敘這些差異，本文目錄結(jié)構(gòu)如下： 

1. LinkedList

LinkedList經(jīng)典的雙鏈表結(jié)構(gòu)，適用于亂序插入，刪除。指定序列操作則性能不如ArrayList，這也是其數(shù)據(jù)結(jié)構(gòu)決定的。

add(E) / addLast(E) 

add(index, E)

這邊有個小的優(yōu)化，他會先判斷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底層就是一個數(shù)組，因此按序查找快，亂序插入，刪除因為涉及到后面元素移位所以性能慢。

add(index, E) 

擴(kuò)容

一般默認(rèn)容量是10，擴(kuò)容后，會length*1.5。 

remove(E)

循環(huán)遍歷數(shù)組，判斷E是否equals當(dāng)前元素，刪除性能不如LinkedList。 

3. Stack

Stack是經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，底層也是數(shù)組，繼承自Vector，先進(jìn)后出FILO，默認(rèn)new Stack()容量為10，超出自動擴(kuò)容。

push(E) 

pop() 

4. 后綴表達(dá)式

Stack的一個典型應(yīng)用就是計算表達(dá)式如 9 + (3 - 1) * 3 + 10 / 2，計算機(jī)將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式，再對后綴表達(dá)式進(jìn)行計算。

中綴轉(zhuǎn)后綴

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

計算后綴表達(dá)

• 遇到數(shù)字時，將數(shù)字壓入堆棧
• 遇到運算符時，彈出棧頂?shù)膬蓚€數(shù)，用運算符對它們做相應(yīng)的計算, 并將結(jié)果入棧
• 重復(fù)上述過程直到表達(dá)式最右端
• 運算得出的值即為表達(dá)式的結(jié)果 

5. 隊列

與Stack的區(qū)別在于：Stack的刪除與添加都在隊尾進(jìn)行，而Queue刪除在隊頭，添加在隊尾。

ArrayBlockingQueue

生產(chǎn)消費者中常用的阻塞有界隊列，F(xiàn)IFO。

put(E) 

put(E) 隊列滿了

final ReentrantLock lock = this.lock; 
lock.lockInterruptibly(); 
try { 
 while (count == items.length) 
 notFull.await(); 
 enqueue(e); 
} finally { 
 lock.unlock(); 
} 

take()

當(dāng)元素被取出后，并沒有對數(shù)組后面的元素位移，而是更新takeIndex來指向下一個元素。

takeIndex是一個環(huán)形的增長，當(dāng)移動到隊列尾部時，會指向0，再次循環(huán)。

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

最常用的哈希表，面試的童鞋必備知識了，內(nèi)部通過數(shù)組 + 單鏈表的方式實現(xiàn)。dk8中引入了紅黑樹對長度 > 8的鏈表進(jìn)行優(yōu)化，我們另外篇幅再講。

put(K, V) 

put(K, V) 相同hash值 

resize 動態(tài)擴(kuò)容

當(dāng)map中元素超出設(shè)定的閾值后，會進(jìn)行resize (length * 2)操作，擴(kuò)容過程中對元素一通操作，并放置到新的位置。

具體操作如下：

• 在jdk7中對所有元素直接rehash, 并放到新的位置.
• 在jdk8中判斷元素原h(huán)ash值新增的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; 
 //循環(huán)遍歷出鏈條鏈 
 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); 
 //擴(kuò)容前后位置不變的鏈 
 if (loTail != null) { 
 loTail.next = null; 
 newTab[j] = loHead; 
 } 
 //擴(kuò)容后位置加上原數(shù)組長度的鏈 
 if (hiTail != null) { 
32 hiTail.next = null; 
33 newTab[j + oldCap] = hiHead; 
34 } 

7. LinkedHashMap

繼承自HashMap，底層額外維護(hù)了一個雙向鏈表來維持?jǐn)?shù)據(jù)有序?？梢酝ㄟ^設(shè)置accessOrder來實現(xiàn)FIFO(插入有序)或者LRU(訪問有序)緩存。

put(K, V) 

get(K)

accessOrder為false的時候，直接返回元素就行了，不需要調(diào)整位置。

accessOrder為true的時候，需要將最近訪問的元素，放置到隊尾。 

removeEldestEntry 刪除最老的元素