HashSet的特点与用法
HashSet的数据结构
HashSet的常用方法及实现
TreeSet的简要说明

HashSet的特点与用法

HashSet是一个没有重复元素的集合，其内部元素也没有顺序。
它可以放入空元素。
它不是线程安全的。
它内部是基于HashMap实现的。

以下摘取了一部分HashSet文档：

...   

* This class implements the <tt>Set</tt> interface, backed by a hash table
* (actually a <tt>HashMap</tt> 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 <tt>null</tt>
* element.
*
* <p>This class offers constant time performance for the basic operations
* (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
* assuming the hash function disperses the elements properly among the
* buckets.  Iterating over this set requires time proportional to the sum of
* the <tt>HashSet</tt> instance's size (the number of elements) plus the
* "capacity" of the backing <tt>HashMap</tt> instance (the number of
* buckets).  Thus, it's very important not to set the initial capacity too
* high (or the load factor too low) if iteration performance is important.

...

如果要遍历元素，则需要注意容器的大小，因为遍历的时间复杂度是容器的实际大小X容器的初始化大小。（测试一有代码和测试结果。）

HashSet的数据结构

HashSet内部使用HashMap来存储数据，新加入的元素会作为key储存到set当中。value部分由一个默认的object元素来进行填充。

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**
 * 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的常用方法

add

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

remove

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

contain

public boolean contains(Object o) {
    return map.containsKey(o);
}

构造函数

没什么好说的，直接上代码

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

附一元素遍历的测试

测试1.1

首先，测试当一个集合包含1000个元素时，集合初始容量为10000和100000时的性能。

long startTime = System.currentTimeMillis();
for(int i=0;i<10000;i++){
    HashSet<String> set = new HashSet<String>(100000);
    for(int j=0;j<1000;j++){
        set.add(j+"");
    }
    Iterator<String> ite = set.iterator();
    while(ite.hasNext()){
        ite.next();
    }
}
System.out.println("开始时间:"+(System.currentTimeMillis()-startTime));
startTime = System.currentTimeMillis();
for(int i=0;i<10000;i++){
    HashSet<String> set = new HashSet<String>(1000);
    for(int j=0;j<1000;j++){
        set.add(j+"");
    }
    Iterator<String> ite = set.iterator();
    while(ite.hasNext()){
        ite.next();
    }
}
System.out.println("开始时间:"+(System.currentTimeMillis()-startTime));

运行结果：

开始时间:2647
开始时间:781

测试1.2

为了消除元素初始化时，不同容量大小引起的误差，去掉遍历，测试运行的时间

long startTime = System.currentTimeMillis();
for(int i=0;i<10000;i++){
    HashSet<String> set = new HashSet<String>(100000);
    for(int j=0;j<1000;j++){
        set.add(j+"");
    }
    /*Iterator<String> ite = set.iterator();
    while(ite.hasNext()){
        ite.next();
    }*/
}
System.out.println("开始时间:"+(System.currentTimeMillis()-startTime));
startTime = System.currentTimeMillis();
for(int i=0;i<1000;i++){
    HashSet<String> set = new HashSet<String>(1000);
    for(int j=0;j<1000;j++){
        set.add(j+"");
    }
    /*Iterator<String> ite = set.iterator();
    while(ite.hasNext()){
        ite.next();
    }*/
}
System.out.println("开始时间:"+(System.currentTimeMillis()-startTime));

运行结果：

开始时间:1142
开始时间:795

TreeSet的简要说明

TreeSet的实现除了委托的数据结构是TreeMap外，其他的操作与HashSet基本类似