Java八股文——集合「Set篇」

Set集合有什么特点？如何实现key无重复的？

面试官您好，Set 集合是 Java 集合框架中的一个重要接口，它继承自 Collection 接口，其最显著的特点和设计目标就是存储一组不重复的元素。

一、Set集合的主要特点：

元素唯一性 (Uniqueness)：
- 这是 Set 最核心的特点。Set 中不允许包含重复的元素。如果你尝试向一个 Set 中添加一个已经存在的元素（根据 equals() 方法判断为相同），那么添加操作通常会失败（或者说，不会改变 Set 的内容），并且 add() 方法会返回 false。
- 这种唯一性是基于对象的 equals() 方法来判断的。
无序性 (Unordered) 或特定顺序 (Ordered)：
- Set 接口本身并不保证元素的任何特定顺序。
- 具体的 Set 实现类会决定元素的存储顺序：
  - HashSet：是最常用的 Set 实现，它不保证元素的顺序，元素的存储和迭代顺序可能与插入顺序不同，并且可能会随时间变化（例如，在扩容后）。
  - LinkedHashSet：它继承自 HashSet，但额外维护了一个双向链表来记录元素的插入顺序。因此，LinkedHashSet保证元素按照插入顺序进行迭代。
  - TreeSet：它实现了 SortedSet 接口，能够将元素保持在排序状态。元素可以按照其自然顺序（如果元素实现了 Comparable 接口）或者根据创建 TreeSet 时提供的 Comparator 进行排序。
允许null元素：
- 大多数 Set 实现（如 HashSet 和 LinkedHashSet）允许包含一个null元素。因为 null 也是唯一的。
- TreeSet 默认情况下不允许 null 元素（除非其 Comparator 特别处理了 null 的比较），因为 null 无法进行自然的比较。

二、Set如何实现元素（或称之为Key）无重复的原理：

Set 接口的实现类通常是基于对应的Map实现来保证元素唯一性的。它们巧妙地利用了 Map 中键（Key）的唯一性特性。

HashSet的实现原理：
- HashSet 内部实际上是持有一个HashMap实例。
- 当你向 HashSet 中 add(E e) 一个元素时，这个元素 e 实际上是被当作 HashMap 的键（Key） 来存储的。
- HashMap 的值（Value）部分对于 HashSet 来说并不重要，所以 HashSet 内部会使用一个固定的、虚拟的Object对象（名为PRESENT）作为所有键对应的值。

// HashSet 源码片段 (示意)
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();public boolean add(E e) {return map.put(e, PRESENT) == null;
}

因此，HashSet 添加元素的逻辑就转换为了向内部 HashMap 中 put(element, PRESENT)。
- HashMap 在 put 操作时，会遵循以下步骤来确保键的唯一性：
  1. 计算hashCode()：首先计算要添加的元素（作为 Key）的 hashCode() 值，以确定其在 HashMap 内部数组中的存储位置（哈希桶）。
  2. 检查冲突并调用equals()：
    - 如果哈希桶为空，直接存入。
    - 如果哈希桶不为空（发生哈希冲突），则会遍历该桶中的链表或红黑树，对每个已存在的键，使用要添加元素的 equals() 方法进行比较。
    - 如果 equals() 方法返回 true，说明找到了一个与待添加元素相等的键，HashMap 不会再次插入这个键（而是可能会更新其值，但对于 HashSet，值是固定的 PRESENT，所以实际上是不做任何改变）。
    - 如果遍历完整个桶都没有找到 equals() 相等的键，则将新元素（作为键）添加到链表或红黑树中。
- 由于 HashMap 保证了其键的唯一性，所以依赖于 HashMap 的 HashSet 也就自然地保证了其元素的唯一性。

LinkedHashSet的实现原理：
- 与 HashSet 类似，LinkedHashSet 内部持有的是一个 LinkedHashMap实例。
- LinkedHashMap 在 HashMap 的基础上额外维护了一个双向链表来记录键的插入顺序。因此，LinkedHashSet 能够保证元素的迭代顺序与插入顺序一致，同时通过 LinkedHashMap 键的唯一性来保证元素的唯一性。
TreeSet的实现原理：
- TreeSet 内部持有的是一个 TreeMap实例(或者更准确地说，是一个 NavigableMap，通常是 TreeMap)。
- 元素被作为 TreeMap 的键存储，值同样是虚拟的 PRESENT 对象。
- TreeMap 是基于红黑树实现的，它通过元素的自然顺序（Comparable）或自定义比较器（Comparator）来对键进行排序和比较。当添加元素时，TreeMap 会根据比较结果来判断元素是否已存在（比较结果为0则认为已存在），从而保证元素的唯一性，并维持元素的排序状态。

