面试篇:Java集合
为什么java的集合只能存放封装类
在 Java 中,集合类(如 List
、Set
和 Map
)是基于泛型的,而泛型要求使用对象类型参数。然而,int
和其他基本数据类型(如 char
、float
等)并不是对象,而是原始类型(primitive types)。因此,Java 的集合不能直接存放原始类型。
为了支持在集合中存储原始类型,Java 提供了封装类(Wrapper classes),例如 Integer
对应 int
,Character
对应 char
,Double
对应 double
等。这些封装类是对象,它们使得基本数据类型能够作为对象使用,从而可以被存储在集合中。
为什么会这样?
-
泛型的设计:Java 泛型是基于对象的,因为泛型要求类型参数必须是引用类型(即对象)。原始数据类型(primitive types)是值类型,它们不是对象,因此不能直接作为泛型类型参数。
-
封装类的引入:Java 提供了封装类(如
Integer
、Double
等)来解决这个问题。封装类是原始数据类型的对象表示,可以让我们在集合中存储数值,同时提供一些额外的方法来操作这些数值。 -
自动装箱(Autoboxing)与拆箱(Unboxing):从 Java 5 开始,Java 引入了自动装箱和拆箱的概念,允许在原始类型和对应的封装类之间自动转换。这意味着,尽管我们可以使用基本数据类型的值(如
int
),Java 会自动将其转换为Integer
对象,并在需要时将其还原为基本类型。这个过程使得基本类型和对象类型之间的转换变得更加简便。
Java集合框架基础
Java集合框架的主要接口有哪些?
Java集合框架的主要接口有:
-
Collection:是最基本的集合接口,List、Set 和 Queue 都继承自它。
-
List:有序集合,元素可重复。
-
Set:无序集合,元素不可重复。
-
Queue:队列接口,用于按特定规则处理元素,比如先进先出。
-
Deque:双端队列,支持从两端插入和删除元素。
-
Map:键值对集合,key 不重复,value 可重复,不继承自 Collection。
这些接口定义了集合的基本行为,不同实现类根据具体需求优化了性能或线程安全等方面。
List、Set、Map的区别是什么?
List是有序可重复集合,可以通过索引访问元素,常用实现有ArrayList和LinkedList,适合顺序存储和频繁读操作。 Set是无序不可重复集合,元素唯一,常用实现有HashSet、LinkedHashSet、TreeSet,适合去重场景。 Map是键值对结构,key唯一,value可以重复,常用实现有HashMap、TreeMap、LinkedHashMap,适合映射关系的存储,如缓存和配置项。
集合框架中哪些是线程安全的?
Vector 和 Hashtable 是早期的线程安全集合,但性能差。 Collections.synchronizedList、synchronizedMap 等方法可以把普通集合变成线程安全的,但是通过外部锁,性能也不高。 更推荐使用并发包下的集合,如 CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentHashMap、ConcurrentLinkedQueue、LinkedBlockingQueue 等,它们通过分段锁或无锁机制实现高并发访问,适合多线程环境。
什么是fail-fast机制?
fail-fast 机制是指在 Java 集合类中,当多个线程同时修改集合时,如果在遍历集合时发现集合结构被修改,程序会立即抛出 ConcurrentModificationException 异常,避免出现不可预测的行为。
fail-fast 机制主要出现在 Iterator 中。当你使用迭代器遍历集合时,如果在遍历过程中集合被结构性修改(如添加、删除元素),迭代器会检测到这种修改并立刻抛出异常,从而避免继续进行不一致的操作。
需要注意的是,fail-fast 机制并不一定是线程安全的,而是用于保证单线程环境下的集合遍历过程的稳定性。在并发环境下,通常使用其他并发控制手段来处理。
什么是迭代器(Iterator)?
迭代器(Iterator)是 Java 中用于遍历集合元素的一种机制。它提供了一个统一的接口,用于访问集合中的元素,而不需要关心集合的具体实现方式。
迭代器主要有三个方法:
-
hasNext()
:判断集合中是否还有下一个元素,返回布尔值。 -
next()
:返回集合中的下一个元素。如果没有更多元素,则抛出NoSuchElementException
。 -
remove()
:删除当前迭代器指向的元素。这是一个可选操作,某些集合可能不支持。
通过迭代器,集合的元素可以被遍历,而不需要暴露集合的实现细节。
List相关
ArrayList和LinkedList的区别?
ArrayList 和 LinkedList 都是 List 接口的实现类,但它们的内部结构和性能特点不同:
-
内部结构:
-
ArrayList 底层使用数组来存储元素,具有随机访问能力。
-
LinkedList 底层使用双向链表来存储元素,每个元素都包含对前后元素的引用。
-
-
访问速度:
-
ArrayList 支持通过索引直接访问元素,时间复杂度为 O(1)。
-
LinkedList 需要从头或尾开始遍历,直到找到指定元素,时间复杂度为 O(n)。
-
-
插入和删除操作:
-
ArrayList 在中间插入或删除元素时,必须移动元素,时间复杂度为 O(n)。
-
LinkedList 在中间插入或删除元素时,只需要调整链表节点的引用,时间复杂度为 O(1)。
-
-
内存使用:
-
ArrayList 由于底层是数组,内存使用较为紧凑,但如果数组扩容时会发生性能下降。
-
LinkedList 由于每个元素都需要存储前后指针,内存开销较大。
-
总结:如果频繁进行访问操作,ArrayList 更合适;如果频繁进行插入和删除操作,LinkedList 更优。
ArrayList的扩容机制是怎样的?
ArrayList 的扩容机制是基于数组的,当 ArrayList 中的元素数量达到数组的容量时,它会自动进行扩容。具体扩容过程如下:
-
初始容量:当创建一个 ArrayList 时,如果没有指定初始容量,默认的初始容量是 10。也就是说,ArrayList 会先分配一个大小为 10 的数组来存储元素。
-
扩容条件:当 ArrayList 中的元素数量超过当前数组容量时,就会触发扩容操作。
-
扩容比例:每次扩容时,ArrayList 会将原数组的大小扩大为原来的 1.5 倍。也就是说,新的容量是旧容量的 1.5 倍,并且是向上取整的。
-
扩容过程:扩容时,ArrayList 会创建一个新的更大的数组,并将原数组中的元素复制到新的数组中。
这种扩容机制虽然确保了 ArrayList 能够容纳更多的元素,但也带来了性能上的开销,尤其是在频繁插入元素时,可能会导致频繁的数组复制。
总结:ArrayList 扩容时会将容量增加为原容量的 1.5 倍,扩容操作会带来性能损失,但它能够保证 ArrayList 能够灵活增长。
Vector和ArrayList的区别?
Vector 和 ArrayList 都是基于数组实现的 List,但它们的主要区别有以下几点:
-
是否线程安全:Vector 是线程安全的,所有方法都加了 synchronized;ArrayList 是非线程安全的,性能更高。
-
扩容机制:Vector 每次扩容是原容量的 2 倍;ArrayList 是 1.5 倍。
-
性能开销:由于加锁机制,Vector 在多线程下能保证安全,但在单线程环境中性能比 ArrayList 差。
-
使用场景:单线程建议用 ArrayList;如果需要线程安全,优先考虑使用 Concurrent 包下的集合,如 CopyOnWriteArrayList,而不是 Vector。
总结:Vector 是早期设计,已经过时,ArrayList 性能更优,适用于大多数场景。
CopyOnWriteArrayList是如何实现线程安全的?
CopyOnWriteArrayList 通过“写时复制”机制实现线程安全。它的核心原理是:
每当有写操作(如 add、remove、set)时,不是在原数组上直接修改,而是先复制出一个新的数组,在这个新数组上执行修改操作,修改完成后再将新数组的引用赋值回原来的引用。这样做的好处是,读操作仍然使用旧数组,不会受到写操作的影响。
具体特点如下:
-
读操作无需加锁,多个线程可以并发读,性能高。
-
写操作会复制整个数组,成本较高,因此不适合写操作频繁的场景。
-
适合读多写少的并发场景,比如缓存、事件监听器列表。
它牺牲了写性能,换来了读的无锁高并发。线程读时看到的永远是稳定、不变的快照。
Set相关
HashSet和TreeSet的区别?
HashSet 和 TreeSet 都是实现了 Set 接口的集合类,但它们在底层结构、排序方式和性能上有明显区别:
-
底层实现 HashSet 基于 HashMap 实现,元素无序,依赖 hashCode 和 equals 方法判断唯一性。 TreeSet 基于 TreeMap,底层是红黑树,元素有序,按自然顺序或指定的 Comparator 排序。
-
元素顺序 HashSet 不保证元素顺序,插入顺序和遍历顺序可能不同。 TreeSet 会自动对元素进行排序,插入和遍历时都是有序的。
-
性能差异 HashSet 插入、删除、查找的平均时间复杂度是 O(1),性能更高。 TreeSet 所有操作的时间复杂度是 O(log n),因为它维护了元素的有序性。
-
使用场景 HashSet 更适合快速查找、去重、无序集合。 TreeSet 适合需要排序的场景,比如从小到大遍历、范围查询等。
总结:HashSet 快但无序,TreeSet 有序但慢,按是否需要排序来选择。
HashSet是如何保证元素唯一的?
HashSet 是通过元素的 hashCode 和 equals 方法来保证元素唯一的。
具体过程如下:
-
当你向 HashSet 添加一个元素时,它会先调用该元素的 hashCode 方法,计算出一个哈希值,用于确定在底层 HashMap 中的桶位置。
-
如果这个位置还没有元素,直接插入;如果已经有元素(即发生哈希冲突),它会继续调用 equals 方法,逐个和已有元素比较。
-
如果 equals 判断出已有相同元素,则认为是重复元素,不会添加;如果都不相等,就插入到该位置的链表或红黑树中。
所以,要让 HashSet 正确判断元素是否唯一,必须确保你自定义的类重写了 hashCode 和 equals 方法,并且两者逻辑保持一致。否则可能导致无法去重或行为异常。
LinkedHashSet的特点是什么?
LinkedHashSet 继承自 HashSet,它的主要特点是在保证元素唯一性的同时,保持元素的插入顺序。
具体特点如下:
-
底层结构是 HashMap 加一条双向链表。链表记录元素的插入顺序。
-
插入顺序不会改变,遍历时元素顺序和插入时一致。
-
元素唯一性依旧通过 hashCode 和 equals 判断,和 HashSet 一样。
-
性能略低于 HashSet,因为维护了额外的顺序信息,但插入、删除、查找的时间复杂度仍是 O(1)。
总结:如果你需要一个去重且保持插入顺序的集合,就选 LinkedHashSet。它在 HashSet 的基础上多了一条顺序链。
Map相关
HashMap的工作原理是什么?
HashMap 的核心是“数组 + 链表(或红黑树)”的结构,它的工作原理主要包括以下几个步骤:
-
存储结构 底层是一个数组,每个数组元素是一个链表或红黑树的头节点。这个结构称为桶(bucket)。
-
添加元素 当你调用 put(key, value) 时,HashMap 会先对 key 进行 hash 计算,然后通过取模运算确定应该放到哪个桶里。
-
处理冲突 如果多个 key 经过 hash 后落在同一个桶里(哈希冲突),就通过链表的方式向后连接。如果链表长度超过阈值(默认是8)并且数组长度大于64,就转换为红黑树,提高查找效率。
-
覆盖旧值 在插入之前,会遍历该桶下的链表或红黑树,通过 equals 方法判断 key 是否已经存在。如果存在,就更新 value,否则新增节点。
-
扩容机制 当 HashMap 的元素数量超过负载因子(默认是 0.75 × 容量)时,会触发扩容,将数组扩展为原来的 2 倍,并重新计算所有元素的位置,这个过程叫 rehash。
-
查找和删除 查找就是根据 key 计算 hash,然后去对应的桶中遍历链表或树;删除也是一样,先定位到桶,再从结构中移除节点。
总结:HashMap 通过 hash + 链表/树 结合的方式实现高效存储,查找是平均 O(1),在冲突严重或极端情况下最坏是 O(n)。线程不安全,适用于单线程或通过额外手段控制并发。
HashMap和Hashtable的区别?
HashMap 和 Hashtable 的主要区别如下:
-
线程安全性 Hashtable 是线程安全的,内部所有方法基本都加了 synchronized。 HashMap 是非线程安全的,需要自己保证并发控制。
-
性能 由于 Hashtable 加锁,性能比 HashMap 差。 HashMap 在单线程环境下更高效。
-
null 值处理 Hashtable 不允许 key 或 value 为 null,任何一个为 null 都会抛异常。 HashMap 允许一个 key 为 null,value 可以有多个 null。
-
出现时间 Hashtable 是早期的类,出现在 JDK 1.0,属于遗留类。 HashMap 是 JDK 1.2 引入的,属于集合框架的一部分。
-
替代关系 在多线程环境中,Hashtable 不再推荐使用,建议用 ConcurrentHashMap。 在单线程或需要手动控制同步的情况下,用 HashMap 更合适。
总结:HashMap 更现代、更灵活,Hashtable 设计过时,能不用就不用。
HashMap的put方法执行过程是怎样的?
HashMap 的 put 方法执行过程大致如下:
-
先判断 key 是否为 null,如果是 null,会固定放到 table[0] 的桶中处理。
-
如果 key 不为 null,就调用 key 的 hashCode 方法,经过扰动函数计算出 hash 值,再根据 hash 决定应该放到哪个桶(index = (n - 1) & hash)。
-
找到目标桶后,如果桶是空的,直接新建节点放进去。
-
如果桶中已有节点,就遍历链表或红黑树:
-
如果发现已有节点的 key 和当前 key 相等(通过 equals 判断),就更新该节点的 value。
-
如果没有相等的 key,就在链尾插入新节点。
-
-
插入完成后,如果桶中的节点数量超过阈值(8),并且当前数组长度大于等于 64,就将链表转为红黑树。
-
最后判断是否需要扩容。如果当前元素总数超过阈值(capacity × load factor),就将数组扩容为原来的 2 倍,并将原有节点重新分布(rehash)。
整个过程体现了 HashMap 的三大特性:哈希定位、高效插入、动态扩容。
HashMap的扩容机制是怎样的?
HashMap 的扩容机制本质上是数组的动态扩展,用来保证在元素增多时仍能保持较高的性能。具体过程如下:
-
触发条件 当 HashMap 中的元素数量超过容量 × 负载因子(默认是 0.75)时,就会触发扩容。
-
扩容大小 每次扩容都是将当前数组容量扩大为原来的 2 倍。例如从 16 扩展为 32。
-
创建新数组 扩容时,会新建一个更大的数组,并将原数组中的所有节点重新计算索引位置,迁移过去。这个过程叫做 rehash。
-
节点再分布 由于数组长度变了,元素的位置也要重新分配。节点根据
(newCapacity - 1) & hash
重新定位。链表节点按顺序重新链接,树节点也会被拆分成高位链和低位链。 -
链表转树或树转链 在扩容过程中,如果某个桶原本是红黑树,元素少了之后可能会退化成链表,反之链表在新桶中元素增多也可能变成树。
注意:扩容是非常消耗性能的操作,因为涉及所有元素的重新分布。所以如果你知道要存多少数据,建议提前指定初始容量,避免频繁扩容。
总结:HashMap 扩容是“容量翻倍 + 元素重分布”,用以保证散列均匀,提高性能,但代价是 rehash 过程非常重。
HashMap为什么线程不安全?
HashMap 线程不安全的原因主要在于它的设计没有对并发访问做同步控制。具体原因包括:
-
多个线程同时 put 可能导致数据丢失 如果两个线程同时向同一个桶 put 元素,可能一个线程刚写完,另一个线程就覆盖了,导致前一个值丢失。
-
扩容时的并发问题 在多线程环境中,如果多个线程同时触发扩容,可能导致旧数组中的链表断裂,元素丢失,甚至出现死循环(JDK 1.7 中曾出现过)。
-
非原子操作 put、resize、rehash 等操作本质上不是原子的,由多个步骤组成,如果中途被打断,集合结构可能就不一致了。
-
无同步机制 HashMap 本身没有使用 synchronized 或其他并发控制手段,所以线程之间的修改完全不可见,会发生竞态条件。
总结:HashMap 适用于单线程环境或通过外部手段保证同步。在并发场景下建议使用 ConcurrentHashMap,它通过分段锁或 CAS 等机制保证线程安全。
ConcurrentHashMap如何实现线程安全?
ConcurrentHashMap 通过分段锁(Segment)和细粒度锁的机制来实现线程安全,相比 HashMap,它提供了更高效的并发访问能力。具体的实现方式包括以下几个关键点:
-
分段锁机制(JDK 1.7 及之前) 在 JDK 1.7 中,ConcurrentHashMap 通过将整个哈希表分为多个段(Segment),每个段都维护着一个小的 HashMap。在多线程环境下,每个线程只需要锁住自己操作的段,这样就能避免多个线程争抢同一个锁,减少了锁的竞争。每个段使用独立的锁,实现了对不同段的并发访问。
-
桶级别锁(JDK 1.8) 在 JDK 1.8 中,ConcurrentHashMap 采用了更加细粒度的锁,使用 CAS(Compare And Swap) 和 桶级别锁(对于链表或红黑树的桶)来提高并发度。
-
CAS 用于原子性操作,确保更新操作是无锁的。
-
锁分离:不同的桶(Bucket)通过独立的锁来保证线程安全,这样多个线程可以并行地操作不同的桶,进一步减少了竞争。
-
-
无锁操作(读操作) 在 ConcurrentHashMap 中,读操作是无锁的。即使有线程在进行写操作,读操作也不会阻塞。通过将结构操作与数据访问操作分开,使得读操作在没有修改结构的情况下可以安全并发。
-
扩容机制 扩容时,ConcurrentHashMap 使用的是 延迟扩容 的策略,而不是像 HashMap 一样在发生扩容时立即锁住整个哈希表。在并发环境下,扩容是分段执行的,不会影响正在进行的读写操作。
-
操作粒度细化 除了读操作和扩容,ConcurrentHashMap 还通过在更新操作(如 put、remove 等)上实现更细粒度的锁控制,使得多个线程可以高效地执行不同的操作。
总结:ConcurrentHashMap 通过分段锁(JDK 1.7)、桶级别锁(JDK 1.8)、无锁读操作、CAS 等手段,极大地提高了并发性能,确保线程安全。它提供了更高的吞吐量,尤其适合高并发环境。
JDK1.7和JDK1.8中HashMap的实现有什么不同?
JDK 1.7 和 JDK 1.8 中 HashMap 的实现有一些显著的不同,主要体现在 扩容机制 和 链表与树的处理 上。以下是两者的主要区别:
1. 扩容机制
-
JDK 1.7:在 JDK 1.7 中,HashMap 使用了 分段锁 的设计来实现线程安全(在
ConcurrentHashMap
中使用类似的方式)。当 HashMap 的容量达到阈值时,会进行扩容操作,扩容时会创建一个新的数组,并将原数组中的元素重新哈希到新的数组中。这个过程在扩容时是同步的,可能会导致性能问题。 -
JDK 1.8:在 JDK 1.8 中,HashMap 的扩容机制有所变化,采用了 “树化” 机制。扩容时,原来的链表如果超过一定长度(默认是 8),会被转化为红黑树,从而提高查找效率。扩容的触发条件和 JDK 1.7 相似,但它的性能得到了显著提升,特别是在链表较长时。
2. 链表与红黑树的处理
-
JDK 1.7:HashMap 在 JDK 1.7 中使用链表来解决哈希冲突。当多个元素发生哈希冲突时,它们会以链表的形式存储在同一个桶中。每次访问时都需要遍历链表来查找目标元素,性能较低。
-
JDK 1.8:JDK 1.8 引入了红黑树机制。当某个桶中的链表长度超过 8,该链表会自动转化为红黑树,这样可以使得查找操作的时间复杂度从 O(n) 降低为 O(log n),从而提升性能。当红黑树的元素数量较少时,依然使用链表,这样可以避免红黑树结构带来的性能开销。
3. 默认负载因子和容量
-
在 JDK 1.7 和 JDK 1.8 中,默认的 负载因子 都是 0.75,初始容量 默认为 16。但 JDK 1.8 的 扩容机制 进行了优化,避免了大量的链表操作。
4. 性能优化
-
JDK 1.7:JDK 1.7 中的 HashMap 只是简单地使用链表来处理哈希冲突,没有针对链表较长的情况进行优化,性能较差。
-
JDK 1.8:JDK 1.8 引入了红黑树的优化,使得 HashMap 在处理哈希冲突时更加高效,尤其是在大量数据插入导致哈希冲突严重时。
5. Null 键和空值处理
-
JDK 1.7 和 JDK 1.8 在这方面没有变化,HashMap 依旧允许一个
null
的键和多个null
的值。null
键会被特殊处理,存放在数组的第一个位置。
总结:
-
JDK 1.7 中的 HashMap 主要使用 链表 来解决哈希冲突,扩容时效率较低,且没有对链表较长的情况进行优化。
-
JDK 1.8 引入了 红黑树 机制,在链表长度较长时将链表转换为红黑树,提高查找效率,避免了性能瓶颈。并且扩容过程和哈希冲突的处理进行了优化,使得整体性能得到了显著提升。
总的来说,JDK 1.8 对 HashMap 的实现做了很多性能优化,尤其是在哈希冲突较多的情况下,提供了更好的处理方式。
TreeMap的特点是什么?
TreeMap 是基于红黑树(Red-Black Tree)实现的 NavigableMap 接口的 Map 实现类,它有以下几个主要特点:
-
有序性 TreeMap 保证键值对按键的自然顺序(通过 Comparable 接口)或者根据构造时传入的 Comparator 进行排序。与 HashMap 不同,TreeMap 按照键的顺序进行存储和遍历。
-
红黑树实现 TreeMap 底层是红黑树,保证了插入、删除、查找等操作的时间复杂度为 O(log n),这使得 TreeMap 在处理大量数据时比 HashMap 更适合需要排序或范围查询的场景。
-
键的唯一性 和 HashMap 一样,TreeMap 也保证键的唯一性。每个键只能映射到一个值,如果插入重复的键,会覆盖原有的值。
-
支持导航操作 由于实现了 NavigableMap 接口,TreeMap 提供了多种导航方法,支持 范围查询(如
subMap()
、headMap()
、tailMap()
)、获取最小/最大键值对(如firstEntry()
、lastEntry()
)等功能。 -
不允许 null 键 TreeMap 不允许插入
null
作为键。如果尝试将null
作为键插入,会抛出NullPointerException
。但值部分可以是null
。 -
线程不安全 TreeMap 不是线程安全的。如果需要在多线程环境中使用,必须自己使用同步机制或者使用
ConcurrentSkipListMap
替代。 -
遍历顺序 由于 TreeMap 内部按顺序存储元素,因此在遍历时会按照自然顺序或指定的比较器顺序输出键值对。
总结:TreeMap 是一个有序的 Map 实现,底层基于红黑树,支持高效的查找、插入、删除操作,并且提供了丰富的范围查询和导航功能,适用于需要保持键排序的场景。
其他集合类
Queue和Deque的区别?
Queue 和 Deque 是 Java 中两个常用的集合接口,它们的区别主要体现在 操作方式 和 功能扩展 上:
-
基本定义
-
Queue:是一个线性数据结构,通常用于表示一个 先进先出(FIFO) 的队列。它提供了基本的入队(offer)、出队(poll)和查看队头(peek)等操作。
-
Deque:全称 双端队列(Double-Ended Queue),是 Queue 的一个扩展,它支持在队列的两端进行元素的添加和移除操作,即既可以作为队列(FIFO),也可以作为栈(LIFO)使用。
-
-
操作支持
-
Queue:通常只支持从队列的一端(队头)进行移除(poll),从另一端(队尾)进行插入(offer)。它只支持 FIFO(先进先出)模式。
-
Deque:支持在队列的两端插入和移除元素。可以在头部插入(offerFirst、addFirst)或删除(pollFirst)元素,也可以在尾部插入(offerLast、addLast)或删除(pollLast)元素。它可以同时作为队列和栈使用,既支持 FIFO,又支持 LIFO(后进先出)。
-
-
功能扩展
-
Queue 仅限于队列的基本操作,适合需要顺序处理的场景,如任务调度。
-
Deque 提供了更灵活的操作方式,适用于需要从两端操作的场景,比如浏览器历史记录、双向任务调度等。
-
-
线程安全
-
Queue:Java 提供了线程安全的实现,如 ConcurrentLinkedQueue 和 BlockingQueue 等。
-
Deque:也有线程安全的实现,如 ConcurrentLinkedDeque 和 LinkedBlockingDeque 等。
-
-
典型实现
-
Queue:常见的实现有 LinkedList 和 PriorityQueue(优先队列)。
-
Deque:常见的实现有 ArrayDeque 和 LinkedList(同时实现了 Queue 和 Deque)。
-
总结:Queue 只支持队列的一端操作,适合需要顺序处理的场景;而 Deque 提供了更加灵活的双端操作,适合需要双向处理元素的场景。
PriorityQueue的特点是什么?
PriorityQueue 是一个基于 堆结构 实现的队列,它的主要特点如下:
-
优先级排序,不保证 FIFO 元素不是按插入顺序排列,而是按照优先级(通过元素的自然顺序或自定义的 Comparator)进行排序。每次出队的都是当前优先级最高的元素。
-
底层实现是最小堆 默认情况下,PriorityQueue 是一个 小顶堆,也就是说队头是最小的元素。如果你传入了 Comparator,可以自定义优先级规则,实现大顶堆或其他排序方式。
-
不允许 null 元素 添加 null 会抛出 NullPointerException,因为 null 无法比较优先级。
-
非线程安全 PriorityQueue 是非线程安全的,在多线程环境中需要使用外部同步或使用线程安全的替代品,比如 PriorityBlockingQueue。
-
允许重复元素 PriorityQueue 允许添加多个具有相同优先级的元素,它们会根据堆规则存储,不保证顺序。
-
性能 插入和删除的时间复杂度为 O(log n),因为每次操作都涉及堆的调整。
-
迭代器无序 遍历 PriorityQueue 得到的顺序不是有序的,只能保证每次 poll 出来的元素是当前最小(或最大)。
总结:PriorityQueue 是一个按照优先级出队的队列,适合任务调度、路径搜索、模拟优先处理逻辑等场景。它不是一个“排序好的列表”,而是一个用堆实现的“动态排序结构”。
ArrayDeque和LinkedList的区别?
ArrayDeque 和 LinkedList 都实现了 Deque 接口,可以作为队列或栈使用,但它们在实现方式和性能上有明显区别:
-
底层结构不同
-
ArrayDeque 是基于 可扩展的循环数组 实现的。
-
LinkedList 是基于 双向链表 实现的。
-
-
性能差异
-
ArrayDeque 的插入、删除、访问性能一般优于 LinkedList,因为它使用数组,内存连续,CPU 缓存友好,且没有对象节点的额外开销。
-
LinkedList 在插入和删除方面的性能也为 O(1),但需要维护前后指针,并且频繁创建节点对象,可能导致 GC 压力。
-
-
随机访问
-
ArrayDeque 不支持索引访问,但可以高效地作为栈和队列使用。
-
LinkedList 虽然实现了 List 接口,可以按索引访问,但访问效率低,时间复杂度为 O(n)。
-
-
内存使用
-
ArrayDeque 使用一块连续数组,扩容时需要整体复制。
-
LinkedList 使用链式结构,每个节点都需要额外的内存存储前后指针。
-
-
线程安全
-
两者都不是线程安全的,使用时需外部同步。
-
-
null 元素
-
ArrayDeque 不允许添加 null,会抛出异常。
-
LinkedList 允许存储 null 元素。
-
-
扩容机制
-
ArrayDeque 会在容量不够时自动扩容,通常是容量翻倍。
-
LinkedList 没有容量限制,插入节点时动态创建对象。
-
总结:ArrayDeque 更适合在栈或队列场景中高效使用,是替代 Stack 和 LinkedList 的首选;而 LinkedList 在需要频繁插入、删除任意位置节点时更有优势,但整体性能和内存使用效率略逊一筹。
集合工具类
Collections类提供了哪些常用方法?
Collections
是 Java 提供的一个工具类,位于 java.util
包中,专门为集合类(List、Set、Map 等)提供操作的静态方法。常用方法如下:
-
排序
-
sort(List<T> list)
:对 List 进行升序排序(元素需实现 Comparable)。 -
sort(List<T> list, Comparator<? super T> c)
:按指定比较器排序。
-
-
查找和替换
-
binarySearch(List<? extends Comparable<? super T>> list, T key)
:在已排序的 List 中进行二分查找。 -
max(Collection<? extends T> coll)
/min(...)
:找最大或最小值。 -
replaceAll(List<T> list, T oldVal, T newVal)
:批量替换元素。
-
-
逆序、打乱、填充
-
reverse(List<?> list)
:反转顺序。 -
shuffle(List<?> list)
:随机打乱顺序。 -
fill(List<? super T> list, T obj)
:用指定元素填充整个 List。
-
-
同步包装(线程安全)
-
synchronizedList(List<T> list)
:将非线程安全的 List 包装成线程安全的。 -
synchronizedMap(Map<K,V> map)
/synchronizedSet(...)
等。
-
-
不可变集合
-
unmodifiableList(List<? extends T> list)
:返回不可修改的 List。 -
unmodifiableMap(...)
/unmodifiableSet(...)
:类似用法。
-
-
频率统计与判重
-
frequency(Collection<?> c, Object o)
:统计某元素出现次数。 -
disjoint(Collection<?> c1, Collection<?> c2)
:判断两个集合是否无交集。
-
-
拷贝
-
copy(List<? super T> dest, List<? extends T> src)
:把一个 List 的内容复制到另一个 List 中(前提是 dest 至少和 src 一样大)。
-
-
空集合
-
emptyList()
、emptySet()
、emptyMap()
:返回不可变的空集合,常用于返回值防止 NullPointerException。
-
总结:Collections
提供的这些方法极大地简化了集合的常用操作,是 Java 集合框架中非常实用的工具类。
Arrays.asList()方法有什么注意事项?
Arrays.asList()
方法会将数组转为一个固定大小的列表,不能添加或删除元素,只能修改已有元素。它返回的不是 java.util.ArrayList,而是 Arrays 内部的一个包装类。原数组和返回的列表是共享数据的,互相影响。传入基本类型数组时可能造成误解,整个数组会被当作一个元素。
重点:不能扩容,数据共享,基本类型小心用。