Java集合：HashSet和TreeSet

从前文可知，List中的元素是可以重复的，而Map中的key是不可重复的，但是它存放的是一个key-value对的映射，那么有没有一种结构，可以让它存放不重复的数据呢？答案就是Set。

Set最常用的实现类就是HashSet和TreeMap，下面分别进行介绍。

HashSet

HashSet的底层实际上是一个HashMap，因此它的元素是无序的，可以插入null值，它的绝大部分方法底层都调用了map的方法。在类结构中，它持有一个HashMap的字段：

private transient HashMap<E,Object> map;

这就是它的底层存储。

它的构造方法实际上是对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<>();
}

添加元素 add(Object o)

private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

PRESENT是类中的一个静态常量，引用了一个Object对象，因为Set只是利用了map对key的去重型，所以实际上每次添加值的时候只需要往key插入值，value总是一个Object。

获取元素 

跟list不同，Set的底层是hash表的结构，所以我们无法利用像List.get(int index)这种方法获取数据，因此，我们只能通过遍历的方法去获取Set的值。

TreeSet

TreeSet是一个有序的集合，如果调用了默认的构造方法，那么插入数据时它会按照元素的自然顺序进行排序，否则就需要在构造时传入一个Comparator比较器进行元素顺序的定义。

其底层使用的是TreeMap，其他的都是类似的。

LinkedHashSet也是类似于LinkedHashMap，这里就不详细展开了。