2025 届秋招常见八股文汇总——Java 集合

Java 的集合类有哪些，哪些是线程安全的，哪些是线程不安全的？

Java 中的集合类主要由 Collection 和 Map 这两个接口派生而出，其中 Collection 接口又派生出三个子接口，分别是 Set、List、Queue。所有的 Java 集合类，都是 Set、List、Queue、Map 这四个接口的实现类。

    • List 接口：有序集合，允许重复元素。常见的实现类有 ArrayList、LinkedList 等。
    • Set 接口：不允许重复元素的集合。常见的实现类有 HashSet、LinkedHashSet、TreeSet 等。
    • Queue 接口：用于表示队列的数据结构。 常见的实现类有 LinkedList、ArrayDeque、PriorityQueue 等。
    • Map 接口：表示键值对的集合。常见的实现类有 HashMap、LinkedHashMap、TreeMap 等。

线程不安全的集合类

  • ArrayList、LinkedList、HashSet、HashMap：这些集合类是非线程安全的。在多线程环境中，如果没有适当的同步措施，对这些集合的并发操作可能导致不确定的结果。
  • TreeMap、TreeSet： 虽然 TreeMap 和、 TreeSet 是有序的集合，但它们也是非线程安全的。

线程安全的集合类

  • Vector：类似于 ArrayList，它的方法都是同步的，因此是线程安全的。然而，它相对较重，不够灵活，现在通常建议使用 ArrayList。
  • HashTable：类似于 HashMap，但它是线程安全的，通过同步整个对象实现。但它的使用已经不太推荐，通常建议使用 HashMap。
  • ConcurrentHashMap：提供更好的并发性能，通过锁分离技术实现线程安全。
  • Collections.synchronizedList、Collections.synchronizedSet、Collections.synchronizedMap： 这些方法可以将非线程安全的集合包装成线程安全的集合。

ArrayList 和 Array 有什么区别？ArrayList 和 LinkedList 的区别是什么？

  1. ArrayList vs Array：
    • ArrayList 是动态数组的实现，而 Array 是固定长度的数组。
    • ArrayList 提供了更多的功能，比如自动扩容、增加和删除元素等，Array 则没有这些功能。
    • Array 可以直接存储基本类型数据，也可以存储对象。 ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）
    • 在随机访问时，Array 由于其连续内存存储，性能通常优于 ArrayList。
  2. ArrayList vs LinkedList：
    • ArrayList 基于动态数组，LinkedList 基于双向链表。
    • 随机访问：ArrayList 在随机访问时性能更好，而 LinkedList 访问元素时效率较低，因为需要从头开始或从尾开始通过链接遍历，时间复杂度为 O(n)。
    • 删除/添加元素：在 ArrayList 末尾添加元素通常很快，但在 ArrayList 中间或开始插入或删除元素时，可能需要移动后续元素，时间复杂度为 O(n)。而 LinkedList 添加和删除元素时性能更佳，只需改变节点的引用。
    • 扩容：当容量不足以容纳更多元素时，ArrayList 会扩容，这个过程涉及创建新数组和复制旧数组的内容，有一定的开销。
    • 使用场景：选择 ArrayList 或者 LinkedList 通常取决于你的 Java 应用是否需要频繁的随机访问操作，还是更多的插入和删除操作。

总结来说，ArrayList 和 Array 的主要区别在于动态大小和功能，而 ArrayList 和 LinkedList 的主要区别在于底层数据结构和它们对元素操作的性能特点。选择使用哪一个取决于具体的应用场景和性能需求。

ArrayList 扩容机制

  1. ArrayList 扩容的本质就是计算出新的扩容数组的 size 后实例化，并将原有数组内容复制到新数组中去。（不是原数组，而是新数组然后给予数组对象地址）。
  2. 当创建一个 ArrayList 对象时，它会分配一定的初始容量，通常为 10。
  3. 当 ArrayList 中的元素数量达到当前容量时，ArrayList 会自动增加其容量。ArrayList 扩容的计算是在一个 grow() 方法里面，grow 方法先尝试将数组扩大为原数组的 1.5 倍。（默新容量 = 旧容量右移一位（相当于除于 2）在加上旧容量）
  4. 若新的容量满足需求，会调用一个 Arrays.copyof 方法, 将所有的元素从旧数组复制到新数组中，这个方法是真正实现扩容的步骤。如果扩容后的新容量还是不满足需求，那新容量大小为当前所需的容量加 1。

HashMap 的底层实现是什么？

在 JDK 1.8 之前，HashMap 由数组和链表组成，当发生哈希冲突时，多个元素会以链表的形式存储在同一个数组位置。JDK 1.8 开始引入了红黑树，当链表长度超过一定阈值（TREEIFY_THRESHOLD，默认为 8）且当前数组的长度大于 64 时，链表会转换成红黑树，以提高搜索效率。

