概览
我们先来看一看 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 集合之 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 源码分析
死磕 java 集合之 LinkedList 源码分析
总结
其实上面的问题很多都具有共性,我觉得以下几个问题在看每个集合类的时候都要掌握清楚:
(1)使用的数据结构?
(2)添加元素、删除元素的基本逻辑?
(3)是否是 fail-fast 的?
(4)是否需要扩容?扩容规则?
(5)是否有序?是按插入顺序还是自然顺序还是访问顺序?
(6)是否线程安全?
(7)使用的锁?
(8)优点?缺点?
(9)适用的场景?
(10)时间复杂度?
(11)空间复杂度?
(12)还有呢?
彩蛋
到这里整个集合的内容就全部完毕了,其实看了这么多集合的源码之后,笔者发现,基本上所有集合类使用的数据结构都是数组和链表,包括树和跳表也可以看成是链表的一种方式。
对于并发安全的集合,还要再加上相应的锁策略,要不就是重入锁,要不就是 CAS+ 自旋,偶尔也来个 synchronized。
所以,掌握集合的源码不算什么,数据结构和锁才是王道。
预告:下一个专题是 java 并发包,也就是著名的 JUC,当然这里是除了并发集合以外的内容,也就是原子类、各种锁、线程池三块硬骨头。
欢迎关注我的公众号“彤哥读源码”,查看更多源码系列文章, 与彤哥一起畅游源码的海洋。