总结来说，Set集合通过其内部依赖的Map实现（如HashMap,LinkedHashMap,TreeMap）来巧妙地实现了元素的唯一性。核心机制是：将待添加的元素作为Map的键，利用Map在存储键时会先通过hashCode()定位，再通过equals()(或compareTo()对于TreeSet) 精确判断键是否重复的特性，来确保Set中不会出现重复元素。

有序的Set是什么？记录插入顺序的集合是什么？

面试官您好，关于 Java 中有序的 Set 集合以及能记录插入顺序的 Set 集合，主要涉及到以下两种实现：

一、有序的Set(SortedSet / NavigableSet)

当提到“有序的 Set”，通常指的是元素在集合中按照某种比较规则（自然顺序或自定义顺序）保持排序状态。

主要实现类：TreeSet
- TreeSet 实现了 NavigableSet 接口，而 NavigableSet 又继承了 SortedSet 接口。
- 排序机制：
  - TreeSet 的底层是基于红黑树 (Red-Black Tree) 实现的（内部实际上依赖一个 TreeMap）。
  - 它能保证元素在集合中始终处于排序状态。排序规则可以是：
    1. 自然顺序：如果存入 TreeSet 的元素实现了 java.lang.Comparable 接口，并且其 compareTo() 方法定义了元素间的自然比较顺序（如数字的大小、字符串的字典序）。
    2. 自定义顺序：如果在创建 TreeSet 时提供了一个 java.util.Comparator 对象，那么元素将按照这个比较器定义的规则进行排序。
- 特点：
  - 元素唯一（Set 的基本特性）。
  - 元素有序（按照定义的比较规则）。
  - 提供了丰富的导航方法（如 first(), last(), lower(), higher(), floor(), ceiling(), 以及获取子集的方法），这些都得益于其有序性。
  - 查找、插入、删除操作的时间复杂度通常是 O(log N)。
- 注意：TreeSet 默认情况下不允许存入 null 元素，因为 null 无法进行自然的比较。如果需要支持 null，必须提供一个能处理 null 的 Comparator。

二、记录插入顺序的Set

当提到“记录插入顺序的 Set”，指的是集合中的元素在迭代时，其顺序与它们被添加到集合中的顺序保持一致。

主要实现类：LinkedHashSet
- LinkedHashSet 继承自 HashSet，并在其基础上增加了一个机制来维护元素的插入顺序。
- 顺序机制：
  - LinkedHashSet 内部实际上依赖一个 LinkedHashMap。
  - LinkedHashMap 在 HashMap 的基础上，额外维护了一个双向链表。这个链表连接了所有存入的条目（在 LinkedHashSet 中即元素），并记录了它们的插入顺序。
- 特点：
  - 元素唯一（Set 的基本特性，由其内部 LinkedHashMap 的键唯一性保证）。
  - 迭代顺序与插入顺序一致。这是它与 HashSet（无序）和 TreeSet（按比较规则排序）的主要区别。
  - 查找、插入、删除操作的平均时间复杂度与 HashSet 类似，通常是 O(1)（假设哈希函数分布良好），但由于维护链表的额外开销，其性能常数因子会略大于 HashSet。
  - 允许一个 null 元素。

总结对比：

特性	`TreeSet`	`LinkedHashSet`	`HashSet` (作为参照)
元素唯一	是	是	是
顺序性	按比较规则排序(自然顺序或自定义比较器)	按插入顺序	无序
底层实现	红黑树 (基于 `TreeMap`)	哈希表 + 双向链表 (基于 `LinkedHashMap`)	哈希表 (基于 `HashMap`)
`null`支持	默认不允许 (除非 `Comparator` 支持)	允许一个 `null`	允许一个 `null`
主要用途	需要排序的唯一元素集合	需要保持插入顺序的唯一元素集合	不需要特定顺序的唯一元素集合

因此：

如果您需要一个根据元素值本身进行排序的 Set，那么应该选择 TreeSet。
如果您需要一个保持元素插入顺序的 Set，那么应该选择 LinkedHashSet。
如果您对顺序没有要求，只关心元素的唯一性和高效的存取，那么通常选择 HashSet。

LinkedHashSet 保证的是插入顺序，而不是元素本身的自然排序。TreeSet 才保证元素本身的自然排序（或比较器排序）。

Comparable 和 Comparator 的区别

面试官您好，Comparable 和 Comparator 都是 Java 中用于对象比较和排序的核心接口，但它们在设计和使用上有着明确的区别：

一、Comparable接口

