HashSet TreeSet LinkedHashSet 区别

桃扇骨 2022-08-08 21:29 231阅读 0赞

set不包含重复的元素，这也是使用set的一个主要原因，set有三个常用的实现，分别是HashSet、TreeSet和LinkedList。总之，对于这三个实现，何时使用是一个重要的问题，如果你需要一个快速的set，你应该使用hashSet；如果需要使用一个排序好的set，那么应该是TreeSet；如果需要一个保持插入顺序的set，那么LinkedHashSet是一个不错的选择。

### Set接口 ###

set接口扩展自collection接口，在set中，是不允许有重复元素存在的，在set中的元素必须是独一无二的，你可以随意的将任一元素添加到set中，set会自动将重复的元素移除。

![Center][]

### HashSet、TreeSet和LinkedHashSet比较 ###

HashSet是用hash table 实现的，它其中的元素是无序的，add、remove和contains方法的时间复杂度都是O(1)。

TreeSet是使用tree 结构实现的（算法书中的红黑树）。它其中的元素是有序的，但是add、remove和contains方法的时间复杂度是 O(log (n))，TreeSet提供了frist()、last()、headset()和tailset()等方法来处理这个有序的set。

LinkedHashSet是介于TreeSet和HashSet之间的，它利用hash table 实现的，同时使用了Link  List，所以它提供了插入的顺序，基本方法的时间复杂度是O(1)。

### 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

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\`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

### 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

注意：这个顺序是不确定的。

### 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

### 性能测试 ###

下边的三个类的方法测试都是基于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是排序的所以它是最慢的。

![Center 1][]

原文链接：http://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/

下边是原文的一些评论，这里一并翻译出来：

如果你想访问set中的任意元素，无疑TreeSet是最快的，因为TreeSet已经排序好了无需再遍历整个数组或者是链表。所有的linked实现的结构在访问任意元素傻上都很慢，但是在移动和替换元素上是很快的。

HashSet是大多内存要求的，如果你有大量的RAM，并且在你的set中的读写的性能相对合理的话，那么HashSet是个不错的选择。

**关注我，获取400个的赚钱金点子，轻松开启程序员的副业生涯**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb3llcWl1_size_16_color_FFFFFF_t_70][]

[Center]: /images/20220731/8e77f2c346fb4ab499b6f744fe845336.png
[Center 1]: /images/20220731/af1130a138ba4569bdcaeeda88bec988.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb3llcWl1_size_16_color_FFFFFF_t_70]: /images/20220731/01890439bf1842e1bdb4579625e98753.png