最近在整理數據結構方面的知識, 系統化看了下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
底層就是一個數組, 因此按序查找快, 亂序插入, 刪除因為涉及到後面元素移位所以性能慢.
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) 隊列滿了
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(訪問有序)緩存.
put(K, V)
get(K)
accessOrder為false的時候, 直接返回元素就行了, 不需要調整位置.
accessOrder為true的時候, 需要將最近訪問的元素, 放置到隊尾.
removeEldestEntry 刪除最老的元素
最新整理的Java技術乾貨文檔資料：【Java核心知識點整理】涵蓋29個Java核心技術詳解，JVM，Redis，Nginx，Spring Boot，Spring Cloud，Kafka，併發編程，Tomcat，MyBatis，BAT面試題，Java技術精講視頻等。轉發+關注，私信回覆“乾貨”即可獲得免費領取方式。
鏈接：https://www.jianshu.com/p/2cfaa2da1d16
閱讀更多 IT知識課堂 的文章
