數據結構課程設計求大神幫忙實現跳表動態演示

與分析基本要求① 構造并實現跳表（Skip List）的ADT ADT辦

網站建設哪家好，找創新互聯建站！專注于網頁設計、網站建設、微信開發、成都微信小程序、集團企業網站建設等服務項目。為回饋新老客戶創新互聯還提供了溧陽免費建站歡迎大家使用！

比較順的對待

跳躍表(SkipList)

跳躍表是一種基于有序鏈表的拓展，簡稱跳表。

下面正式開始了哦，跟著思路來，非常簡單理解:

給定一個有序鏈表：

1-2-3-5-6-7-8

跳表的思想就是利用了類似索引的思想，提取出鏈表中的部分關鍵節點，然后再用二分查找。

上面的有序鏈表，把奇數作為關鍵節點提取出來：

上面只是介紹了基本思想，其實還可以繼續優化，看到這別擔心，難度不會增加，也非常好理解:

既然上面提取了一層節點作為索引，那是不是也可以進一步提取？

有了2級索引后，插入的節點可以先和2級索引比較，確定大體范圍;然后再和1級索引比較;最后再回到原鏈表，找到并插入對應的位置。

節點多的時候還可以進一步提取，保證每一層是上一層節點的一半。提取的極限是同一層只有兩個節點的時候，因為一個節點比較沒有意義。

到這里，多層鏈表結構就提取完了，這就是跳躍表。

當大量新節點通過逐層比較插入到鏈表中后，上層節點就會顯得不夠用，這就需要從新節點中“提拔”一部分節點到上一層，問題就是“提拔”誰呢(如何選擇索引)？

跳表設計者采用了“拋硬幣”的方法，隨機決定新節點是否提拔。因為跳表的添加和刪除的節點是不可預測的，很難用算法保證跳表的索引分布始終均勻。雖然拋硬幣的方式不能保證絕對均勻，但大體上是趨于均勻的。

比如說，9插入到鏈表后，開始分析：

跳躍表插入操作的時間復雜度是O（logN），而這種數據結構所占空間是2N，既空間復雜度是 O（N）。

刪除的時候只要在索引層找到要刪除的節點，然后刪除每一層相同的節點即可。如果某一層刪到只剩下一個，那么整層都可以刪掉。比如刪除5:

跳躍表刪除操作的時間復雜度是O（logN）。

跳表維持結構平衡的成本較低，完全靠隨機。二叉查找樹在多次插入和刪除后需要重新保持自平衡。

Redis的五種數據類型之一Sorted-set(zset)這種有序集合，正是對于跳躍表的改進和應用。

還有Java中的ConcurrentSkipListMap和ConcurrentSkipListSet內部都是用跳表的數據結構。

java是否可以實現心跳的程序

java是可以實現心跳的程序的。

心跳顧名思義就是每隔一段時間執行，或者輪詢查詢狀態，可以使用timer來實現，代碼如下：

定時器可以實現

//1000毫秒，固定時間，每隔1秒鐘執行一次actionPerformed方法

javax.swing.Timer?clock?=?new?javax.swing.Timer(1000,new?ActionListener(){

public?void?actionPerformed(ActionEvent?e)?{

//執行心跳方法

/**...*/

//調用其他方法

/**...*/

}

});

clock.start();

可以獨立用個線程管理，也可以直接寫在主線程中

javase線程怎么存儲到容器

Java 并發重要知識點

java 線程池

ThreadPoolExecutor 類分析

ThreadPoolExecutor 類中提供的四個構造方法。我們來看最長的那個，其余三個都是在這個構造方法的基礎上產生（其他幾個構造方法說白點都是給定某些默認參數的構造方法比如默認制定拒絕策略是什么）。

/**

* 用給定的初始參數創建一個新的ThreadPoolExecutor。

*/

