当前位置: 首页 > web >正文

面试篇:Java集合

为什么java的集合只能存放封装类

在 Java 中,集合类(如 ListSetMap)是基于泛型的,而泛型要求使用对象类型参数。然而,int 和其他基本数据类型(如 charfloat 等)并不是对象,而是原始类型(primitive types)。因此,Java 的集合不能直接存放原始类型。

为了支持在集合中存储原始类型,Java 提供了封装类(Wrapper classes),例如 Integer 对应 intCharacter 对应 charDouble 对应 double 等。这些封装类是对象,它们使得基本数据类型能够作为对象使用,从而可以被存储在集合中。

为什么会这样?

  1. 泛型的设计:Java 泛型是基于对象的,因为泛型要求类型参数必须是引用类型(即对象)。原始数据类型(primitive types)是值类型,它们不是对象,因此不能直接作为泛型类型参数。

  2. 封装类的引入:Java 提供了封装类(如 IntegerDouble 等)来解决这个问题。封装类是原始数据类型的对象表示,可以让我们在集合中存储数值,同时提供一些额外的方法来操作这些数值。

  3. 自动装箱(Autoboxing)与拆箱(Unboxing):从 Java 5 开始,Java 引入了自动装箱和拆箱的概念,允许在原始类型和对应的封装类之间自动转换。这意味着,尽管我们可以使用基本数据类型的值(如 int),Java 会自动将其转换为 Integer 对象,并在需要时将其还原为基本类型。这个过程使得基本类型和对象类型之间的转换变得更加简便。

Java集合框架基础

Java集合框架的主要接口有哪些?

Java集合框架的主要接口有:

  1. Collection:是最基本的集合接口,List、Set 和 Queue 都继承自它。

  2. List:有序集合,元素可重复。

  3. Set:无序集合,元素不可重复。

  4. Queue:队列接口,用于按特定规则处理元素,比如先进先出。

  5. Deque:双端队列,支持从两端插入和删除元素。

  6. 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 中用于遍历集合元素的一种机制。它提供了一个统一的接口,用于访问集合中的元素,而不需要关心集合的具体实现方式。

迭代器主要有三个方法:

  1. hasNext():判断集合中是否还有下一个元素,返回布尔值。

  2. next():返回集合中的下一个元素。如果没有更多元素,则抛出 NoSuchElementException

  3. remove():删除当前迭代器指向的元素。这是一个可选操作,某些集合可能不支持。

通过迭代器,集合的元素可以被遍历,而不需要暴露集合的实现细节。

List相关

ArrayList和LinkedList的区别?

ArrayList 和 LinkedList 都是 List 接口的实现类,但它们的内部结构和性能特点不同:

  1. 内部结构

    • ArrayList 底层使用数组来存储元素,具有随机访问能力。

    • LinkedList 底层使用双向链表来存储元素,每个元素都包含对前后元素的引用。

  2. 访问速度

    • ArrayList 支持通过索引直接访问元素,时间复杂度为 O(1)。

    • LinkedList 需要从头或尾开始遍历,直到找到指定元素,时间复杂度为 O(n)。

  3. 插入和删除操作

    • ArrayList 在中间插入或删除元素时,必须移动元素,时间复杂度为 O(n)。

    • LinkedList 在中间插入或删除元素时,只需要调整链表节点的引用,时间复杂度为 O(1)。

  4. 内存使用

    • ArrayList 由于底层是数组,内存使用较为紧凑,但如果数组扩容时会发生性能下降。

    • LinkedList 由于每个元素都需要存储前后指针,内存开销较大。

总结:如果频繁进行访问操作,ArrayList 更合适;如果频繁进行插入和删除操作,LinkedList 更优。

ArrayList的扩容机制是怎样的?

ArrayList 的扩容机制是基于数组的,当 ArrayList 中的元素数量达到数组的容量时,它会自动进行扩容。具体扩容过程如下:

  1. 初始容量:当创建一个 ArrayList 时,如果没有指定初始容量,默认的初始容量是 10。也就是说,ArrayList 会先分配一个大小为 10 的数组来存储元素。

  2. 扩容条件:当 ArrayList 中的元素数量超过当前数组容量时,就会触发扩容操作。

  3. 扩容比例:每次扩容时,ArrayList 会将原数组的大小扩大为原来的 1.5 倍。也就是说,新的容量是旧容量的 1.5 倍,并且是向上取整的。

  4. 扩容过程:扩容时,ArrayList 会创建一个新的更大的数组,并将原数组中的元素复制到新的数组中。

这种扩容机制虽然确保了 ArrayList 能够容纳更多的元素,但也带来了性能上的开销,尤其是在频繁插入元素时,可能会导致频繁的数组复制。

总结:ArrayList 扩容时会将容量增加为原容量的 1.5 倍,扩容操作会带来性能损失,但它能够保证 ArrayList 能够灵活增长。

Vector和ArrayList的区别?

Vector 和 ArrayList 都是基于数组实现的 List,但它们的主要区别有以下几点:

  1. 是否线程安全:Vector 是线程安全的,所有方法都加了 synchronized;ArrayList 是非线程安全的,性能更高。

  2. 扩容机制:Vector 每次扩容是原容量的 2 倍;ArrayList 是 1.5 倍。

  3. 性能开销:由于加锁机制,Vector 在多线程下能保证安全,但在单线程环境中性能比 ArrayList 差。

  4. 使用场景:单线程建议用 ArrayList;如果需要线程安全,优先考虑使用 Concurrent 包下的集合,如 CopyOnWriteArrayList,而不是 Vector。

总结:Vector 是早期设计,已经过时,ArrayList 性能更优,适用于大多数场景。

CopyOnWriteArrayList是如何实现线程安全的?

CopyOnWriteArrayList 通过“写时复制”机制实现线程安全。它的核心原理是:

每当有写操作(如 add、remove、set)时,不是在原数组上直接修改,而是先复制出一个新的数组,在这个新数组上执行修改操作,修改完成后再将新数组的引用赋值回原来的引用。这样做的好处是,读操作仍然使用旧数组,不会受到写操作的影响。

具体特点如下:

  1. 读操作无需加锁,多个线程可以并发读,性能高。

  2. 写操作会复制整个数组,成本较高,因此不适合写操作频繁的场景。

  3. 适合读多写少的并发场景,比如缓存、事件监听器列表。

它牺牲了写性能,换来了读的无锁高并发。线程读时看到的永远是稳定、不变的快照。

Set相关

HashSet和TreeSet的区别?

HashSet 和 TreeSet 都是实现了 Set 接口的集合类,但它们在底层结构、排序方式和性能上有明显区别:

  1. 底层实现 HashSet 基于 HashMap 实现,元素无序,依赖 hashCode 和 equals 方法判断唯一性。 TreeSet 基于 TreeMap,底层是红黑树,元素有序,按自然顺序或指定的 Comparator 排序。

  2. 元素顺序 HashSet 不保证元素顺序,插入顺序和遍历顺序可能不同。 TreeSet 会自动对元素进行排序,插入和遍历时都是有序的。

  3. 性能差异 HashSet 插入、删除、查找的平均时间复杂度是 O(1),性能更高。 TreeSet 所有操作的时间复杂度是 O(log n),因为它维护了元素的有序性。

  4. 使用场景 HashSet 更适合快速查找、去重、无序集合。 TreeSet 适合需要排序的场景,比如从小到大遍历、范围查询等。

总结:HashSet 快但无序,TreeSet 有序但慢,按是否需要排序来选择。

HashSet是如何保证元素唯一的?

HashSet 是通过元素的 hashCode 和 equals 方法来保证元素唯一的。

具体过程如下:

  1. 当你向 HashSet 添加一个元素时,它会先调用该元素的 hashCode 方法,计算出一个哈希值,用于确定在底层 HashMap 中的桶位置。

  2. 如果这个位置还没有元素,直接插入;如果已经有元素(即发生哈希冲突),它会继续调用 equals 方法,逐个和已有元素比较。

  3. 如果 equals 判断出已有相同元素,则认为是重复元素,不会添加;如果都不相等,就插入到该位置的链表或红黑树中。

