和面试官扯了半小时ArrayBlockingQueue源码
和面试官扯了半小时ArrayBlockingQueue源码
最聪明的人是最不愿浪费时间的人。 ——但丁
0 前言
由数组支持的有界阻塞队列。此队列对元素按 FIFO（先进先出）进行排序。队首是已在队列中最长时间的元素。队尾是最短时间出现在队列中的元素。新元素插入到队列的尾部，并且队列检索操作在队列的开头获取元素。 这是经典的“有界缓冲区”，其中固定大小的数组包含由生产者插入并由消费者提取的元素。一旦创建，容量将无法更改。试图将一个元素放入一个完整的队列将导致操作阻塞；从空队列中取出一个元素的尝试也会类似地阻塞。
此类支持可选的公平性策略，用于排序正在等待的生产者和使用者线程。默认情况下，不保证此排序。但是，将公平性设置为true构造的队列将按FIFO顺序授予线程访问权限。公平通常会降低吞吐量，但会减少可变性并避免饥饿。
此类及其迭代器实现了Collection和Iterator接口的所有可选方法。
此类是Java Collections Framework的成员。
1 继承体系
- Java中的阻塞队列接口BlockingQueue继承自Queue接口。
2 属性
- 存储队列元素的数组，是个循环数组
- 下次take, poll, peek or remove 时的数据索引
- 下次 put, offer, or add 时的数据索引
有了上面两个关键字段，在存数据和取数据时，无需计算，就能知道应该新增到什么位置，应该从什么位置取数据。
- 队列中的元素数
并发控制采用经典的双条件（notEmpty + notFull）算法
- Lock 锁
- 等待take的条件,在 put 成功时使用
- 等待put的条件,在 take 成功时使用
ArrayBlockingQueue is a State-Dependent class，该类只有一些先决条件才能执行操作.
如果前提条件（notFull）为 false ，写线程将只能等待. 如果队列满，写需要等待. 原子式释放锁，并等待信号(读线程发起的 notFull.signal())
对于读，概念是相同的，但使用 notEmpty 条件: 如果队列为空，则读线程需要等待. 原子地释放锁，并等待信号(由写线程触发的 notEmpty.signal())
当一个线程被唤醒，那么你需要做2件主要的事情：
- 获取锁
- 重测条件
这种设计，它支持只唤醒对刚刚发生的事情感兴趣的线程. 例如，一个试图从空队列中取数据的线程，只对队列是否为空(有一些数据要取出)感兴趣，而并不关心队列是否满。确实经典的设计！
3 构造方法
3.1 无参
注意这是没有无参构造方法的哦!必须设置容量!
3.2 有参
- 创建具有给定（固定）容量和默认访问策略(非公平)的ArrayBlockingQueue
- 创建具有给定（固定）容量和指定访问策略的ArrayBlockingQueue
- 创建一个具有给定（固定）容量，指定访问策略并最初包含给定集合的元素的ArrayBlockingQueue，该元素以集合的迭代器的遍历顺序添加.
fair 参数
指定读写锁是否公平
- 公平锁，锁竞争按先来先到顺序
- 非公平锁，锁竞争随机
3 新增数据
ArrayBlockingQueue有不同的几个数据添加方法，add、offer、put方法,数据都会按照 putIndex 的位置新增.
3.1 add
- 如果可以在不超过队列容量的情况下立即将指定元素插入此队列的尾部，则在成功插入时返回true，如果此队列已满则抛出IllegalStateException.
调用的是抽象父类 AbstractQueue的 add 方法
offer
- 之后又是调用的自身实现的 offer 方法.
enqueue
在当前放置位置插入元素,更新并发出信号. 仅在持有锁时可以调用
- 内部继续调用入队方法
类似的看 put 方法.
3.2 put
- 将指定的元素插入此队列的末尾，如果队列已满，则等待空间变为可用.
实现类似 add,不再赘述.
4 取数据
从队首取数据,我们以 poll 为例看源码.
4.1 poll
dequeue
- 提取当前位置的元素，更新并发出信号.仅在持有锁时可调用.
5 删除数据
从源码可以看出删除有两种情景：
- 删除位置等于takeIndex,直接将该位元素置 null ,并重新计算 takeIndex
- 找到要删除元素的下一个，计算删除元素和 putIndex 的关系,若下一个元素
- 是 putIndex，将 putIndex 的值修改成删除位
- 非 putIndex，将下一个元素往前移动一位
6 总结
ArrayBlockingQueue 是一种循环队列，通过维护队首、队尾的指针，来优化插入、删除，从而使时间复杂度为O(1).