java中的集合分成哪幾類?
java中的集合常見面試題有哪些?
java中的集合你不知道的那些事?
概覽
我們先來看一看java中所有集合的類關系圖。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLx42bpR3YlxGbvN2LcV2YyV3bzVmcvw1N5UCO4USNFViQCVyMCVyNFVCO4UCM5USNFViN4UiQ5USOFVSY2FmawITJ1kTJzEUJ3UUJCJUJEFUJ2UUJvwlclR3ch12LcdXYy9CXuFWd59CX0RXLn5WY01ibhxWYvwVbvNmLlVGdpd2Lc9CX6MHc0RHaiojIsJye.png)
這裡面的類太多了,請放大看,如果放大還看不清,請再放大看,如果還是看不清,請放棄。
我們下面主要分成五個部分來逐個擊破。
List
List中的元素是有序的、可重複的,主要實作方式有動态數組和連結清單。
java中提供的List的實作主要有ArrayList、LinkedList、CopyOnWriteArrayList,另外還有兩個古老的類Vector和Stack。
關于List相關的問題主要有:
(1)ArrayList和LinkedList有什麼差別?
(2)ArrayList是怎麼擴容的?
(3)ArrayList插入、删除、查詢元素的時間複雜度各是多少?
(4)怎麼求兩個集合的并集、交集、差集?
(5)ArrayList是怎麼實作序列化和反序列化的?
(6)集合的方法toArray()有什麼問題?
(7)什麼是fail-fast?
(8)LinkedList是單連結清單還是雙連結清單實作的?
(9)LinkedList除了作為List還有什麼用處?
(10)LinkedList插入、删除、查詢元素的時間複雜度各是多少?
(11)什麼是随機通路?
(12)哪些集合支援随機通路?他們都有哪些共性?
(13)CopyOnWriteArrayList是怎麼保證并發安全的?
(14)CopyOnWriteArrayList的實作采用了什麼思想?
(15)CopyOnWriteArrayList是不是強一緻性的?
(16)CopyOnWriteArrayList适用于什麼樣的場景?
(17)CopyOnWriteArrayList插入、删除、查詢元素的時間複雜度各是多少?
(18)CopyOnWriteArrayList為什麼沒有size屬性?
(19)比較古老的集合Vector和Stack有什麼缺陷?
關于List的問題大概就這麼多,你都能回答上來嗎?
點選下面連結可以直接到相應的章節檢視:
死磕 Java集合之ArrayList源碼分析
死磕 java集合之LinkedList源碼分析
死磕 java集合之CopyOnWriteArrayList源碼分析
Map
Map是一種(key/value)的映射結構,其它語言裡可能稱作字典(Dictionary),包括java早期也是叫做字典,Map中的元素是一個key隻能對應一個value,不能存在重複的key。
java中提供的Map的實作主要有HashMap、LinkedHashMap、WeakHashMap、TreeMap、ConcurrentHashMap、ConcurrentSkipListMap,另外還有兩個比較古老的Map實作HashTable和Properties。
關于Map的問題主要有:
(1)什麼是散清單?
(2)怎麼實作一個散清單?
(3)java中HashMap實作方式的演進?
(4)HashMap的容量有什麼特點?
(5)HashMap是怎麼進行擴容的?
(6)HashMap中的元素是否是有序的?
(7)HashMap何時進行樹化?何時進行反樹化?
(8)HashMap是怎麼進行縮容的?
(9)HashMap插入、删除、查詢元素的時間複雜度各是多少?
(10)HashMap中的紅黑樹實作部分可以用其它資料結構代替嗎?
(11)LinkedHashMap是怎麼實作的?
(12)LinkedHashMap是有序的嗎?怎麼個有序法?
(13)LinkedHashMap如何實作LRU緩存淘汰政策?
(14)WeakHashMap使用的資料結構?
(15)WeakHashMap具有什麼特性?
(16)WeakHashMap通常用來做什麼?
(17)WeakHashMap使用String作為key是需要注意些什麼?為什麼?
(18)什麼是弱引用?
(19)紅黑樹具有哪些特性?
(20)TreeMap就有序的嗎?怎麼個有序法?
(21)TreeMap是否需要擴容?
(22)什麼是左旋?什麼是右旋?
(23)紅黑樹怎麼插入元素?
(24)紅黑樹怎麼删除元素?
(25)為什麼要進行平衡?
(26)如何實作紅黑樹的周遊?
(27)TreeMap中是怎麼周遊的?
(28)TreeMap插入、删除、查詢元素的時間複雜度各是多少?
(29)HashMap在多線程環境中什麼時候會出現問題?
(30)ConcurrentHashMap的存儲結構?
(31)ConcurrentHashMap是怎麼保證并發安全的?
(32)ConcurrentHashMap是怎麼擴容的?
(33)ConcurrentHashMap的size()方法的實作知多少?
(34)ConcurrentHashMap是強一緻性的嗎?
(35)ConcurrentHashMap不能解決什麼問題?
(36)ConcurrentHashMap中哪些地方運用到分段鎖的思想?
(37)什麼是僞共享?怎麼避免僞共享?
(38)什麼是跳表?
(40)ConcurrentSkipList是有序的嗎?
(41)ConcurrentSkipList是如何保證線程安全的?
(42)ConcurrentSkipList插入、删除、查詢元素的時間複雜度各是多少?
(43)ConcurrentSkipList的索引具有什麼特性?
(44)為什麼Redis選擇使用跳表而不是紅黑樹來實作有序集合?
關于Map的問題大概就這麼多,你都能回答上來嗎?
死磕 java集合之HashMap源碼分析
死磕 java集合之LinkedHashMap源碼分析
死磕 java集合之WeakHashMap源碼分析
死磕 java集合之TreeMap源碼分析(一)
死磕 java集合之TreeMap源碼分析(二)
死磕 java集合之TreeMap源碼分析(三)
死磕 java集合之TreeMap源碼分析(四)
死磕 java集合之ConcurrentHashMap源碼分析(一)
死磕 java集合之ConcurrentHashMap源碼分析(二)
死磕 java集合之ConcurrentHashMap源碼分析(三)
死磕 java集合之ConcurrentSkipListMap源碼分析
Set
java裡面的Set對應于數學概念上的集合,裡面的元素是不可重複的,通常使用Map或者List來實作。
java中提供的Set的實作主要有HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipSet。
關于Set的問題主要有:
(1)HashSet怎麼保證添加元素不重複?
(2)HashSet是有序的嗎?
(3)HashSet是否允許null元素?
(4)Set是否有get()方法?
(5)LinkedHashSet是有序的嗎?怎麼個有序法?
(6)LinkedHashSet支援按元素通路順序排序嗎?
(8)TreeSet真的是使用TreeMap來存儲元素的嗎?
(9)TreeSet是有序的嗎?怎麼個有序法?
(10)TreeSet和LinkedHashSet有何不同?
(11)TreeSet和SortedSet有什麼差別和聯系?
(12)CopyOnWriteArraySet是用Map實作的嗎?
(13)CopyOnWriteArraySet是有序的嗎?怎麼個有序法?
(14)CopyOnWriteArraySet怎麼保證并發安全?
(15)CopyOnWriteArraySet以何種方式保證元素不重複?
(16)如何比較兩個Set中的元素是否完全一緻?
(17)ConcurrentSkipListSet的底層是ConcurrentSkipListMap嗎?
(18)ConcurrentSkipListSet是有序的嗎?怎麼個有序法?
關于Set的問題大概就這麼多,你都能回答上來嗎?
死磕 java集合之HashSet源碼分析
死磕 java集合之LinkedHashSet源碼分析
死磕 java集合之TreeSet源碼分析
死磕 java集合之CopyOnWriteArraySet源碼分析
死磕 java集合之ConcurrentSkipListSet源碼分析
Queue
Queue是一種叫做隊列的資料結構,隊列是遵循着一定原則的入隊出隊操作的集合,一般來說,入隊是在隊列尾添加元素,出隊是在隊列頭删除元素,但是,也不一定,比如優先級隊列的原則就稍微有些不同。
java中提供的Queue的實作主要有PriorityQueue、ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityBlockingQueue、LinkedTransferQueue、DelayQueue、ConcurrentLinkedQueue。
關于Queue的問題主要有:
(1)什麼是堆?什麼是堆化?
(2)什麼是優先級隊列?
(3)PriorityQueue是怎麼實作的?
(4)PriorityQueue是有序的嗎?
(5)PriorityQueue入隊、出隊的時間複雜度各是多少?
(6)PriorityQueue是否需要擴容?擴容規則呢?
(7)ArrayBlockingQueue的實作方式?
(8)ArrayBlockingQueue是否需要擴容?
(9)ArrayBlockingQueue怎麼保證線程安全?
(9)ArrayBlockingQueue有什麼缺點?
(10)LinkedBlockingQueue的實作方式?
(11)LinkedBlockingQueue是有界的還是無界的隊列?
(12)LinkedBlockingQueue怎麼保證線程安全?
(13)LinkedBlockingQueue與ArrayBlockingQueue對比?
(14)SynchronousQueue的實作方式?
(15)SynchronousQueue真的是無緩沖的嗎?
(16)SynchronousQueue怎麼保證線程安全?
(17)SynchronousQueue的公平模式和非公平模式有什麼差別?
(18)SynchronousQueue在高并發情景下會有什麼問題?
(19)PriorityBlockingQueue的實作方式?
(20)PriorityBlockingQueue是否需要擴容?
(21)PriorityBlockingQueue怎麼保證線程安全?
(22)PriorityBlockingQueue為什麼不需要notFull條件?
(23)什麼是雙重隊列?
(24)LinkedTransferQueue是怎麼實作阻塞隊列的?
(25)LinkedTransferQueue是怎麼控制并發安全的?
(26)LinkedTransferQueue與SynchronousQueue有什麼異同?
(27)ConcurrentLinkedQueue是阻塞隊列嗎?
(28)ConcurrentLinkedQueue如何保證并發安全?
(29)ConcurrentLinkedQueue能用于線程池嗎?
(30)DelayQueue是阻塞隊列嗎?
(31)DelayQueue的實作方式?
(32)DelayQueue主要用于什麼場景?
關于Queue的問題大概就這麼多,你都能回答上來嗎?
死磕 java集合之PriorityQueue源碼分析
死磕 java集合之ArrayBlockingQueue源碼分析
死磕 java集合之LinkedBlockingQueue源碼分析
死磕 java集合之SynchronousQueue源碼分析
死磕 java集合之PriorityBlockingQueue源碼分析
死磕 java集合之LinkedTransferQueue源碼分析
死磕 java集合之ConcurrentLinkedQueue源碼分析
死磕 java集合之DelayQueue源碼分析
Deque
Deque是一種特殊的隊列,它的兩端都可以進出元素,故而得名雙端隊列(Double Ended Queue)。
java中提供的Deque的實作主要有ArrayDeque、LinkedBlockingDeque、ConcurrentLinkedDeque、LinkedList。
關于Deque的問題主要有:
(1)什麼是雙端隊列?
(2)ArrayDeque是怎麼實作雙端隊列的?
(3)ArrayDeque是有界的嗎?
(4)LinkedList與ArrayDeque的對比?
(5)雙端隊列是否可以作為棧使用?
(6)LinkedBlockingDeque是怎麼實作雙端隊列的?
(7)LinkedBlockingDeque是怎麼保證并發安全的?
(8)ConcurrentLinkedDeque是怎麼實作雙端隊列的?
(9)ConcurrentLinkedDeque是怎麼保證并發安全的?
(10)LinkedList是List和Deque的集合體?
關于Deque的問題大概就這麼多,你都能回答上來嗎?
點選下面連結可以直接到相應的章節檢視(LinkedBlockingDeque和ConcurrentLinkedDeque跟相應的Queue的實作方式基本一緻,是以筆者沒寫這兩個類的源碼分析):
死磕 java集合之ArrayDeque源碼分析
總結
其實上面的問題很多都具有共性,我覺得以下幾個問題在看每個集合類的時候都要掌握清楚:
(1)使用的資料結構?
(2)添加元素、删除元素的基本邏輯?
(3)是否是fail-fast的?
(4)是否需要擴容?擴容規則?
(5)是否有序?是按插入順序還是自然順序還是通路順序?
(6)是否線程安全?
(7)使用的鎖?
(8)優點?缺點?
(9)适用的場景?
(10)時間複雜度?
(11)空間複雜度?
(12)還有呢?
彩蛋
到這裡整個集合的内容就全部完畢了,其實看了這麼多集合的源碼之後,筆者發現,基本上所有集合類使用的資料結構都是數組和連結清單,包括樹和跳表也可以看成是連結清單的一種方式。
對于并發安全的集合,還要再加上相應的鎖政策,要不就是重入鎖,要不就是CAS+自旋,偶爾也來個synchronized。
是以,掌握集合的源碼不算什麼,資料結構和鎖才是王道。
預告:下一個專題是java并發包,也就是著名的JUC,當然這裡是除了并發集合以外的内容,也就是原子類、各種鎖、線程池三塊硬骨頭。
歡迎關注我的公衆号“彤哥讀源碼”,檢視更多源碼系列文章, 與彤哥一起暢遊源碼的海洋。