HashSet vs. TreeSet vs. LinkedHashSet

零度非安全 · 发表于 2017-5-8 11:26:10

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由零度非安全于 2017-5-8 11:25 编辑

本文由 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

复制代码

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

账号		自动登录	找回密码
密码			立即注册

[好文转载] HashSet vs. TreeSet vs. LinkedHashSet

马上注册，结交更多好友，享用更多功能^_^