HashSet

官方描述：

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

通过这段介绍，可以看出HashSet底层是使用HashMap实现的。

• 其中的无参构造函数如下：

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

创建HashSet的时候创建一个HashMap。我们还可以通过其有参构造函数调用不同的HashMap构造函数，具体可参考源码。

• 添加一个对象

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

调用add方法，向map中添加一个对象，map的key就是这个对象。值是一个虚拟值，没有含义，只是为了添加hashmap使用。

TreeSet

官方描述：

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

• 类似的，它的实现基本相同，只不过它底层使用NavigableMap，而TreeSet使用了HashMap。

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

• add操作源码如下：

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element {@code e} to this set if
     * the set contains no element {@code e2} such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns {@code false}.
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     *         element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in this set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

总结

知道了HashSet与TreeSet的底层实现，就知道了他们依赖这些实现的效果。

1.HashSet使用HashMap实现，所以它的性质就和HashMap是类似的，首先它是无序的，其次就是它增加、查找和删除操作的时间复杂度都是O(1)。

2.TreeSet底层使用NavigableMap实现，NavigableMap是利用红黑树实现的，所以它是有序的，其次就是它增加、查找和删除操作的时间复杂度都是O(log(n))。