java容器

2022-01-12 17:42:43   10  举报





AI智能生成

Java容器是Java编程语言中用于存储和管理对象的集合类。它们提供了一种便捷的方式来组织和操作数据，使得代码更加简洁、可读性更高。常见的Java容器包括List、Set、Map等。List是一种有序的集合，可以包含重复的元素；Set是一种无序且不包含重复元素的集合；Map是一种键值对映射的数据结构。Java容器还提供了丰富的方法，如添加、删除、遍历等，以满足不同的需求。使用Java容器可以提高代码的复用性和可维护性，减少代码冗余。总之，Java容器是Java编程中不可或缺的重要组成部分，对于开发高效的程序具有重要的作用。

java容器

java容器源码分析

作者其他创作

大纲/内容

说明

红色为线程安全的

灰色为非线程安全的

Collection

List

ArrayList

说明

基于数组实现，按下标查找速度快，增删除成本高

扩容机制

默认大小为10，当添加元素个数超过10个时会进行扩容，扩容后大小为10+(10/2)=15

常见问题

1. 使用迭代器遍历时为什么会抛出ConcurrentModificationException异常？

问题的根本原因在于使用List#remove删除元素时modCount变量会+1,该变量主要用来记录list被修改的次数
在通过迭代器遍历的前会记录当前modCount的值，变量的过程中如果发现该值发生了变化则抛出ConcurrentModificationException异常
主要是用来防止在遍历的时候有其他线程修改list

代码演示

LinkedList

说明

基于链表实现，按下标查找速度慢，增删成本低

LinkedList数据结构

CopyOnWriteArrayList

Set

HashSet

基于HashMap实现，添加元素时将将元素作为key put到该map中，value为一个固定的Object对象

LinkedHashSet

基于LinkedHashMap实现

TreeSet

基于TreeMap实现

CopyOnWriteArraySet

ConcurrentSkipListSet

Queue

Deque

阻塞

LinkedBlockingDeque

非阻塞

ConcurrentLinkedDeque

阻塞

ArrayBlockingQueue(有界，无默认值，必须指定)

说明

内部基于数组实现，通过单锁（lock）+两个condition（notEmpty和notFull）实现线程的同步和互斥

示例分析

相关api

入队

put

队列满时入队失败阻塞线程等待出队操作，不满则添加到队列尾部

offer

队列满时入队失败返回false，不满则添加到队列尾部

add

队列满时入队失败抛出IllegalStateException异常，不满则添加到队列尾部

出队

take

队列为空时阻塞线程等待入队操作，不为空头结点出队并返回头结点

poll

队列为空时返回null，不为空头结点出队并返回结点

remove

移除队列中的某个结点，可能会引发队列中数组元素的移动

获取头结点

peek

LinkedBlockingQueue(默认无界，为Integer.MAX_VALUE，可指定)

说明

与ArrayBlockingQueue不同的是，内部基于单向链表实现，使用双锁（putLock和takeLock）+各自的condition（notFull和notEmpty）实现线程的同步和互斥（在remove和clear需要同时获取这两把锁），这样入队和出队操作可以同时进行能够提升并发下的吞吐量，不过由于链表的缘故出队后会多出Node对象需要回收，GC压力相对ArrayBlockingQueue会大些

常见问题

LinkedBlockingQueue使用双锁能提高并发吞吐量，为什么ArrayBlockingQueue不使用双锁

可能是因为ArrayBlockingQueue使用一把锁，可以实现入队和出队线程的公平锁

示例分析

SynchronousQueue

非公平模式（基于TransferStack栈实现，默认）

当一个线程put数据时，该put线程自旋一会后会进入阻塞状态，直到有take线程来消费才会被缓存，如果有多个线程put后进入阻塞状态，当有一个线程来take的话最后put的那个线程会被唤醒（栈的特性）

公平模式（基于TransferQueue队列实现）

当一个线程put数据时，该put线程自旋一会后会进入阻塞状态，直到有take线程来消费才会被缓存，如果有多个线程put后进入阻塞状态，当有一个线程来take的话最先put的那个线程会被唤醒（队列的特性）

LinkedTransferQueue

PriorityBlockingQueue

内部基于堆实现，队列中的元素需要实现Comparable或创建PriorityBlockingQueue时传入比较器来确认优先级。需要注意的是创建PriorityBlockingQueue时只能指定初始容量大小，当达到初始容量时会扩容，所以对写操作是没有限制的，要注意内存溢出的问题

使用示例

DelayQueue

该队列中的元素需要实现Delayed接口，该接口中有个getDelay方法用于获取元素的延时时间，而且该接口实现了Comparable接口。因为内部是通过一个PriorityQueue队列进行存储元素（和上面的PriorityBlockingQueue类似，只是没有处理线程同步）。在每次添加元素的到PriorityQueue中的时候PriorityQueue里面会重新计算优先级，然后执行available.signal()唤醒阻塞在available条件变量上线程重新获取PriorityQueue中最先的元素设计阻塞时间

使用示例

ScheduledThreadPoolExecutor内部自己实现了一个延时队列DelayedWorkQueue，和此处的DelayQueue类似

ScheduledExecutorService示例

非阻塞

ConcurrentLinkedQueue

Map

HashMap

HashMap相关原理

说明

capacity(数组长度)：默认16
loadFactor(负载因子)：默认0.75
threshold(扩容阈值)：capacity*loadFactor=12

扩容后数组长度为之前的2倍，负载因子也为原来的两倍

常见问题

1. entrySet属性是何时被初始化的？

在第一次调用entrySet()方法的时候
需要注意的是，在调试的时候会发现没有调用entrySet()方法entrySet属性也被初始化了，是因为调试的时候调试器调用了AbstractMap#toString方法，而toString方法中使用了如下代码进行迭代导致的（通过在非调试模式下反射输出属性entrySet值可验证）
Iterator<Entry<K,V>> i = entrySet().iterator();

2. 为什么不建议使用map.keySet()进行遍历map？

使用map.keySet()遍历的时候如果需要取value则需要通过key计算出在数组中的下标然后再遍历链表进行查找。如果通过entrySet()进行遍历的话直接就能取到value了

3. 使用迭代器遍历时为什么会抛出ConcurrentModificationException异常？

问题的根本原因在于使用HashMapt#remove删除元素时modCount变量会+1,该变量主要用来记录map被修改的次数。在通过迭代器遍历的前会记录当前modCount的值，变量的过程中如果发现该值发生了变化则抛出ConcurrentModificationException异常。主要是用来防止在遍历的时候有其他线程修改list

代码演示（test1）

4. 并发下出现环引用的问题

1.8中已解决，如何解决具体查看上面"HashMap相关原理"中流程图部分

LinkedHashMap

说明

LinkedHashMap数据结构

继承自HashMap，不同的是LinkedHashMap中新增了head和tail属性，分别指向整个map中第一次添加的节点和最后一次添加的节点。而每个节点中新增了before和after分别保存着在自己之前添加的节点和在自己之后添加的节点。在遍历的时候从head开始通过节点中的after引用进行遍历链表中的元素，从而保证能按照添加顺序进行输出

TreeMap

HashTable

ConcurrentHashMap

待研究

ConcurrentSkipListMap