首页 死磕 Java 优质系列 Java 技术总览 Java 面试宝典 关于我
logo

Java 集合面试题

原
 2023-12-11
©版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 本文链接：https://www.skjava.com/mianshi/tiji/1491278714

List 接口

List、Set、Map 之间的区别

  1. List（列表）
    • 有序性：List 是有序集合，元素的顺序是按照它们被添加的顺序来存储和访问的。你可以通过索引来访问列表中的元素。
    • 元素重复性：List 允许存储重复的元素，同一个元素可以出现多次。
  2. Set（集合）
    • 无序性：Set 是无序集合，元素之间没有明确的顺序。你不能通过索引来访问集合中的元素。
    • 元素唯一性：Set 中不允许存储重复的元素，每个元素在集合中只能出现一次。
  3. Map
    • 存储键值对：Map 存储键值对，每个键关联一个唯一的值。这使得你可以通过键来查找和访问与之相关联的值。
    • 键的唯一性：在一个 Map 中，每个键只能出现一次，但不同的键可以关联不同的值。

Arraylist 与 LinkedList 的区别

  1. 内部实现
    • ArrayList 使用一个动态数组来存储元素。当元素数量增加时，ArrayList 会自动增加其底层数组的大小以容纳更多元素。
    • LinkedList 使用一个双向链表来存储元素。每个元素都包含对前一个元素和后一个元素的引用。
  2. 插入和删除操作
    • 在 ArrayList 中，插入和删除元素通常比较慢，特别是在列表的中间位置，因为需要移动元素来保持顺序。在列表末尾添加元素的操作相对较快。
    • 在 LinkedList 中，插入和删除元素通常比较快，尤其是在列表的中间位置，因为只需要更新节点的引用。但在列表末尾添加元素的操作可能比 ArrayList 慢一些，因为需要遍历链表找到末尾节点。
  3. 访问元素
    • 通过索引访问元素的操作非常快速，因为可以直接在数组中找到元素。
    • 在 LinkedList 中，通过索引访问元素需要从头节点或尾节点开始遍历链表，因此访问速度相对较慢。
  4. 内存占用
    • 由于需要预分配一定大小的数组，ArrayList 可能会浪费一些内存空间。如果数组大小超过了实际元素数量，会导致内存浪费。
    • LinkedList 比较节省内存，因为它只存储实际的元素以及每个元素的前后节点引用。
  5. 适用场景
    • ArrayList 适用于需要快速访问元素、不需要频繁插入和删除操作的情况。
    • LinkedList 适用于需要频繁插入和删除操作、不需要快速访问元素的情况。

ArrayList 和 Vector 的区别

ArrayList 和 Vector 都是 Java 中用于存储和操作动态数组（可变长度数组）的集合类，但他们之间还是有一些差异的：

  1. 线程安全性
    • ArrayList 是非线程安全的，这意味着在多线程环境下，如果不采取额外的同步措施，多个线程同时访问和修改 ArrayList 可能会导致数据不一致或抛出异常。
    • Vector 是线程安全的，它的方法都是同步的，这意味着在多线程环境下，多个线程可以安全地访问和修改 Vector，但这也会导致性能开销，因为每个方法都要获得锁。
  2. 性能：
    • 由于不需要进行同步，ArrayList 在单线程环境下通常比 Vector 性能更好，因为它没有额外的同步开销。
    • 由于需要同步，Vector 在多线程环境下可能会有较高的性能开销，因此在单线程环境中可能不如 ArrayList 快。
  3. 增长策略：
    • ArrayList 的增长策略是在当前容量不足时，将容量扩大一半。
    • Vector 的增长策略是在当前容量不足时，将容量翻倍。

综上所述，如果你在单线程环境下工作，并且不需要线程安全性，建议使用 ArrayList，因为它在性能上通常更优。如果你需要线程安全性，可以使用 Vector，但需要注意性能开销。

ArrayList 的扩容机制？

ArrayList 的扩容机制是在当前容量不足时自动增加其内部数组的大小，以容纳更多元素。机制如下：

  1. 初始容量： 当你创建一个 ArrayList 时，它会分配一个初始容量。默认情况下，初始容量为 10，但你可以在创建 ArrayList 时指定不同的初始容量。
  2. 添加元素： 当你向 ArrayList 添加元素时，它会检查当前元素数量是否已经达到了容量上限。如果元素数量等于或超过容量上限，就会触发扩容操作。
  3. 扩容操作： 扩容操作会创建一个新的更大的数组（通常是原来容量的 1.5 倍或 2 倍，具体取决于具体的实现），然后将所有元素从旧数组复制到新数组中。这个过程涉及数组的拷贝操作，因此具有一定的时间开销。
  4. 更新引用： 一旦新数组创建并所有元素都复制到新数组中，ArrayList 会更新内部引用，使其指向新数组。

ArrayList 采用这种扩容策略是为了平衡空间的利用和时间开销。如果每次添加元素都触发扩容，会导致性能下降，因为需要频繁地进行数组复制操作。因此，通过一次性扩容一定的大小，可以减少扩容的频率，提高整体性能。

需要注意的是，虽然扩容操作是 ArrayList 内部自动处理的，但在某些情况下，如果你知道 ArrayList 预计会存储大量元素，你可以在创建 ArrayList 时指定一个较大的初始容量，以减少扩容次数，从而提高性能。

Queue 与 Deque 的区别

Queue（队列）：

  • Queue 是一种线性数据结构，它遵循先进先出（FIFO）的原则，即最早添加的元素最早被移除。
  • Queue 接口继承自 Collection 接口，它定义了一组用于添加、删除和检查元素的方法，如 add、offer、remove、poll、element 和 peek 等。
  • Queue 不支持在中间插入或删除元素，只能在队列的头部添加和尾部移除元素。

Deque（双端队列）：

  • Deque 也是一种线性数据结构，它允许在队列的两端进行插入和删除操作，因此可以用作队列和栈的结合体。
  • Deque 接口继承自 Queue 接口，因此包含了 Queue 的所有方法，同时还定义了一组用于在两端添加和删除元素的方法，如 addFirst、addLast、removeFirst、removeLast、getFirst 和 getLast 等。
  • Deque 允许在队列的头部和尾部插入和删除元素，因此具有更灵活的使用方式。

总结一下，主要区别在于以下两点：

  • Queue 是一种遵循先进先出（FIFO）原则的线性数据结构，只支持在队列的头部添加和尾部移除元素。
  • Deque 是一种允许在队列的两端进行插入和删除操作的线性数据结构，可以用作队列和栈的结合体，具有更灵活的使用方式。

说一说PriorityQueue

PriorityQueue（优先队列）是一个基于优先级堆（Priority Heap）实现的队列。与普通队列不同，PriorityQueue 中的元素并不是按照它们的插入顺序进行处理，而是按照它们的优先级顺序进行处理。在 PriorityQueue 中，具有最高优先级的元素将首先被处理。

以下是关于 PriorityQueue 的一些重要特点和使用方式：

  1. 优先级顺序：PriorityQueue 中的元素按照它们的自然顺序或者根据指定的比较器（Comparator）来确定优先级。具有最高优先级的元素将位于队列的头部。
  2. 插入和删除操作：PriorityQueue 提供了插入（offer 或 add）和删除（poll 或 remove）元素的操作。插入操作会根据元素的优先级将元素放入合适的位置，删除操作会移除并返回队列中具有最高优先级的元素。
  3. 不允许 null 元素：PriorityQueue 不允许存储 null 元素，因为 null 无法用于确定元素的优先级。
  4. 底层数据结构：PriorityQueue 通常使用二叉堆（binary heap）或斐波那契堆（Fibonacci heap）等数据结构来实现。这些数据结构保证了插入和删除操作的高效性，插入和删除的时间复杂度通常为 O(log n)。
  5. 用途：PriorityQueue 在很多场景下都非常有用，例如实现优先级调度算法、Dijkstra 算法（用于求解最短路径问题）、Prim 算法（用于生成最小生成树）等。它也常用于任务调度、事件驱动编程等领域。

有数组了为什么还要搞个 ArrayList 呢？

通常我们在使用的时候，如果在不明确要插入多少数据的情况下，普通数组就很尴尬了，因为你不知道需要初始化数组大小为多少，而 ArrayList 可以使用默认的大小，当元素个数到达一定程度后，会自动扩容。 可以这么来理解：我们常说的数组是定死的数组，ArrayList 却是动态数组。

如何实现数组和 List 之间的转换？

  • List转换成为数组：调用ArrayList的toArray方法。
  • 数组转换成为List：调用Arrays的asList方法。

什么是 fail-fast 机制？

fail-fast 机制是 Java 集合（Collection）中的一种错误机制。它的主要思想是，如果在迭代或操作集合的过程中检测到了不一致或并发冲突等问题，立即抛出异常或报错，而不是继续执行可能会导致更严重问题的操作。

例如：当某一个线程 A 通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变了，那么线程 A 访问集合时，就会抛出 ConcurrentModificationException 异常，产生 fail-fast 事件。这里的操作主要是指 add、remove 和 clear，对集合元素个数进行修改。

HashMap

HashMap 和 Hashtable 的区别

线程安全性

  • HashMap 是非线程安全的，不提供任何内置的线程同步机制。这意味着如果多个线程同时访问和修改一个 HashMap，可能会导致数据不一致或抛出并发异常（ConcurrentModificationException）。
  • HashTable 是线程安全的，它的方法都是同步的，因此多个线程可以安全地访问和修改 HashTable。但这也会导致性能开销，因为同步操作会引入竞争和等待。

性能

  • 由于不提供内置的线程同步，HashMap 在单线程环境下通常比 HashTable 性能更好。在多线程环境下，如果需要线程安全性，可以考虑使用 ConcurrentHashMap。
  • HashTable 在多线程环境下提供了线程安全性，但会降低性能。

空键和空值

  • HashMap 允许使用一个键为 null，并且允许多个值为 null。
  • HashTable 不允许使用 null 作为键或值，任何尝试将 null 插入 HashTable 都会导致抛出 NullPointerException。

迭代器：

  • HashMap 的迭代器是快速失败的，这意味着在迭代期间如果有其他线程修改了 HashMap，会抛出 ConcurrentModificationException 异常。
  • HashTable 的迭代器不是快速失败的，允许在迭代期间修改表格，但可能会导致不确定的行为。

遗留性质

HashTable 是 Java 1.0 时引入的遗留类，虽然仍然可用，但通常不建议在新代码中使用。推荐使用 ConcurrentHashMap 来替代 HashTable。

HashMap 和 TreeMap 区别

内部数据结构

  • HashMap内部使用哈希表（散列表）来存储键值对。哈希表允许通过键来快速检索值，因此查找操作的时间复杂度通常是常数时间O(1)，但在某些情况下可能会达到O(n)。
  • TreeMap内部使用红黑树来存储键值对。红黑树是一种自平衡的二叉搜索树，它保持键值对的有序性，因此查找、插入和删除操作的时间复杂度是对数时间O(log n)。

元素顺序

  • HashMap不保证元素的顺序。即使您添加元素的顺序是固定的，迭代HashMap时也不能保证元素按照特定的顺序返回。
  • TreeMap会按照键的自然顺序或者通过提供的Comparator进行排序，因此元素会按照键的顺序返回。

性能

  • HashMap通常在大多数情况下具有更快的性能，因为它的查找操作是常数时间的，除非发生哈希冲突。
  • TreeMap在保持元素有序的同时，需要付出额外的性能代价，因此在某些情况下可能比HashMap慢一些。

排序和自定义比较

  • 如果您需要对键进行自定义排序或使用非自然顺序，TreeMap更适合，因为它允许您提供自定义的Comparator。
  • HashMap没有内置的排序功能，如果需要对键进行排序，您需要将键提取到一个列表中，手动排序该列表。

允许的键和值

  • HashMap的键和值可以为null，因为它们使用了哈希表的数据结构。
  • TreeMap要求键不能为null（因为它需要保持有序性），但值可以为null。

HashMap 的结构