所以,要让 HashSet 正确判断元素是否唯一,必须确保你自定义的类重写了 hashCode 和 equals 方法,并且两者逻辑保持一致。否则可能导致无法去重或行为异常。

LinkedHashSet的特点是什么?

LinkedHashSet 继承自 HashSet,它的主要特点是在保证元素唯一性的同时,保持元素的插入顺序

具体特点如下:

  1. 底层结构是 HashMap 加一条双向链表。链表记录元素的插入顺序。

  2. 插入顺序不会改变,遍历时元素顺序和插入时一致。

  3. 元素唯一性依旧通过 hashCode 和 equals 判断,和 HashSet 一样。

  4. 性能略低于 HashSet,因为维护了额外的顺序信息,但插入、删除、查找的时间复杂度仍是 O(1)。

总结:如果你需要一个去重且保持插入顺序的集合,就选 LinkedHashSet。它在 HashSet 的基础上多了一条顺序链。

Map相关

HashMap的工作原理是什么?

HashMap 的核心是“数组 + 链表(或红黑树)”的结构,它的工作原理主要包括以下几个步骤:

  1. 存储结构 底层是一个数组,每个数组元素是一个链表或红黑树的头节点。这个结构称为桶(bucket)。

  2. 添加元素 当你调用 put(key, value) 时,HashMap 会先对 key 进行 hash 计算,然后通过取模运算确定应该放到哪个桶里。

  3. 处理冲突 如果多个 key 经过 hash 后落在同一个桶里(哈希冲突),就通过链表的方式向后连接。如果链表长度超过阈值(默认是8)并且数组长度大于64,就转换为红黑树,提高查找效率。

  4. 覆盖旧值 在插入之前,会遍历该桶下的链表或红黑树,通过 equals 方法判断 key 是否已经存在。如果存在,就更新 value,否则新增节点。

  5. 扩容机制 当 HashMap 的元素数量超过负载因子(默认是 0.75 × 容量)时,会触发扩容,将数组扩展为原来的 2 倍,并重新计算所有元素的位置,这个过程叫 rehash。

  6. 查找和删除 查找就是根据 key 计算 hash,然后去对应的桶中遍历链表或树;删除也是一样,先定位到桶,再从结构中移除节点。

总结:HashMap 通过 hash + 链表/树 结合的方式实现高效存储,查找是平均 O(1),在冲突严重或极端情况下最坏是 O(n)。线程不安全,适用于单线程或通过额外手段控制并发。

HashMap和Hashtable的区别?

HashMap 和 Hashtable 的主要区别如下:

  1. 线程安全性 Hashtable 是线程安全的,内部所有方法基本都加了 synchronized。 HashMap 是非线程安全的,需要自己保证并发控制。

  2. 性能 由于 Hashtable 加锁,性能比 HashMap 差。 HashMap 在单线程环境下更高效。

  3. null 值处理 Hashtable 不允许 key 或 value 为 null,任何一个为 null 都会抛异常。 HashMap 允许一个 key 为 null,value 可以有多个 null。

  4. 出现时间 Hashtable 是早期的类,出现在 JDK 1.0,属于遗留类。 HashMap 是 JDK 1.2 引入的,属于集合框架的一部分。

  5. 替代关系 在多线程环境中,Hashtable 不再推荐使用,建议用 ConcurrentHashMap。 在单线程或需要手动控制同步的情况下,用 HashMap 更合适。

总结:HashMap 更现代、更灵活,Hashtable 设计过时,能不用就不用。

HashMap的put方法执行过程是怎样的?

HashMap 的 put 方法执行过程大致如下:

  1. 先判断 key 是否为 null,如果是 null,会固定放到 table[0] 的桶中处理。

  2. 如果 key 不为 null,就调用 key 的 hashCode 方法,经过扰动函数计算出 hash 值,再根据 hash 决定应该放到哪个桶(index = (n - 1) & hash)。

  3. 找到目标桶后,如果桶是空的,直接新建节点放进去。

  4. 如果桶中已有节点,就遍历链表或红黑树:

    • 如果发现已有节点的 key 和当前 key 相等(通过 equals 判断),就更新该节点的 value。

    • 如果没有相等的 key,就在链尾插入新节点。

  5. 插入完成后,如果桶中的节点数量超过阈值(8),并且当前数组长度大于等于 64,就将链表转为红黑树。

  6. 最后判断是否需要扩容。如果当前元素总数超过阈值(capacity × load factor),就将数组扩容为原来的 2 倍,并将原有节点重新分布(rehash)。

整个过程体现了 HashMap 的三大特性:哈希定位、高效插入、动态扩容。

HashMap的扩容机制是怎样的?

HashMap 的扩容机制本质上是数组的动态扩展,用来保证在元素增多时仍能保持较高的性能。具体过程如下:

  1. 触发条件 当 HashMap 中的元素数量超过容量 × 负载因子(默认是 0.75)时,就会触发扩容。

  2. 扩容大小 每次扩容都是将当前数组容量扩大为原来的 2 倍。例如从 16 扩展为 32。

  3. 创建新数组 扩容时,会新建一个更大的数组,并将原数组中的所有节点重新计算索引位置,迁移过去。这个过程叫做 rehash。

  4. 节点再分布 由于数组长度变了,元素的位置也要重新分配。节点根据 (newCapacity - 1) & hash 重新定位。链表节点按顺序重新链接,树节点也会被拆分成高位链和低位链。

  5. 链表转树或树转链 在扩容过程中,如果某个桶原本是红黑树,元素少了之后可能会退化成链表,反之链表在新桶中元素增多也可能变成树。

注意:扩容是非常消耗性能的操作,因为涉及所有元素的重新分布。所以如果你知道要存多少数据,建议提前指定初始容量,避免频繁扩容。

总结:HashMap 扩容是“容量翻倍 + 元素重分布”,用以保证散列均匀,提高性能,但代价是 rehash 过程非常重。

HashMap为什么线程不安全?

HashMap 线程不安全的原因主要在于它的设计没有对并发访问做同步控制。具体原因包括:

  1. 多个线程同时 put 可能导致数据丢失 如果两个线程同时向同一个桶 put 元素,可能一个线程刚写完,另一个线程就覆盖了,导致前一个值丢失。

  2. 扩容时的并发问题 在多线程环境中,如果多个线程同时触发扩容,可能导致旧数组中的链表断裂,元素丢失,甚至出现死循环(JDK 1.7 中曾出现过)。

  3. 非原子操作 put、resize、rehash 等操作本质上不是原子的,由多个步骤组成,如果中途被打断,集合结构可能就不一致了。

  4. 无同步机制 HashMap 本身没有使用 synchronized 或其他并发控制手段,所以线程之间的修改完全不可见,会发生竞态条件。

总结:HashMap 适用于单线程环境或通过外部手段保证同步。在并发场景下建议使用 ConcurrentHashMap,它通过分段锁或 CAS 等机制保证线程安全。

ConcurrentHashMap如何实现线程安全?

ConcurrentHashMap 通过分段锁(Segment)和细粒度锁的机制来实现线程安全,相比 HashMap,它提供了更高效的并发访问能力。具体的实现方式包括以下几个关键点:

  1. 分段锁机制(JDK 1.7 及之前) 在 JDK 1.7 中,ConcurrentHashMap 通过将整个哈希表分为多个段(Segment),每个段都维护着一个小的 HashMap。在多线程环境下,每个线程只需要锁住自己操作的段,这样就能避免多个线程争抢同一个锁,减少了锁的竞争。每个段使用独立的锁,实现了对不同段的并发访问。

  2. 桶级别锁(JDK 1.8) 在 JDK 1.8 中,ConcurrentHashMap 采用了更加细粒度的锁,使用 CAS(Compare And Swap)桶级别锁(对于链表或红黑树的桶)来提高并发度。

    • CAS 用于原子性操作,确保更新操作是无锁的。

    • 锁分离:不同的桶(Bucket)通过独立的锁来保证线程安全,这样多个线程可以并行地操作不同的桶,进一步减少了竞争。

  3. 无锁操作(读操作) 在 ConcurrentHashMap 中,读操作是无锁的。即使有线程在进行写操作,读操作也不会阻塞。通过将结构操作与数据访问操作分开,使得读操作在没有修改结构的情况下可以安全并发。

  4. 扩容机制 扩容时,ConcurrentHashMap 使用的是 延迟扩容 的策略,而不是像 HashMap 一样在发生扩容时立即锁住整个哈希表。在并发环境下,扩容是分段执行的,不会影响正在进行的读写操作。

  5. 操作粒度细化 除了读操作和扩容,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 实现类,它有以下几个主要特点:

  1. 有序性 TreeMap 保证键值对按键的自然顺序(通过 Comparable 接口)或者根据构造时传入的 Comparator 进行排序。与 HashMap 不同,TreeMap 按照键的顺序进行存储和遍历。

  2. 红黑树实现 TreeMap 底层是红黑树,保证了插入、删除、查找等操作的时间复杂度为 O(log n),这使得 TreeMap 在处理大量数据时比 HashMap 更适合需要排序或范围查询的场景。

  3. 键的唯一性 和 HashMap 一样,TreeMap 也保证键的唯一性。每个键只能映射到一个值,如果插入重复的键,会覆盖原有的值。

  4. 支持导航操作 由于实现了 NavigableMap 接口,TreeMap 提供了多种导航方法,支持 范围查询(如 subMap()headMap()tailMap())、获取最小/最大键值对(如 firstEntry()lastEntry())等功能。

  5. 不允许 null 键 TreeMap 不允许插入 null 作为键。如果尝试将 null 作为键插入,会抛出 NullPointerException。但值部分可以是 null

  6. 线程不安全 TreeMap 不是线程安全的。如果需要在多线程环境中使用,必须自己使用同步机制或者使用 ConcurrentSkipListMap 替代。

  7. 遍历顺序 由于 TreeMap 内部按顺序存储元素,因此在遍历时会按照自然顺序或指定的比较器顺序输出键值对。

总结:TreeMap 是一个有序的 Map 实现,底层基于红黑树,支持高效的查找、插入、删除操作,并且提供了丰富的范围查询和导航功能,适用于需要保持键排序的场景。

其他集合类

Queue和Deque的区别?

Queue 和 Deque 是 Java 中两个常用的集合接口,它们的区别主要体现在 操作方式功能扩展 上:

  1. 基本定义

    • Queue:是一个线性数据结构,通常用于表示一个 先进先出(FIFO) 的队列。它提供了基本的入队(offer)、出队(poll)和查看队头(peek)等操作。

    • Deque:全称 双端队列(Double-Ended Queue),是 Queue 的一个扩展,它支持在队列的两端进行元素的添加和移除操作,即既可以作为队列(FIFO),也可以作为栈(LIFO)使用。

  2. 操作支持

    • Queue:通常只支持从队列的一端(队头)进行移除(poll),从另一端(队尾)进行插入(offer)。它只支持 FIFO(先进先出)模式。

    • Deque:支持在队列的两端插入和移除元素。可以在头部插入(offerFirst、addFirst)或删除(pollFirst)元素,也可以在尾部插入(offerLast、addLast)或删除(pollLast)元素。它可以同时作为队列和栈使用,既支持 FIFO,又支持 LIFO(后进先出)。

  3. 功能扩展

    • Queue 仅限于队列的基本操作,适合需要顺序处理的场景,如任务调度。

    • Deque 提供了更灵活的操作方式,适用于需要从两端操作的场景,比如浏览器历史记录、双向任务调度等。

  4. 线程安全

    • Queue:Java 提供了线程安全的实现,如 ConcurrentLinkedQueueBlockingQueue 等。

    • Deque:也有线程安全的实现,如 ConcurrentLinkedDequeLinkedBlockingDeque 等。

  5. 典型实现

    • Queue:常见的实现有 LinkedListPriorityQueue(优先队列)。

    • Deque:常见的实现有 ArrayDequeLinkedList(同时实现了 Queue 和 Deque)。

