并发容器（Queue/ConcurrentHashMap）
2021-03-02 21:27:00 0 举报AI智能生成
并发容器（Queue/ConcurrentHashMap）
作者其他创作
大纲/内容
阅读导航
线程 👉
CPU+JMM 👉
CAS+Volatile 👉
Synchronized 👉
JUC
locks锁+atomic原子类 👉
executor自定义线程池 👉
collections并发容器
tools并发工具类 👉
线程池 👉
ThreadLocal 👉
BlockingQueue
ArrayBlockingQueue
有界阻塞队列，先进先出，存取相互排斥
数据结构：静态数组
容量固定必须指定长度，没有扩容机制
没有元素的位置也占用空间，被 null 占位
锁：ReentrantLock
存取是同一把锁，操作的是同一个数组对象
阻塞对象
notEmpty
无元素可取时，阻塞在该对象上（count=0）
notFull
放不进去时，阻塞在该对象上（count=length）
入队
从队首开始添加元素，记录putIndex
每次都唤醒notEmpty
出队
从队首开始取出元素，记录takeIndex
每次都唤醒notFull
两个指针都是从队首向队尾移动，保证队列的先进先出原则
LinkedBlockingQueue
无界阻塞队列，可以指定容量，默认为 Integer.MAX_VALUE，先进先出，存取互不干扰
数据结构：链表
内部类 Node 存储元素
锁分离：存取操作的是不同的Node对象
takeLock
putLock
阻塞对象
notEmpty
无元素可取时，阻塞在该对象上（count=0）
notFull
放不进去时，阻塞在该对象上（count=length）
入队
队尾入队，由last指针记录
出队
队首出队，由head指针记录
线程池中为什么使用LinkedBlockingQueue而不用ArrayBlockingQueue？
锁分离
SynchronousQueue
说是不存储元素（无缓冲）的阻塞队列，其实不准确，准确的说是完成了线程间的数据交换
数据结构：链表
在其内部类中维护了数据
第一个线程Thread0是消费者访问，此时队列为空，则入队（创建Node结点并赋值）
第二个线程Thread1也是消费者访问，与队尾模式相同，继续入队
第三个线程Thread2是生产者，携带了数据e，与队尾模式不同，不进行入队操作
直接将该线程携带的数据e返回给队首的消费者，并唤醒队首线程Thread0，出队
直接将该线程携带的数据e返回给队首的消费者，并唤醒队首线程Thread0，出队
锁：CAS+自旋（没有使用锁）
阻塞：自旋了一定次数后调用 LockSupport.park()
存取调用同一个方法：transfer()
put、offer 为生产者，携带了数据 e，为 Data 模式，设置到 QNode 属性中
take、poll 为消费者，不携帯数据，为 Request 模式，设置到 QNode 属性中
过程
线程访问阻塞队列，先判断队尾节点或者栈顶节点的 Node 与当前入队模式是否相同
相同则构造节点 Node 入队，并阻塞当前线程，元素 e 和线程赋值给 Node 属性
不同则将元素 e（不为 null） 返回给取数据线程，队首或栈顶线程被唤醒，出队
公平模式
TransferQueue
队尾匹配，队头出队，先进先出
非公平模式
TransferStack
栈顶匹配，栈顶出栈，后进先出
PriorityBlockingQueue
一个支持优先级排序的无界阻塞队列
优先级高的先出队，优先级低的后出队
数据结构：数组+二叉堆（完全二叉树）
可指定初始容量，会自动扩容，最大容量是Integer.MAX_VALUE
可理解为无界队列，超出最大长度会报 OOM 异常
锁：ReentrantLock
存取是同一把锁
阻塞对象：NotEmpty
出队，队列为空时阻塞
入队
不阻塞，永远返回成功，无界
根据比较器进行堆化（排序）自下而上
传入比较器对象就按照比较器的顺序排序
如果比较器为 null，则按照自然顺序排序
出队
优先级最高的元素在堆顶（弹出堆顶元素）
弹出前比较两个子节点再进行堆化（自上而下）
LinkedTransferQueue
数据结构：链表Node
由链表结构组成的无界阻塞队列
锁：CAS+自旋（没有使用锁）
阻塞：自旋了一定次数后调用 LockSupport.park()
可以自己控制存元素是否需要阻塞线程，比如使用四个添加元素的方法就不会阻塞线程，只入队元素，使用 transfer() 会阻塞线程
取元素与 SynchronousQueue 基本一样，都会阻塞等待有新的元素进入被匹配到
LinkedBlockingDeque
一个链表阻塞双端队列，无界可以指定容量，默认为 Integer.MAX_VALUE
数据结构：链表（同LinkedBlockingQueue）
内部类 Node 存储元素
锁：ReentrantLock（同ArrayBlockingQueue）
存取是同一把锁，操作的是同一个数组对象
阻塞对象（同ArrayBlockingQueue）
notEmpty
无元素可取时，阻塞在该对象上（count=0）
notFull
放不进去时，阻塞在该对象上（count=length）
入队
出队
DelayQueue
一个使用优先级队列实现的无界阻塞队列
数据结构：PriorityQueue
与PriorityBlockingQueue类型，不过没有阻塞功能
锁：ReentrantLock
阻塞对象：Condition available
入队：不阻塞，无界队列，与优先级队列入队相同，available
出队
为空时阻塞
检查堆顶元素过期时间
小于等于0则出队
大于0，说明没过期，则阻塞
判断leader线程是否为空
（为了保证优先级）
（为了保证优先级）
不为空（已有线程阻塞），直接阻塞
为空，则将当前线程置为leader，
并按照过期时间进行阻塞
并按照过期时间进行阻塞
手写阻塞队列
仿照ArrayBlockQueue
CopyOnWriteArrayList
List list = new CopyOnWriteArrayList<>();
CopyOnWrite容器是 “写时复制” 容器，在写的时候不对原集合进行修改，而是
重新复制一份，修改完之后，再移动指针（复制时加锁，此时读取则读旧数据）
重新复制一份，修改完之后，再移动指针（复制时加锁，此时读取则读旧数据）
优点
因为加锁的原因，数据一致性得到了保证
解决了像ArrayList、Vector这种集合多线程遍历迭代的安全问题
缺点：耗内存（集合复制）且实时性不高
ConcurrentMap
ConcurrentHashMap 👉
ConcurrentNavigableMap
ConcurrentSkipListMap
关于作者
我的博客 👉
微信公众号 👉
GitHub 导航 👉
ProcessOn 主页 👉
0 条评论
下一页
