HashSet vs. TreeSet vs. LinkedHashSet
原文地址：http://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/
Set 中不包含重复的元素，这是使用 Set 的主要原因之一。 Set 有 3 个常用的实现类：HashSet，TreeSet 和 LinkedHashSet。何时使用哪个是一个重要的问题。简而言之，如果你需要一个快速的 Set，你应该使用 HashSet; 如果你需要一个排序 Set，那么应该使用 TreeSet; 如果您需要可以存储插入顺序的集合，则应使用 LinkedHashSet。
1. Set 接口
Set 接口继承自 Collection 接口。 在 Set 中，不允许重复的元素。 Set 中的每个元素都必须是唯一的。您可以简单地将元素添加到一个 Set 中，并且重复的内容将被自动删除。
2. HashSet vs. TreeSet vs. LinkedHashSet
HashSet 使用哈希表实现，元素是无序的。 add，remove 和 contains 方法具有不变的时间复杂度 O(1)。
TreeSet 使用树结构（算法书中的红黑树）实现，集合中的元素被排序，但是 add，remove 和 contains 方法具有 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 + "";
}
}
然后添加一些 dogs 到 TreeSet 中：
import java.util.Iterator;
import java.util.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的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
这个测试可能不精确，但可以反映出 TreeSet 比较慢的基本思想，因为它被排序了。
