linkedhashset java8_[译]HashSet、TreeSet和LinkedHashSet的使用区别

日常中我们经常跟集合打交道，但是如何选择对应的数据结构常常搞不清楚，今天我们就简单看一下HashSet、TreeSet和LinkedHashSet的使用区别.

我们都知道，集合是不包含重复元素的，这是我们选择使用集合的一个重要的原因. 集合有三个我们常用到的实现类：HashSet, TreeSet and LinkedHashSet. 如何根据场景去选择使用哪一种集合是让人头疼的问题. 简而言之,如何你需要的是一个快速的集合，建议你使用HashSet，如果你需要的是一个排序集合，请选择TreeSet，如果你需要一套能够存储插入顺序的集合,请使用LinkedHashSet。

1. Set接口

Set接口继承Collection接口.在集合中不允许出现重复的元素，你可以简单的添加，重复的元素会自动的被移除。

java-collection-hierarchy

2. HashSet vs. TreeSet vs. LinkedHashSet

HashSet使用哈希表实现的，元素是无序的。添加、删除操作时间复杂度都是O(1)。TreeSet内部结构是一个树结构(红黑树)，元素是有序的，添加、删除操作时间复杂度为O(log(n))，并且提供了first(), last(), headSet(), tailSet()等方法来处理有序集合。

LinkedHashSet是介于HashSet 和 TreeSet之间，内部是一个双向链表结构，所以它的插入是有序的，时间复杂度是O(1)。

3. TreeSet 示例

TreeSet tree = new TreeSet();

tree.add(12);

tree.add(63);

tree.add(34);

tree.add(45);

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 + "";

}

}

往TreeSet中添加几只dogs：

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类不是有序的，我们需要将Dog类实现Comparable接口。

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

所以我们在使用TreeSet时候，里面装的元素一定是有序的，否则就不应该选择TreeSet。

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() + " ");

}

按插入的顺序进行输出：

2 1 3 5 4

6. 性能测试

public static void main(String[] args) {

Random r = new Random();

HashSet hashSet = new HashSet();

TreeSet treeSet = new TreeSet();

LinkedHashSet linkedSet = new LinkedHashSet();

// 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要慢得多,因为它是有序的。

hashset-treeset-linkedhashset