public ThreadPoolExecutor(int corePoolSize,//線程池的核心線程數量

int maximumPoolSize,//線程池的最大線程數

long keepAliveTime,//當線程數大于核心線程數時，多余的空閑線程存活的最長時間

TimeUnit unit,//時間單位

BlockingQueueRunnable workQueue,//任務隊列，用來儲存等待執行任務的隊列

ThreadFactory threadFactory,//線程工廠，用來創建線程，一般默認即可

RejectedExecutionHandler handler//拒絕策略，當提交的任務過多而不能及時處理時，我們可以定制策略來處理任務

) {

if (corePoolSize 0 ||

maximumPoolSize = 0 ||

maximumPoolSize corePoolSize ||

keepAliveTime 0)

throw new IllegalArgumentException();

if (workQueue == null || threadFactory == null || handler == null)

throw new NullPointerException();

this.corePoolSize = corePoolSize;

this.maximumPoolSize = maximumPoolSize;

this.workQueue = workQueue;

this.keepAliveTime = unit.toNanos(keepAliveTime);

this.threadFactory = threadFactory;

this.handler = handler;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

下面這些對創建非常重要，在后面使用線程池的過程中你一定會用到！所以，務必拿著小本本記清楚。

ThreadPoolExecutor 3 個最重要的參數：

corePoolSize : 核心線程數線程數定義了最小可以同時運行的線程數量。

maximumPoolSize : 當隊列中存放的任務達到隊列容量的時候，當前可以同時運行的線程數量變為最大線程數。

workQueue: 當新任務來的時候會先判斷當前運行的線程數量是否達到核心線程數，如果達到的話，新任務就會被存放在隊列中。

ThreadPoolExecutor其他常見參數 :

keepAliveTime:當線程池中的線程數量大于 corePoolSize 的時候，如果這時沒有新的任務提交，核心線程外的線程不會立即銷毀，而是會等待，直到等待的時間超過了 keepAliveTime才會被回收銷毀；

unit : keepAliveTime 參數的時間單位。

threadFactory :executor 創建新線程的時候會用到。

handler :飽和策略。關于飽和策略下面單獨介紹一下。

下面這張圖可以加深你對線程池中各個參數的相互關系的理解（圖片來源：《Java 性能調優實戰》）：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-nzbqGRz9-1654600571133)()]

ThreadPoolExecutor 飽和策略定義:

如果當前同時運行的線程數量達到最大線程數量并且隊列也已經被放滿了任務時，ThreadPoolTaskExecutor 定義一些策略:

ThreadPoolExecutor.AbortPolicy ：拋出 RejectedExecutionException來拒絕新任務的處理。

ThreadPoolExecutor.CallerRunsPolicy ：調用執行自己的線程運行任務，也就是直接在調用execute方法的線程中運行(run)被拒絕的任務，如果執行程序已關閉，則會丟棄該任務。因此這種策略會降低對于新任務提交速度，影響程序的整體性能。如果您的應用程序可以承受此延遲并且你要求任何一個任務請求都要被執行的話，你可以選擇這個策略。

ThreadPoolExecutor.DiscardPolicy ：不處理新任務，直接丟棄掉。

ThreadPoolExecutor.DiscardOldestPolicy ： 此策略將丟棄最早的未處理的任務請求。

舉個例子：

Spring 通過 ThreadPoolTaskExecutor 或者我們直接通過 ThreadPoolExecutor 的構造函數創建線程池的時候，當我們不指定 RejectedExecutionHandler 飽和策略的話來配置線程池的時候默認使用的是 ThreadPoolExecutor.AbortPolicy。在默認情況下，ThreadPoolExecutor 將拋出 RejectedExecutionException 來拒絕新來的任務 ，這代表你將丟失對這個任務的處理。 對于可伸縮的應用程序，建議使用 ThreadPoolExecutor.CallerRunsPolicy。當最大池被填滿時，此策略為我們提供可伸縮隊列。（這個直接查看 ThreadPoolExecutor 的構造函數源碼就可以看出，比較簡單的原因，這里就不貼代碼了。）

推薦使用 ThreadPoolExecutor 構造函數創建線程池

