java并發(fā)容器-ConcurrentSkipListMap(跳表)

對于正常的鏈表來說选泻,如果需要查找某個數據時冲粤,需要從頭到尾遍歷鏈表,效率比較低页眯。
而跳表就同時維護了多個鏈表梯捕,并且這些鏈表是分層的,用來快速查找數據窝撵。

最底層的鏈表維護了跳表內所有的元素傀顾,每上面一層鏈表都是下面一層鏈表的子集,
鏈表越往上數據越少碌奉。

跳表內所有元素都是排序的短曾,這樣在查找時,可以先從頂層鏈表查找道批,
一旦發(fā)現被查找的元素大于當前鏈表的取值错英,就會轉入下一層鏈表繼續(xù)查找。
也就是說在查找過程中隆豹,是跳躍式搜索椭岩。

因為持有多個鏈表,也就是說使用了空間換取時間的算法。

附上一張圖片判哥,來源于網絡
查找18這個元素時的查找路徑

跳表.jpeg
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末献雅,一起剝皮案震驚了整個濱河市,隨后出現的幾起案子塌计,更是在濱河造成了極大的恐慌挺身,老刑警劉巖,帶你破解...
    沈念sama閱讀 221,635評論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件锌仅,死亡現場離奇詭異章钾,居然都是意外死亡,警方通過查閱死者的電腦和手機热芹,發(fā)現死者居然都...
    沈念sama閱讀 94,543評論 3 399
  • 文/潘曉璐 我一進店門贱傀,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人伊脓,你說我怎么就攤上這事府寒。” “怎么了报腔?”我有些...
    開封第一講書人閱讀 168,083評論 0 360
  • 文/不壞的土叔 我叫張陵株搔,是天一觀的道長。 經常有香客問我纯蛾,道長纤房,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,640評論 1 296
  • 正文 為了忘掉前任茅撞,我火速辦了婚禮帆卓,結果婚禮上,老公的妹妹穿的比我還像新娘米丘。我一直安慰自己剑令,他們只是感情好,可當我...
    茶點故事閱讀 68,640評論 6 397
  • 文/花漫 我一把揭開白布拄查。 她就那樣靜靜地躺著吁津,像睡著了一般。 火紅的嫁衣襯著肌膚如雪堕扶。 梳的紋絲不亂的頭發(fā)上碍脏,一...
    開封第一講書人閱讀 52,262評論 1 308
  • 那天,我揣著相機與錄音稍算,去河邊找鬼典尾。 笑死,一個胖子當著我的面吹牛糊探,可吹牛的內容都是我干的钾埂。 我是一名探鬼主播河闰,決...
    沈念sama閱讀 40,833評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼褥紫!你這毒婦竟也來了姜性?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 39,736評論 0 276
  • 序言:老撾萬榮一對情侶失蹤髓考,失蹤者是張志新(化名)和其女友劉穎部念,沒想到半個月后,有當地人在樹林里發(fā)現了一具尸體氨菇,經...
    沈念sama閱讀 46,280評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡儡炼,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,369評論 3 340
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現自己被綠了查蓉。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片射赛。...
    茶點故事閱讀 40,503評論 1 352
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖奶是,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情竣灌,我是刑警寧澤聂沙,帶...
    沈念sama閱讀 36,185評論 5 350
  • 正文 年R本政府宣布,位于F島的核電站初嘹,受9級特大地震影響及汉,放射性物質發(fā)生泄漏。R本人自食惡果不足惜屯烦,卻給世界環(huán)境...
    茶點故事閱讀 41,870評論 3 333
  • 文/蒙蒙 一坷随、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧驻龟,春花似錦温眉、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,340評論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至露懒,卻和暖如春闯冷,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背懈词。 一陣腳步聲響...
    開封第一講書人閱讀 33,460評論 1 272
  • 我被黑心中介騙來泰國打工蛇耀, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人坎弯。 一個月前我還...
    沈念sama閱讀 48,909評論 3 376
  • 正文 我出身青樓纺涤,卻偏偏與公主長得像译暂,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子洒琢,可洞房花燭夜當晚...
    茶點故事閱讀 45,512評論 2 359

推薦閱讀更多精彩內容

  • 除了同步控制秧秉,線程池等基本工具以外,JDK還準備了一大批好用的容器類衰抑。 1.1 并發(fā)集合 JDK提供的這些容器大部...
    AaronSimon閱讀 1,012評論 0 3
  • Redis為什么用跳表而不用平衡樹呛踊? 本文是《Redis內部數據結構詳解》系列的第六篇砾淌。在本文中,我們圍繞一個Re...
    meng_philip123閱讀 3,990評論 0 26
  • Java提供的并發(fā)容器基本都在java.util.concurrent包中谭网。比較常用的有ConcurrentHas...
    夏與清風閱讀 385評論 0 0
  • 早上我擠上牙膏準備刷牙汪厨,一不小心,切把牙膏吞下去了愉择,感覺涼涼的劫乱。
    李昊宇_8ebc閱讀 178評論 0 0
  • 第一次聽說 WFH 是在上家公司進第二個項目的時候。項目本身是個美國項目锥涕,團隊里面的 PM衷戈,BA 和 TL 都在美...
    ForBravo閱讀 13,740評論 2 3