Java中的HashSet和TreeSet

在讨论集合(Set)的区别时，首先需要考虑的是元素的插入顺序和处理方式。Java中的HashSet是一个实现Set接口的类，支持由哈希表实现的HashMap。该类允许空元素，对于增加、删除、包含和大小等基本操作的性能表现非常快，前提是哈希函数将元素正确分散在桶中。而TreeSet是实现SortedSet接口的类，使用树来存储元素，并保持元素的自然顺序，无论是否提供了显式比较器都可以这样做。

1. 速度和内部实现

对于搜索、插入和删除等操作，HashSet的平均时间复杂度为常量级，性能比TreeSet更快。HashSet是利用哈希表实现的。而TreeSet则需要O(Log n)的时间，可以提供排序的数据，它支持较多的操作，如higher()（返回最小的高层元素）、floor()、ceiling()等，这些操作在TreeSet中的时间复杂度也是O(Log n)，但是在HashSet中不支持。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()方法来比较集合中的两个对象以及检测重复。而TreeSet则使用compareTo()方法来完成相同的目的。如果equals()和compareTo()不一致，即对于两个相等的对象，equals()应该返回true，而compareTo()应该返回零，则会打破Set接口的约定，并允许在Set的实现中（如TreeSet）中存在重复元素。

注意： 如果需要排序的Set，最好先将元素添加到HashSet中，然后再将其转换为TreeSet，而不是创建TreeSet后再向其中添加元素。

程序员们在比较HashSet和TreeSet之后可能会问： 何时应选择TreeSet而不是HashSet呢？

需要排序的唯一元素而非唯一元素。由TreeSet给出的排序列表始终是升序的。
TreeSet的局部性大于HashSet。如果两个条目在顺序中相邻，则TreeSet会将它们放在数据结构和内存中彼此靠近的位置，而HashSet则会将它们分散到内存中，无论它们与哪些键关联。
TreeSet在底层使用红黑树算法对元素进行排序。当需要频繁进行读/写操作时，TreeSet是一个很好的选择。
LinkedHashSet是介于这两者之间的另一种数据结构。它提供了与HashSet相似的时间复杂度，并保持插入顺序（注意这不是排序顺序，而是元素插入的顺序）。

实现： 在这里，我们将会提供两个示例，分别讨论HashSet和TreeSet的实现。首先来看HashSet，然后再探讨TreeSet。

HashSet例子
TreeSet例子

例1：

// Java程序演示HashSet类的工作原理

// 从java.util包中导入必需的HashSet类
import java.util.HashSet;

// 主类
class GFG {

  // 主驱动程序方法
  public static void main(String[] args) {
    // 创建一个字符串类型的HashSet对象
    HashSet<String> hset = new HashSet<String>();

    // 使用add()方法向HashSet添加元素
    hset.add("geeks");
    hset.add("for");
    hset.add("practice");
    hset.add("contribute");

    // 删除重复内容
    hset.add("geeks");

    // 使用for each循环打印HashSet元素
    // 仅显示消息
    System.out.println("HashSet包含的元素: ");

    // 使用for-each循环遍历hashSet
    for (String temp: hset) {

        // 打印上述哈希集内的所有元素
        System.out.println(temp);
    }
  }
}

输出：

HashSet包含的元素: 
practice
geeks
for
contribute

例2：

// Java程序演示HashSet类的工作原理
// 从另一个集合中导入
 
// 导入实用类
import java.util.*;

class GFG {

  // 主驱动程序方法
  public static void main(String[] args) {

    ArrayList<String> ll = new ArrayList<String>();

    //向ArrayList添加元素
    ll.add("Computer");
    ll.add("Science");

    // 创建一个字符串类型的HashSet对象
    HashSet<String> hs = new HashSet(ll);
    hs.add("Portal");
    hs.add("GFG");

    // 通过迭代器遍历
    Iterator<String> iter = hs.iterator();

    // 在列表中存在单个元素时条件成立
    while (iter.hasNext()) {
        // 打印对象内的所有元素
        System.out.println(iter.next());
    }
  }
}

输出：

Java中的HashSet和TreeSet

现在是时候 实现TreeSet 来更好地理解它。

例1：

// Java程序演示TreeSet类的工作原理

// 导入需要的类
import java.util.TreeSet;

// 类
class TreeSetDemo {

  // 主驱动程序方法
  public static void main(String[] args) {
    // 创建一个空的TreeSet
    TreeSet<String> tset = new TreeSet<String>();

    // 使用add()方法添加元素到HashSet
    tset.add("geeks");
    tset.add("for");
    tset.add("practice");
    tset.add("contribute");

    // 删除重复内容
    tset.add("geeks");

    // 显示TreeSet元素
    System.out.println("TreeSet包含的元素: ");

    for (String temp: tset) {
        System.out.println(temp);
    }
  }
}

输出：

TreeSet包含的元素: 
contribute
for
geeks
practice

例2：

// Java程序演示了TreeSet从另一个集合中获取元素的工作原理

// 导入实用类
import java.util.*;

// 主类
class GFG {

    // 主驱动程序方法
    public static void main(String[] args)
    {

        // 创建字符串列表
        ArrayList<String> ll = new ArrayList<String>();

        // 使用add()方法向ArrayList中添加元素
        ll.add("计算机");
        ll.add("科学");

        // 创建字符串类型的TreeSet对象
        TreeSet<String> ts = new TreeSet(ll);

        // 向上述TreeSet中添加元素
        ts.add("门户网站");
        ts.add("GFG");

        // 通过迭代器遍历元素
        Iterator<String> iter = ts.iterator();

        // 在列表中只有一个元素的情况下为真的条件
        while (iter.hasNext()) {

            // 打印对象中的所有元素
            System.out.println(iter.next());
        }
    }
}

输出:

Java中的HashSet和TreeSet