Set接口

• Set接口
  • HashSet
  • TreeSet
  • LinkedHashSet
  • EnumSet
  • CopyOnWriteArraySet

HashSet

Java中的HashSet是集合框架中非常重要的一个类，它实现了Set接口，提供了存储不重复元素的功能。

特点

1. 无序性：HashSet不保证元素的顺序，即元素的存储顺序与插入顺序无关。遍历HashSet的结果是无序的，即使每次遍历的结果可能相同，但并不代表元素是按照特定的顺序存储的。
2. 唯一性：HashSet中不允许包含重复的元素。当向HashSet添加元素时，它会使用元素的hashCode()方法来确定元素的存储位置，并使用equals()方法来判断元素的唯一性。如果两个元素的hashCode()相等且equals()返回true，则HashSet将不会存储第二个元素。
3. 基于哈希表实现：HashSet内部使用哈希表数据结构来存储元素。哈希表通过将元素的键转换为哈希码（即整数）来确定元素的存储位置，这使得HashSet具有快速的插入、删除和查找操作的特性。
4. 允许空元素：HashSet可以存储null元素，实际上它可以存储最多一个null元素，因为HashSet不允许重复元素。
5. 非线程安全：HashSet不是线程安全的，如果多个线程同时访问和修改同一个HashSet实例，可能会导致不确定的结果。如果需要在多线程环境中使用HashSet，可以使用Collections.synchronizedSet()方法将其转换为线程安全的集合，或者使用ConcurrentHashMap等线程安全的集合。

底层数据结构

HashSet的底层依赖于HashMap的数据结构，即一个哈希表。这个哈希表是一个数组，数组中的每个元素都是一个链表或红黑树（Java 8以后引入了红黑树优化）。当向HashSet中添加元素时，并不是直接将元素放入数组，而是将元素作为HashMap的key来存储，而对应的value则是一个固定的对象——PRESENT（一个私有的、唯一的Object实例），用于占位，表示这个键存在于HashSet中。

常用方法

HashSet提供了丰富的常用方法来操作集合中的元素，以下是一些主要的方法：

1. 添加元素：

   • add(Object obj)：将元素添加到HashSet中，如果已存在则不添加，返回true表示添加成功，false表示元素已存在。

2. 删除元素：

   • remove(Object obj)：从HashSet中移除指定的元素，返回true表示移除成功，false表示元素不存在。

3. 检查元素：

   • contains(Object obj)：检查HashSet是否包含指定的元素，返回true表示存在，false表示不存在。

4. 清空集合：

   • clear()：清空HashSet中所有的元素。

5. 获取集合大小：

   • size()：返回HashSet中元素的个数。

6. 判断集合是否为空：

   • isEmpty()：判断HashSet是否为空，如果为空则返回true，否则返回false。

7. 遍历集合：

   • 可以使用Iterator迭代器或增强的for-each循环来遍历HashSet中的元素。需要注意的是，由于HashSet是无序的，所以遍历的结果也是无序的。

综上所述，HashSet是一个基于哈希表实现的、无序且不包含重复元素的集合类，它提供了丰富的常用方法来操作集合中的元素。在使用时需要注意其无序性和非线程安全性的特点，并根据需要选择合适的集合类来满足不同的需求。

TreeSet

Java中的TreeSet是一个基于红黑树（Red-Black Tree）实现的NavigableSet接口的实现类，它提供了一系列与排序相关的特性。

特点

1. 有序性：TreeSet中的元素按照升序排列。默认情况下，如果元素实现了Comparable接口，则按照元素的自然顺序进行排序；如果没有实现Comparable接口，则需要在创建TreeSet时提供一个Comparator来指定排序规则。
2. 唯一性：TreeSet不允许存储重复的元素。当尝试向TreeSet中添加重复元素时，添加操作会失败，并且元素不会被添加到集合中。
3. 动态数据结构：TreeSet是一个动态的数据结构，它可以根据需要自动地调整其内部容量来存储更多的元素。
4. 性能：TreeSet的插入、删除和查找操作的时间复杂度通常为O(log N)，其中N是TreeSet中元素的数量。这是因为红黑树是一种自平衡的二叉查找树，它能够保持树的平衡性，从而保证这些操作的高效性。
5. 线程不安全：TreeSet不是线程安全的，如果多个线程同时访问和修改TreeSet，则需要在外部进行同步处理。

底层数据结构

TreeSet的底层数据结构是红黑树（Red-Black Tree）。红黑树是一种自平衡的二叉查找树，它通过特定的规则和旋转操作来保持树的平衡性，从而确保在动态数据结构中维持排序和二分搜索的性能。红黑树的每个节点都包含颜色属性（红色或黑色），并遵循以下规则：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色的。
• 每个叶节点（NIL或空节点）是黑色的。
• 如果一个节点是红色的，则它的两个子节点都是黑色的。
• 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