定义与来源：
- Comparable 接口位于 java.lang 包下。
- 它只包含一个方法：int compareTo(T o)。
设计意图 (内比较器 / 自然排序)：
- Comparable 的设计意图是让一个类的对象自身具备可比较性。当一个类实现了 Comparable 接口，就意味着这个类的实例可以相互比较大小，它们拥有了所谓的“自然排序”顺序。
- 可以把它看作是对象的 “内比较器”或“默认比较规则”。
使用方式：
- 类需要直接实现Comparable接口，并重写 compareTo(T o) 方法来定义其比较逻辑。
- compareTo(T o) 方法的返回值约定：
  - 如果当前对象 (this) 小于参数对象 o，返回负整数。
  - 如果当前对象 (this) 等于参数对象 o，返回零。
  - 如果当前对象 (this) 大于参数对象 o，返回正整数。
- 一旦类实现了 Comparable，其对象就可以直接被一些排序工具使用，例如：
  - Collections.sort(List<T> list)：如果 List 中的元素类型 T 实现了 Comparable，可以直接调用此方法进行排序。
  - Arrays.sort(T[] a)：同理。
  - TreeSet<T> 和 TreeMap<K,V>：如果元素/键 T 或 K 实现了 Comparable，它们在存入这些集合时会自动按自然顺序排序。
示例场景：
- 像 String, Integer, Date 等 Java 内置的许多类都实现了 Comparable 接口，定义了它们各自的自然排序规则（如字符串按字典序，数字按大小）。
- 如果我们有一个自定义的 Student 类，我们可能希望它默认按学号排序，那么 Student 类就可以实现 Comparable<Student> 并重写 compareTo 方法比较学号。

二、Comparator接口

定义与来源：
- Comparator 接口位于 java.util 包下。
- 它主要包含一个方法：int compare(T o1, T o2)。（Java 8 之后还增加了一些默认方法和静态方法，如 thenComparing, comparingInt 等，用于构建更复杂的比较器）。
设计意图 (外比较器 / 定制排序)：
- Comparator 的设计意图是提供一种独立于对象本身的比较逻辑。它允许我们为那些没有实现 Comparable 接口的类定义排序规则，或者为已经实现了 Comparable 接口的类提供额外的、不同的排序方式。
- 可以把它看作是对象的 “外比较器”或“定制比较规则”。它像一个“裁判”，专门负责比较两个对象。
使用方式：
- 创建一个单独的类来实现Comparator<T>接口，并重写 compare(T o1, T o2) 方法。
- 或者，更常见的是使用匿名内部类或Lambda 表达式(Java 8+) 来创建一个 Comparator 实例。
- compare(T o1, T o2) 方法的返回值约定：
  - 如果 o1 小于 o2，返回负整数。
  - 如果 o1 等于 o2，返回零。
  - 如果 o1 大于 o2，返回正整数。
- 使用 Comparator 时，通常需要将其作为参数传递给排序工具：
  - Collections.sort(List<T> list, Comparator<? super T> c)
  - Arrays.sort(T[] a, Comparator<? super T> c)
  - new TreeSet<T>(Comparator<? super T> comparator)
  - new TreeMap<K,V>(Comparator<? super K> comparator)
示例场景：
- 正如您提到的，如果我们有一个 Song 对象，它可能实现了 Comparable 按歌名排序。但我们有时又想按歌手名排序，或者按发行日期排序，这时就可以创建不同的 Comparator<Song> 实现来满足这些不同的排序需求。
- 对于第三方库中的类，如果它们没有实现 Comparable 或者其自然排序不符合我们的要求，我们就可以通过 Comparator 来定义自己的排序逻辑，而无需修改这些类的源码。

三、总结与选择：

特性	`Comparable` (内比较器)	`Comparator` (外比较器)
定义位置	`java.lang`	`java.util`
实现方式	类自身实现接口	单独的比较器类实现接口，或 Lambda/匿名内部类
方法签名	`int compareTo(T o)`	`int compare(T o1, T o2)`
主要作用	定义对象的自然排序/默认排序规则	定义对象的定制排序/多种排序规则
耦合性	比较逻辑与类本身耦合	比较逻辑与类解耦
灵活性	一种排序规则	可提供多种排序规则
使用场景	当类有明确的、主要的“自然”比较方式时	当需要多种排序方式，或无法修改类源码，或排序逻辑与业务场景相关时

简单来说：

如果一个类有其主要的、通用的比较方式（“自然顺序”），那么让这个类实现 Comparable 接口。
如果需要多种不同的排序方式，或者目标类无法修改（比如是第三方库的类），或者排序逻辑与特定业务场景紧密相关而非对象的固有属性，那么应该使用 Comparator。

