关于List、Set
手画Collection结构图（Vector和Stack已经废弃）
集合框架图.png
Collection思维导图
Collection下集合的类关键词
- List 有序，可重复集合
- Set 无序，不可重复集合
- Queue 先进先出队列
- Deque 双向队列
- Array 数组方式实现，内存上不连续
- Linked 链表方式实现，内存上连续
- CopyOnWrite 采用写入时复制技术
- SkipList 采用跳表技术提高搜索效率
- Concurrent 非阻塞的方式实现线程安全
- Blocking 阻塞方式实现线程安全
Collection下哪些是线程安全的？
- CopyOnWrite系列：CopyOnWriteArrayList、CopyOnWriteArraySet
- Concurrent系列：ConcurrentLinkedQueue、ConcurrentLinkedDeque、ConcurrentSkipListSet
- Blocking系列：ArrayBlockingQueue、LinkedBlockingQueue、LinkedBlockingDeque、DelayQueue、SynchronousQueue、PriorityBlockingQueue
ArrayList和LinkedList的差异
- 结构上：ArrayList数组实现，内存连续，LinkedList 链表实现，内存不连续
- 在随机访问上：ArrayList更快
- 插入/删除：LinkedList更快
ArrayList是如何扩容的
- 计算最小需要空间
- 判断是否需要扩容
- 扩容到原来的1.5倍
- 使用System.arraycopy方法将数据复制到新的内存空间
ArrayList扩容因子为什么是1.5倍
真实的倍数为oldCapacity + (oldCapacity >> 1)，约等于1.5倍，这么设计应该是出于位运算性能的考虑。
fast-fail机制
- 对集合的每一次增删操作都会增加modCount的值
- iterator遍历集合前会记录该值
- 调用next方法时会校验该值是否发生改变，如果改变抛出并发修改异常。
fast-fail机制常发生在哪些场景
- 多线程对Util包下集合的并发操作（可通过使用CopyOnWrite系列类）
- 遍历集合的同时进行增删操作（可通过使用Iterator的增删方法）
- subList后对主列表的增删，将导致子列表的遍历、增、删报错
并发容器CopyOnWrite系列类
- 读写分离，如果是写操作，则复制一个新集合，在新集合内添加或删除元素。待一切修改完成之后，再将原集合的引用指向新的集合
- 扩容的空间代价比较大
- 使用批量添加或删除方法
- 适用于读多写极少的情况
关于队列
各队列特点
| 队列 | 数据结构 | 是否有界 | 线程安全 |
|---|---|---|---|
| ArrayBlockingQueue | 数组 | 有 | ReentrantLock保证出入队线程安全 |
| LinkedBlockingQueue | 链表 | 无 | 出入队锁分别使用ReentrantLock |
| DelayQueue | 二叉堆 | 无 | 同上 |
| PriorityBlockingQueue | 二叉堆 | 无 | 同上 |
| SynchronousQueue | 队列或堆栈 | - | CAS保证出入队线程安全 |
队列方法
| 方法名 | 描述 | 备注 |
|---|---|---|
| add | 增加一个元索 | 如果队列已满，则抛出异常 |
| remove | 移除并返回队列头部的元素 | 如果队列为空，则抛出异常 |
| element | 返回队列头部的元素 | 如果队列为空，则抛出异常 |
| offer | 添加一个元素并返回true | 如果队列已满，则返回false |
| poll | 移除并返问队列头部的元素 | 如果队列为空，则返回null |
| peek | 返回队列头部的元素 | 如果队列为空，则返回null |
| put | 添加一个元素 | 如果队列满，则阻塞 |
| take | 移除并返回队列头部的元素 | 如果队列为空，则阻塞 |
ArrayBlockingQueue 入队代码流程
- 获取锁
- 判断是否已满，满则等待
- 加入数组
- 唤醒出队线程
为什么ArrayBlockingQueue单锁实现，而LinkedBlockingQueue是双锁。
？
PriorityBlockingQueue入队流程
- 获取锁
- 自旋判断队列容量是否足够，不足时扩容
- 二叉堆排序
- 唤醒出队线程
PriorityBlockingQueue扩容机制
- 扩容大小，小于64时约为2倍，大于64时约为1.5倍
- 默认大小，11
- 通过自旋CAS加锁后再进行扩容
DelayQueue 入队流程
- 加锁
- 加入PriorityBlockingQueue队列
- 判断刚加入的是否为队首
- 是则leader设置为空，唤醒一个线程
- 释放锁
DelayQueue出队流程
- 加锁
- 取队首，判断是否到了执行时间，是则唤醒其他线程、释放锁并返回
- 如果已经有leader，则永久等待
- 如果没有leader，则晋升为leader，等待直到队首的执行时间
- 释放锁
DelayQueue的重点
- 底层依赖PriorityBlockingQueue
- 入队的数据必须实现Delayed接口
- leader的作用,多个消费者线程同时用take方法去取时，只有一个线程能成为leader，其他的会由于leader不为空 ，而永久等待。
SynchronousQueue的重点
- 容量为0
- 匹配插入线程和移除线程，资源从插入线程移交给移除线程
- 有公平模式（先进先出队列）和非公平模式（先进后出栈）
- 适合作为管道，资源从一个线程传递给另一个线程
ConcurrentLinkedQueue 核心
- 不允许null入列，因为尾节点的定位是通过next是否为null判断的
- 底层使用cas包装入列出列安全。
- head节点跟tail不一定指向头节点或尾节点，可能存在滞后性。
- size方法是通过遍历获取的，当同时存在其他线程入队出队操作时，该值可能不精确。