这些规则保证了红黑树的平衡性，并使得在插入、删除和查找等操作中的时间复杂度能够保持在O(log N)。

常用方法

TreeSet提供了一系列与集合操作相关的方法，包括添加、删除、查找、遍历等。以下是一些常用的方法：

• add(Object o)：将指定元素添加到TreeSet中。如果该元素已经存在，则不添加。
• remove(Object o)：从TreeSet中移除指定元素。
• contains(Object o)：检查TreeSet中是否包含指定元素。
• size()：返回TreeSet中元素的数量。
• first()：返回TreeSet中的第一个元素（即最小的元素）。
• last()：返回TreeSet中的最后一个元素（即最大的元素）。
• iterator()：返回一个迭代器，用于按照元素的自然顺序或Comparator指定的顺序遍历TreeSet。
• descendingIterator()：返回一个逆序迭代器，用于按照与迭代器相反的顺序遍历TreeSet。
• headSet(Object toElement)：返回TreeSet中所有小于指定元素的子集合，该子集合也是一个TreeSet。
• tailSet(Object fromElement)：返回TreeSet中所有大于或等于指定元素的子集合，该子集合也是一个TreeSet。
• subSet(Object fromElement, Object toElement)：返回TreeSet中从指定起始元素（包括）到指定结束元素（不包括）之间的子集合，该子集合也是一个TreeSet。

需要注意的是，TreeSet中的元素必须是可比较的，因此如果要将自定义对象存储在TreeSet中，需要实现Comparable接口或使用Comparator比较器来指定排序方式。

LinkedHashSet

Java中的LinkedHashSet是HashSet的一个子类，它继承了HashSet的所有特性，并在此基础上增加了保持元素插入顺序的能力。

特点

1. 有序性：LinkedHashSet通过内部维护一个双向链表来记录元素的插入顺序，因此它遍历元素时是按照元素的插入顺序进行的。这与HashSet的无序性形成对比。
2. 唯一性：与HashSet一样，LinkedHashSet也不允许集合中存在重复元素。如果尝试添加已经存在的元素，则添加操作会被忽略。
3. 基于哈希表和链表实现：LinkedHashSet的底层数据结构是由哈希表和链表组成的。哈希表用于保证元素的唯一性，而链表则用于维护元素的插入顺序。
4. 性能：由于需要维护元素的插入顺序，LinkedHashSet的性能相对于HashSet来说会稍微低一些。特别是插入和删除操作，因为它们需要同时更新哈希表和链表。
5. 线程不安全：和HashSet一样，LinkedHashSet也不是线程安全的集合类。如果多个线程同时修改集合中的元素，可能会导致数据不一致的问题。

底层数据结构

LinkedHashSet的底层数据结构是由哈希表和双向链表组成的。哈希表用于存储元素及其对应的哈希码，以支持快速的查找、插入和删除操作。而双向链表则用于记录元素的插入顺序，以支持按照插入顺序遍历元素。这种组合结构使得LinkedHashSet既能够保持元素的唯一性，又能够保持元素的插入顺序。

常用方法

LinkedHashSet提供了丰富的常用方法来操作集合中的元素，以下是一些主要的方法：

• 添加元素：add(E e)，向集合中添加元素。如果元素已经存在，则不会进行添加操作。
• 删除元素：remove(Object o)，从集合中删除指定的元素。如果元素不存在，则不会进行删除操作。
• 判断元素是否存在：contains(Object o)，判断集合中是否包含指定的元素。
• 获取集合大小：size()，返回集合中元素的数量。
• 判断集合是否为空：isEmpty()，判断集合是否为空。
• 清空集合：clear()，清空集合中的所有元素。
• 遍历集合：可以使用增强for循环或迭代器（Iterator<E>）来遍历集合中的元素。遍历结果将按照元素的插入顺序进行。
• 克隆集合：clone()，返回集合的一个浅拷贝。
• 将集合转换为数组：toArray()，将集合转换为一个数组。
• 比较集合：equals(Object o)，比较两个集合是否相等。如果两个集合包含的元素相同且元素的顺序也相同，则这两个集合相等。
• 获取集合的哈希码：hashCode()，返回集合的哈希码。
• 将集合转换为字符串：toString()，返回集合的字符串表示形式。

总的来说，LinkedHashSet是一个有序且不重复的集合类，它适合在需要保持元素插入顺序的场景下使用。通过合理运用其提供的常用方法，可以方便地对集合进行操作和管理。

EnumSet

Java中的EnumSet是专门为枚举类型设计的一个高效集合实现，它继承自AbstractSet<E>类并实现了Set<E>接口。

特点

1. 高效性：EnumSet在内部使用位向量（bit vector）来存储枚举常量，因此在时间和空间上都非常高效。特别是当枚举类型的常量数目较小时，EnumSet的性能优势更加明显。
2. 类型安全：EnumSet只能包含单个枚举类型的值，这使得它比其他集合类更为类型安全。
3. 有序性：EnumSet中的元素会按照枚举类型中声明的顺序进行排序，这保证了集合元素的有序性。
4. 不允许null元素：EnumSet不允许插入null元素，这是由枚举类型的特性决定的。
5. 便捷性：EnumSet提供了一系列静态工厂方法来创建实例，如allOf、noneOf、of、range等，使得使用起来非常方便。

