圖解Java常用數據結構
- 2019 年 10 月 6 日
- 筆記
最近在整理數據結構方面的知識, 系統化看了下 Java 中常用數據結構, 突發奇想用動畫來繪製數據流轉過程.
主要基於 jdk8, 可能會有些特性與 jdk7 之前不相同, 例如 LinkedList LinkedHashMap 中的雙向列表不再是迴環的.
HashMap 中的單鏈表是尾插, 而不是頭插入等等, 後文不再贅敘這些差異, 本文目錄結構如下:
LinkedList
經典的雙鏈表結構, 適用於亂序插入, 刪除. 指定序列操作則性能不如 ArrayList, 這也是其數據結構決定的.
add(E) / addLast(E)
add(index, E)
這邊有個小的優化, 他會先判斷 index 是靠近隊頭還是隊尾, 來確定從哪個方向遍歷鏈入.
if(index<(size>>1)) Node x = first; for (inti = 0; i < index; i++) { x = x.next; } return x; }else{ Node 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 的方式遍歷.
正是金九銀十跳槽季，為大家收集了2019年最新的面試資料，有文檔、有攻略、有影片。有需要的同學可以在公眾號【Java知己】，發送【面試】領取最新面試資料攻略！暗號【1024】千萬不要發，否則…..
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, 電腦將中綴表達式轉為後綴表達式, 再對後綴表達式進行計算.
中綴轉後綴
數字直接輸出
棧為空時，遇到運算符，直接入棧
遇到左括弧, 將其入棧
遇到右括弧, 執行出棧操作，並將出棧的元素輸出，直到彈出棧的是左括弧，左括弧不輸出。
遇到運算符 (加減乘除)：彈出所有優先順序大於或者等於該運算符的棧頂元素，然後將該運算符入棧
最終將棧中的元素依次出棧，輸出。
計算後綴表達
遇到數字時，將數字壓入堆棧
遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算, 並將結果入棧
重複上述過程直到表達式最右端
運算得出的值即為表達式的結果
隊列
與 Stack 的區別在於, Stack 的刪除與添加都在隊尾進行, 而 Queue 刪除在隊頭, 添加在隊尾.
ArrayBlockingQueue
生產消費者中常用的阻塞有界隊列, FIFO.
put(E)
put(E) 隊列滿了
final ReentrantLocklock=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; }
HashMap
最常用的哈希表, 面試的童鞋必備知識了, 內部通過數組 + 單鏈表的方式實現. jdk8 中引入了紅黑樹對長度 > 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 loHead =null, loTail =null; // 原來的 hash 值新增的 bit 為 1 的鏈，頭部和尾部 Node hiHead =null, hiTail =null; Node 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) { hiTail.next =null; newTab[j + oldCap] = hiHead; }
LinkedHashMap
繼承自 HashMap, 底層額外維護了一個雙向鏈表來維持數據有序. 可以通過設置 accessOrder 來實現 FIFO(插入有序) 或者 LRU(訪問有序) 快取.
put(K, V)
get(K)
accessOrder 為 false 的時候, 直接返回元素就行了, 不需要調整位置.
accessOrder 為 true 的時候, 需要將最近訪問的元素, 放置到隊尾.
removeEldestEntry 刪除最老的元素
你的贊和關注是我繼續創作的動力~
