最近在整理資料結構方面的知識, 系統化看了下Java中常用資料結構, 突發奇想用動畫來繪制資料流轉過程。
主要基于jdk8, 可能會有些特性與jdk7之前不相同, 例如LinkedList LinkedHashMap中的雙向清單不再是回環的。
HashMap中的單連結清單是尾插, 而不是頭插入等等, 後文不再贅叙這些差異, 本文目錄結構如下：
LinkedList
經典的雙連結清單結構, 适用于亂序插入, 删除. 指定序列操作則性能不如ArrayList, 這也是其資料結構決定的.
add(E) / addLast(E)
add(index, E)
這邊有個小的優化, 他會先判斷index是靠近隊頭還是隊尾, 來确定從哪個方向周遊鍊入.
靠隊尾
get(index)
也是會先判斷index, 不過性能依然不好, 這也是為什麼不推薦用for(int i = 0; i < lengh; i++)的方式周遊linkedlist, 而是使用iterator的方式周遊.
remove(E)
ArrayList
底層就是一個數組, 是以按序查找快, 亂序插入, 删除因為涉及到後面元素移位是以性能慢.
擴容
一般預設容量是10, 擴容後, 會length*1.5.
循環周遊數組, 判斷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) 隊列滿了
take()
當元素被取出後, 并沒有對數組後面的元素位移, 而是更新takeIndex來指向下一個元素.
takeIndex是一個環形的增長, 當移動到隊列尾部時, 會指向0, 再次循環.
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".
LinkedHashMap
繼承自HashMap, 底層額外維護了一個雙向連結清單來維持資料有序. 可以通過設定accessOrder來實作FIFO(插入有序)或者LRU(通路有序)緩存.
get(K)
accessOrder為false的時候, 直接傳回元素就行了, 不需要調整位置.
accessOrder為true的時候, 需要将最近通路的元素, 放置到隊尾.
removeEldestEntry 删除最老的元素
原文釋出時間為：2018-12-11
本文作者：大道方圓
本文來自雲栖社群合作夥伴“
機器學習算法與Python學習”，了解相關資訊可以關注“guodongwei1991”微信公衆号