HashMap 是基于哈希表（Hash Table）实现的键值对存储数据结构，它的内部结构包括以下重要部分：

  1. 数组（Bucket 数组）：HashMap 内部维护一个数组，通常称为桶（buckets）数组或散列桶数组。这个数组的每个元素称为桶（bucket）。每个桶可以存储一个或多个键值对。
  2. 键值对：HashMap 存储的数据是键值对（key-value pairs）。每个键值对包括一个键和一个关联的值。键用于唯一标识值，而值则是与键相关联的数据。
  3. 哈希函数：哈希函数是一种算法，它将键转换为整数哈希码。哈希码用于确定键在桶数组中的存储位置。一个好的哈希函数应该尽可能均匀地将不同的键映射到不同的哈希码，以减少碰撞（collision）的概率。
  4. 链表或红黑树：每个桶可以存储一个或多个键值对。当多个键具有相同的哈希码时，它们存储在同一个桶中，并以链表或红黑树的形式来处理。在 Java 8 及以后的版本中，当同一个桶中的键值对数量达到一定阈值时，会将链表转换为红黑树，以提高查询性能。
  5. 加载因子：加载因子（load factor）是一个控制哈希表扩容的参数。当桶数组中的元素数量达到加载因子与桶数组大小的乘积时，HashMap 会自动进行扩容操作。默认加载因子通常为 0.75。
  6. 容量：容量是桶数组的大小，即 HashMap 可以存储的键值对的数量上限。当桶数组中的元素数量达到容量与加载因子的乘积时，HashMap 会自动进行扩容操作。初始容量通常为 16。
  7. 扩容：扩容是指当桶数组中的元素数量达到一定阈值时，HashMap 会创建一个更大的桶数组，然后将所有的键值对重新分布到新的桶中。这个过程涉及到重新计算哈希码和移动键值对，可能会导致一定的性能开销。扩容的目的是保持加载因子在合理范围内，以避免哈希表变得过于拥挤，降低查询性能。

HashMap 的长度为什么是2的幂次方

HashMap 的长度（容量）通常设置为 2 的幂次方的原因涉及到哈希函数和哈希码的计算。

  1. 取模操作优化：HashMap 内部使用哈希函数将键映射到数组的索引位置，通常通过计算键的哈希码并进行取模操作来确定索引位置。使用 2 的幂次方作为容量可以将取模操作优化为位运算，这比一般的取模运算更快速。具体来说，如果容量是 2 的幂次方，可以使用 hashCode & (capacity - 1) 来计算索引位置，这是一种效率很高的位运算。
  2. 均匀分布：当容量是 2 的幂次方时，取模操作的结果会更均匀地分布在桶数组中。这有助于减少哈希碰撞（collision）的概率，即不同的键具有相同的哈希码但被映射到不同的索引位置的情况。

选择容量为 2 的幂次方可以优化 HashMap 的性能，减少碰撞的概率，简化哈希码计算，提高取模操作的效率，并在扩容时提供更高的效率。

什么是 HashMap 的加载因子？加载因子为什么是 0.75？

HashMap 的加载因子（Load Factor）是一个用于衡量哈希表中元素密度的参数。加载因子是一个小数，通常表示为 loadFactor，其值介于 0 和 1 之间。HashMap 的加载因子默认值通常是 0.75。

加载因子的作用是帮助控制哈希表的性能和空间利用之间的平衡。具体来说，加载因子影响以下两个方面：

  1. 容量管理：当哈希表中的元素数量达到容量与加载因子的乘积时，HashMap 会自动进行扩容操作。加载因子越高，扩容的频率越低，但也会导致哈希表变得更拥挤。加载因子越低，扩容的频率越高，但会浪费更多的内存空间。0.75 是一个通常的默认值，它在性能和空间之间提供了一个良好的平衡。
  2. 性能：加载因子也影响了哈希表的性能。较低的加载因子意味着哈希表在扩容前会更早地变得拥挤，这可能会导致更多的哈希冲突和查询性能下降。较高的加载因子意味着哈希表在扩容前会较晚变得拥挤，这可以减少哈希冲突，提高查询性能。但过高的加载因子也可能导致扩容时的性能开销增加。

