Java Set 对比：HashSet vs. TreeSet vs. LinkedHashSet

约定不等于承诺〃 2024-03-27 09:28 59阅读 0赞

## Java Set 对比：HashSet vs. TreeSet vs. LinkedHashSet ##

*本文译自：[HashSet vs. TreeSet vs. LinkedHashSet][]*

Set 不包含重复元素。这是使用集合的主要原因之一。Set 的常用实现有 3 种：HashSet、TreeSet 和 LinkedHashSet。何时使用以及使用哪个是一个重要的问题。简而言之，如果你需要一个快速的集合，你应该使用 HashSet；如果你需要一个排序集，那么应该使用 TreeSet；如果您需要一个可以存储插入顺序的集合，则应使用 LinkedHashSet。

不包含重复元素的集合。更正式地说，集合不包含一对元素e1和e2这样的 e1.equals(e2)，并且最多包含一个空元素。顾名思义，该接口对数学集合抽象进行建模。

除了从Collection接口继承的那些之外，Set 接口还对所有构造函数的契约以及add、equals和 hashCode方法的契约进行了额外的规定。为方便起见，此处还包含其他继承方法的声明。（这些声明附带的规范已针对Set接口进行了定制，但它们不包含任何附加规定。）

毫无疑问，构造函数的附加规定是所有构造函数必须创建一个不包含重复元素（如上定义）的集合。

注意：如果将可变对象用作集合元素，则必须格外小心。如果在对象是集合中的元素时以影响等于比较的方式更改对象的值，则未指定集合的行为。该禁令的一个特例是集合不允许将自身作为元素包含。

一些集合实现对它们可能包含的元素有限制。例如，有些实现禁止空元素，有些实现对其元素的类型有限制。尝试添加不合格的元素会引发未经检查的异常，通常是 NullPointerException或ClassCastException. 尝试查询不合格元素的存在可能会抛出异常，或者可能只是返回 false；有些实现会表现出前者的行为，有些会表现出后者。更一般地，尝试对不合格元素执行操作，其完成不会导致将不合格元素插入集合中可能会抛出异常，也可能会成功，具体取决于实现的选择。此类异常在该接口的规范中被标记为“可选”。

该接口是 Java Collections Framework的成员。

### 1. Set 接口 ###

Set 扩展 Collection 接口。在一组中，不允许重复。集合中的每个元素都必须是唯一的。您可以简单地将元素add到集合中，重复项将自动删除。

![在这里插入图片描述][f39f74cc85924930925774d9d346fc55.png_pic_center]

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

让我们向 TreeSet add一些狗，如下所示：

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因为排序所以慢很多的基本思想。

![在这里插入图片描述][9b131fa805df4af48fa80e2a8cb11b12.png_pic_center]

[HashSet vs. TreeSet vs. LinkedHashSet]: https://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/
[f39f74cc85924930925774d9d346fc55.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8813c0cc0d3d48dfaa0580364894a792.png
[9b131fa805df4af48fa80e2a8cb11b12.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8eb5c6e7de6b49c98cabdc3504a94334.png