一、Set 集合的相同点

无论是 HashSet、LinkedHashSet 还是 TreeSet，它们都继承了 java.util.Set 接口，因此具有以下共同特性：

1. 不允许重复元素

   • 判断重复依赖 equals() 和 hashCode() 方法（TreeSet 特例：用比较器 compareTo() 或 Comparator）。

2. 无索引

   • 不能像 List 那样用 get(int index) 直接访问。

3. 支持迭代器遍历

   • 都支持 Iterator 和增强 for 循环。

4. 线程不安全

   • 多线程操作时需要手动加锁或用 Collections.synchronizedSet() 包装。

5. 允许 null 元素（TreeSet 除外）

   • HashSet、LinkedHashSet 最多允许一个 null。

二、Set 的不同点

三、注意事项

1. hashCode() / equals() 规则

   • 如果重写了 equals()，必须重写 hashCode()，否则会导致 HashSet、LinkedHashSet 元素重复判断出错。

2. TreeSet 元素要求

   • 必须实现 Comparable 接口，或在构造 TreeSet 时提供 Comparator，否则运行时会抛 ClassCastException。

3. null 元素

   • TreeSet 不允许 null，因为比较器无法比较 null 与其他对象。

4. 线程安全

   • 默认不安全，多线程环境要加锁或使用 ConcurrentSkipListSet（线程安全且有序）。

5. 性能差异

   • HashSet、LinkedHashSet 插入/查找比 TreeSet 更快，因为 TreeSet 需要维护有序结构。

四、底层实现原理

1. HashSet 无序，不重复，无索引

• 数据结构：基于 HashMap

• 实现方式：

  public class HashSet<E> implements Set<E> {
      private transient HashMap<E,Object> map;
      private static final Object PRESENT = new Object();
      public boolean add(E e) {
          return map.put(e, PRESENT) == null;
      }
  }
  

• 工作流程：

  1. 调用 hashCode() 计算哈希值。

  2. 哈希值经过扰动函数计算桶位置。

  3. 桶内用 equals() 判断是否已存在。

  4. 如果不存在则插入。

2. LinkedHashSet  有序，不重复，无索引

• 数据结构：基于 LinkedHashMap

• 特点：

  • 继承 HashSet，在哈希表基础上加 双向链表 维护插入顺序。

• 优点：

  • 遍历时顺序可控（按插入顺序）。

• 原理：

  • 每个节点额外保存 before 和 after 指针，形成链表结构。

3. TreeSet  有序，不重复，无索引

• 数据结构：基于 TreeMap（红黑树）

• 特点：

  • 元素有序（默认自然顺序）。

  • 插入、查找、删除时间复杂度 O(log n)。

• 原理：

  • 每次插入节点时，按 compareTo() 或 Comparator 规则在红黑树中定位位置。

  • 保证树的平衡性，避免退化成链表。

五、总结对比图

注意：Set要用到的常量方法，基本上就是 Collection 提供的！自己几乎无额外新增的常用功能！