您好,登錄后才能下訂單哦!
今天小編給大家分享一下jdk8中常用數(shù)據(jù)結(jié)構(gòu)及其設(shè)計原理是什么的相關(guān)知識點,內(nèi)容詳細(xì),邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
1. LinkedList
LinkedList經(jīng)典的雙鏈表結(jié)構(gòu),適用于亂序插入,刪除。指定序列操作則性能不如ArrayList,這也是其數(shù)據(jù)結(jié)構(gòu)決定的。
add(E) / addLast(E)
add(index, E)
這邊有個小的優(yōu)化,他會先判斷index是靠近隊頭還是隊尾,來確定從哪個方向遍歷鏈入。
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; }
靠隊尾
get(index)
也是會先判斷index,不過性能依然不好,這也是為什么不推薦用for(int i = 0; i < lengh; i++)的方式遍歷linkedlist,而是使用iterator的方式遍歷。
remove(E)
2. ArrayList
ArrayList底層就是一個數(shù)組,因此按序查找快,亂序插入,刪除因為涉及到后面元素移位所以性能慢。
add(index, E)
擴(kuò)容
一般默認(rèn)容量是10,擴(kuò)容后,會length*1.5。
remove(E)
循環(huán)遍歷數(shù)組,判斷E是否equals當(dāng)前元素,刪除性能不如LinkedList。
3. Stack
Stack是經(jīng)典的數(shù)據(jù)結(jié)構(gòu),底層也是數(shù)組,繼承自Vector,先進(jìn)后出FILO,默認(rèn)new Stack()容量為10,超出自動擴(kuò)容。
push(E)
pop()
4. 后綴表達(dá)式
Stack的一個典型應(yīng)用就是計算表達(dá)式如 9 + (3 - 1) * 3 + 10 / 2,計算機(jī)將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式,再對后綴表達(dá)式進(jìn)行計算。
中綴轉(zhuǎn)后綴
數(shù)字直接輸出
棧為空時,遇到運算符,直接入棧
遇到左括號, 將其入棧
遇到右括號, 執(zhí)行出棧操作,并將出棧的元素輸出,直到彈出棧的是左括號,左括號不輸出。
遇到運算符(加減乘除):彈出所有優(yōu)先級大于或者等于該運算符的棧頂元素,然后將該運算符入棧
最終將棧中的元素依次出棧,輸出。
計算后綴表達(dá)
遇到數(shù)字時,將數(shù)字壓入堆棧
遇到運算符時,彈出棧頂?shù)膬蓚€數(shù),用運算符對它們做相應(yīng)的計算, 并將結(jié)果入棧
重復(fù)上述過程直到表達(dá)式最右端
運算得出的值即為表達(dá)式的結(jié)果
5. 隊列
與Stack的區(qū)別在于:Stack的刪除與添加都在隊尾進(jìn)行,而Queue刪除在隊頭,添加在隊尾。
ArrayBlockingQueue
生產(chǎn)消費者中常用的阻塞有界隊列,F(xiàn)IFO。
put(E)
put(E) 隊列滿了
final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == items.length) notFull.await(); enqueue(e); } finally { lock.unlock(); }
take()
當(dāng)元素被取出后,并沒有對數(shù)組后面的元素位移,而是更新takeIndex來指向下一個元素。
takeIndex是一個環(huán)形的增長,當(dāng)移動到隊列尾部時,會指向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; }
6. HashMap
最常用的哈希表,面試的童鞋必備知識了,內(nèi)部通過數(shù)組 + 單鏈表的方式實現(xiàn)。dk8中引入了紅黑樹對長度 > 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".
//定義兩條鏈 //原來的hash值新增的bit為0的鏈,頭部和尾部 Node<K,V> loHead = null, loTail = null; //原來的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; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //擴(kuò)容前后位置不變的鏈 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //擴(kuò)容后位置加上原數(shù)組長度的鏈 if (hiTail != null) { 32 hiTail.next = null; 33 newTab[j + oldCap] = hiHead; 34 }
7. LinkedHashMap
繼承自HashMap,底層額外維護(hù)了一個雙向鏈表來維持?jǐn)?shù)據(jù)有序??梢酝ㄟ^設(shè)置accessOrder來實現(xiàn)FIFO(插入有序)或者LRU(訪問有序)緩存。
put(K, V)
get(K)
accessOrder為false的時候,直接返回元素就行了,不需要調(diào)整位置。
accessOrder為true的時候,需要將最近訪問的元素,放置到隊尾。
removeEldestEntry 刪除最老的元素
以上就是“jdk8中常用數(shù)據(jù)結(jié)構(gòu)及其設(shè)計原理是什么”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學(xué)習(xí)更多的知識,請關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。