在《阿里巴巴 Java 開發手冊》“并發處理”這一章節，明確指出線程資源必須通過線程池提供，不允許在應用中自行顯式創建線程。

為什么呢？

使用線程池的好處是減少在創建和銷毀線程上所消耗的時間以及系統資源開銷，解決資源不足的問題。如果不使用線程池，有可能會造成系統創建大量同類線程而導致消耗完內存或者“過度切換”的問題。

另外，《阿里巴巴 Java 開發手冊》中強制線程池不允許使用 Executors 去創建，而是通過 ThreadPoolExecutor 構造函數的方式，這樣的處理方式讓寫的同學更加明確線程池的運行規則，規避資源耗盡的風險

Executors 返回線程池對象的弊端如下(后文會詳細介紹到)：

FixedThreadPool 和 SingleThreadExecutor ： 允許請求的隊列長度為 Integer.MAX_VALUE,可能堆積大量的請求，從而導致 OOM。

CachedThreadPool 和 ScheduledThreadPool ： 允許創建的線程數量為 Integer.MAX_VALUE ，可能會創建大量線程，從而導致 OOM。

方式一：通過ThreadPoolExecutor構造函數實現（推薦）通過構造方法實現

方式二：通過 Executor 框架的工具類 Executors 來實現 我們可以創建三種類型的 ThreadPoolExecutor：

FixedThreadPool

SingleThreadExecutor

CachedThreadPool

對應 Executors 工具類中的方法如圖所示：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-YGd4ygZu-1654600571136)()]

正確配置線程池參數

說到如何給線程池配置參數，美團的騷操作至今讓我難忘（后面會提到）！

我們先來看一下各種書籍和博客上一般推薦的配置線程池參數的方式，可以作為參考！

常規操作

很多人甚至可能都會覺得把線程池配置過大一點比較好！我覺得這明顯是有問題的。就拿我們生活中非常常見的一例子來說：并不是人多就能把事情做好，增加了溝通交流成本。你本來一件事情只需要 3 個人做，你硬是拉來了 6 個人，會提升做事效率嘛？我想并不會。 線程數量過多的影響也是和我們分配多少人做事情一樣，對于多線程這個場景來說主要是增加了上下文切換成本。不清楚什么是上下文切換的話，可以看我下面的介紹。

上下文切換：

多線程編程中一般線程的個數都大于 CPU 核心的個數，而一個 CPU 核心在任意時刻只能被一個線程使用，為了讓這些線程都能得到有效執行，CPU 采取的策略是為每個線程分配時間片并輪轉的形式。當一個線程的時間片用完的時候就會重新處于就緒狀態讓給其他線程使用，這個過程就屬于一次上下文切換。概括來說就是：當前任務在執行完 CPU 時間片切換到另一個任務之前會先保存自己的狀態，以便下次再切換回這個任務時，可以再加載這個任務的狀態。任務從保存到再加載的過程就是一次上下文切換。

上下文切換通常是計算密集型的。也就是說，它需要相當可觀的處理器時間，在每秒幾十上百次的切換中，每次切換都需要納秒量級的時間。所以，上下文切換對系統來說意味著消耗大量的 CPU 時間，事實上，可能是操作系統中時間消耗最大的操作。

Linux 相比與其他操作系統（包括其他類 Unix 系統）有很多的優點，其中有一項就是，其上下文切換和模式切換的時間消耗非常少。

類比于實現世界中的人類通過合作做某件事情，我們可以肯定的一點是線程池大小設置過大或者過小都會有問題，合適的才是最好。

如果我們設置的線程池數量太小的話，如果同一時間有大量任務/請求需要處理，可能會導致大量的請求/任務在任務隊列中排隊等待執行，甚至會出現任務隊列滿了之后任務/請求無法處理的情況，或者大量任務堆積在任務隊列導致 OOM。這樣很明顯是有問題的！ CPU 根本沒有得到充分利用。

但是，如果我們設置線程數量太大，大量線程可能會同時在爭取 CPU 資源，這樣會導致大量的上下文切換，從而增加線程的執行時間，影響了整體執行效率。

