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

主要基于jdk8, 可能會(huì)有些特性與jdk7之前不相同, 例如LinkedList LinkedHashMap中的雙向列表不再是回環(huán)的.

HashMap中的單鏈表是尾插, 而不是頭插入等等, 后文不再贅敘這些差異, 本文目錄結(jié)構(gòu)如下:

---

LinkedList

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

add(E) / addLast(E)

add(index, E)

這邊有個(gè)小的優(yōu)化, 他會(huì)先判斷index是靠近隊(duì)頭還是隊(duì)尾, 來(lái)確定從哪個(gè)方向遍歷鏈入.

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;}

靠隊(duì)尾

get(index)

也是會(huì)先判斷index, 不過(guò)性能依然不好, 這也是為什么不推薦用for(int i = 0; i < lengh; i++)的方式遍歷linkedlist, 而是使用iterator的方式遍歷.

remove(E)

---

ArrayList

底層就是一個(gè)數(shù)組, 因此按序查找快, 亂序插入, 刪除因?yàn)樯婕暗胶竺嬖匾莆凰孕阅苈?

add(index, E)

擴(kuò)容

一般默認(rèn)容量是10, 擴(kuò)容后, 會(huì)length*1.5.

remove(E)

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

---

Stack

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

push(E)

pop()

---

后綴表達(dá)式

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

中綴轉(zhuǎn)后綴

• 數(shù)字直接輸出

• 棧為空時(shí)，遇到運(yùn)算符，直接入棧

• 遇到左括號(hào), 將其入棧

• 遇到右括號(hào), 執(zhí)行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號(hào)，左括號(hào)不輸出。

• 遇到運(yùn)算符(加減乘除)：彈出所有優(yōu)先級(jí)大于或者等于該運(yùn)算符的棧頂元素，然后將該運(yùn)算符入棧

• 最終將棧中的元素依次出棧，輸出。

計(jì)算后綴表達(dá)

• 遇到數(shù)字時(shí)，將數(shù)字壓入堆棧

• 遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)數(shù)，用運(yùn)算符對(duì)它們做相應(yīng)的計(jì)算, 并將結(jié)果入棧

• 重復(fù)上述過(guò)程直到表達(dá)式最右端

• 運(yùn)算得出的值即為表達(dá)式的結(jié)果

---

隊(duì)列

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

ArrayBlockingQueue

生產(chǎn)消費(fèi)者中常用的阻塞有界隊(duì)列, FIFO.

put(E)

put(E) 隊(duì)列滿了

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

take()

當(dāng)元素被取出后, 并沒(méi)有對(duì)數(shù)組后面的元素位移, 而是更新takeIndex來(lái)指向下一個(gè)元素.

takeIndex是一個(gè)環(huán)形的增長(zhǎng), 當(dāng)移動(dòng)到隊(duì)列尾部時(shí), 會(huì)指向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;}

---

HashMap

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

put(K, V)

put(K, V) 相同hash值

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

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

具體操作如下:

• 在jdk7中對(duì)所有元素直接rehash, 并放到新的位置.

• 在jdk8中判斷元素原h(huán)ash值新增的bit位是0還是1, 0則索引不變, 1則索引變成"原索引 + oldTable.length".

//定義兩條鏈//原來(lái)的hash值新增的bit為0的鏈，頭部和尾部Node<K,V>?loHead?=?null,?loTail?=?null;//原來(lái)的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;elseloTail.next?=?e;loTail?=?e;}else?{if?(hiTail?==?null)hiHead?=?e;elsehiTail.next?=?e;hiTail?=?e;}}?while?((e?=?next)?!=?null);//擴(kuò)容前后位置不變的鏈if?(loTail?!=?null)?{loTail.next?=?null;newTab[j]?=?loHead;}//擴(kuò)容后位置加上原數(shù)組長(zhǎng)度的鏈if?(hiTail?!=?null)?{hiTail.next?=?null;newTab[j?+?oldCap]?=?hiHead;}

---

LinkedHashMap

繼承自HashMap, 底層額外維護(hù)了一個(gè)雙向鏈表來(lái)維持?jǐn)?shù)據(jù)有序. 可以通過(guò)設(shè)置accessOrder來(lái)實(shí)現(xiàn)FIFO(插入有序)或者LRU(訪問(wèn)有序)緩存.

put(K, V)

get(K)

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

accessOrder為true的時(shí)候, 需要將最近訪問(wèn)的元素, 放置到隊(duì)尾.

removeEldestEntry 刪除最老的元素

---

---

?

總結(jié)

以上是生活随笔為你收集整理的动图 + 源码，演示 Java 中常用数据结构执行过程及原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。