在实际开发中，两者经常结合使用。例如，一个类可以实现 Comparable 定义其默认排序，同时我们也可以提供多个 Comparator 来满足不同的定制化排序需求。

无序性和不可重复性的含义是什么

面试官您好，在讨论 Java 集合（特别是像 HashSet 这样的 Set 实现或 HashMap 的键集）时，我们经常提到“无序性”和“不可重复性”，它们的具体含义如下：

一、无序性 (Unordered)

核心含义：
- “无序性”指的是元素在集合中的存储顺序和迭代（遍历）顺序通常与它们的添加顺序不一致，并且这种顺序通常是不固定的，可能会因为集合内部状态的变化（如扩容）而改变。
- 正如您所指出的，无序性不等于随机性 (Randomness)。随机性意味着每次迭代的顺序都可能是完全不可预测且不同的。而对于像 HashSet 这样的集合，虽然迭代顺序与插入顺序无关，但在不发生结构性修改（如添加、删除导致扩容）的情况下，对同一个 HashSet 实例多次迭代，通常会得到相同的元素序列。
原因 (主要针对基于哈希的集合，如HashSet,HashMap)：
- 无序性主要是由其底层数据结构和元素定位机制决定的。
- 对于基于哈希表实现的集合（如 HashSet 内部依赖 HashMap），元素在底层数组中的存储位置是根据元素的哈希码 (hashCode()**)**计算得到的。
- 哈希码本身与元素的添加顺序无关。不同的元素，即使添加顺序相邻，它们的哈希码可能差异很大，从而被映射到底层数组的不同、不连续的位置。
- 因此，当你迭代这样一个集合时，你实际上是在按某种顺序（可能是数组索引顺序，加上处理哈希冲突的链表/树的顺序）访问这些由哈希码决定的存储位置，这个顺序自然就不是元素的插入顺序。
需要区分的集合：
- HashSet：是典型的无序集合。
- LinkedHashSet：它虽然是 Set，但通过内部维护一个双向链表来记录元素的插入顺序，所以它是有序的（按插入顺序）。
- TreeSet：它也不是无序的，而是按元素的自然顺序或自定义比较器顺序进行排序的。

二、不可重复性 (No Duplicates / Uniqueness)

核心含义：
- “不可重复性”指的是集合中不能包含两个或多个“相等”的元素。
- 这个“相等”的判断标准是基于元素的 equals()方法。如果尝试向集合中添加一个元素 e1，而集合中已经存在一个元素 e2 使得 e1.equals(e2) 返回 true，那么添加操作通常会失败（或不改变集合内容），add() 方法会返回 false。
实现机制 (主要针对Set实现)：
- 正如您所说，为了正确实现不可重复性，特别是对于自定义对象，必须同时正确地重写其equals()方法和hashCode()方法。
- hashCode()的作用：
  - 当向基于哈希的 Set（如 HashSet）中添加元素时，首先会计算元素的 hashCode() 来快速定位其在底层哈希表中的潜在存储位置（哈希桶）。
- equals()的作用：
  - 如果通过 hashCode() 定位到的哈希桶中已经存在一个或多个元素（即发生哈希冲突），那么集合会逐个调用待添加元素的 equals() 方法与桶中已存在的元素进行比较。
  - 只有当 equals() 方法都返回 false 时，才认为新元素与桶中所有现有元素都不相等，此时才会将新元素添加到该桶中。如果任何一次 equals() 比较返回 true，则认为新元素是重复的，不予添加。
- equals()和hashCode()的协定：
  - 如果 a.equals(b) 为 true，那么 a.hashCode() 必须等于 b.hashCode()。这是保证 Set 能够正确工作的关键。如果相等的对象哈希码不同，它们可能会被放到不同的桶里，Set 就无法检测到它们的重复。
示例：
- 如果 Set 中已有一个字符串 "hello"，再尝试添加另一个内容也是 "hello" 的字符串对象，由于 String 类正确实现了 equals() (比较内容) 和 hashCode() (基于内容计算)，第二个 "hello" 会被认为是重复的，不会被添加。
- 对于自定义的 Person 对象，如果我们希望只要 id 相同就认为是同一个人，那么 Person 类的 equals() 方法就应该只比较 id，并且其 hashCode() 方法也应该主要基于 id 来计算。

总结：

无序性主要描述的是元素在集合中的存储和迭代顺序与添加顺序无关，这是由底层哈希定位机制决定的，它不等于随机。
不可重复性是 Set 的核心特性，意味着集合中不允许存在equals()判断相等的多个元素，其正确实现依赖于元素类型正确重写 equals() 和 hashCode() 方法。