有一個簡單并且適用面比較廣的公式：

CPU 密集型任務(N+1)： 這種任務消耗的主要是 CPU 資源，可以將線程數設置為 N（CPU 核心數）+1，比 CPU 核心數多出來的一個線程是為了防止線程偶發的缺頁中斷，或者其它原因導致的任務暫停而帶來的影響。一旦任務暫停，CPU 就會處于空閑狀態，而在這種情況下多出來的一個線程就可以充分利用 CPU 的空閑時間。

I/O 密集型任務(2N)： 這種任務應用起來，系統會用大部分的時間來處理 I/O 交互，而線程在處理 I/O 的時間段內不會占用 CPU 來處理，這時就可以將 CPU 交出給其它線程使用。因此在 I/O 密集型任務的應用中，我們可以多配置一些線程，具體的計算方法是 2N。

如何判斷是 CPU 密集任務還是 IO 密集任務？

CPU 密集型簡單理解就是利用 CPU 計算能力的任務比如你在內存中對大量數據進行排序。但凡涉及到網絡讀取，文件讀取這類都是 IO 密集型，這類任務的特點是 CPU 計算耗費時間相比于等待 IO 操作完成的時間來說很少，大部分時間都花在了等待 IO 操作完成上。

美團的騷操作

美團技術團隊在《Java線程池實現原理及其在美團業務中的實踐》open in new window這篇文章中介紹到對線程池參數實現可自定義配置的思路和方法。

美團技術團隊的思路是主要對線程池的核心參數實現自定義可配置。這三個核心參數是：

corePoolSize : 核心線程數線程數定義了最小可以同時運行的線程數量。

maximumPoolSize : 當隊列中存放的任務達到隊列容量的時候，當前可以同時運行的線程數量變為最大線程數。

workQueue: 當新任務來的時候會先判斷當前運行的線程數量是否達到核心線程數，如果達到的話，新任務就會被存放在隊列中。

為什么是這三個參數？

我在這篇《新手也能看懂的線程池學習總結》open in new window 中就說過這三個參數是 ThreadPoolExecutor 最重要的參數，它們基本決定了線程池對于任務的處理策略。

如何支持參數動態配置？ 且看 ThreadPoolExecutor 提供的下面這些方法。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Sm89qdJZ-1654600571137)()]

格外需要注意的是corePoolSize， 程序運行期間的時候，我們調用 setCorePoolSize（） 這個方法的話，線程池會首先判斷當前工作線程數是否大于corePoolSize，如果大于的話就會回收工作線程。

另外，你也看到了上面并沒有動態指定隊列長度的方法，美團的方式是自定義了一個叫做 ResizableCapacityLinkedBlockIngQueue 的隊列（主要就是把LinkedBlockingQueue的capacity 字段的final關鍵字修飾給去掉了，讓它變為可變的）。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-cmNN5yAL-1654600571138)()]

還沒看夠？推薦 why神的[《如何設置線程池參數？美團給出了一個讓面試官虎軀一震的回答。》open in new window](如何設置線程池參數？美團給出了一個讓面試官虎軀一震的回答。 (qq.com))這篇文章，深度剖析，很不錯哦！

Java 常見并發容器

JDK 提供的這些容器大部分在 java.util.concurrent 包中。

ConcurrentHashMap : 線程安全的 HashMap

CopyOnWriteArrayList : 線程安全的 List，在讀多寫少的場合性能非常好，遠遠好于 Vector。

ConcurrentLinkedQueue : 高效的并發隊列，使用鏈表實現。可以看做一個線程安全的 LinkedList，這是一個非阻塞隊列。

BlockingQueue : 這是一個接口，JDK 內部通過鏈表、數組等方式實現了這個接口。表示阻塞隊列，非常適合用于作為數據共享的通道。

ConcurrentSkipListMap : 跳表的實現。這是一個 Map，使用跳表的數據結構進行快速查找。

ConcurrentHashMap

