• 延遲隊(duì)列
• 關(guān)鍵代碼
• 主要方法
• 增加take方法的效率
• End

ArrayList和LinkedList有什么區(qū)別？

這種侮辱人的問題，默認(rèn)就把這兩者限定在了同一個(gè)場景之中，它甚至連八股文都算不上。

一旦你被問到這種問題，也證明面試基本上泡湯了--面試官已經(jīng)實(shí)在是找不到其他問題與你交流了。

你Over了。

但當(dāng)我們細(xì)看一下LinkedList的class定義，就會發(fā)現(xiàn)，它并不像是ArrayList的那樣具有純潔的列表精神。

publicclassArrayList<E>extendsAbstractList<E>
implementsList<E>,RandomAccess,Cloneable,java.io.Serializable

//VS

publicclassLinkedList<E>
extendsAbstractSequentialList<E>
implementsList<E>,Deque<E>,Cloneable,java.io.Serializable

LinkedList除了能夠當(dāng)作普通的列表，它還是一個(gè)Deque。雙向鏈表，聽著就比較唬人，這就是一個(gè)既能當(dāng)做隊(duì)列、又能當(dāng)做棧的存在。

有了這種雙重Buff的疊加，LinkedList的應(yīng)用場景比ArrayList豐富的多。除了能做最簡單的LRU緩存，LinkedList在刷題的時(shí)候也是充滿了正能量。

王者ConcurrentLinkedQueue，一個(gè)阻塞的雙向隊(duì)列，它的基本操作方法有：(3[基本]x2[異常與返回值]+4[阻塞加超時(shí)])x3[隊(duì)頭隊(duì)尾]=5x2x3=30，足足有30個(gè)方法?？赐晟厦娴奈恼?，這30個(gè)方法可以很快手到擒來。

不過我們今天要聊的一個(gè)重點(diǎn)，是使用Deque來實(shí)現(xiàn)更快的延遲隊(duì)列。

延遲隊(duì)列

如果你想要某些數(shù)據(jù)延遲一段時(shí)間再進(jìn)行處理，或者要再某段時(shí)間內(nèi)按照分組進(jìn)行一些計(jì)算，那延遲隊(duì)列無疑是非常合適的。

在Java的Concurrent包里，就靜悄悄的躺著DelayQueue。只要你的數(shù)據(jù)實(shí)現(xiàn)了Delayed接口，那么就可以放心大膽的把它們往里面塞。

可惜的是，DelayQueue的底層存儲，使用的是PriorityQueue。

PriorityQueue是堆實(shí)現(xiàn)的，offer和poll數(shù)據(jù)的時(shí)間復(fù)雜度是O(logN)。這就意味著，當(dāng)DelayQueue中的數(shù)據(jù)比較多的時(shí)候，它的性能就會下降。

除了把數(shù)據(jù)分片，使用多個(gè)DelayQueue來完成工作，我們有沒有速度更快的方法？比如把PriorityQueue使用LinkedList來替換？

這要看場景。

如果你向DelayQueue中添加數(shù)據(jù)，是與當(dāng)前添加的時(shí)間相關(guān)的，那完全可以使用LinkedList來替換PriorityQueue。

基于 Spring Boot + MyBatis Plus + Vue & Element 實(shí)現(xiàn)的后臺管理系統(tǒng) + 用戶小程序，支持 RBAC 動(dòng)態(tài)權(quán)限、多租戶、數(shù)據(jù)權(quán)限、工作流、三方登錄、支付、短信、商城等功能

• 項(xiàng)目地址：https://github.com/YunaiV/ruoyi-vue-pro
• 視頻教程：https://doc.iocoder.cn/video/

關(guān)鍵代碼

要了解DelayQueue的運(yùn)行原理，我們可以需要先看一下Delayed接口。任何想要存儲到DelayQueue中的數(shù)據(jù)，都需要實(shí)現(xiàn)這個(gè)接口。

其中，getDelay就是用來判斷當(dāng)前數(shù)據(jù)是否超時(shí)的方法。而compareTo，則是PriorityQueue用來排序的，如果我們是按照當(dāng)前塞入數(shù)據(jù)的，則compareTo方法就不是必要的。

publiclonggetDelay(@NotNullTimeUnitunit){
returnMAX_CACHE_DUAL+this.enqueueTimeNs-System.nanoTime();
}
publicintcompareTo(@NotNullDelayedo){
longd=getDelay(TimeUnit.NANOSECONDS)-o.getDelay(TimeUnit.NANOSECONDS);
return(d==0)?0:(d0?-1:1);
}

按照以上的思路，我們把DelayQueue的代碼拷貝一份，僅保留關(guān)鍵代碼，如下。

