【Java】泛型与集合篇（二）

Set 接口及实现类

HashSet 类

HashSet 是 Java 集合框架中 Set 接口的一个具体实现类，它存储唯一的元素，不允许重复值，且不保证元素的顺序。下面从多个方面详细介绍 HashSet 类。

特点

1. 不允许重复元素：HashSet 会使用元素的 hashCode() 和 equals() 方法来确保元素的唯一性。当添加一个元素时，HashSet 首先会计算元素的哈希码，然后根据哈希码找到对应的存储位置，如果该位置已经有元素，会进一步使用 equals() 方法来判断两个元素是否相等，如果相等则不会添加该元素。
2. 无序性：HashSet 不保证元素的存储顺序，即元素添加的顺序和遍历的顺序可能不同。
3. 允许存储 null 元素：但只能存储一个 null 元素，因为重复的 null 元素会被视为相同元素而不被添加。
4. 非线程安全：如果在多线程环境下使用，需要进行额外的同步处理，比如使用 Collections.synchronizedSet() 方法来包装 HashSet。

内部实现

HashSet 内部基于 HashMap 实现，它将元素存储在 HashMap 的键中，而值则统一使用一个静态的 PRESENT 对象。HashMap 的哈希表结构使得 HashSet 在插入、删除和查找元素时具有较好的性能，平均时间复杂度为 O (1)。

构造方法

• HashSet() 创建一个空的散列集合，该集合的默认初始容量是 16，默认装填因子是 0.75。
• HashSet(Collection c) 用指定的集合c的元素创建一个散列集合
• HashSet(int initialCapacity) 创建一个散列集合，并指定集合的初始容量
• HashSet(int initialCapacity,float loadFactor) 创建一个散列集合，并指定集合的初始容量和装填因子

以下是使用这些方法的代码示例：

import java.util.*;

public class HashSetExample {
   
    public static void main(String[] args) {
   
        // 使用HashSet()构造方法
        HashSet<Integer> hashSet1 = new HashSet<>();
        hashSet1.add(1);
        hashSet1.add(2);
        System.out.println("使用HashSet()构造的集合: " + hashSet1);

        // 使用HashSet(Collection c)构造方法
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(4);
        HashSet<Integer> hashSet2 = new HashSet<>(list);
        System.out.println("使用HashSet(Collection c)构造的集合: " + hashSet2);

        // 使用HashSet(int initialCapacity)构造方法
        HashSet<Integer> hashSet3 = new HashSet<>(10);
        hashSet3.add(5);
        hashSet3.add(6);
        System.out.println("使用HashSet(int initialCapacity)构造的集合: " + hashSet3);

        // 使用HashSet(int initialCapacity, float loadFactor)构造方法
        HashSet<Integer> hashSet4 = new HashSet<>(10, 0.8f);
        hashSet4.add(7);
        hashSet4.add(8);
        System.out.println("使用HashSet(int initialCapacity, float loadFactor)构造的集合: " + hashSet4);
    }
}

注意事项：

1. 当使用自定义类作为 HashSet 的元素时，必须重写 hashCode() 和 equals() 方法，以确保元素的唯一性判断正确。
2. 在多线程环境下使用时，要进行同步处理，否则可能会出现数据不一致的问题。

LinkedHashSet 类

LinkedHashSet 是 Java 集合框架中的一个类，它结合了 HashSet 的哈希表存储特性和链表维护插入顺序的特性。下面从基本概念、特点、常用方法、示例代码等方面对 LinkedHashSet 类进行详细介绍。

基本概念

LinkedHashSet 继承自 HashSet 并实现了 Set 接口。它内部使用哈希表（HashMap）来存储元素，同时使用双向链表维护元素的插入顺序。这意味着当你遍历 LinkedHashSet 时，元素会按照它们被插入的顺序返回。

特点

1. 元素唯一：和其他 Set 实现类一样，LinkedHashSet 不允许存储重复的元素。当你尝试添加重复元素时，LinkedHashSet 会忽略该操作。
2. 保持插入顺序：LinkedHashSet 会维护元素的插入顺序，当你遍历集合时，元素会按照它们被插入的顺序依次返回。
3. 非线程安全：LinkedHashSet 不是线程安全的。如果多个线程同时访问一个 LinkedHashSet，并且至少有一个线程修改了该集合，那么它必须在外部进行同步。可以使用 Collections.synchronizedSet 方法来包装 LinkedHashSet 以实现线程安全。
4. 性能：LinkedHashSet 的基本操作（如 add、remove 和 contains）的时间复杂度是 ，和 HashSet 相同。但是由于需要维护链表，它的空间开销会略大一些。

构造方法

• LinkedHashSet()：创建一个空的 LinkedHashSet，初始容量为 16，加载因子为 0.75。
• LinkedHashSet(int initialCapacity)：创建一个具有指定初始容量的空 LinkedHashSet，加载因子为 0.75。
• LinkedHashSet(int initialCapacity, float loadFactor)：创建一个具有指定初始容量和加载因子的空 LinkedHashSet。
• LinkedHashSet(Collection<? extends E> c)：创建一个包含指定集合中所有元素的 LinkedHashSet。

常用方法

LinkedHashSet 继承了 HashSet 的大部分方法，因为它是 HashSet 的子类。以下是一些常用方法：

