最近在整理數(shù)據(jù)結(jié)構(gòu)方面的知識, 系統(tǒng)化看了下Java中常用數(shù)據(jù)結(jié)構(gòu), 突發(fā)奇想用動畫來繪制數(shù)據(jù)流轉(zhuǎn)過程.
主要基于jdk8, 可能會有些特性與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)
這邊有個小的優(yōu)化, 他會先判斷index是靠近隊(duì)頭還是隊(duì)尾, 來確定從哪個方向遍歷鏈入.
1if(index < (size >>1)) {
2?Node?x = first;
3?for(inti =0; i < index; i++)
4?x = x.next;
5?returnx;
6}else{
7?Node?x = last;
8?for(inti = size -1; i > index; i--)
9?x = x.prev;
10?returnx;
11}
靠隊(duì)尾
get(index)
也是會先判斷index, 不過性能依然不好, 這也是為什么不推薦用for(int i = 0; i < lengh; i++)的方式遍歷linkedlist, 而是使用iterator的方式遍歷.
remove(E)
ArrayList
底層就是一個數(shù)組, 因此按序查找快, 亂序插入, 刪除因?yàn)樯婕暗胶竺嬖匾莆凰孕阅苈?
add(index, E)
擴(kuò)容
一般默認(rèn)容量是10, 擴(kuò)容后, 會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, 超出自動擴(kuò)容.
push(E)
pop()
后綴表達(dá)式
Stack的一個典型應(yīng)用就是計(jì)算表達(dá)式如 9 + (3 - 1) * 3 + 10 / 2, 計(jì)算機(jī)將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式, 再對后綴表達(dá)式進(jìn)行計(jì)算.
中綴轉(zhuǎn)后綴
數(shù)字直接輸出
棧為空時，遇到運(yùn)算符，直接入棧
遇到左括號, 將其入棧
遇到右括號, 執(zhí)行出棧操作么鹤，并將出棧的元素輸出虐秋，直到彈出棧的是左括號档悠，左括號不輸出届宠。
遇到運(yùn)算符(加減乘除)：彈出所有優(yōu)先級大于或者等于該運(yùn)算符的棧頂元素，然后將該運(yùn)算符入棧
最終將棧中的元素依次出棧萍程，輸出艺糜。
計(jì)算后綴表達(dá)
遇到數(shù)字時剧董，將數(shù)字壓入堆棧
遇到運(yùn)算符時，彈出棧頂?shù)膬蓚€數(shù)破停，用運(yùn)算符對它們做相應(yīng)的計(jì)算, 并將結(jié)果入棧
重復(fù)上述過程直到表達(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ì)列滿了
1final ReentrantLocklock=this.lock;
2lock.lockInterruptibly();
3try{
4?while(count == items.length)
5?notFull.await();
6?enqueue(e);
7}finally{
8?lock.unlock();
9}
take()
當(dāng)元素被取出后, 并沒有對數(shù)組后面的元素位移, 而是更新takeIndex來指向下一個元素.
takeIndex是一個環(huán)形的增長, 當(dāng)移動到隊(duì)列尾部時, 會指向0, 再次循環(huán).
1privateEdequeue(){
2// assert lock.getHoldCount() == 1;
3// assert items[takeIndex] != null;
4finalObject[] items =this.items;
5@SuppressWarnings("unchecked")
6E x = (E) items[takeIndex];
7items[takeIndex] =null;
8if(++takeIndex == items.length)
9?takeIndex =0;
10count--;
11if(itrs !=null)
12?itrs.elementDequeued();
13notFull.signal();
14returnx;
15}
HashMap
最常用的哈希表, 面試的童鞋必備知識了, 內(nèi)部通過數(shù)組 + 單鏈表的方式實(shí)現(xiàn). jdk8中引入了紅黑樹對長度 > 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".
1//定義兩條鏈
2//原來的hash值新增的bit為0的鏈翅楼，頭部和尾部
3Node?loHead =null, loTail =null;
4//原來的hash值新增的bit為1的鏈，頭部和尾部
5Node?hiHead =null, hiTail =null;
6Node?next;
7//循環(huán)遍歷出鏈條鏈
8do{
9next = e.next;
10if((e.hash & oldCap) ==0) {
11?if(loTail ==null)
12?loHead = e;
13?else
14?loTail.next = e;
15?loTail = e;
16}
17else{
18?if(hiTail ==null)
19?hiHead = e;
20?else
21?hiTail.next = e;
22?hiTail = e;
23}
24}while((e = next) !=null);
25//擴(kuò)容前后位置不變的鏈
26if(loTail !=null) {
27loTail.next =null;
28newTab[j] = loHead;
29}
30//擴(kuò)容后位置加上原數(shù)組長度的鏈
31if(hiTail !=null) {
32hiTail.next =null;
33newTab[j + oldCap] = hiHead;
34}
LinkedHashMap
繼承自HashMap, 底層額外維護(hù)了一個雙向鏈表來維持?jǐn)?shù)據(jù)有序. 可以通過設(shè)置accessOrder來實(shí)現(xiàn)FIFO(插入有序)或者LRU(訪問有序)緩存.
put(K, V)
get(K)
accessOrder為false的時候, 直接返回元素就行了, 不需要調(diào)整位置.?
accessOrder為true的時候, 需要將最近訪問的元素, 放置到隊(duì)尾.
removeEldestEntry 刪除最老的元素
?為了讓學(xué)習(xí)變得輕松真慢、高效毅臊，今天給大家免費(fèi)分享一套Java教學(xué)資源。幫助大家在成為Java架構(gòu)師的道路上披荊斬棘黑界。需要資料的歡迎加入學(xué)習(xí)交流群：479 749 726
