简述

---

Set和List一样，也继承于Collection,是集合的一种。和List不同的是，Set内部实现是基于Map的，所以Set取值时不保证数据和存入的时候顺序一致，并且不允许空值，不允许重复值。

然后我们来看下Set的继承结构

可以看出,Set主要有2个实现方式，一个是TreeSet，另一个是HashSet
这个Set的特点，主要由其内部的Map决定的，可以负责人的说一句，Set就是Map的一个马甲

HashSet和TreeSet

---

就如它的名字一样，HashSet主要由HashMap实现

如果调用HashSet的无参构造函数，那么就会使用默认的HashMap，初始化Size为16，扩张系数为0.75

    //简单看下HashMap的几个主要数据执行操作都是间接的调用了内部的HashMap的数据操作
    //比较有意思的是，从add()方法看出，HashSet的值是HashMap的key，
    //HashMap的value是写死的PRESENT
    //所以遍历HashSet的值，也就是遍历HashMap的KeyEntry
    /**
     * Returns an iterator over the elements in this set.  The elements
     * are returned in no particular order.
     *
     * @return an Iterator over the elements in this set
     * @see ConcurrentModificationException
     */
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    /**
     * Returns the number of elements in this set (its cardinality).
     *
     * @return the number of elements in this set (its cardinality)
     */
    public int size() {
        return map.size();
    }

    /**
     * Returns <tt>true</tt> if this set contains no elements.
     *
     * @return <tt>true</tt> if this set contains no elements
     */
    public boolean isEmpty() {
        return map.isEmpty();
    }

    /**
     * Returns <tt>true</tt> if this set contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this set
     * contains an element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this set is to be tested
     * @return <tt>true</tt> if this set contains the specified element
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    /**
     * 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;
    }

    /**
     * Removes the specified element from this set if it is present.
     * More formally, removes an element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
     * if this set contains such an element.  Returns <tt>true</tt> if
     * this set contained the element (or equivalently, if this set
     * changed as a result of the call).  (This set will not contain the
     * element once the call returns.)
     *
     * @param o object to be removed from this set, if present
     * @return <tt>true</tt> if the set contained the specified element
     */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

    /**
     * Removes all of the elements from this set.
     * The set will be empty after this call returns.
     */
    public void clear() {
        map.clear();
    }

TreeSet和HashMap的处理方式相似，这里就不重复展开，区别的地方是，TreeSet内部的是一颗红黑树，至于红黑树的特点，再下一章会详细展开

comparator和comparable

---

由于Set的实现都基于Map，所以操作都十分简单，所以在这章把Map会提到的comparator和comparable提前分析

直观的翻译我们也可以得出，这2个东西都是和排序有关。

comparator和comparable都是接口。

1.comparable

先来看看comparable

Comparable 接口强行对实现它的每个类的对象进行整体排序，Java称这种排序为自然排序，对比于comparator，又称为内部排序

Comparable接口只有一个方法

public int compareTo(T o);

对于需要排序的对象，只要继承这个接口，实现这个compareTo()方法就可以了，（T o）代表传入的数据，需要进行比较的对象。如果位于对象 o 之前，返回负值，如果两个对象在排序中位置相同，则返回 0 ，如果位于对象 o 后面，则返回正值。
在注释中又说到，希望把comparaTo()和equal(）联系起来。因为这个2个方法都是对对象进行比较，如果这2个方法对同一个比较对象产生不同的结果，会造成逻辑上的困惑。

举个例子,

class Test{
    int compareFactor;

    //setCompareFactor...getCompareFactor...

    public int compareTo(T o){
    if(o == null){
    //这里是注释上建议这么做的，如果传入一个空值，需要抛出一个异常
        throw new RuntimeException ("test");
    }

    //如果相等，表示处于比较的同一个位置
    if(this.compareFactor == ((Test)o).getCompareFactor()){
        return 0;
    } else if(this.compareFactor > ((Test)o).getCompareFactor()){
        return 1;
    } else {
        return 0;
    }

}

//使用的时候只要调用Collections或者Array的sort（）方法就好了
Collections.sort(list);

2.Comparator

相对于Comparable ，comparator又称为外部排序。对于一些已经封装好的对象，我们在尽量不修改已有结构的基础上，通过实现Comparator类来新建一个比较器，然后通过该比较器来对类进行排序。Comparator 接口其实就是一种策略模式的实践

Comparator内部包含了2个方法

int compare(T o1, T o2);

boolean equals(Object obj);

由于所有java对象都继承于Object，所以equals(Object obj)已经被实现了，我们只要实现compare(T o1, T o2)方法就好了。实现的思路和comparable一样，只不过comparable是和自己比较，Comparator是对于两个对象进行比较。

3.异同

Comparable是由对象自己实现的，一旦一个对象封装好了，compare的逻辑也就定了，如果我们需要对同一个对象增加一个字段的排序就比较麻烦，又要修改对象本身。比如淘宝的购买页面，增加一种受欢迎度的排序，就需要修改对象内部compare方法。好处是对外部不可见，调用者无需知道排序逻辑，只要调用排序即可，类似于静态绑定。

而Comparator由外部实现，比较灵活，争对上述问题，只要新增一个Comparator即可。缺点是所有排序逻辑对外部暴露，需要对象外部实现。不过这里的外部仅指对象的外部，也可以由API的开发者封装好所有的Comparator，对调用者隐藏内部逻辑。好处是很灵活，随时可以增加一种排序方法，只要对象内部字段支持，类似动态绑定。

总结

---

在这一章节中简单介绍了Set的结构，实现原理。Set是Map的一个马甲，主要逻辑都交给Map实现。在下一章中，会详细介绍Map的实现原理。

还介绍了与排序相关的两个接口comparator和comparable