Set是如何保证元素不重复的？

在 Java 中，`Set` 是一种不允许元素重复的集合类型。不同类型的 `Set` 通过各自的实现方式保证了元素不重复。主要的实现包括 `HashSet` 和 `TreeSet`。 ### 1. HashSet（基于哈希表实现） `HashSet` 是通过 `HashMap` 来存储数据的，底层使用了哈希表的机制，保证了元素的唯一性。以下是其工作方式： - **哈希计算**：当向 `HashSet` 中添加元素时，首先会计算该元素的 `hashCode` 值。 - **位置计算**：通过 `hashCode` 进行扰动计算和按位操作，确定元素在哈希表中的存储位置。 - **位置检查**：若该位置为空，则直接将元素添加进去；若该位置已有元素，则调用 `equals` 方法检查元素是否相同。 - 如果 `equals` 返回 `true`，表示元素已存在，不添加。 - 如果 `equals` 返回 `false`，表示位置冲突但元素不同，系统会尝试寻找新的位置或使用链表（或红黑树）将冲突元素链在该位置后。 **特点**： - `HashSet` 不保证元素顺序。 - 允许存储一个 `null` 值，但只能有一个。 - 添加和查询操作的时间复杂度为 O(1)。 ### 2. TreeSet（基于红黑树实现） `TreeSet` 是通过 `TreeMap` 实现的，底层采用红黑树（平衡二叉搜索树）数据结构，保证了元素的唯一性和排序。 - **自然排序或自定义排序**：`TreeSet` 会根据元素的自然顺序（通过 `Comparable` 接口）或自定义顺序（通过 `Comparator`）来存储元素。 - **重复判断**：插入元素时，`TreeSet` 会调用 `compareTo()` 方法（或 `compare()` 方法）比较新元素和已有元素的顺序。 - 如果 `compareTo()` 或 `compare()` 返回 0，表示元素重复，不允许插入。 - 如果返回非 0，表示元素不同，则继续插入。 **特点**： - `TreeSet` 保证元素的自然顺序（升序）或自定义顺序。 - 不允许 `null` 值，因为比较操作会引发 `NullPointerException`。 - 添加和查询操作的时间复杂度为 O(log n)。 ### 总结 - `HashSet` 通过 `hashCode` 和 `equals` 方法保证元素唯一性，适合无序存储。 - `TreeSet` 通过 `compareTo` 或 `compare` 方法保证元素唯一性和排序，适合需要排序的场景。 两者的实现机制不同，但都确保了 `Set` 中元素不重复的特性。