我們知道 HashMap 不是線程安全的，在并發場景下如果要保證一種可行的方式是使用 Collections.synchronizedMap() 方法來包裝我們的 HashMap。但這是通過使用一個全局的鎖來同步不同線程間的并發訪問，因此會帶來不可忽視的性能問題。

所以就有了 HashMap 的線程安全版本—— ConcurrentHashMap 的誕生。

在 ConcurrentHashMap 中，無論是讀操作還是寫操作都能保證很高的性能：在進行讀操作時(幾乎)不需要加鎖，而在寫操作時通過鎖分段技術只對所操作的段加鎖而不影響客戶端對其它段的訪問。

CopyOnWriteArrayList

CopyOnWriteArrayList 簡介

public class CopyOnWriteArrayListE

extends Object

implements ListE, RandomAccess, Cloneable, Serializable

在很多應用場景中，讀操作可能會遠遠大于寫操作。由于讀操作根本不會修改原有的數據，因此對于每次讀取都進行加鎖其實是一種資源浪費。我們應該允許多個線程同時訪問 List 的內部數據，畢竟讀取操作是安全的。

這和我們之前在多線程章節講過 ReentrantReadWriteLock 讀寫鎖的思想非常類似，也就是讀讀共享、寫寫互斥、讀寫互斥、寫讀互斥。JDK 中提供了 CopyOnWriteArrayList 類比相比于在讀寫鎖的思想又更進一步。為了將讀取的性能發揮到極致，CopyOnWriteArrayList 讀取是完全不用加鎖的，并且更厲害的是：寫入也不會阻塞讀取操作。只有寫入和寫入之間需要進行同步等待。這樣一來，讀操作的性能就會大幅度提升。那它是怎么做的呢？

CopyOnWriteArrayList 是如何做到的？

CopyOnWriteArrayList 類的所有可變操作（add，set 等等）都是通過創建底層數組的新副本來實現的。當 List 需要被修改的時候，我并不修改原有內容，而是對原有數據進行一次復制，將修改的內容寫入副本。寫完之后，再將修改完的副本替換原來的數據，這樣就可以保證寫操作不會影響讀操作了。

從 CopyOnWriteArrayList 的名字就能看出 CopyOnWriteArrayList 是滿足 CopyOnWrite 的。所謂 CopyOnWrite 也就是說：在計算機，如果你想要對一塊內存進行修改時，我們不在原有內存塊中進行寫操作，而是將內存拷貝一份，在新的內存中進行寫操作，寫完之后呢，就將指向原來內存指針指向新的內存，原來的內存就可以被回收掉了。

CopyOnWriteArrayList 讀取和寫入源碼簡單分析

CopyOnWriteArrayList 讀取操作的實現

讀取操作沒有任何同步控制和鎖操作，理由就是內部數組 array 不會發生修改，只會被另外一個 array 替換，因此可以保證數據安全。

/** The array, accessed only via getArray/setArray. */

private transient volatile Object[] array;

public E get(int index) {

return get(getArray(), index);

}

@SuppressWarnings("unchecked")

private E get(Object[] a, int index) {

return (E) a[index];

}

final Object[] getArray() {

return array;

}

CopyOnWriteArrayList 寫入操作的實現

CopyOnWriteArrayList 寫入操作 add()方法在添加集合的時候加了鎖，保證了同步，避免了多線程寫的時候會 copy 出多個副本出來。

/**

* Appends the specified element to the end of this list.

*

* @param e element to be appended to this list

* @return {@code true} (as specified by {@link Collection#add})

*/

public boolean add(E e) {

final ReentrantLock lock = this.lock;

lock.lock();//加鎖

try {

Object[] elements = getArray();

int len = elements.length;

Object[] newElements = Arrays.copyOf(elements, len + 1);//拷貝新數組

newElements[len] = e;

setArray(newElements);

return true;

} finally {

lock.unlock();//釋放鎖

}

}

ConcurrentLinkedQueue

