java中的集合分成哪幾類? java中的集合常見面試題有哪些? java中的集合你不知道的那些事? ...
概覽
我們先來看一看java中所有集合的類關係圖。
這裡面的類太多了,請放大看,如果放大還看不清,請再放大看,如果還是看不清,請放棄。
我們下麵主要分成五個部分來逐個擊破。
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集合之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集合之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集合之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集合之ArrayBlockingQueue源碼分析
死磕 java集合之LinkedBlockingQueue源碼分析
死磕 java集合之SynchronousQueue源碼分析
死磕 java集合之PriorityBlockingQueue源碼分析
死磕 java集合之LinkedTransferQueue源碼分析
死磕 java集合之ConcurrentLinkedQueue源碼分析
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的實現方式基本一致,所以筆者沒寫這兩個類的源碼分析):
總結
其實上面的問題很多都具有共性,我覺得以下幾個問題在看每個集合類的時候都要掌握清楚:
(1)使用的數據結構?
(2)添加元素、刪除元素的基本邏輯?
(3)是否是fail-fast的?
(4)是否需要擴容?擴容規則?
(5)是否有序?是按插入順序還是自然順序還是訪問順序?
(6)是否線程安全?
(7)使用的鎖?
(8)優點?缺點?
(9)適用的場景?
(10)時間複雜度?
(11)空間複雜度?
(12)還有呢?
彩蛋
到這裡整個集合的內容就全部完畢了,其實看了這麼多集合的源碼之後,筆者發現,基本上所有集合類使用的數據結構都是數組和鏈表,包括樹和跳錶也可以看成是鏈表的一種方式。
對於併發安全的集合,還要再加上相應的鎖策略,要不就是重入鎖,要不就是CAS+自旋,偶爾也來個synchronized。
所以,掌握集合的源碼不算什麼,數據結構和鎖才是王道。
預告:下一個專題是java併發包,也就是著名的JUC,當然這裡是除了併發集合以外的內容,也就是原子類、各種鎖、線程池三塊硬骨頭。
歡迎關註我的公眾號“彤哥讀源碼”,查看更多源碼系列文章, 與彤哥一起暢游源碼的海洋。