总结:Queue 只支持队列的一端操作,适合需要顺序处理的场景;而 Deque 提供了更加灵活的双端操作,适合需要双向处理元素的场景。

PriorityQueue的特点是什么?

PriorityQueue 是一个基于 堆结构 实现的队列,它的主要特点如下:

  1. 优先级排序,不保证 FIFO 元素不是按插入顺序排列,而是按照优先级(通过元素的自然顺序或自定义的 Comparator)进行排序。每次出队的都是当前优先级最高的元素。

  2. 底层实现是最小堆 默认情况下,PriorityQueue 是一个 小顶堆,也就是说队头是最小的元素。如果你传入了 Comparator,可以自定义优先级规则,实现大顶堆或其他排序方式。

  3. 不允许 null 元素 添加 null 会抛出 NullPointerException,因为 null 无法比较优先级。

  4. 非线程安全 PriorityQueue 是非线程安全的,在多线程环境中需要使用外部同步或使用线程安全的替代品,比如 PriorityBlockingQueue。

  5. 允许重复元素 PriorityQueue 允许添加多个具有相同优先级的元素,它们会根据堆规则存储,不保证顺序。

  6. 性能 插入和删除的时间复杂度为 O(log n),因为每次操作都涉及堆的调整。

  7. 迭代器无序 遍历 PriorityQueue 得到的顺序不是有序的,只能保证每次 poll 出来的元素是当前最小(或最大)。

总结:PriorityQueue 是一个按照优先级出队的队列,适合任务调度、路径搜索、模拟优先处理逻辑等场景。它不是一个“排序好的列表”,而是一个用堆实现的“动态排序结构”。

ArrayDeque和LinkedList的区别?

ArrayDeque 和 LinkedList 都实现了 Deque 接口,可以作为队列或栈使用,但它们在实现方式和性能上有明显区别:

  1. 底层结构不同

    • ArrayDeque 是基于 可扩展的循环数组 实现的。

    • LinkedList 是基于 双向链表 实现的。

  2. 性能差异

    • ArrayDeque 的插入、删除、访问性能一般优于 LinkedList,因为它使用数组,内存连续,CPU 缓存友好,且没有对象节点的额外开销。

    • LinkedList 在插入和删除方面的性能也为 O(1),但需要维护前后指针,并且频繁创建节点对象,可能导致 GC 压力。

  3. 随机访问

    • ArrayDeque 不支持索引访问,但可以高效地作为栈和队列使用。

    • LinkedList 虽然实现了 List 接口,可以按索引访问,但访问效率低,时间复杂度为 O(n)。

  4. 内存使用

    • ArrayDeque 使用一块连续数组,扩容时需要整体复制。

    • LinkedList 使用链式结构,每个节点都需要额外的内存存储前后指针。

  5. 线程安全

    • 两者都不是线程安全的,使用时需外部同步。

  6. null 元素

    • ArrayDeque 不允许添加 null,会抛出异常。

    • LinkedList 允许存储 null 元素。

  7. 扩容机制

    • ArrayDeque 会在容量不够时自动扩容,通常是容量翻倍。

    • LinkedList 没有容量限制,插入节点时动态创建对象。

总结:ArrayDeque 更适合在栈或队列场景中高效使用,是替代 Stack 和 LinkedList 的首选;而 LinkedList 在需要频繁插入、删除任意位置节点时更有优势,但整体性能和内存使用效率略逊一筹。

集合工具类

Collections类提供了哪些常用方法?