Java 提供的線程安全的 Queue 可以分為阻塞隊列和非阻塞隊列，其中阻塞隊列的典型例子是 BlockingQueue，非阻塞隊列的典型例子是 ConcurrentLinkedQueue，在實際應用中要根據實際需要選用阻塞隊列或者非阻塞隊列。 阻塞隊列可以通過加鎖來實現，非阻塞隊列可以通過 CAS 操作實現。

從名字可以看出，ConcurrentLinkedQueue這個隊列使用鏈表作為其數據結構．ConcurrentLinkedQueue 應該算是在高并發環境中性能最好的隊列了。它之所有能有很好的性能，是因為其內部復雜的實現。

ConcurrentLinkedQueue 內部代碼我們就不分析了，大家知道 ConcurrentLinkedQueue 主要使用 CAS 非阻塞算法來實現線程安全就好了。

ConcurrentLinkedQueue 適合在對性能要求相對較高，同時對隊列的讀寫存在多個線程同時進行的場景，即如果對隊列加鎖的成本較高則適合使用無鎖的 ConcurrentLinkedQueue 來替代。

BlockingQueue

BlockingQueue 簡介

上面我們己經提到了 ConcurrentLinkedQueue 作為高性能的非阻塞隊列。下面我們要講到的是阻塞隊列——BlockingQueue。阻塞隊列（BlockingQueue）被廣泛使用在“生產者-消費者”問題中，其原因是 BlockingQueue 提供了可阻塞的插入和移除的方法。當隊列容器已滿，生產者線程會被阻塞，直到隊列未滿；當隊列容器為空時，消費者線程會被阻塞，直至隊列非空時為止。

BlockingQueue 是一個接口，繼承自 Queue，所以其實現類也可以作為 Queue 的實現來使用，而 Queue 又繼承自 Collection 接口。下面是 BlockingQueue 的相關實現類：

BlockingQueue 的實現類

下面主要介紹一下 3 個常見的 BlockingQueue 的實現類：ArrayBlockingQueue、LinkedBlockingQueue 、PriorityBlockingQueue 。

ArrayBlockingQueue

ArrayBlockingQueue 是 BlockingQueue 接口的有界隊列實現類，底層采用數組來實現。

public class ArrayBlockingQueueE

extends AbstractQueueE

implements BlockingQueueE, Serializable{}

ArrayBlockingQueue 一旦創建，容量不能改變。其并發控制采用可重入鎖 ReentrantLock ，不管是插入操作還是讀取操作，都需要獲取到鎖才能進行操作。當隊列容量滿時，嘗試將元素放入隊列將導致操作阻塞;嘗試從一個空隊列中取一個元素也會同樣阻塞。

ArrayBlockingQueue 默認情況下不能保證線程訪問隊列的公平性，所謂公平性是指嚴格按照線程等待的絕對時間順序，即最先等待的線程能夠最先訪問到 ArrayBlockingQueue。而非公平性則是指訪問 ArrayBlockingQueue 的順序不是遵守嚴格的時間順序，有可能存在，當 ArrayBlockingQueue 可以被訪問時，長時間阻塞的線程依然無法訪問到 ArrayBlockingQueue。如果保證公平性，通常會降低吞吐量。如果需要獲得公平性的 ArrayBlockingQueue，可采用如下代碼：

private static ArrayBlockingQueueInteger blockingQueue = new ArrayBlockingQueueInteger(10,true);

1

1

LinkedBlockingQueue

LinkedBlockingQueue 底層基于單向鏈表實現的阻塞隊列，可以當做無界隊列也可以當做有界隊列來使用，同樣滿足 FIFO 的特性，與 ArrayBlockingQueue 相比起來具有更高的吞吐量，為了防止 LinkedBlockingQueue 容量迅速增，損耗大量內存。通常在創建 LinkedBlockingQueue 對象時，會指定其大小，如果未指定，容量等于 Integer.MAX_VALUE 。

相關構造方法:

/**

*某種意義上的無界隊列

* Creates a {@code LinkedBlockingQueue} with a capacity of

* {@link Integer#MAX_VALUE}.

*/

public LinkedBlockingQueue() {

this(Integer.MAX_VALUE);

}

