TreeSet,LinkedHashSet以及HashSet之间的区别

原文链接:Difference between TreeSet, LinkedHashSet and HashSet in Java with Example

TreeSet,LinkedHashSet以及HashSet均实现了Set接口,因此他们都遵循Set接口的协议,比如他们都不允许重复的元素。尽管他们都来自同一类型的层次结构,但是他们之间还是有很多区别;理解他们之间的区别非常重要,这样您就可以根据您的需求选择最合适的集合实现。另外,TreeSet和HashSet(或者LinkedHashSet)之间的区别是一个非常流行的Java集合面试题,虽然不如“比较Hashtable和HashMap”或者“比较ArrayList和Vector”这类问题普遍,但是依然出现在各种Java面试中。在这篇文章中,我们将看看HashSet,TreeSet以及LinkedHashSet在各个方面之间的区别,比如元素顺序、性能、是否允许null值等,然后我们会看到在Java中什么时候使用TreeSet、LinkedHashSet、HashSet。

TreeSet,LinkedHashSet以及HashSet之间的区别

TreeSet,LinkedHashSet以及HashSet是Java集合框架中Set接口的三种实现类型,并且像许多其他集合类型一样,他们也用于存储对象。TreeSet的主要特性是其中元素时排序的,LinkedHashSet的主要特性是其中元素是基于插入顺序的,HashSet则仅仅是用于存储对象这一通用集合功能。在Java中HashSet是基于HashMap实现的,而TreeSet是基于TreeMap实现的。TreeSet同时是一个SortedSet接口的实现,因此允许TreeSet中元素基于Comparable或者Comparator接口定义保持元素顺序排序。Comparable通常用于按照对象自然顺序排序,Comparator通常用于对象自定义排序,可以在创建TreeSet实例时提供这两种接口之一用于实例中元素排序。在了解TreeSet, LinkedHashSet 以及HashSet之间的区别之前,我们先看看他们之间的相同之处。

1)是否允许重复元素:三者都实现了Set接口,意味着他们都不允许存储重复元素。

2)线程安全性:HashSet, TreeSet 以及 LinkedHashSet都不是线程安全的。 如果你将他们用于多线程环境下,并且至少有一个线程修改Set集合中的内容的话,你需要使用外部的同步机制来同步他们。

3)快速失败迭代器(Fail-Fast Iterator):TreeSet, LinkedHashSet 以及 HashSet返回的迭代器均为快速失败迭代器。关于更多 fail-fast vs fail-safe Iterator 请阅读这里。

现在让我们来看看HashSet, LinkedHashSet 以及 TreeSet之间的区别

性能和速度:他们之间的第一个区别来自速度,HashSet 是最快的,LinkedHashSet 在性能方面排第二,或者近乎接近于HashSet,TreeSet稍微慢一些,因为每一次插入元素都需要执行排序操作。TreeSet 对于常见操作如add,remove,contains等能够保证时间复杂度为 O(log(n)) ,而 HashSet 和 LinkedHashSet 对于add,contains,remove等操作提供时间复杂度为常数时间的性能,因为HashSet为给定散列函数在桶中均匀分配元素。

排序性:HashSet 不保证元素的任何顺序,而LinkedHashSet 保持元素的插入顺序,更多的像List接口一样,TreeSet 按照元素实现的比较接口保持元素的顺序。

内部实现:HashSet底层基于一个HashMap实例,LinkedHashSet 基于HashSet和LinkedList实现,TreeSet底层基于NavigableMap接口实现,java中默认用TreeMap实现。

null值:HashSet 和 LinkedHashSet允许null值,但是TreeSet 不支持null值,并且当你向TreeSet中插入null值时会抛出 java.lang.NullPointerException 异常。因为TreeSet应用 compareTo() 方法于各个元素来比较他们,当比较null值时会抛出 NullPointerException异常。

比较(Comparison ):HashSet 和 LinkedHashSet 用 equals() 方法用于比较,但是TreeSet 用 compareTo() 方法用于维持元素顺序。这就是为什么在java中compareTo()和 equals() 必须保持一致,否则会打破Set接口的一些通用规则,比如可能会允许重复值。

TreeSet vs HashSet vs LinkedHashSet - 使用示例

让我们通过java编程来比较所有这些Set接口实现在一些方面的异同。在这个例子中我们会证明 TreeSet, HashSet 和 LinkedHashSet在元素顺序和插入1M数据记录所花费的时间之间的差异。这将会帮助我们巩固前面讨论的内容,已经帮助我们决定在java中什么时候应该用HashSet, LinkedHashSet 或者 TreeSet。

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 * Java program to demonstrate difference between TreeSet, HashSet and LinkedHashSet
 * in Java Collection.
 * @author
 */
public class SetComparision {

