Collection（List/Set/Queue）
2021-02-25 21:43:26 2 举报AI智能生成
ArrayList，LinkedList，Queue
作者其他创作
大纲/内容
List
有序，可重复
有序，可重复
ArrayList
底层是数组，是一块连续的内存空间，查找快，方便寻址；但是插入删除慢，因为会发生数据迁移
不严谨
扩容
旧的集合大小 + 旧的集合大小右移一位（右移一位相当于除以2，最终的结果是扩容为原来的1.5倍大小）
不能无限制的扩容，最大的容量是2的31次方；扩容时会创建一个新数组，将旧数组中的数据复制到新数组
如何克服插入删除慢的劣势？
可在初始化时指定具体容量，减少扩容时的性能损耗，或者使用LinkedList
初始化
ArrayList的默认无参构造初始容量是0（jdk1.7以后），第一次add元素的时候会初始化容量，
如果集合中要添加的元素小于10，ArrayList的容量就会设置为10，反之取最大值
如果集合中要添加的元素小于10，ArrayList的容量就会设置为10，反之取最大值
线程不安全
如何解决？
如何解决？
Vector
底层是数组，实现方式和ArrayList相似，不同的是方法上面都有Synchronized修饰
线程安全，系统开销较大，效率较低
扩容为原来的2倍
SynchronizedList
List list = Collections.synchronizedList(new ArrayList<>());
优点：使用同步代码块来为加锁，可以指定锁定的对象，锁的粒度更细
缺点：性能不如Vector，没有解决使用Iterator迭代时的线程安全问题
适合不需要使用Iterator、对性能要求也不高的情况
CopyOnWriteArrayList
List list = new CopyOnWriteArrayList<>();
CopyOnWrite容器是 “写时复制” 容器，在写的时候不对原集合进行修改，而是
重新复制一份，修改完之后，再移动指针（复制时加锁，此时读取则读旧数据）
重新复制一份，修改完之后，再移动指针（复制时加锁，此时读取则读旧数据）
优点
因为加锁的原因，数据一致性得到了保证
解决了像ArrayList、Vector这种集合多线程遍历迭代的安全问题
缺点：耗内存（集合复制）且实时性不高
元素遍历与删除
普通for循环 list.size()
在删除的过程中，由于元素的移动导致相邻的相同元素无法删除
iterator迭代器
推荐使用，必须要使用迭代器的remore方法，否则会抛出并发修改异常
原理：迭代器内部会记录并对比修改次数，防止多个迭代器同时操作
原理：迭代器内部会记录并对比修改次数，防止多个迭代器同时操作
增强for循环
forEach语法糖
LinkedList
底层是双向链表
包含头指针和尾指针，node中包含了上一个节点和下一个节点的引用，每个节点只能知道自己的前
驱pre和后继next，在查询指定位置时需要遍历链表一个一个找，效率不如ArrayList
驱pre和后继next，在查询指定位置时需要遍历链表一个一个找，效率不如ArrayList
头插法：插入节点的next指向first节点，first节点的pre指向插入节点，插入节点的pre置为null
尾插法：插入节点的pre指向last节点，last节点的next指向插入节点，插入节点的next置为null
尾插法：插入节点的pre指向last节点，last节点的next指向插入节点，插入节点的next置为null
线程不安全，允许元素为null的有序序列
优缺点
增删快，用多少空间就申请多少，不浪费内存
查找慢，需要移动指针
Set
无序，不可重复
无序，不可重复
HashSet
底层为HashMap，排列无序，不可重复，可以放入一个null值
其值为HashMap的key，HashMap的value是常量
添加元素
当向HashSet中添加元素的时候，首先计算元素的hashcode值，然后通过扰动计算和按位与的方式计算出这个元素的存储位置
如果这个位置位空，就将元素添加进去，如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则通过链表添加
为什么采用Hash算法？有什么优势？解决了什么问题？
解决的问题是唯一性，避免了元素很多时需要遍历查找这种效率低的方式
TreeSet
底层是TreeMap，基于二叉树（红黑树），排列有序，不可重复，不允许放入null值
TreeMap是按key排序的，元素在插入TreeSet时compareTo()方法要被调用，所以TreeSet中的元素要实现Comparable接口
TreeSet作为一种Set，它不允许出现重复元素。TreeSet是用compareTo()来判断重复元素的
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，
并按照过期时间进行阻塞
并按照过期时间进行阻塞
Map 👉
0 条评论
下一页