理解这两点对于选择和使用合适的集合类型非常重要。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

面试官您好，HashSet, LinkedHashSet, 和 TreeSet 都是 Java 集合框架中 Set 接口的重要实现类，它们在保证元素唯一性的基础上，各自具有不同的特点和适用场景。

一、共同点：

实现Set接口：它们都实现了 java.util.Set 接口，因此都具备 Set 的核心特性。
元素唯一性：它们都能保证集合中的元素是唯一的，不允许重复（根据元素的 equals() 方法判断）。
非线程安全：这三个类本身都不是线程安全的。如果在多线程环境下需要对它们进行并发修改，必须进行外部同步，或者使用 java.util.concurrent 包下对应的线程安全集合（如 CopyOnWriteArraySet 或通过 Collections.newSetFromMap(new ConcurrentHashMap<>()) 创建）。
允许null元素 (大部分情况)：
- HashSet 和 LinkedHashSet 都允许存储一个 null 元素。
- TreeSet 默认情况下不允许 null 元素（除非其构造时传入的 Comparator 明确支持对 null 的比较），因为 null 无法进行自然的比较。

二、主要区别：

主要区别在于它们的底层数据结构不同，这直接导致了它们在元素顺序性、性能特性和适用场景上的差异。

HashSet
- 底层数据结构：基于哈希表实现，内部实际上是依赖一个 HashMap 实例。元素作为 HashMap 的键存储，值是一个固定的 PRESENT 对象。
- 元素顺序性：无序。它不保证元素的任何特定存储或迭代顺序，元素的顺序可能与插入顺序不同，并且可能随时间变化（如扩容后）。
- 性能特性：
  - 添加（add）、删除（remove）、查找（contains）操作的平均时间复杂度是O(1)（假设哈希函数分布良好，哈希冲突不严重）。
  - 最坏情况下的时间复杂度（哈希冲突严重导致链表过长）是 O(N)。在 JDK 1.8+ 中，当链表过长会转换为红黑树，此时最坏情况为 O(log N)。
- 适用场景：当对集合中元素的顺序没有要求，只关心元素的唯一性和高效的存取操作时，HashSet 是最常用的选择。
LinkedHashSet
- 底层数据结构：基于哈希表 + 双向链表实现。它继承自 HashSet，内部依赖一个 LinkedHashMap 实例。
- 元素顺序性：有序，保持插入顺序。迭代时，元素将按照它们被添加到集合中的顺序出现。
- 性能特性：
  - 添加、删除、查找操作的平均时间复杂度仍然是O(1)（与 HashSet 类似）。
  - 但由于需要额外维护双向链表，其性能常数因子会略大于 HashSet（即，在相同数据量和哈希分布下，LinkedHashSet 的操作会比 HashSet 稍微慢一点点）。
- 适用场景：当既需要保证元素的唯一性，又需要保持元素插入时的顺序时，LinkedHashSet 是理想选择。例如，实现 LRU (Least Recently Used) 缓存的键集合时，或者需要按历史记录顺序展示唯一项时。
TreeSet
- 底层数据结构：基于红黑树 (Red-Black Tree) 实现。内部依赖一个 TreeMap 实例（更准确地说是 NavigableMap）。
- 元素顺序性：有序，按照元素的比较规则排序。
  - 可以是元素的自然顺序（如果元素实现了 Comparable 接口）。
  - 也可以是根据创建 TreeSet 时提供的自定义比较器 (Comparator) 的顺序。
- 性能特性：
  - 添加、删除、查找操作的时间复杂度是O(log N)，其中 N 是集合中元素的数量。这是由红黑树的特性决定的。
- 适用场景：当需要一个自动排序的、元素唯一的集合时，TreeSet 是最佳选择。它还提供了丰富的导航方法（如获取最小/最大元素、获取某个范围的子集等）。

三、总结列表：

特性	`HashSet`	`LinkedHashSet`	`TreeSet`
元素唯一	是	是	是
线程安全	否	否	否
`null`支持	允许一个	允许一个	默认不允许 (除非 `Comparator` 支持)
顺序性	无序	按插入顺序	按比较规则排序 (自然/自定义)
底层实现	哈希表 (基于 `HashMap`)	哈希表 + 双向链表 (基于 `LinkedHashMap`)	红黑树 (基于 `TreeMap`)
性能 (平均)	O(1) (add, remove, contains)	O(1) (add, remove, contains) (略慢于HashSet)	O(log N) (add, remove, contains)
主要用途	快速存取，无序唯一集合	保持插入顺序的唯一集合	自动排序的唯一集合，支持导航操作