Java HashSet vs TreeSet

当涉及到讨论Set之间的差异时，最重要的是插入顺序和如何处理元素的问题。Java中的HashSet是一个实现Set接口的类，由一个哈希表支持，哈希表实际上是一个HashMap实例。这个类允许空元素的存在。该类还为基本操作提供了恒定的时间性能，如添加、删除、包含和大小，假设哈希函数在桶中正确地分散了元素，而TreeSet是SortedSet接口的一个实现，正如其名称所暗示的，它使用树来存储，这里的元素的排序是由一个集合使用其自然排序来维护的，无论是否提供一个显式比较器。

HashSet vs TreeSet in Java

1.速度和内部实现

对于搜索、插入和删除等操作，HashSet平均需要恒定的时间来完成这些操作。HashSet比TreeSet快。HashSet是用一个哈希表实现的。TreeSet在搜索、插入和删除时需要O(Log n)，比HashSet高。但是TreeSet保持排序的数据。此外，它还支持像higher()（返回至少高的元素）、floor()、 ceiling()等操作。这些操作在TreeSet中也是O(Log n)，在HashSet中不支持。TreeSet是用一个自平衡的二进制搜索树（Red-Black Tree）实现的。TreeSet是由Java中的TreeMap支持的。

2. 排序

HashSet中的元素是没有顺序的。TreeSet维护对象的排序顺序由Java中的Comparable或Comparator方法定义。TreeSet的元素默认以升序排序。它提供了几种方法来处理有序的集合，如first()、last()、headSet()、tailSet()等。

3.空对象

HashSet允许空对象。TreeSet不允许空对象并抛出NullPointerException，为什么，因为TreeSet使用compareTo()方法来比较键，compareTo()会抛出java.lang.NullPointerException。

4. 比较

HashSet使用equals()方法来比较Set中的两个对象，用于检测重复的对象。TreeSet使用compareTo()方法实现同样的目的。如果equals()和compareTo()不一致，即对于两个相等的对象，equals应该返回true，而compareTo()应该返回0，那么它将破坏Set接口的契约，并将允许在Set的实现中出现重复，如TreeSet

注意： 如果你想要一个排序的Set，那么最好是将元素添加到HashSet中，然后将其转换为TreeSet，而不是创建一个TreeSet并添加元素到其中。

看完它们的区别后，你一定想知道 什么时候应该选择TreeSet而不是HashSet ？

需要排序的唯一元素而不是唯一元素。TreeSet给出的排序列表总是按升序排列。
如果两个条目在顺序上很接近，那么TreeSet就会将它们放在数据结构中的附近，从而放在内存中，而HashSet则将条目分散在内存中，不管它们与哪个键有关。
TreeSet使用下面的 红黑树算法 来对元素进行排序。当一个人需要经常执行读/写操作时，那么TreeSet是一个不错的选择。
LinkedHashSet是另一种介于这两者之间的数据结构。它提供了像HashSet一样的时间复杂性，并且保持了插入的顺序（注意，这不是排序的顺序，而是元素插入的顺序）。

实现： 在这里我们将用两个例子来讨论这两个东西。让我们从HashSet开始讨论，然后再讨论TreeSet。

HashSet的例子
TreeSet的例子

例1 :

// Java Program to Demonstrate Working of HashSet Class
 
// Importing required HashSet class from java.util package
import java.util.HashSet;
 
// Main class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Creating a HashSet object of string type
        HashSet<String> hset = new HashSet<String>();
 
        // Adding elements to HashSet
        // using add() method
        hset.add("geeks");
        hset.add("for");
        hset.add("practice");
        hset.add("contribute");
 
        // Duplicate removed
        hset.add("geeks");
 
        // Printing HashSet elements using for each loop
 
        // Display message only
        System.out.println("HashSet contains: ");
 
        // Iterating over hashSet using for-each loop
        for (String temp : hset) {
 
            // Printing all elements inside above hashSet
            System.out.println(temp);
        }
    }
}

输出

HashSet contains: 
practice
geeks
for
contribute

例2 :

// Java Program to Illustrate Working of HashSet Class
// From another Collection
 
// Importing utility classes
import java.util.*;
 
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
 
        ArrayList<String> ll = new ArrayList<String>();
 
        // Adding elements to ArrayList
        ll.add("Computer");
        ll.add("Science");
 
        // Creating HashSet object of string type
        HashSet<String> hs = new HashSet(ll);
        hs.add("Portal");
        hs.add("GFG");
 
        // Iterating via iterators
        Iterator<String> iter = hs.iterator();
 
        // Condition holds true till there is single element
        // in the List
        while (iter.hasNext()) {
 
            // Printing all elements inside objects
            System.out.println(iter.next());
        }
    }
}

输出

HashSet vs TreeSet in Java

现在是 实现TreeSet 的时候了，通过实现它可以更好地理解。

例1 :

// Java program to demonstrate working of
// TreeSet Class
 
// Importing required classes
import java.util.TreeSet;
 
// Class
class TreeSetDemo {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Create an empty TreeSet
        TreeSet<String> tset = new TreeSet<String>();
 
        // Adding elements to HashSet
        // using add() method
        tset.add("geeks");
        tset.add("for");
        tset.add("practice");
        tset.add("contribute");
 
        // Duplicate elements being removed
        tset.add("geeks");
 
        // Displaying TreeSet elements
        System.out.println("TreeSet contains: ");
       
        for (String temp : tset) {
            System.out.println(temp);
        }
    }
}

输出

TreeSet contains: 
contribute
for
geeks
practice

例2 :

// Java Program to Illustrate Working of TreeSet
// From another Collection
 
// Importing utility classes
import java.util.*;
 
// Main class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
 
        // Creating list of string
        ArrayList<String> ll = new ArrayList<String>();
 
        // Adding elements to ArrayList
        // using add() method
        ll.add("Computer");
        ll.add("Science");
 
        // Creating TreeSet object of string type
        TreeSet<String> ts = new TreeSet(ll);
 
        // Adding elements to above TreeSet
        ts.add("Portal");
        ts.add("GFG");
 
        // Iterating via iterators
        Iterator<String> iter = ts.iterator();
 
        // Condition that holds true till
        // there is single element in th List
        while (iter.hasNext()) {
 
            // Printing all elements inside objects
            System.out.println(iter.next());
        }
    }
}

输出

HashSet vs TreeSet in Java