/**

*有界隊列

* Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity.

*

* @param capacity the capacity of this queue

* @throws IllegalArgumentException if {@code capacity} is not greater

* than zero

*/

public LinkedBlockingQueue(int capacity) {

if (capacity = 0) throw new IllegalArgumentException();

this.capacity = capacity;

last = head = new NodeE(null);

}

PriorityBlockingQueue

PriorityBlockingQueue 是一個支持優先級的無界阻塞隊列。默認情況下元素采用自然順序進行排序，也可以通過自定義類實現 compareTo() 方法來指定元素排序規則，或者初始化時通過構造器參數 Comparator 來指定排序規則。

PriorityBlockingQueue 并發控制采用的是可重入鎖 ReentrantLock，隊列為無界隊列（ArrayBlockingQueue 是有界隊列，LinkedBlockingQueue 也可以通過在構造函數中傳入 capacity 指定隊列最大的容量，但是 PriorityBlockingQueue 只能指定初始的隊列大小，后面插入元素的時候，如果空間不夠的話會自動擴容）。

簡單地說，它就是 PriorityQueue 的線程安全版本。不可以插入 null 值，同時，插入隊列的對象必須是可比較大小的（comparable），否則報 ClassCastException 異常。它的插入操作 put 方法不會 block，因為它是無界隊列（take 方法在隊列為空的時候會阻塞）。

推薦文章： 《解讀 Java 并發隊列 BlockingQueue》open in new window

ConcurrentSkipListMap

下面這部分內容參考了極客時間專欄《數據結構與算法之美》open in new window以及《實戰 Java 高并發程序設計》。

為了引出 ConcurrentSkipListMap，先帶著大家簡單理解一下跳表。

對于一個單鏈表，即使鏈表是有序的，如果我們想要在其中查找某個數據，也只能從頭到尾遍歷鏈表，這樣效率自然就會很低，跳表就不一樣了。跳表是一種可以用來快速查找的數據結構，有點類似于平衡樹。它們都可以對元素進行快速的查找。但一個重要的區別是：對平衡樹的插入和刪除往往很可能導致平衡樹進行一次全局的調整。而對跳表的插入和刪除只需要對整個數據結構的局部進行操作即可。這樣帶來的好處是：在高并發的情況下，你會需要一個全局鎖來保證整個平衡樹的線程安全。而對于跳表，你只需要部分鎖即可。這樣，在高并發環境下，你就可以擁有更好的性能。而就查詢的性能而言，跳表的時間復雜度也是 O(logn) 所以在并發數據結構中，JDK 使用跳表來實現一個 Map。

跳表的本質是同時維護了多個鏈表，并且鏈表是分層的，

2級索引跳表

最低層的鏈表維護了跳表內所有的元素，每上面一層鏈表都是下面一層的子集。

跳表內的所有鏈表的元素都是排序的。查找時，可以從頂級鏈表開始找。一旦發現被查找的元素大于當前鏈表中的取值，就會轉入下一層鏈表繼續找。這也就是說在查找過程中，搜索是跳躍式的。如上圖所示，在跳表中查找元素 18。

在跳表中查找元素18

查找 18 的時候原來需要遍歷 18 次，現在只需要 7 次即可。針對鏈表長度比較大的時候，構建索引查找效率的提升就會非常明顯。

從上面很容易看出，跳表是一種利用空間換時間的算法。

使用跳表實現 Map 和使用哈希算法實現 Map 的另外一個不同之處是：哈希并不會保存元素的順序，而跳表內所有的元素都是排序的。因此在對跳表進行遍歷時，你會得到一個有序的結果。所以，如果你的應用需要有序性，那么跳表就是你不二的選擇。JDK 中實現這一數據結構的類是 ConcurrentSkipListMap。

文章標題：跳表代碼實現java 跳表代碼實現
分享路徑：http://vcdvsql.cn/article30/doicepo.html

成都網站建設公司_創新互聯，為您提供云服務器、軟件開發、外貿建站、響應式網站、網站改版、網站收錄

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