为什么加载因子通常设置为 0.75 呢？这是一个经验值，经过实际测试和优化得出的结果。0.75 的加载因子在绝大多数情况下提供了合理的性能和空间利用之间的平衡。它意味着当哈希表中元素数量达到容量的 75% 时，会触发扩容操作，从而在不过于拥挤的情况下保持了较好的性能。当然，在某些特殊情况下，你可能需要根据具体需求调整加载因子的值，以优化性能和内存利用。

HashMap 1.7和1.8版本区别

数据结构优化

  • Java 1.7 中的 HashMap 使用了数组 + 链表的数据结构来处理哈希冲突。这意味着在发生哈希冲突时，多个键值对会存储在同一个桶中，并以链表的形式连接起来。
  • Java 1.8 中的 HashMap 在解决哈希冲突时引入了红黑树。当桶中的键值对数量达到一定阈值时，会将链表转换为红黑树，以提高查询性能。这对于处理大量数据的情况下具有明显的性能优势。

性能改进

  • Java 1.8 中的 HashMap 在处理哈希冲突时通常比 Java 1.7 版本更快，特别是当哈希表中的元素数量较大时。这是因为红黑树在查找操作上的性能更好，具有 O(log n) 的复杂度，而链表具有 O(n) 的复杂度。

并行性改进

  • Java 1.8 引入了一些并行性改进，包括对于并行操作的支持。这对于多线程环境下的 HashMap 使用有一定的性能提升。

内部实现细节

  • Java 1.7 和 Java 1.8 中的 HashMap 在内部实现上有一些不同，主要是由于引入了红黑树和并行性支持。这些细节不同可以在源代码中找到。

HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

在理论上，确实可以使用 hashCode() 处理后的哈希值直接作为哈希表（如 HashMap）的数组下标，但这样做会面临一些问题和挑战，因此通常不是一个好的做法：

  1. 范围限制问题：hashCode() 返回的哈希码是一个 32 位整数，而哈希表的数组可能不是 32 位。如果直接使用 hashCode() 作为数组下标，哈希码的范围可能会超出数组的范围，导致数组越界错误。
  2. 哈希冲突：hashCode() 可能会返回相同的哈希码，即不同的键具有相同的哈希码。如果直接使用哈希码作为下标，这些键将被存储在相同的数组位置上，导致碰撞（collision）。解决哈希冲突是哈希表的一个关键问题，通常需要使用开放地址法、链地址法或其他方法来处理。
  3. 不均匀分布：hashCode() 可能返回的哈希码分布不均匀，导致一些数组位置上的元素较多，而其他位置上的元素较少。这会降低哈希表的性能，因为在发生碰撞时，需要花更多的时间来查找正确的位置。
  4. 可变性问题：hashCode() 的返回值是可变的，如果键的状态发生变化，哈希码也会变化。这会导致键在哈希表中无法正确查找或删除。

怎么解决呢？

  1. HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
  2. 保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储。

那为什么是两次扰动呢？

这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

为什么HashMap中String、Integer这样的包装类适合作为Key？

在 HashMap 中，String、Integer 这样的包装类适合作为键（Key）的原因主要与它们的不可变性、稳定的哈希码、可预测性和普遍性相关：

  1. 不可变性：包装类（如String和Integer）的对象是不可变的，一旦创建就不能修改它们的值。这意味着作为HashMap的键时，它们的哈希码（由hashCode()方法确定）不会在键的生命周期内改变。不可变性有助于确保键的一致性，使得键在存储和检索时不会发生变化。
  2. 稳定的哈希码：包装类的hashCode()方法通常会根据对象的内容计算出一个稳定的哈希码。这意味着，如果两个包装类对象的内容相同，它们的hashCode()方法会返回相同的哈希码。这有助于确保在HashMap中查找键时能够正确匹配对象。
  3. 可预测性：由于包装类的hashCode()方法通常根据对象的内容计算哈希码，所以可以预测哈希码的生成方式。这使得在调试和测试时更容易理解HashMap的行为。
  4. 普遍性：包装类是Java中的基本数据类型的包装，它们常常用于表示各种类型的数据，包括字符串、整数、日期等。因此，使用包装类作为键使得HashMap可以适用于多种场景，而不仅限于特定的数据类型。

如果想要让自己的Object作为 key 应该怎么办呢？重写hashCode()和equals()方法 。 重写**hashCode()是因为需要计算存储数据的存储位置， 重写equals()**方法目的是为了保证key在哈希表中的唯一性。

HashMap 有哪几种常见的遍历方式

使用迭代器遍历键值对

  • 使用 entrySet() 方法获取键值对的集合，然后使用迭代器遍历。
  • 这是最常见的遍历方式，也是最通用的方式，可以同时访问键和值。
HashMap<K, V> map = new HashMap<>();
// 添加键值对
Iterator<Map.Entry<K, V>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<K, V> entry = iterator.next();
    K key = entry.getKey();
    V value = entry.getValue();
    // 处理键值对
}

遍历键或值集合

  • 使用 keySet() 方法获取键的集合或使用 values() 方法获取值的集合，然后使用迭代器或增强型 for 循环遍历。
  • 这种方式适用于只需要访问键或值的情况。
HashMap<K, V> map = new HashMap<>();
// 添加键值对
Iterator<K> keyIterator = map.keySet().iterator();
while (keyIterator.hasNext()) {
    K key = keyIterator.next();
    // 处理键
}

for (V value : map.values()) {
    // 处理值
}

Java 8+ 的 forEach 方法

  • 使用 Java 8+ 提供的 forEach 方法来遍历键值对。
  • 这种方式更简洁，可以使用 lambda 表达式来处理键值对。
HashMap<K, V> map = new HashMap<>();
// 添加键值对
map.forEach((key, value) -> {
    // 处理键值对
});

Java 8+ 的 Stream API

  • 使用 Java 8+ 提供的 Stream API 来遍历和处理键值对。
  • 这种方式可以进行更复杂的操作，如过滤、映射等。
HashMap<K, V> map = new HashMap<>();
// 添加键值对
map.entrySet().stream()
    .filter(entry -> entry.getKey().startsWith("prefix"))
    .forEach(entry -> {
        // 处理符合条件的键值对
    });

forEachRemaining 方法

  • 使用 Iterator 的 forEachRemaining 方法遍历键值对。
  • 这种方式与传统的迭代器方式类似，但更简洁。
HashMap<K, V> map = new HashMap<>();
// 添加键值对
Iterator<Map.Entry<K, V>> iterator = map.entrySet().iterator();
iterator.forEachRemaining(entry -> {
    // 处理键值对
});

HashSet

HashSet、LinkedHashSet 和 TreeSet 三者的区别

HashSet

  • HashSet 是基于哈希表（HashMap）实现的集合，它不保证元素的顺序。
  • 插入和查找元素的性能都很高，平均时间复杂度为 O(1)。
  • 由于使用哈希表，HashSet 不会维护元素的插入顺序或访问顺序。
  • HashSet 允许存储一个 null 元素。

LinkedHashSet

  • LinkedHashSet 继承自 HashSet，它在内部使用哈希表和链表来维护元素的顺序。
  • 插入元素的性能与 HashSet 相似，但它可以保持插入顺序，即元素被添加到集合中的顺序。
  • 遍历 LinkedHashSet 时，元素会按照插入顺序返回。
  • LinkedHashSet 允许存储一个 null 元素。

TreeSet

  • TreeSet 是基于红黑树（Red-Black Tree）实现的集合，它可以对元素进行排序。
  • 插入和查找元素的性能较 HashSet 和 LinkedHashSet 略低，平均时间复杂度为 O(log n)。
  • TreeSet 会根据元素的自然顺序或指定的比较器对元素进行排序。
  • TreeSet 不允许存储 null 元素。

总结一下，三者的主要区别在于元素的排序和性能特性：

  • HashSet：不保证元素的顺序，性能高，不维护插入顺序。
  • LinkedHashSet：保持插入顺序，性能高，适合需要保留插入顺序的场景。
  • TreeSet：对元素进行排序，性能略低，适合需要有序集合的场景。
阅读全文