Collections 是 Java 提供的一个工具类,位于 java.util 包中,专门为集合类(List、Set、Map 等)提供操作的静态方法。常用方法如下:

  1. 排序

    • sort(List<T> list):对 List 进行升序排序(元素需实现 Comparable)。

    • sort(List<T> list, Comparator<? super T> c):按指定比较器排序。

  2. 查找和替换

    • binarySearch(List<? extends Comparable<? super T>> list, T key):在已排序的 List 中进行二分查找。

    • max(Collection<? extends T> coll) / min(...):找最大或最小值。

    • replaceAll(List<T> list, T oldVal, T newVal):批量替换元素。

  3. 逆序、打乱、填充

    • reverse(List<?> list):反转顺序。

    • shuffle(List<?> list):随机打乱顺序。

    • fill(List<? super T> list, T obj):用指定元素填充整个 List。

  4. 同步包装(线程安全)

    • synchronizedList(List<T> list):将非线程安全的 List 包装成线程安全的。

    • synchronizedMap(Map<K,V> map) / synchronizedSet(...) 等。

  5. 不可变集合

    • unmodifiableList(List<? extends T> list):返回不可修改的 List。

    • unmodifiableMap(...) / unmodifiableSet(...):类似用法。

  6. 频率统计与判重

    • frequency(Collection<?> c, Object o):统计某元素出现次数。

    • disjoint(Collection<?> c1, Collection<?> c2):判断两个集合是否无交集。

  7. 拷贝

    • copy(List<? super T> dest, List<? extends T> src):把一个 List 的内容复制到另一个 List 中(前提是 dest 至少和 src 一样大)。

  8. 空集合

    • emptyList()emptySet()emptyMap():返回不可变的空集合,常用于返回值防止 NullPointerException。

总结:Collections 提供的这些方法极大地简化了集合的常用操作,是 Java 集合框架中非常实用的工具类。

Arrays.asList()方法有什么注意事项?

Arrays.asList() 方法会将数组转为一个固定大小的列表,不能添加或删除元素,只能修改已有元素。它返回的不是 java.util.ArrayList,而是 Arrays 内部的一个包装类。原数组和返回的列表是共享数据的,互相影响。传入基本类型数组时可能造成误解,整个数组会被当作一个元素。

重点:不能扩容,数据共享,基本类型小心用。

http://www.xdnf.cn/news/1401.html

相关文章:

  • 新手村:过拟合(Overfitting)
  • WPF 图片文本按钮 自定义按钮
  • Shopee五道质检系统重构东南亚跨境格局,2025年电商游戏规则悄然改写
  • DIY钢铁侠方舟反应堆第二期—第一代电路板展示
  • 【开源】STM32HAL库驱动ST7789_240×240(硬件SPI+软件SPI)
  • Yocto项目实战教程-第8章树莓派启动定制镜像-8.3小节-树莓派BSP层
  • Redis的string类型使用
  • 大数据利器Kafka
  • 基于PaddleOCR对图片中的excel进行识别并转换成word优化(二)
  • 【白雪讲堂】GEO优化第7篇 -构建《推荐类》内容的结构化模板
  • EasySearch 服务昨天还好好的,为什么今天突然访问不了了?
  • 安卓14默认赋予应用权限
  • 克拉屈滨联合阿糖胞苷与米托蒽醌(CLAM方案)
  • 基于ARM+FPGA+DSP的储能协调控制器解决方案,支持国产化
  • 视频智能分析平台EasyCVR无线监控:全流程安装指南与功能应用解析
  • Python 流程控制
  • radare2 入门与反汇编
  • Linux实现网络计数器
  • VS中回显109:对‘pthread_create’未定义的引用
  • HCIP-H12-821 核心知识梳理 (6)
  • 黑马Java基础笔记-3
  • 提高Spring Boot开发效率的实践
  • 算法题-图论
  • Linux进程状态及转换关系
  • webrtc建立连接的过程
  • UML 顺序图:电子图书馆管理系统的交互之道
  • RocketMQ 核心架构速览
  • 45、子类需要重写父类的构造函数嘛,子类自己的构造函数呢?
  • Git技术详解:从核心原理到实际应用
  • 示波器探头干扰致晶振停振的机理与工程对策