Set接口的常用实现类特点

1.HashSet

• 特点:

  • 基于哈希表实现。
  • 元素的存储和检索效率很高（平均时间复杂度为 O(1)）。
  • 不保证元素的顺序。
  • 不允许 null 元素。

为什么hashset有很好的存储、查找、删除性能？

性能分析

1. 插入操作 (add)

   • 当插入一个新元素时，首先计算该元素的哈希码。
   • 根据哈希码确定元素在哈希表中的位置。
   • 如果没有冲突，则直接将元素放入该位置；如果有冲突，则将元素添加到该位置上的链表中。
   • 平均时间复杂度为 O(1)。

2. 查找操作 (contains)

   • 查找操作与插入类似，先计算元素的哈希码。
   • 根据哈希码定位到元素可能存在的位置。
   • 如果没有冲突，则立即找到元素；如果有冲突，则需要遍历该位置上的链表。
   • 平均时间复杂度为 O(1)，最坏情况为 O(n)（当所有的元素都在同一个链表中时）。

3. 删除操作 (remove)

   • 删除操作也先计算元素的哈希码。
   • 定位到元素所在位置，并从链表中移除该元素。
   • 平均时间复杂度为 O(1)。

2.LinkedHashSet

• 特点:
  • 继承自 HashSet，但是维护了一个运行于所有条目的双重链接列表。
  • 保证迭代顺序与插入顺序相同。
  • 不允许 null 元素。

LinkedHashSet怎么保证迭代顺序与插入顺序相同？

LinkedHashSet 的内部结构

LinkedHashSet 实际上是在 HashSet 的基础上添加了一个双向链表来维持元素的插入顺序。这意味着每个元素不仅存储在一个哈希表中，而且还被连接到一个双向链表中。

1. 哈希表：用于存储元素，以保证快速查找。
2. 双向链表：用于维护元素的插入顺序。

元素的存储

当向 LinkedHashSet 添加元素时，会执行以下步骤：

• 计算元素的哈希码。
• 根据哈希码确定元素在哈希表中的位置。
• 如果没有冲突，则直接将元素放入该位置；如果有冲突，则将元素添加到该位置上的链表中。
• 在双向链表中将新元素添加到最后。

迭代顺序

由于每个元素都被添加到了双向链表的末尾，所以当使用迭代器遍历 LinkedHashSet 时，元素的访问顺序遵循链表的顺序，也就是元素的插入顺序。

3.TreeSet

• 特点:
  • 基于红黑树实现。
  • 自然排序或自定义排序。
  • 保证元素按升序排列。
  • 不允许 null 元素。