HashSet vs. TreeSet vs. LinkedHashSet

零度非安全

本文由 ImportNew - 唐小娟 翻译自 Programcreek。
原文出处：Programcreek
原文链接：http://www.programcreek.com/2013 ... t-vs-linkedhashset/

Set 集合不包含重复的元素，这是使用 Set 的主要原因。有三种常见的 Set 实现 —— HashSet，TreeSet 和 LinkedHash

Set。什么时候使用它们，使用哪个是个重要的问题。总体而言，如果你需要一个访问快速的 Set，你应该使用 HashSet；

当你需要一个排序的 Set，你应该使用 TreeSet；当你需要记录下插入时的顺序时，你应该使用 LinedHashSet。

1. Set 接口

Set 接口继承了 Collection 接口。Set 集合中不能包含重复的元素，每个元素必须是唯一的。你只需将元素加入 set 中，重

复的元素会自动移除。

2. HashSet vs. TreeSet vs. LinkedHashSet

HashSet 是采用 hash 表来实现的。其中的元素没有按顺序排列，add()、remove() 以及 contains() 等方法都是复杂度为

O(1) 的方法。

TreeSet 是采用树结构实现(红黑树算法)。元素是按顺序进行排列，但是 add()、remove() 以及 contains() 等方法都是复

杂度为 O(log (n)) 的方法。它还提供了一些方法来处理排序的 set，如 first()， last()， headSet()，tailSet() 等等。

LinkedHashSet 介于 HashSet 和 TreeSet 之间。它也是一个 hash 表，但是同时维护了一个双链表来记录插入的顺序。基

本方法的复杂度为 O(1)。

3. TreeSet的例子

TreeSet tree = new TreeSet();
tree.add(12);
tree.add(63);
tree.add(34);
tree.add(45);
//用Collection中的iterator()方法获取该集合对象的迭代器
Iterator 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 中：

import java.util.Iterator;
import java.util.TreeSet;
 
public class TestTreeSet {
    public static void main(String[] args) {
        TreeSet dset = new TreeSet();
        dset.add(new Dog(2));
        dset.add(new Dog(1));
        dset.add(new Dog(3));
 
        Iterator 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{
    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 dset = new HashSet();
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 iterator = dset.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

输出：

5 3 2 1 4

注意输出顺序是不确定的。

5. LinkedHashSet 的例子

LinkedHashSet dset = new LinkedHashSet();
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 iterator = dset.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

输出的顺序时确定的，就是插入的顺序。

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

这个测试并不是非常精确，但足以反映基本的情况。