为什么链表大小超过 8 会自动转为红黑树，小于 6 时重新变成链表？

根据泊松分布 ，在负载因子默认为 0.75 的时候，单个 hash 槽内元素个数为 8 的概率小于百万分 之一，所以将 7 作为一个分水岭， 等于 7 的时候不转换，大于等于 8 的时候才转换成红黑树，小于等于 6 的时候转化为链表。

HashMap 读和写的时间复杂度是多少？

读：

  • 在最佳情况下：读操作的时间复杂度是 O(1)
  • 最坏情况下：发生哈希冲突，链表为 O(n)，红黑树为 O(log n)。

写：

  • 理想情况：与读操作类似，如果哈希函数分布均匀，写操作的时间复杂度也是 O(1)。
  • 处理哈希冲突：如果发生哈希冲突，需要在链表尾部添加新元素或将链表转换为红黑树。在这种情况下，写操作的时间复杂度可能达到 O(n)，其中 n 是链表的长度。

解决 hash 冲突的方法有哪些？HashMap 是如何解决 hash 冲突的？

解决哈希冲突的方法主要有以下两种：

  1. 链地址法：在数组的每个位置维护一个链表。当发生冲突时，新的元素会被添加到链表的尾部。
  2. 开放寻址法：当发生冲突时，根据某种探测算法在哈希表中寻找下一个空闲位置来存储元素。

Java 中的 HashMap 使用链地址法解决 hash 冲突。

HashMap 的 put 方法流程

  1. 判断键值对数组是否为空或为 null，否则执行 resize() 进行扩容；
  2. 根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加，转向步骤 6，如果 table[i] 不为空，转向步骤 3；
  3. 判断数组的首个元素是否和 key 一样，如果相同直接覆盖 value，否则转向 4，这里的相同指的是 hashCode 以及 equals；
  4. 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向 5；
  5. 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value即可；
  6. 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量，如果超过，进行扩容。

HashMap 的扩容机制

JDK 1.7 扩容机制

  1. 生成新数组；
  2. 遍历老数组中的每个位置上的链表上的每个元素；
  3. 获取每个元素的 key，并基于新数组长度，计算出每个元素在新数组中的下标；
  4. 将元素添加到新数组中去；
  5. 所有元素转移完之后，将新数组赋值给 HashMap 对象的 table 属性。

JDK 1.8 扩容机制

  1. 生成新数组；
  2. 遍历老数组中的每个位置上的链表或红黑树；
  3. 如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去；
  4. 如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标位置；
  5. 统计每个下标位置的元素个数：如果该位置下的元素个数超过了 8，则生成一个新的红黑树，并将根节点添加到新数组的对应位置。如果该位置下的元素个数没有超过 8，那么则生成一个链表，并将链表的头节点添加到新数组的对应位置；
  6. 所有元素转移完了之后，将新数组赋值给 HashMap 对象的 table 属性。

HashMap 为什么是线程不安全的? 如何实现线程安全

为什么是线程不安全的

主要原因是它的操作不是原子的，即在多个线程同时进行读写操作时，可能会导致数据不一致性或抛出异常.

  1. 并发修改：当一个线程进行写操作（插入、删除等）时，另一个线程进行读操作，可能会导致读取到不一致的数据，甚至抛出 ConcurrentModificationException 异常。
  2. 非原子性操作：HashMap 的一些操作不是原子的，例如，检查是否存在某个键、获取某个键对应的值等，这样在多线程环境中可能发生竞态条件。

如何实现线程安全

为了实现线程安全的 HashMap，有以下几种方式：

  • 使用 Collections.synchronizedMap() 方法：可以通过 Collections.synchronizedMap() 方法创建一个线程安全的 HashMap，该方法返回一个同步的 Map 包装器，使得所有对 Map 的操作都是同步的。
  • 使用 ConcurrentHashMap：ConcurrentHashMap 是专门设计用于多线程环境的哈希表实现。它使用分段锁机制，允许多个线程同时进行读操作，提高并发性能。
  • 使用锁机制：可以在自定义的 HashMap 操作中使用显式的锁（例如 ReentrantLock）来保证线程安全。

ConcurrentHashMap 如何保证线程安全

  1. ConcurrentHashMap 在 JDK 1.7 中使用的数组加链表的结构，其中数组分为两类，大树组 Segment 和小数组 HashEntry，ConcurrentHashMap 的线程安全是建立在 Segment 加 ReentrantLock 重入锁来保证。
  2. ConcurrentHashMap 在 JDK1.8 中使用的是数组+链表+红黑树的方式实现，它是通过 CAS 或者 synchronized 来保证线程安全的，并且缩小了锁的粒度，查询性能也更高。

