千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構(gòu)

手機站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時隨地免費學(xué)

千鋒教育

掃一掃進入千鋒手機站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時隨地免費學(xué)習(xí)課程

當前位置:首頁  >  技術(shù)干貨  > 隊列和棧是什么?有什么區(qū)別?

隊列和棧是什么?有什么區(qū)別?

來源:千鋒教育
發(fā)布人:qyf
時間: 2022-08-01 17:03:03 1659344583

隊列和棧

  隊列先進先出,棧先進后出。

  遍歷數(shù)據(jù)速度不同。

  棧只能從頭部取數(shù)據(jù) 也就最先放入的需要遍歷整個棧最后才能取出來,而且在遍歷數(shù)據(jù)的時候還得為數(shù)據(jù)開辟臨時空間,保持數(shù)據(jù)在遍歷前的一致性;

  隊列則不同,他基于地址指針進行遍歷,而且可以從頭或尾部開始遍歷,但不能同時遍歷,無需開辟臨時空間,因為在遍歷的過程中不影像數(shù)據(jù)結(jié)構(gòu),速度要快的多。

  Java8開始ConcurrentHashMap,為什么舍棄分段鎖?

  ConcurrentHashMap的原理是引用了內(nèi)部的 Segment ( ReentrantLock ) 分段鎖,保證在操作不同段 map 的時候, 可以并發(fā)執(zhí)行, 操作同段 map 的時候,進行鎖的競爭和等待。從而達到線程安全, 且效率大于 synchronized。

  但是在 Java 8 之后, JDK 卻棄用了這個策略,重新使用了 synchronized+CAS。

  棄用原因:

  通過 JDK 的源碼和官方文檔看來, 他們認為的棄用分段鎖的原因由以下幾點:

  加入多個分段鎖浪費內(nèi)存空間;

  生產(chǎn)環(huán)境中, map 在放入時競爭同一個鎖的概率非常小,分段鎖反而會造成更新等操作的長時間等待;

  為了提高 GC 的效率;

  提供了新的同步方案:既然棄用了分段鎖, 那么一定由新的線程安全方案, 我們來看看源碼是怎么解決線程安全的呢?(源碼保留了segment 代碼, 但并沒有使用)。

  ConcurrentHashMap(JDK1.8)為什么要使用synchronized而不是如ReentranLock這樣的可重入鎖?

  我想從下面幾個角度討論這個問題:

  1. 鎖的粒度

  首先鎖的粒度并沒有變粗,甚至變得更細了。每當擴容一次,ConcurrentHashMap的并發(fā)度就擴大一倍。

  2. Hash沖突

  JDK1.7中,ConcurrentHashMap從過二次hash的方式(Segment -> HashEntry)能夠快速的找到查找的元素。在1.8中通過鏈表加紅黑樹的形式彌補了put、get時的性能差距。

  JDK1.8中,在ConcurrentHashmap進行擴容時,其他線程可以通過檢測數(shù)組中的節(jié)點決定是否對這條鏈表(紅黑樹)進行擴容,減小了擴容的粒度,提高了擴容的效率。

  下面是我對那個面試問題的一些看法,即為什么是synchronized,而不是ReentranLock?

  1. 減少內(nèi)存開銷

  假設(shè)使用可重入鎖來獲得同步支持,那么每個節(jié)點都需要通過繼承AQS來獲得同步支持。但并不是每個節(jié)點都需要獲得同步支持的,只有鏈表的頭節(jié)點(紅黑樹的根節(jié)點)需要同步,這無疑帶來了巨大內(nèi)存浪費。

  2. 獲得JVM的支持

  可重入鎖畢竟是API這個級別的,后續(xù)的性能優(yōu)化空間很小。

  synchronized則是JVM直接支持的,JVM能夠在運行時作出相應(yīng)的優(yōu)化措施:鎖粗化、鎖消除、鎖自旋等等。這就使得synchronized能夠隨著JDK版本的升級而不改動代碼的前提下獲得性能上的提升。

  更多關(guān)于“Java培訓(xùn)”的問題,歡迎咨詢千鋒教育在線名師。千鋒已有十余年的培訓(xùn)經(jīng)驗,課程大綱更科學(xué)更專業(yè),有針對零基礎(chǔ)的就業(yè)班,有針對想提升技術(shù)的好程序員班,高品質(zhì)課程助力你實現(xiàn)java程序員夢想。

tags:
聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學(xué)習(xí)老師24小時內(nèi)將與您1V1溝通
免費領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT