## 23 隊列在源碼方面的面試題 ## 引導語 隊列在源碼方面的面試題，一般面試官會從鎖，線程池等知識點作為問題入口，慢慢的問到隊列，由于鎖、線程池咱們還沒有學習到，所以本章就直奔主題，從隊列入手，看看隊列都有哪些面試題（隊列種類很多，本文在說隊列的通用特征時，都是在說其大部分隊列的通用特征，如有某種隊列特征不符，不在一一說明）。 ### 1 面試題 #### 1.1 說說你對隊列的理解，隊列和集合的區別。 答：對隊列的理解： 1. 首先隊列本身也是個容器，底層也會有不同的數據結構，比如 LinkedBlockingQueue 是底層是鏈表結構，所以可以維持先入先出的順序，比如 DelayQueue 底層可以是隊列或堆棧，所以可以保證先入先出，或者先入后出的順序等等，底層的數據結構不同，也造成了操作實現不同； 2. 部分隊列（比如 LinkedBlockingQueue ）提供了暫時存儲的功能，我們可以往隊列里面放數據，同時也可以從隊列里面拿數據，兩者可以同時進行； 3. 隊列把生產數據的一方和消費數據的一方進行解耦，生產者只管生產，消費者只管消費，兩者之間沒有必然聯系，隊列就像生產者和消費者之間的數據通道一樣，如 LinkedBlockingQueue； 4. 隊列還可以對消費者和生產者進行管理，比如隊列滿了，有生產者還在不停投遞數據時，隊列可以使生產者阻塞住，讓其不再能投遞，比如隊列空時，有消費者過來拿數據時，隊列可以讓消費者hodler 住，等有數據時，喚醒消費者，讓消費者拿數據返回，如 ArrayBlockingQueue； 5. 隊列還提供阻塞的功能，比如我們從隊列拿數據，但隊列中沒有數據時，線程會一直阻塞到隊列有數據可拿時才返回。 隊列和集合的區別： 1. 和集合的相同點，隊列（部分例外）和集合都提供了數據存儲的功能，底層的儲存數據結構是有些相似的，比如說 LinkedBlockingQueue 和 LinkedHashMap 底層都使用的是鏈表，ArrayBlockingQueue 和 ArrayList 底層使用的都是數組。 2. 和集合的區別： 2.1 部分隊列和部分集合底層的存儲結構很相似的，但兩者為了完成不同的事情，提供的 API 和其底層的操作實現是不同的。 2.2 隊列提供了阻塞的功能，能對消費者和生產者進行簡單的管理，隊列空時，會阻塞消費者，有其他線程進行 put 操作后，會喚醒阻塞的消費者，讓消費者拿數據進行消費，隊列滿時亦然。 2.3 解耦了生產者和消費者，隊列就像是生產者和消費者之間的管道一樣，生產者只管往里面丟，消費者只管不斷消費，兩者之間互不關心。 #### 1.2 哪些隊列具有阻塞的功能，大概是如何阻塞的？ 答：隊列主要提供了兩種阻塞功能，如下： 1. LinkedBlockingQueue 鏈表阻塞隊列和 ArrayBlockingQueue 數組阻塞隊列是一類，前者容量是 Integer 的最大值，后者數組大小固定，兩個阻塞隊列都可以指定容量大小，當隊列滿時，如果有線程 put 數據，線程會阻塞住，直到有其他線程進行消費數據后，才會喚醒阻塞線程繼續 put，當隊列空時，如果有線程 take 數據，線程會阻塞到隊列不空時，繼續 take。 2. SynchronousQueue 同步隊列，當線程 put 時，必須有對應線程把數據消費掉，put 線程才能返回，當線程 take 時，需要有對應線程進行 put 數據時，take 才能返回，反之則阻塞，舉個例子，線程 A put 數據 A1 到隊列中了，此時并沒有任何的消費者，線程 A 就無法返回，會阻塞住，直到有線程消費掉數據 A1 時，線程 A 才能返回。 #### 1.3 底層是如何實現阻塞的？ 答：隊列本身并沒有實現阻塞的功能，而是利用 Condition 的等待喚醒機制，阻塞底層實現就是更改線程的狀態為沉睡，細節我們在鎖小節會說到。 #### 1.4 LinkedBlockingQueue 和 ArrayBlockingQueue 有啥區別。 答： 相同點： 1. 兩者的阻塞機制大體相同，比如在隊列滿、空時，線程都會阻塞住。 不同點： 1. LinkedBlockingQueue 底層是鏈表結構，容量默認是 Interge 的最大值，ArrayBlockingQueue 底層是數組，容量必須在初始化時指定。 2. 兩者的底層結構不同，所以 take、put、remove 的底層實現也就不同。 #### 1.5 往隊列里面 put 數據是線程安全的么？為什么？ 答：是線程安全的，在 put 之前，隊列會自動加鎖，put 完成之后，鎖會自動釋放，保證了同一時刻只會有一個線程能操作隊列的數據，以 LinkedBlockingQueue 為例子，put 時，會加 put 鎖，并只對隊尾 tail 進行操作，take 時，會加 take 鎖，并只對隊頭 head 進行操作，remove 時，會同時加 put 和 take 鎖，所以各種操作都是線程安全的，我們工作中可以放心使用。 #### 1.6 take 的時候也會加鎖么？既然 put 和 take 都會加鎖，是不是同一時間只能運行其中一個方法。 答：1：是的，take 時也會加鎖的，像 LinkedBlockingQueue 在執行 take 方法時，在拿數據的同時，會把當前數據刪除掉，就改變了鏈表的數據結構，所以需要加鎖來保證線程安全。 2：這個需要看情況而言，對于 LinkedBlockingQueue 來說，隊列的 put 和 take 都會加鎖，但兩者的鎖是不一樣的，所以兩者互不影響，可以同時進行的，對于 ArrayBlockingQueue 而言，put 和 take 是同一個鎖，所以同一時刻只能運行一個方法。 #### 1.7 工作中經常使用隊列的 put、take 方法有什么危害，如何避免。 答：當隊列滿時，使用 put 方法，會一直阻塞到隊列不滿為止。 當隊列空時，使用 take 方法，會一直阻塞到隊列有數據為止。 兩個方法都是無限（永遠、沒有超時時間的意思）阻塞的方法，容易使得線程全部都阻塞住，大流量時，導致機器無線程可用，所以建議在流量大時，使用 offer 和 poll 方法來代替兩者，我們只需要設置好超時阻塞時間，這兩個方法如果在超時時間外，還沒有得到數據的話，就會返回默認值（LinkedBlockingQueue 為例），這樣就不會導致流量大時，所有的線程都阻塞住了。 這個也是生產事故常常發生的原因之一，嘗試用 put 和 take 方法，在平時自測中根本無法發現，對源碼不熟悉的同學也不會意識到會有問題，當線上大流量打進來時，很有可能會發生故障，所以我們平時工作中使用隊列時，需要謹慎再謹慎。 #### 1.8 把數據放入隊列中后，有木有辦法讓隊列過一會兒再執行？ 答：可以的，DelayQueue 提供了這種機制，可以設置一段時間之后再執行，該隊列有個唯一的缺點，就是數據保存在內存中，在重啟和斷電的時候，數據容易丟失，所以定時的時間我們都不 會設置很久，一般都是幾秒內，如果定時的時間需要設置很久的話，可以考慮采取延遲隊列中間件（這種中間件對數據會進行持久化，不怕斷電的發生）進行實現。 #### 1.9 DelayQueue 對元素有什么要求么，我把 String 放到隊列中去可以么？ 答：DelayQueue 要求元素必須實現 Delayed 接口，Delayed 本身又實現了 Comparable 接口，Delayed 接口的作用是定義還剩下多久就會超時，給使用者定制超時時間的，Comparable 接口主要用于對元素之間的超時時間進行排序的，兩者結合，就可以讓越快過期的元素能夠排在前面。 所以把 String 放到 DelayQueue 中是不行的，編譯都無法通過，DelayQueue 類在定義的時候，是有泛型定義的，泛型類型必須是 Delayed 接口的子類才行。 #### 1.10 DelayQueue 如何讓快過期的元素先執行的？ 答：DelayQueue 中的元素都實現 Delayed 和 Comparable 接口的，其內部會使用 Comparable 的 compareTo 方法進行排序，我們可以利用這個功能，在 compareTo 方法中實現過期時間和當前時間的差，這樣越快過期的元素，計算出來的差值就會越小，就會越先被執行。 #### 1.11 如何查看 SynchronousQueue 隊列的大小？ 答：此題是個陷進題，題目首先設定了 SynchronousQueue 是可以查看大小的，實際上 SynchronousQueue 本身是沒有容量的，所以也無法查看其容量的大小，其內部的 size 方法都是寫死的返回 0。 #### 1.12 SynchronousQueue 底層有幾種數據結構，兩者有何不同？ 答：底層有兩種數據結構，分別是隊列和堆棧。 兩者不同點： 1. 隊列維護了先入先出的順序，所以最先進去隊列的元素會最先被消費，我們稱為公平的，而堆棧則是先入后出的順序，最先進入堆棧中的數據可能會最后才會被消費，我們稱為不公平的。 2. 兩者的數據結構不同，導致其 take 和 put 方法有所差別，具體的可以看 《 SynchronousQueue 源碼解析 》章節。 #### 1.13 假設 SynchronousQueue 底層使用的是堆棧，線程 1 執行 take 操作阻塞住了，然后有線程 2 執行 put 操作，問此時線程 2 是如何把 put 的數據傳遞給 take 的？ 答：這是一個好問題，也是理解 SynchronousQueue 的核心問題。 首先線程 1 被阻塞住，此時堆棧頭就是線程 1 了，此時線程 2 執行 put 操作，會把 put 的數據賦值給堆棧頭的 match 屬性，并喚醒線程 1，線程 1 被喚醒后，拿到堆棧頭中的 match 屬性，就能夠拿到 put 的數據了。 嚴格上說并不是 put 操作直接把數據傳遞給了 take，而是 put 操作改變了堆棧頭的數據，從而 take 可以從堆棧頭上直接拿到數據，堆棧頭是 take 和 put 操作之間的溝通媒介。 #### 1.14 如果想使用固定大小的隊列，有幾種隊列可以選擇，有何不同？ 答：可以使用 LinkedBlockingQueue 和 ArrayBlockingQueue 兩種隊列。 前者是鏈表，后者是數組，鏈表新增時，只要建立起新增數據和鏈尾數據之間的關聯即可，數組新增時，需要考慮到索引的位置（takeIndex 和 putIndex 分別記錄著下次拿數據、放數據的索引位置），如果增加到了數組最后一個位置，下次就要重頭開始新增。 #### 1.15 ArrayBlockingQueue 可以動態擴容么？用到數組最后一個位置時怎么辦？ 答：不可以的，雖然 ArrayBlockingQueue 底層是數組，但不能夠動態擴容的。 假設 put 操作用到了數組的最后一個位置，那么下次 put 就需要從數組 0 的位置重新開始了。 假設 take 操作用到數組的最后一個位置，那么下次 take 的時候也會從數組 0 的位置重新開始。 #### 1.16 ArrayBlockingQueue take 和 put 都是怎么找到索引位置的？是利用 hash 算法計算得到的么？ 答：ArrayBlockingQueue 有兩個屬性，為 takeIndex 和 putIndex，分別標識下次 take 和 put 的位置，每次 take 和 put 完成之后，都會往后加一，雖然底層是數組，但和 HashMap 不同，并不是通過 hash 算法計算得到的。