HashMap 和 ConcurrentHashMap 的区别

  1. 线程安全性：
  • HashMap 不是线程安全的。在多线程环境中，如果同时进行读写操作，可能会导致数据不一致或抛出异常。
  • ConcurrentHashMap 是线程安全的，它使用了分段锁（Segment Locking）的机制，将整个数据结构分成多个段（Segment），每个段都有自己的锁。这样，不同的线程可以同时访问不同的段，提高并发性能。
  1. 同步机制：
  • HashMap 在实现上没有明确的同步机制，需要在外部进行同步，例如通过使用 Collections.synchronizedMap() 方法。
  • ConcurrentHashMap 内部使用了一种更细粒度的锁机制，因此在多线程环境中具有更好的性能。
  1. 迭代时是否需要加锁：
  • 在 HashMap 中，如果在迭代过程中有其他线程对其进行修改，可能抛出 ConcurrentModificationException 异常。
  • ConcurrentHashMap 允许在迭代时进行并发的插入和删除操作，而不会抛出异常。但是，它并不保证迭代器的顺序，因为不同的段可能会以不同的顺序完成操作。
  1. 初始化容量和负载因子：
  • HashMap 可以通过构造方法设置初始容量和负载因子。
  • ConcurrentHashMap 在 JDK 8 及之后版本中引入了 ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) 构造方法，允许设置初始容量、负载因子和并发级别。
  1. 性能：
  • 在低并发情况下，HashMap 的性能可能会比 ConcurrentHashMap 稍好，因为 ConcurrentHashMap 需要维护额外的并发控制。
  • 在高并发情况下，ConcurrentHashMap 的性能通常更好，因为它能够更有效地支持并发访问。

总的来说，如果需要在多线程环境中使用哈希表，而且需要高性能的并发访问，通常会选择使用 ConcurrentHashMap。如果在单线程环境中使用，或者能够手动进行外部同步管理，那么 HashMap 可能是更简单的选择。

HashSet 和 HashMap 的区别

HashMap 适用于需要存储键值对的情况，而 HashSet 适用于只关心元素唯一性的情况。在某些情况下，可以使用 HashMap来模拟 HashSet 的行为，只使用键而将值设为固定的常量。

  1. 使用
  • HashMap 用于存储键值对，其中每个键都唯一，每个键关联一个值。
  • HashSet 用于存储唯一的元素，不允许重复。
  1. 内部实现：
  • HashMap 使用键值对的方式存储数据，通过哈希表实现。
  • HashSet 实际上是基于 HashMap 实现的，它只使用了 HashMap 的键部分，将值部分设置为一个固定的常量。
  1. 元素类型：
  • HashMap 存储键值对，可以通过键获取对应的值。
  • HashSet 存储单一元素，只能通过元素本身进行操作。
  1. 允许 null：
  • HashMap 允许键和值都为 null。
  • HashSet 允许存储一个 null 元素。
  1. 迭代方式：
  • HashMap 的迭代是通过迭代器或增强型 for 循环遍历键值对。
  • HashSet 的迭代是通过迭代器或增强型 for 循环遍历元素。
  1. 关联关系：
  • HashMap 中的键与值是一一对应的关系。
  • HashSet 中的元素没有关联的值，只有元素本身。
  1. 性能影响：
  • HashMap 的性能受到键的哈希分布和哈希冲突的影响。
  • HashSet 的性能也受到元素的哈希分布和哈希冲突的影响，但由于它只存储键，通常比 HashMap 的性能稍好。

HashMap 和 HashTable 的区别

  1. 同步

Hashtable 是同步的，即它的方法是线程安全的。这是通过在每个方法上添加同步关键字来实现的，但这也可能导致性能下降。

HashMap 不是同步的，因此它不保证在多线程环境中的线程安全性。如果需要同步，可以使用 Collections.synchronizedMap() 方法来创建一个同步的 HashMap。

  1. 性能
  • 由于 Hashtable 是同步的，它在多线程环境中的性能可能较差。
  • HashMap 在单线程环境中可能比 Hashtable 更快，因为它没有同步开销。
  1. 空值
  • Hashtable 不允许键或值为 null。
  • HashMap 允许键和值都为 null。
  1. 继承关系

Hashtable 是 Dictionary 类的子类，而 HashMap 是 AbstractMap 类的子类，实现了 Map 接口。

  1. 迭代器
  • Hashtable 的迭代器是通过 Enumerator 实现的。
  • HashMap 的迭代器是通过 Iterator 实现的。
  1. 初始容量和加载因子
  • Hashtable 的初始容量和加载因子是固定的。
  • HashMap 允许通过构造方法设置初始容量和加载因子，以便更好地调整性能。
打赏

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注