Set是不包含重复的元素的集合， 这是使用Set的主要原因之一。 有3个常用的Set：HashSet，TreeSet和LinkedHashSet。 何时怎么使用是一个重要问题。简而言之，如果你需要一个快速的Set，你应该使用HashSet; 如果你需要一个有序集合，那么应该使用TreeSet; 如果您需要一个可以存储插入顺序的集合，则应该使用LinkedHashSet。
1. Set接口
Set接口继承了Collection接口。在一个Set中重复元素是不被允许的，Set中的每一个元素必须是唯一的。你可以很容易的添加元素到Set中，并且重复的元素会自动被移除。
java-collection-hierarchy.jpeg
2. HashSet TreeSet LinkedHashSet
HashSet是使用哈希表实现的。 元素没有排序。 add，remove和contains 方法具有恒定的时间复杂度O(1)。
TreeSet使用树结构实现（红黑树）。 集合中的元素是排序的，但添加，删除和包含方法的时间复杂度为O(log(n))。 它提供了几种处理有序集的方法，如first()，last()，headSet()，tailSet()等。
LinkedHashSet位于HashSet和TreeSet之间。 它被实现为一个哈希表，其中包含一个链表，它提供了插入的顺序。 基本方法的时间复杂度是O(1)。
3. TreeSet实例
TreeSet<Integer> tree = new TreeSet<Integer>();
tree.add(12);
tree.add(63);
tree.add(34);
tree.add(45);
Iterator<Integer> iterator = tree.iterator();
System.out.print("Tree set data: ");
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
输出如下：
Tree set data: 12 34 45 63
现在定义一个Dog类如下：
class Dog {
int size;
public Dog(int s) {
size = s;
}
public String toString() {
return size + "";
}
}
添加一些Dog实例到TreeSet中：
public class TestTreeSet {
public static void main(String[] args) {
TreeSet<Dog> dset = new TreeSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
}
编译可以通过，但是运行时报错：
Exception in thread "main" java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(Unknown Source)
at java.util.TreeSet.add(Unknown Source)
at collection.TestTreeSet.main(TestTreeSet.java:22)
因为TreeSet是有序的，Dog对象需要实现 java.lang.Comparable's compareTo() 方法：
class Dog implements Comparable<Dog>{
int size;
public Dog(int s) {
size = s;
}
public String toString() {
return size + "";
}
@Override
public int compareTo(Dog o) {
return size - o.size;
}
}
输出为：
1 2 3
4. HashSet实例
HashSet<Dog> dset = new HashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
输出：
5 3 2 1 4
注意顺序是不确定的。
5. LinkedHashSet 实例
LinkedHashSet<Dog> dset = new LinkedHashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
顺序是确定的即插入时的顺序：
2 1 3 5 4
6. 性能测试
以下是测试三个类的add()方法的性能。
public static void main(String[] args) {
Random r = new Random();
HashSet<Dog> hashSet = new HashSet<Dog>();
TreeSet<Dog> treeSet = new TreeSet<Dog>();
LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
// start time
long startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
hashSet.add(new Dog(x));
}
// end time
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
treeSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
linkedSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet: " + duration);
}
从下面的输出中，我们可以清楚地知道HashSet是最快的。
HashSet: 2244768
TreeSet: 3549314
LinkedHashSet: 2263320
