【数据结构】Java 集合 Set 接口及其实现类的定义简介

接口继承接口，类实现接口。

Set 是一个接口，实现了 Collection 接口（都带有泛型）。它可以被继承或实现。在Java 集合章节的知识点中，学习其子类对象的实现以及关系。

类关系图

可以在IDEA中直接生成

<interface> Set

集合 Set 均是非线程安全的。

public interface Set<E> extends Collection<E> {
    // Query Operations
}

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

顾名思义，此接口对数学集抽象进行建模。

一个不含重复元素的集合，即任意元素使用equals函数比较时都返回false。

常用的 Set 实现类有：

• TreeSet
• HashSet
  • LinkedHashSet 是 HashSet 的子类

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {}

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {}

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {}

实现类 TreeSet

非线程安全的

实现类 HashSet

实现类 LinkedHashSet

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s. add(e) is invoked when s. contains(e) would return true immediately prior to the invocation.)

This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet. It can be used to produce a copy of a set that has the same order as the original, regardless of the original set's implementation:
      void foo(Set s) {
          Set copy = new LinkedHashSet(s);
          ...
      }

A linked hash set has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashSet. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashSet, as iteration times for this class are unaffected by capacity.

LinkedHashSet 虽然继承 HashSet ，但跟 HashSet 有差别：

• 其内维护了一个双向链表（doubly-linked），有序插入。
• 可以传入Set参数直接创建 LinkedHashSet 对象为原始 Set 的副本，构造方法如下：

    /**
     * Constructs a new linked hash set with the same elements as the
     * specified collection.  The linked hash set is created with an initial
     * capacity sufficient to hold the elements in the specified collection
     * and the default load factor (0.75).
     *
     * @param c  the collection whose elements are to be placed into
     *           this set
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

• LinkedHashSet 和 HashSet 都有两个影响性能的参数：初始容量capacity  和 load factor。但是 LinkedHashSet 因为自身的迭代时间不受容量的影响（内部定义了迭代器方法），所以初始容量选择过高值的损失比 HashSet 要轻。
  • 迭代器只能尽力抛出ConcurrentModificationException，但不能完全保证非线程安全的 LinkedHashSet 可以不在并发场景中出问题。

    /**
     * Constructs a new, empty linked hash set with the specified initial
     * capacity and load factor.
     *
     * @param      initialCapacity the initial capacity of the linked hash set
     * @param      loadFactor      the load factor of the linked hash set
     * @throws     IllegalArgumentException  if the initial capacity is less
     *               than zero, or if the load factor is nonpositive
     */
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    /**
     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
     * and <em>fail-fast</em> {@code Spliterator} over the elements in this set.
     *
     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
     * {@link Spliterator#DISTINCT}, and {@code ORDERED}.  Implementations
     * should document the reporting of additional characteristic values.
     *
     * @implNote
     * The implementation creates a
     * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
     * from the set's {@code Iterator}.  The spliterator inherits the
     * <em>fail-fast</em> properties of the set's iterator.
     * The created {@code Spliterator} additionally reports
     * {@link Spliterator#SUBSIZED}.
     *
     * @return a {@code Spliterator} over the elements in this set
     * @since 1.8
     */
    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }

Note that this implementation is not synchronized. If multiple threads access a linked hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the Collections. synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the set:
    Set s = Collections. synchronizedSet(new LinkedHashSet(...));

LinkedHashSet 是非同步的，即非线程安全的。如果多线程并发操作 LinkedHashSet 并至少有一个线程修改了此哈希集，则必须在外部同步该数据。

• 通常在自然封装的集合的某个对象上进行同步
• 如果不存在此类对象，则应该使用如下Collections 类的方法同步，最好在创建对象时就执行操作，以避免不同步访问Set的不同步造成异常

 Set s = Collections. synchronizedSet(new LinkedHashSet(set));