底层数据结构

EnumSet的底层数据结构是位向量（bit vector）。位向量是一种数据结构，它使用单个位的集合来表示元素的存在与否。在EnumSet中，每个枚举常量都对应位向量中的一个位，如果该位被设置为1，则表示对应的枚举常量存在于集合中；如果该位被设置为0，则表示对应的枚举常量不存在于集合中。这种表示方法使得EnumSet在存储和操作枚举常量时非常高效。

常用方法

EnumSet提供了一系列与Set接口一致的方法，如add、remove、contains、size等，同时还提供了一些特有的方法，如allOf、noneOf、of、range等。以下是常用方法的简要介绍：

• add(E e)：向EnumSet中添加一个元素。如果该元素已经存在，则添加操作将被忽略。
• remove(Object o)：从EnumSet中移除一个元素。如果该元素不存在，则移除操作将被忽略。
• contains(Object o)：检查EnumSet中是否包含指定的元素。
• size()：返回EnumSet中元素的数量。
• allOf(Class elementType)：创建一个包含指定枚举类型的所有元素的EnumSet。
• noneOf(Class elementType)：创建一个空的EnumSet，其元素类型为指定的枚举类型。
• of(E e, E... elements)：创建一个包含指定元素的EnumSet。这是一个可变参数方法，可以接受一个或多个枚举常量作为参数。
• range(E from, E to)：创建一个包含从from到to（包括两者）之间所有元素的EnumSet。需要注意的是，from和to必须是同一枚举类型中的有效常量，并且from的值必须小于或等于to的值。

此外，EnumSet还支持一些集合操作，如union、intersection、complement等，这些操作可以方便地对两个或更多个EnumSet实例进行位运算与集合运算。

综上所述，EnumSet是Java中专门为枚举类型设计的一个高效集合实现，它通过位向量来存储枚举常量，具有高效性、类型安全、有序性和便捷性等特点。在实际开发中，当需要处理一组固定的常量，并且这些常量属于同一个枚举类型时，使用EnumSet是一个很好的选择。

CopyOnWriteArraySet

Java中的CopyOnWriteArraySet是一个线程安全的Set集合，它基于CopyOnWriteArrayList实现，适用于读多写少的并发场景。

特点

1. 线程安全：CopyOnWriteArraySet通过写时复制（Copy-On-Write）的策略来保证线程安全。每次修改集合时（如添加、删除元素），都会复制底层数组，并在新数组上进行修改，然后将引用指向新数组，从而避免并发冲突。
2. 读操作高效：由于读操作不需要加锁，且始终读取的是一致的数组快照，因此读操作非常高效。
3. 写操作开销大：写操作（如添加、删除元素）需要复制整个底层数组，因此开销较大。特别是在数据量较大的情况下，写操作可能会成为性能瓶颈。
4. 迭代器弱一致性：迭代器不会抛出ConcurrentModificationException，但也不会反映迭代器创建之后对集合的修改。迭代器的数据来源于迭代时的快照数据。
5. 适用场景：适用于读多写少且数据量不是特别大的并发场景，如缓存等。

底层数据结构

CopyOnWriteArraySet的底层数据结构是基于CopyOnWriteArrayList实现的。CopyOnWriteArrayList内部使用动态数组（Object[]数组）来存储元素，并通过写时复制的策略来保证线程安全。因此，CopyOnWriteArraySet也间接地使用了动态数组作为其底层数据结构。

常用方法

CopyOnWriteArraySet继承自AbstractCollection<E>并实现了Set<E>接口，因此它提供了Set接口的所有方法。以下是一些常用的方法：

• add(E e)：向集合中添加元素。如果集合中不存在该元素，则添加成功；否则，添加失败。
• remove(Object o)：从集合中移除指定的元素。如果集合中存在该元素，则移除成功；否则，移除失败。
• contains(Object o)：检查集合中是否包含指定的元素。
• size()：返回集合中元素的数量。
• isEmpty()：检查集合是否为空。
• clear()：清空集合中的所有元素。
• iterator()：返回集合的迭代器，用于遍历集合中的元素。

需要注意的是，由于CopyOnWriteArraySet的写操作开销较大，因此在写操作频繁的并发场景下，其性能可能会受到影响。此外，由于其迭代器是弱一致性的，因此在迭代器上进行的修改操作可能不会立即反映在集合中。

总的来说，CopyOnWriteArraySet是一个适用于特定场景的线程安全集合，其特点、底层数据结构以及常用方法都体现了其设计理念和适用场景。在实际开发中，应根据具体需求选择合适的集合类来实现功能。