    public static void main(String args[]){             
        HashSet<String> fruitsStore = new HashSet<String>();
        LinkedHashSet<String> fruitMarket = new LinkedHashSet<String>();
        TreeSet<String> fruitBuzz = new TreeSet<String>();

        for(String fruit: Arrays.asList("mango", "apple", "banana")){
            fruitsStore.add(fruit);
            fruitMarket.add(fruit);
            fruitBuzz.add(fruit);
        }

        //no ordering in HashSet – elements stored in random order
        System.out.println("Ordering in HashSet :" + fruitsStore);

        //insertion order or elements – LinkedHashSet storeds elements as insertion
        System.err.println("Order of element in LinkedHashSet :" + fruitMarket);

        //should be sorted order – TreeSet stores element in sorted order 
        System.out.println("Order of objects in TreeSet :" + fruitBuzz); 


        //Performance test to insert 10M elements in HashSet, LinkedHashSet and TreeSet
        Set<Integer> numbers = new HashSet<Integer>();
        long startTime = System.nanoTime();
        for(int i =0; i<10000000; i++){
            numbers.add(i);
        }

        long endTime = System.nanoTime();
        System.out.println("Total time to insert 10M elements in HashSet in sec : "
                            + (endTime - startTime));


        // LinkedHashSet performance Test – inserting 10M objects
        numbers = new LinkedHashSet<Integer>();
        startTime = System.nanoTime();
        for(int i =0; i<10000000; i++){
            numbers.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("Total time to insert 10M elements in LinkedHashSet in sec : "
                            + (endTime - startTime));

        // TreeSet performance Test – inserting 10M objects
        numbers = new TreeSet<Integer>();
        startTime = System.nanoTime();
        for(int i =0; i<10000000; i++){
            numbers.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("Total time to insert 10M elements in TreeSet in sec : "
                            + (endTime - startTime));
    }
}

Output
Ordering in HashSet :[banana, apple, mango]
Order of element in LinkedHashSet :[mango, apple, banana]
Order of objects in TreeSet :[apple, banana, mango]
Total time to insert 10M elements in HashSet in sec : 3564570637
Total time to insert 10M elements in LinkedHashSet in sec : 3511277551
Total time to insert 10M elements in TreeSet in sec : 10968043705

何时用 HashSet, TreeSet 以及 LinkedHashSet

所有三种Set接口实现都可以用于通用的Set操作,比如不允许重复元素,但是三者又都有其独特的特性,所以在特定的环境下可以有更合适的选择。 由于TreeSet保持元素顺序,所以当你需要一个集合保持元素顺序并且不允许重复元素时,可以使用TreeSet;HashSet是通用的Set集合实现,如果你需要一个效率比较快、且不允许重复元素的集合,则可以使用HashSet;LinkedHashSet 是HashSet的扩展,它更适合当你需要保持元素的插入顺序时使用,更像一个不牺牲昂贵性能的List。LinkedHashSet 的另一个用法是用于创建一个已经存在的Set集合的副本,因为LinkedHashSet 保持插入顺序,它返回包含同一顺序的相同元素的集合,更像精确的复制。总之,尽管他们三个都是Set接口的实现,但是他们均有各自独特的特性,HashSet是一个通用功能的Set,而LinkedHashSet 提供元素插入顺序保证,TreeSet是一个SortedSet实现,由Comparator 或者 Comparable指定的元素顺序存储元素。

如何从一个集合中复制对象到另一个集合

下面是一个LinkedHashSet 的代码示例,来展示LinkedHashSet 如何从一个集合复制对象到另一个集合而且能够保持元素顺序。你将得到一个源Set的精确复制,无论是内容还是顺序都一致。这里静态方法copy(Set source)使用泛型来实现,这样的参数化方法可以提供类型安全,以及帮助避免运行时异常。

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

/**
 * Java program to copy object from one HashSet to another using LinkedHashSet.
 * LinkedHashSet preserves order of element while copying elements.
 * 
 * @author Javin
 */
public class SetUtils{

    public static void main(String args[]) {

        HashSet<String> source = new HashSet<String>(Arrays.asList("Set, List, Map"));
        System.out.println("source : " + source);
        Set<String> copy = SetUtils.copy(source);
        System.out.println("copy of HashSet using LinkedHashSet: " + copy);
    }

    /*
     * Static utility method to copy Set in Java
     */
    public static <T> Set<T> copy(Set<T> source){
           return new LinkedHashSet<T>(source);
    }
}

Output:
source : [Set, List, Map]
copy of HashSet using LinkedHashSet: [Set, List, Map]

通常在代码中用接口而不是具体的接口实现类型,可以在需求变化时很方便的替换为HashSet、LinkedHashSet 或者TreeSet。这就是java中HashSet, LinkedHashSet 以及 TreeSet之间所有的区别,如果你了解这三者之间任何其他更有意义的区别,请在评论区中评论。