publicclassLightweightDelayedQueue<EextendsDelayed>{
privatefinaltransientReentrantLocklock=newReentrantLock();
privatefinalLinkedListq=newLinkedList<>();
privatefinalConditionavailable=lock.newCondition();
privateThreadleader;

publicvoidput(Ee){
finalReentrantLocklock=this.lock;
lock.lock();
try{
q.offer(e);
if(q.peek()==e){
leader=null;
available.signal();
}
}finally{
lock.unlock();
}
}

publicEtake()throwsInterruptedException{
finalReentrantLocklock=this.lock;
lock.lockInterruptibly();
try{
for(;;){
Efirst=q.peek();
if(first==null)
available.await();
else{
longdelay=first.getDelay(NANOSECONDS);
if(delay<=?0L)
returnq.poll();
first=null;//don'tretainrefwhilewaiting
if(leader!=null)
available.await();
else{
ThreadthisThread=Thread.currentThread();
leader=thisThread;
try{
available.awaitNanos(delay);
}finally{
if(leader==thisThread)
leader=null;
}
}
}
}
}finally{
if(leader==null&&q.peek()!=null)
available.signal();
lock.unlock();
}
}

publicintsize(){
finalReentrantLocklock=this.lock;
lock.lock();
try{
returnq.size();
}finally{
lock.unlock();
}
}

publicintdrainTo(CollectionsuperE>c,intmaxElements){
Objects.requireNonNull(c);
if(c==this)
thrownewIllegalArgumentException();
if(maxElements<=?0)
return0;
finalReentrantLocklock=this.lock;
lock.lock();
try{
intn=0;
for(Efirst;
nnull
&&first.getDelay(NANOSECONDS)<=?0;){
c.add(first);//Inthisorder,incaseadd()throws.
q.poll();
++n;
}
returnn;
}finally{
lock.unlock();
}
}
}

基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 實(shí)現(xiàn)的后臺管理系統(tǒng) + 用戶小程序，支持 RBAC 動(dòng)態(tài)權(quán)限、多租戶、數(shù)據(jù)權(quán)限、工作流、三方登錄、支付、短信、商城等功能

• 項(xiàng)目地址：https://github.com/YunaiV/yudao-cloud
• 視頻教程：https://doc.iocoder.cn/video/

主要方法

輕量級的延遲隊(duì)列，如果一旦采用了LinkedList，那么它的入隊(duì)、出隊(duì)方法，就都變成了O(1)的時(shí)間復(fù)雜度。在延遲隊(duì)列中的數(shù)據(jù)增加時(shí)，時(shí)間復(fù)雜度也能維持不變，可以說是速度快的連兔子都追不上了。

一般，在java中，put和take方法，都是代表阻塞性方法。比如，take方法，我們可以將其安全的阻塞在某個(gè)線程上，而不用擔(dān)心太多的資源浪費(fèi)。

finalThreadthread=Thread.currentThread();
while(!this.close&&!thread.isInterrupted()){
Datadata=q.take();
}

這一切都是Condition辦到的，它和wait、notify的作用是一樣的。

當(dāng)我們通過put方法添加新的數(shù)據(jù)到隊(duì)列中，會通過signal方法，來通知等待的線程獲取數(shù)據(jù)。

相同的，如果take方法發(fā)現(xiàn)隊(duì)列中的數(shù)據(jù)為空，它將進(jìn)入等待狀態(tài)。如果有數(shù)據(jù)，也并不是馬上把這些數(shù)據(jù)取出來，因?yàn)閿?shù)據(jù)還沒到期。比如最老的數(shù)據(jù)還剩下5秒才到期，代碼也對這種情況進(jìn)行了處理，它會嘗試awaitNanos對應(yīng)的時(shí)間。

這樣，我們就可以使用這種簡單的輪詢方式來實(shí)現(xiàn)延遲隊(duì)列，而不需要單獨(dú)的線程去檢測隊(duì)列中的數(shù)據(jù)。

增加take方法的效率

但是這樣還不夠。

當(dāng)數(shù)據(jù)量比較大的時(shí)候，隊(duì)列的數(shù)據(jù)可能有多條已經(jīng)到期。如果我們通過take方法來一條一條獲取的話，效率自然不如批量獲取高。

drainTo方法，可以一股腦的把到期的數(shù)據(jù)轉(zhuǎn)移到其他的集合中，但它并不是一個(gè)阻塞性的方法。

我們可以先使用take來阻塞線程，然后再批量取出所有數(shù)據(jù)。

下面代碼，會一次性獲取100條數(shù)據(jù)作為一個(gè)批量。

finalDatatakeItem=q.take();
finalListbuckets=newArrayList<>(100);
q.drainTo(buckets,99);
buckets.add(takeItem);

End

實(shí)際上，我們的某個(gè)業(yè)務(wù)，當(dāng)采用LinkedList來替代PriorityQueue，并進(jìn)行批量操作后，CPU的使用直接降低了1/3。

Deque是xjjdog最喜歡的一個(gè)接口。每當(dāng)使用offerFirst、offerLast這樣精準(zhǔn)的API進(jìn)行操作，都會體驗(yàn)到多巴胺的樂趣。LinkedList作為它的兒子，自然擁有了這些所有的功能。

當(dāng)我們使用concurrent包里的基本API，對這些淳樸的工具進(jìn)行封裝，它們就會煥發(fā)出新的活力。