• 添加元素
  • boolean add(E e)：将指定的元素添加到集合中，如果集合中已经包含该元素，则返回 false。
  • boolean addAll(Collection<? extends E> c)：将指定集合中的所有元素添加到该集合中。
• 删除元素
  • void clear()：移除集合中的所有元素。
  • boolean remove(Object o)：如果集合中包含指定的元素，则将其移除。
• 查找元素
  • boolean contains(Object o)：如果集合包含指定的元素，则返回 true。
• 集合大小
  • int size()：返回集合中的元素数量。
• 遍历元素
  • 可以使用迭代器（Iterator）、增强 for 循环或 forEach 方法来遍历 LinkedHashSet 中的元素。

以下是使用这些方法的代码示例：

import java.util.LinkedHashSet;

public class LinkedHashSetExample {
   
    public static void main(String[] args) {
   
        // 创建一个 LinkedHashSet 并添加元素
        LinkedHashSet<String> fruits = new LinkedHashSet<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        fruits.add("Apple"); // 重复元素，不会被添加

        // 输出集合中的元素，会按插入顺序排序
        System.out.println("LinkedHashSet 中的元素: " + fruits);

        // 查找元素
        System.out.println("是否包含元素 Banana: " + fruits.contains("Banana"));

        // 删除元素
        fruits.remove("Orange");
        System.out.println("删除元素 Orange 后，LinkedHashSet 中的元素: " + fruits);

        // 遍历元素
        System.out.println("遍历 LinkedHashSet 中的元素:");
        for (String fruit : fruits) {
   
            System.out.println(fruit);
        }
    }
}

适用场景

由于 LinkedHashSet 能保持元素的插入顺序，它适用于需要保证元素插入顺序的场景，例如记录用户的操作历史，在展示时需要按照操作的先后顺序展示，就可以使用 LinkedHashSet 来存储操作记录。

用 Set 对象实现集合运算

使用 Set 对象的批量操作方法，可以实现标准集合代数运算。假设 s1 和 s2 是 Set 对象，下面的操作可以实现相关的集合运算：

• s1.addAll(s2); 实现集合 s1 与 s2 的并运算。
• s1.retainAll(s2); 实现集合 s1 与 s2 的交运算。
• s1.removeAll(s2); 实现集合 s1 与 s2 的差运算。
• s1.containAll(s2); 如果 s2 是 s1 的子集，该方法返回 true。

以下是使用这些方法的代码示例：

import java.util.HashSet;
import java.util.Set;

public class SetOperationExample {
   
    public static void main(String[] args) {
   
        // 创建Set对象s1
        Set<Integer> s1 = new HashSet<>();
        s1.add(1);
        s1.add(2);
        s1.add(3);

        // 创建Set对象s2
        Set<Integer> s2 = new HashSet<>();
        s2.add(3);
        s2.add(4);
        s2.add(5);

        // 并运算
        Set<Integer> unionResult = new HashSet<>(s1);
        unionResult.addAll(s2);
        System.out.println("并集结果: " + unionResult);

        // 交运算
        Set<Integer> intersectionResult = new HashSet<>(s1);
        intersectionResult.retainAll(s2);
        System.out.println("交集结果: " + intersectionResult);

        // 差运算
        Set<Integer> differenceResult = new HashSet<>(s1);
        differenceResult.removeAll(s2);
        System.out.println("差集结果: " + differenceResult);

        // 判断子集
        boolean isSubset = s1.containsAll(s2);
        System.out.println("s2是否是s1的子集: " + isSubset);
    }
}

TreeSet 类

TreeSet 是 Java 集合框架中的一个重要类，它实现了 NavigableSet 接口（NavigableSet 接口继承的 SortedSet 接口是 Set 接口的子接口），底层基于红黑树（一种自平衡的二叉搜索树）实现。以下将详细介绍 TreeSet 类：

特性

1. 元素唯一性：TreeSet 遵循 Set 接口的通用特性，不允许存储重复元素。当试图添加已存在的元素时，添加操作会失败。
2. 元素有序性：TreeSet 中的元素会自动排序，默认按照元素的自然顺序（如果元素实现了 Comparable 接口）排列；也可以在创建 TreeSet 时传入自定义的 Comparator 来指定排序规则。
3. 高效操作：由于采用红黑树结构，TreeSet 在添加、删除和查找元素操作上具有 的时间复杂度。
4. 非线程安全：和大多数集合类一样，TreeSet 不是线程安全的。如果在多线程环境下使用，需要进行额外的同步处理。

构造方法

• TreeSet()：创建一个空的 TreeSet，元素按照自然顺序排序。
• TreeSet(Comparator<? super E> comparator)：创建一个空的 TreeSet，使用指定的比较器对元素进行排序。
• TreeSet(Collection<? extends E> c)：创建一个包含指定集合中所有元素的 TreeSet，元素按照自然顺序排序。
• TreeSet(SortedSet<E> s)：创建一个包含指定有序集合中所有元素的 TreeSet，使用与指定有序集合相同的比较器。

以下是使用构造方法的代码示例：

import java.util.*;

class CustomComparator implements Comparator<Integer> {
   
    @Override
    public int compare(Integer o1, Integer o2) {
   
        return o2 - o1;  // 逆序比较
    }
}

public class TreeSetExample {
   
    public static void main(String[] args) {
   
        // 使用TreeSet()构造方法
        TreeSet<Integer> treeSet1 = new TreeSet<>();
        treeSet1.add(3);
        treeSet1.add