為了引出 ConcurrentSkipListMap渐裸，先來簡單理解下什么是跳表。
對于單鏈表仍劈，即使鏈表是有序的厕倍，如果想要在其中查找某個數(shù)據(jù)，也只能從頭到尾遍歷鏈表贩疙，這樣效率自然就會很低讹弯，跳表就不一樣了。跳表是一種可以用來快速查找的數(shù)據(jù)結構这溅，有點類似于平衡樹组民。它們都可以對元素進行快速的查找。但一個重要的區(qū)別是：對平衡樹的插入和刪除往往很可能導致平衡樹進行一次全局的調(diào)整悲靴；而對跳表的插入和刪除臭胜，只需要對整個數(shù)據(jù)結構的局部進行操作即可。這樣帶來的好處是：在高并發(fā)的情況下，需要一個全局鎖庇楞，來保證整個平衡樹的線程安全榜配；而對于跳表否纬，則只需要部分鎖即可吕晌。這樣，在高并發(fā)環(huán)境下临燃，就可以擁有更好的性能睛驳。就查詢的性能而言，跳表的時間復雜度是 O(logn)膜廊， 所以在并發(fā)數(shù)據(jù)結構中乏沸，JDK 使用跳表來實現(xiàn)一個 Map。
跳表的本質(zhì)爪瓜，是同時維護了多個鏈表蹬跃，并且鏈表是分層的：
最低層的鏈表，維護了跳表內(nèi)所有的元素铆铆，每上面一層鏈表蝶缀，都是下面一層的子集。
跳表內(nèi)所有鏈表的元素都是排序的薄货。查找時翁都，可以從頂級鏈表開始找。一旦發(fā)現(xiàn)被查找的元素大于當前鏈表中的取值谅猾，就會轉(zhuǎn)入下一層鏈表繼續(xù)找柄慰。這也就是說在查找過程中，搜索是跳躍式的税娜。如上圖所示坐搔，在跳表中查找元素18。
查找18 的時候敬矩，原來需要遍歷 18 次概行，現(xiàn)在只需要 7 次即可。針對鏈表長度比較大的時候谤绳，構建索引占锯，查找效率的提升就會非常明顯。
從上面很容易看出缩筛，跳表是一種利用空間換時間的算法消略。
使用跳表實現(xiàn) Map，和使用哈希算法實現(xiàn) Map 的另外一個不同之處是：哈希并不會保存元素的順序瞎抛，而跳表內(nèi)所有的元素都是排序的艺演。因此，在對跳表進行遍歷時，你會得到一個有序的結果胎撤。所以晓殊，如果你的應用需要有序性，那么跳表就是你不二的選擇伤提，JDK 中實現(xiàn)這一數(shù)據(jù)結構的類是 ConcurrentSkipListMap巫俺。
