快速失败(Fail-Fast)是 Java 集合框架的一种机制,当多个线程对集合进行并发修改时,或者单线程在遍历集合过程中修改了集合结构如添加、删除元素,会抛出ConcurrentModificationException。
其实现原理是集合内部维护一个 modCount 计数器,每次修改结构时递增。迭代器在遍历时会检查modCount 是否与预期值一致,不一致则抛出异常。
Java集合框架主要分为两大体系:Collection和 Map。
-
Collection 是存储单元素对象的根接口,其下包含三个主要子接口:
-
List:有序、可重复的集合,如
ArrayList、LinkedList。 -
Set:无序、不可重复的集合,如
HashSet、TreeSet。 -
Queue:用于模拟队列或双端队列,如
LinkedList、PriorityQueue。
-
-
Map 是存储键值对(key-value)的接口,每个键唯一映射到一个值,如
HashMap、TreeMap。
两大体系的区别:
-
存储内容不同:
Collection存储单个元素,Map存储键值对。 -
访问方式不同:
Collection通过元素本身操作,Map通过键来访问值。
ArrayList底层基于动态数组实现。当调用add方法且当前数组已满时,会触发扩容:
-
计算新容量:通常为旧容量的1.5倍。(oldCapacity + (oldCapacity >> 1))
-
创建新数组,并将原数组所有元素通过
Arrays.copyOf复制到新数组。 -
将新数组赋值给内部数组引用,后续添加操作在新数组上进行。(默认初始容量为10,扩容操作代价较高,因此在已知元素数量时可预先指定容量)
-
底层数据结构:
ArrayList基于动态数组,LinkedList基于双向链表。 -
随机访问:
ArrayList支持高效随机访问(O(1)),LinkedList需要遍历(O(n))。 -
插入和删除:
ArrayList在中间或头部插入/删除需要移动元素,效率低(O(n)),尾部插入(未满时)较快。LinkedList只需修改节点指针,插入删除快(O(1)),但需要先定位到位置。 -
内存占用:
ArrayList可能预留容量空间,LinkedList每个节点存储数据和前后指针,额外开销大。 -
适用场景:
ArrayList适合频繁读取、尾部操作。LinkedList适合频繁插入删除、作为队列或栈使用。
HashMap底层在JDK 1.8之前是数组+链表,每个数组元素是一个链表的头节点。JDK 1.8及之后引入红黑树优化。
-
当链表长度 ≥ 8 且数组长度 ≥ 64时,链表转为红黑树,以提高查询效率
-
当红黑树节点 ≤ 6时,退化为链表
当 HashMap 中元素个数超过阈值(容量 × 负载因子,默认0.75)时,触发扩容:
-
新容量为原容量的2倍。创建新数组,并将原数组所有元素重新计算哈希位置后迁移到新数组。
-
迁移时,由于容量变为2倍,元素的新位置要么在原索引,要么在原索引+旧容量,这一特性由哈希值高位参与运算决定。
-
JDK 1.7:实现原理采用分段锁(Segment)机制。将数据分成多个Segment(默认16个),每个Segment继承
ReentrantLock,独立加锁。不同Segment可并发访问,提高了并发度。每个Segment内部维护一个HashEntry数组,类似于HashMap的数组+链表结构。 -
JDK 1.8:实现原理废弃分段锁,改用CAS + synchronized。底层数据结构与
HashMap一致(数组+链表+红黑树)。锁粒度细化到每个数组元素(桶),使用synchronized对链表头节点或树根节点加锁,同时利用CAS进行无锁操作。并发度更高,且引入红黑树优化长链表查询性能。
HashMap 线程不安全的原因
-
多线程
put导致数据覆盖:当多个线程同时执行put操作,且计算出的数组索引相同时,后写入的线程可能覆盖前一个线程的结果,造成数据丢失。 -
扩容时形成环形链表(JDK 1.7):在 JDK 1.7 中,扩容采用头插法,多线程同时触发扩容可能导致链表形成环,后续
get操作陷入死循环。 -
put与get并发可见性问题:一个线程put的元素可能对另一个线程不可见,因为没有内存可见性保证。
ConcurrentHashMap 线程安全的原因
-
JDK 1.7 实现(分段锁):内部使用
Segment数组,每个Segment继承ReentrantLock,将整个哈希表分成多个段。不同线程操作不同段时互不干扰,同一段内才需要竞争锁,从而提高了并发度。 -
JDK 1.8 实现(CAS + synchronized):
-
读操作无锁:使用
volatile修饰Node的value和next,保证可见性,读操作无需加锁。 -
写操作采用 CAS 和 synchronized:插入元素时,先通过 CAS 尝试将节点放入空桶,若桶非空,则对桶的首节点使用
synchronized加锁,然后执行插入或更新。锁粒度缩小到单个桶,进一步减少竞争。
-
-
ConcurrentHashMap:高效线程安全的哈希表。 -
CopyOnWriteArrayList和CopyOnWriteArraySet:适用于读多写少的场景,写时复制。 -
ConcurrentLinkedQueue和ConcurrentLinkedDeque:基于 CAS 的无锁非阻塞队列。 -
BlockingQueue接口的实现类ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue等,支持阻塞操作。 -
ConcurrentSkipListMap和ConcurrentSkipListSet:基于跳表的并发有序集合。
-
BIO(Blocking I/O):同步阻塞I/O模型。服务器通常采用“一个连接一个线程”的方式,即每当有一个客户端连接请求,服务器就会创建一个独立的线程去处理该连接的所有I/O操作。
-
NIO(Non-blocking I/O):同步非阻塞I/O模型。基于多路复用器(Selector)实现,服务器可以用一个线程管理多个连接。线程通过Selector不断轮询注册在其上的通道,只有当某个通道的I/O操作真正就绪时,才会启动读写操作,否则可以处理其他就绪通道。
-
AIO(Asynchronous I/O):异步非阻塞I/O模型。它更进一步,由操作系统在I/O操作完成后主动通知应用程序。应用程序发起读写操作后立即返回,无需等待,当内核完成数据拷贝或操作结束后,会通过回调函数或Future机制通知用户线程进行后续处理。
简记:
-
BIO是同步阻塞,线程在读写期间被阻塞,一个连接一个线程。
-
NIO是同步非阻塞,通过多路复用器selector管理多个连接,线程在轮询时可能短暂阻塞,但读写仍需主动完成,适合高并发场景。
-
AIO是异步非阻塞,由操作系统完成I/O后通知应用,线程无需等待,真正解放线程资源。