Java集合

⋯

快速失败(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的扩容机制

ArrayList底层基于动态数组实现。当调用add方法且当前数组已满时,会触发扩容:

  • 计算新容量:通常为旧容量的1.5倍。(oldCapacity + (oldCapacity >> 1))

  • 创建新数组,并将原数组所有元素通过Arrays.copyOf复制到新数组。

  • 将新数组赋值给内部数组引用,后续添加操作在新数组上进行。(默认初始容量为10,扩容操作代价较高,因此在已知元素数量时可预先指定容量)

ArrayList和LinkedList的区别是什么

  • 底层数据结构:ArrayList 基于动态数组,LinkedList 基于双向链表。

  • 随机访问:ArrayList 支持高效随机访问(O(1)),LinkedList 需要遍历(O(n))。

  • 插入和删除:ArrayList 在中间或头部插入/删除需要移动元素,效率低(O(n)),尾部插入(未满时)较快。LinkedList 只需修改节点指针,插入删除快(O(1)),但需要先定位到位置。

  • 内存占用:ArrayList 可能预留容量空间,LinkedList 每个节点存储数据和前后指针,额外开销大。

  • 适用场景:ArrayList 适合频繁读取、尾部操作。LinkedList 适合频繁插入删除、作为队列或栈使用。

HashMap的底层数据结构是什么

HashMap底层在JDK 1.8之前是数组+链表,每个数组元素是一个链表的头节点。JDK 1.8及之后引入红黑树优化。

  • 当链表长度 ≥ 8 且数组长度 ≥ 64时,链表转为红黑树,以提高查询效率

  • 当红黑树节点 ≤ 6时,退化为链表

HashMap的扩容机制

当 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:基于跳表的并发有序集合。

  1. BIO(Blocking I/O):同步阻塞I/O模型。服务器通常采用“一个连接一个线程”的方式,即每当有一个客户端连接请求,服务器就会创建一个独立的线程去处理该连接的所有I/O操作。

  2. NIO(Non-blocking I/O):同步非阻塞I/O模型。基于多路复用器(Selector)实现,服务器可以用一个线程管理多个连接。线程通过Selector不断轮询注册在其上的通道,只有当某个通道的I/O操作真正就绪时,才会启动读写操作,否则可以处理其他就绪通道。

  3. AIO(Asynchronous I/O):异步非阻塞I/O模型。它更进一步,由操作系统在I/O操作完成后主动通知应用程序。应用程序发起读写操作后立即返回,无需等待,当内核完成数据拷贝或操作结束后,会通过回调函数或Future机制通知用户线程进行后续处理。

简记:

  • BIO是同步阻塞,线程在读写期间被阻塞,一个连接一个线程。

  • NIO是同步非阻塞,通过多路复用器selector管理多个连接,线程在轮询时可能短暂阻塞,但读写仍需主动完成,适合高并发场景。

  • AIO是异步非阻塞,由操作系统完成I/O后通知应用,线程无需等待,真正解放线程资源。


复盘手记

搜索笔记

输入关键词,搜索所有主题与问答。