day10：HashSet与其他集合

📚 学习目标

• 理解HashSet的实现原理
• 掌握HashSet的常用方法
• 理解TreeSet与自然排序
• 理解LinkedHashSet的特点
• 掌握各集合类的选择和使用
• 理解Collections工具类的使用

---

一、HashSet概述

1.1 HashSet简介

什么是HashSet？

HashSet是基于HashMap实现的Set集合，存储不重复的元素。

继承体系

java.lang.Object
  └── java.util.AbstractCollection<E>
        └── java.util.AbstractSet<E>
              └── java.util.HashSet<E>

实现接口

• Set：集合接口
• Cloneable：支持克隆
• Serializable：支持序列化

---

1.2 HashSet特点

特点	说明
无序性	不保证元素的顺序
元素唯一	不允许存储重复元素
允许null	允许存储一个null元素
非线程安全	多线程环境下需要手动同步
底层实现	基于HashMap
查询快	基于哈希表，contains时间复杂度O(1)

---

二、HashSet源码分析

2.1 核心成员变量

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    
    // 底层使用HashMap存储元素
    private transient HashMap<E,Object> map;
    
    // 空的Object对象，作为HashMap的value
    private static final Object PRESENT = new Object();
}

---

2.2 构造方法

public class HashSet<E> {
    // 底层创建一个空的HashMap
    public HashSet() {
        map = new HashMap<>();
    }
    
    // 指定初始容量
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    
    // 指定初始容量和负载因子
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    
    // 使用集合初始化
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
}

---

2.3 常用方法实现

// add方法
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

// remove方法
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

// contains方法
public boolean contains(Object o) {
    return map.containsKey(o);
}

// size方法
public int size() {
    return map.size();
}

// isEmpty方法
public boolean isEmpty() {
    return map.isEmpty();
}

// clear方法
public void clear() {
    map.clear();
}

---

三、HashSet常用方法

3.1 添加元素

import java.util.HashSet;

public class HashSetAddDemo {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        
        // 1. add(E e)：添加元素
        boolean added1 = set.add("Java");
        boolean added2 = set.add("Python");
        boolean added3 = set.add("Java");  // 重复元素
        
        System.out.println("添加Java: " + added1);  // true
        System.out.println("添加Python: " + added2);  // true
        System.out.println("添加重复Java: " + added3);  // false
        
        System.out.println("HashSet: " + set);
        
        // 2. addAll(Collection c)：添加集合
        HashSet<String> otherSet = new HashSet<>();
        otherSet.add("C++");
        otherSet.add("Go");
        
        set.addAll(otherSet);
        System.out.println("addAll后: " + set);
    }
}

---

3.2 删除元素

import java.util.HashSet;

public class HashSetRemoveDemo {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Java");
        set.add("Python");
        set.add("C++");
        set.add("Go");
        
        System.out.println("原始集合: " + set);
        
        // 1. remove(Object o)：删除元素
        boolean removed = set.remove("Python");
        System.out.println("删除Python: " + removed);  // true
        System.out.println("删除后: " + set);
        
        // 2. removeAll(Collection c)：删除集合中的所有元素
        HashSet<String> toRemove = new HashSet<>();
        toRemove.add("C++");
        toRemove.add("Ruby");
        
        boolean changed = set.removeAll(toRemove);
        System.out.println("removeAll: " + changed);
        System.out.println("removeAll后: " + set);
        
        // 3. clear()：清空集合
        set.clear();
        System.out.println("clear后: " + set);
        System.out.println("isEmpty: " + set.isEmpty());
    }
}

---

3.3 查询元素

import java.util.HashSet;

public class HashSetQueryDemo {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Java");
        set.add("Python");
        set.add("C++");
        set.add("Go");
        
        // 1. contains(Object o)：判断是否包含元素
        System.out.println("contains(\"Java\"): " + set.contains("Java"));
        System.out.println("contains(\"Rust\"): " + set.contains("Rust"));
        
        // 2. isEmpty()：判断是否为空
        System.out.println("isEmpty: " + set.isEmpty());
        
        // 3. size()：获取元素个数
        System.out.println("size: " + set.size());
        
        // 4. 遍历
        System.out.println("\n遍历方式1：forEach");
        for (String item : set) {
            System.out.println(item);
        }
        
        System.out.println("\n遍历方式2：Iterator");
        java.util.Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

---

四、HashSet去重原理

4.1 去重机制

HashSet通过hashCode()和equals()两个方法判断元素是否重复。

去重流程

1. 添加元素A
   ↓
2. 计算A的hashCode()
   ↓
3. 根据hashCode()找到存储位置
   ↓
4. 如果该位置为空，直接存入
   ↓
5. 如果该位置不为空，遍历链表/红黑树
   ↓
6. 比较A与已有元素的equals()
   ↓
7. 如果equals()返回true，拒绝添加
   ↓
8. 否则，添加成功

4.2 自定义对象去重

import java.util.HashSet;
import java.util.Objects;

public class HashSetDeduplication {
    public static void main(String[] args) {
        HashSet<Student> set = new HashSet<>();
        
        set.add(new Student(1, "张三"));
        set.add(new Student(2, "李四"));
        set.add(new Student(1, "张三"));  // 会去重吗？
        
        System.out.println("集合大小: " + set.size());  // 取决于是否重写hashCode和equals
        
        for (Student s : set) {
            System.out.println(s);
        }
    }
}

class Student {
    private int id;
    private String name;
    
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return id == student.id && Objects.equals(name, student.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
    
    @Override
    public String toString() {
        return "Student{id=" + id + ", name='" + name + "'}";
    }
}

---

五、TreeSet

5.1 TreeSet概述

什么是TreeSet？

TreeSet是基于红黑树实现的Set集合，可以对元素进行排序。

特点

特点	说明
有序	按照自然顺序或自定义顺序排序
元素唯一	不允许存储重复元素
非线程安全	多线程环境下需要手动同步
底层实现	基于TreeMap（红黑树）
不允许null	不允许存储null（除非Comparator允许）

---

5.2 自然排序

import java.util.TreeSet;

public class TreeSetNaturalOrder {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        
        // 添加元素
        set.add(5);
        set.add(2);
        set.add(8);
        set.add(1);
        set.add(9);
        
        System.out.println("TreeSet: " + set);
        System.out.println("first: " + set.first());
        System.out.println("last: " + set.last());
        System.out.println("lower(5): " + set.lower(5));
        System.out.println("higher(5): " + set.higher(5));
        
        // 遍历（有序）
        System.out.println("\n遍历:");
        for (int num : set) {
            System.out.println(num);
        }
    }
}

---

5.3 自定义排序

import java.util.TreeSet;

public class TreeSetCustomOrder {
    public static void main(String[] args) {
        // 方式1：使用Lambda表达式（Java 8+）
        TreeSet<String> set1 = new TreeSet<>((s1, s2) -> s2.compareTo(s1));
        set1.add("Apple");
        set1.add("Banana");
        set1.add("Cherry");
        System.out.println("降序: " + set1);
        
        // 方式2：使用Comparator接口
        TreeSet<String> set2 = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
        set2.add("apple");
        set2.add("BANANA");
        set2.add("Cherry");
        System.out.println("忽略大小写: " + set2);
        
        // 方式3：自定义Comparator
        TreeSet<Student> studentSet = new TreeSet<>(new StudentComparator());
        studentSet.add(new Student(3, "张三"));
        studentSet.add(new Student(1, "李四"));
        studentSet.add(new Student(2, "王五"));
        
        System.out.println("\n学生按年龄排序:");
        for (Student s : studentSet) {
            System.out.println(s);
        }
    }
}

// 学生类
class Student {
    private int age;
    private String name;
    
    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }
    
    public int getAge() { return age; }
    public String getName() { return name; }
    
    @Override
    public String toString() {
        return "Student{age=" + age + ", name='" + name + "'}";
    }
}

// 自定义比较器
import java.util.Comparator;
class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getAge() - s2.getAge();
    }
}

---

六、LinkedHashSet

6.1 LinkedHashSet概述

什么是LinkedHashSet？

LinkedHashSet是HashSet的子类，基于LinkedHashMap实现，可以维护元素的插入顺序。

特点

特点	说明
有序	保持元素的插入顺序
元素唯一	不允许存储重复元素
允许null	允许存储一个null元素
底层实现	基于LinkedHashMap

---

6.2 使用示例

import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        
        set.add("Java");
        set.add("Python");
        set.add("C++");
        set.add("Java");  // 重复，不会添加
        set.add("Go");
        
        System.out.println("LinkedHashSet: " + set);
        System.out.println("保持插入顺序: " + set);
        
        // LinkedHashSet vs HashSet
        System.out.println("\n对比HashSet:");
        java.util.HashSet<String> hashSet = new java.util.HashSet<>();
        hashSet.add("Java");
        hashSet.add("Python");
        hashSet.add("C++");
        hashSet.add("Go");
        System.out.println("HashSet: " + hashSet);  // 无序
    }
}

---

七、各Set集合对比

7.1 对比表

对比项	HashSet	TreeSet	LinkedHashSet
底层实现	HashMap	TreeMap	LinkedHashMap
顺序	无序	有序（自然/自定义）	插入顺序
查找效率	O(1)	O(log n)	O(1)
插入删除效率	O(1)	O(log n)	O(1)
null支持	允许一个null	不允许null	允许一个null
线程安全	否	否	否

---

7.2 选择建议

场景	推荐使用
只关心元素唯一，不关心顺序	HashSet
需要对元素排序	TreeSet
需要保持插入顺序	LinkedHashSet
需要频繁查询	HashSet
需要范围操作	TreeSet

---

八、Collections工具类

8.1 排序操作

import java.util.*;

public class CollectionsSortDemo {
    public static void main(String[] args) {
        // 1. sort(List<T> list)：自然排序
        List<Integer> list1 = new ArrayList<>();
        list1.add(5);
        list1.add(2);
        list1.add(8);
        list1.add(1);
        
        Collections.sort(list1);
        System.out.println("sort: " + list1);
        
        // 2. sort(List<T> list, Comparator<? super T> c)：自定义排序
        List<String> list2 = new ArrayList<>();
        list2.add("Banana");
        list2.add("Apple");
        list2.add("Cherry");
        
        Collections.sort(list2, Collections.reverseOrder());
        System.out.println("降序: " + list2);
        
        // 3. reverse(List<?> list)：反转
        Collections.reverse(list1);
        System.out.println("reverse: " + list1);
        
        // 4. shuffle(List<?> list)：随机打乱
        Collections.shuffle(list1);
        System.out.println("shuffle: " + list1);
        
        // 5. swap(List<?> list, int i, int j)：交换
        Collections.swap(list1, 0, list1.size() - 1);
        System.out.println("swap: " + list1);
    }
}

---

8.2 查找操作

import java.util.*;

public class CollectionsSearchDemo {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 3, 5, 7, 9, 11);
        
        // 1. binarySearch(List<?> list, T key)：二分查找（必须先排序）
        int index = Collections.binarySearch(list, 7);
        System.out.println("binarySearch(7): " + index);
        
        // 2. max(Collection<?> coll)：获取最大元素
        System.out.println("max: " + Collections.max(list));
        
        // 3. min(Collection<?> coll)：获取最小元素
        System.out.println("min: " + Collections.min(list));
        
        // 4. frequency(Collection<?> c, Object o)：统计出现次数
        List<String> list2 = Arrays.asList("A", "B", "A", "C", "A");
        System.out.println("frequency(A): " + Collections.frequency(list2, "A"));
    }
}

---

8.3 同步控制

import java.util.*;

public class CollectionsSyncDemo {
    public static void main(String[] args) {
        // 1. synchronizedList：创建线程安全的List
        List<String> syncList = Collections.synchronizedList(new ArrayList<>());
        
        // 2. synchronizedSet：创建线程安全的Set
        Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
        
        // 3. synchronizedMap：创建线程安全的Map
        Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
        
        // 注意：迭代时需要加锁
        synchronized (syncList) {
            for (String s : syncList) {
                System.out.println(s);
            }
        }
    }
}

---

8.4 不可变集合

import java.util.*;

public class CollectionsImmutableDemo {
    public static void main(String[] args) {
        // 1. emptyList()：空List
        List<String> emptyList = Collections.emptyList();
        // emptyList.add("test");  // UnsupportedOperationException
        
        // 2. singletonList(T o)：单元素List
        List<String> singletonList = Collections.singletonList("唯一");
        System.out.println("singletonList: " + singletonList);
        
        // 3. unmodifiableList(List<? extends T> list)：不可变List
        List<String> modifiable = new ArrayList<>();
        modifiable.add("A");
        List<String> unmodifiable = Collections.unmodifiableList(modifiable);
        // unmodifiable.add("B");  // UnsupportedOperationException
        
        // 4. Map的不可变集合
        Map<String, Integer> singletonMap = Collections.singletonMap("key", 1);
        Map<String, Integer> unmodifiableMap = Collections.unmodifiableMap(new HashMap<>());
    }
}

---

九、实践案例

9.1 数组去重

import java.util.*;

public class ArrayDeduplication {
    public static void main(String[] args) {
        // 方法1：使用HashSet去重
        Integer[] arr = {1, 2, 3, 2, 4, 3, 5, 1, 6, 5};
        
        Set<Integer> set = new HashSet<>(Arrays.asList(arr));
        System.out.println("去重后: " + set);
        
        // 方法2：保持顺序的去重
        LinkedHashSet<Integer> linkedSet = new LinkedHashSet<>(Arrays.asList(arr));
        System.out.println("保持顺序去重: " + linkedSet);
        
        // 方法3：统计重复元素
        Map<Integer, Integer> countMap = new HashMap<>();
        for (Integer num : arr) {
            countMap.merge(num, 1, Integer::sum);
        }
        System.out.println("元素统计: " + countMap);
    }
}

---

9.2 找出两个数组的交集和并集

import java.util.*;

public class SetOperations {
    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        Set<Integer> set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));
        
        // 并集
        Set<Integer> union = new HashSet<>(set1);
        union.addAll(set2);
        System.out.println("并集: " + union);
        
        // 交集
        Set<Integer> intersection = new HashSet<>(set1);
        intersection.retainAll(set2);
        System.out.println("交集: " + intersection);
        
        // 差集（set1 - set2）
        Set<Integer> difference = new HashSet<>(set1);
        difference.removeAll(set2);
        System.out.println("差集(set1-set2): " + difference);
        
        // 对称差集（set1 ∪ set2 - set1 ∩ set2）
        Set<Integer> symmetricDifference = new HashSet<>(union);
        symmetricDifference.removeAll(intersection);
        System.out.println("对称差集: " + symmetricDifference);
    }
}

---

9.3 成绩统计系统

import java.util.*;

public class ScoreStatistics {
    public static void main(String[] args) {
        // 准备数据
        List<Integer> scores = Arrays.asList(
            85, 92, 78, 95, 88, 76, 91, 83, 90, 72,
            88, 95, 81, 77, 89, 94, 86, 79, 92, 85
        );
        
        // 使用TreeSet进行统计
        TreeSet<Integer> scoreSet = new TreeSet<>(scores);
        
        System.out.println("========== 成绩统计 ==========");
        System.out.println("学生人数: " + scores.size());
        System.out.println("最高分: " + scoreSet.last());
        System.out.println("最低分: " + scoreSet.first());
        System.out.println("平均分: " + 
            String.format("%.2f", scores.stream()
                .mapToInt(Integer::intValue).average().orElse(0)));
        
        // 分数段统计
        System.out.println("\n分数段统计:");
        System.out.println("90-100分: " + scoreSet.subSet(90, 101).size() + "人");
        System.out.println("80-89分: " + scoreSet.subSet(80, 90).size() + "人");
        System.out.println("70-79分: " + scoreSet.subSet(70, 80).size() + "人");
        System.out.println("60-69分: " + scoreSet.subSet(60, 70).size() + "人");
        System.out.println("60分以下: " + scoreSet.headSet(60).size() + "人");
        
        // 及格率
        long passCount = scores.stream().filter(s -> s >= 60).count();
        System.out.println("\n及格率: " + 
            String.format("%.2f%%", (double) passCount / scores.size() * 100));
    }
}

---

十、常见问题与注意事项

10.1 HashSet vs HashMap

public class HashSetVsHashMap {
    public static void main(String[] args) {
        // HashSet内部使用HashMap存储
        // key: 元素值
        // value: 固定的PRESENT对象
        
        HashSet<String> set = new HashSet<>();
        set.add("Java");
        set.add("Python");
        
        // 实际上等价于
        HashMap<String, Object> map = new HashMap<>();
        map.put("Java", new Object());
        map.put("Python", new Object());
        
        // 不能像Map一样使用get方法获取元素
        // set.get("Java");  // 错误，没有这个方法
        
        // 应该使用contains方法
        System.out.println("contains(\"Java\"): " + set.contains("Java"));
    }
}

---

10.2 TreeSet元素要求

public class TreeSetRequirement {
    public static void main(String[] args) {
        TreeSet<Student> set = new TreeSet<>();
        
        // 错误：Student类没有实现Comparable接口
        // set.add(new Student(1, "张三"));
        
        // 解决方案1：让Student实现Comparable接口
        // 解决方案2：创建TreeSet时传入Comparator
        TreeSet<Student> set2 = new TreeSet<>((s1, s2) -> s1.getAge() - s2.getAge());
        set2.add(new Student2(20, "张三"));
        set2.add(new Student2(18, "李四"));
        
        System.out.println(set2);
    }
}

class Student2 {
    private int age;
    private String name;
    
    public Student2(int age, String name) {
        this.age = age;
        this.name = name;
    }
    
    public int getAge() { return age; }
    
    @Override
    public String toString() {
        return "Student{age=" + age + ", name='" + name + "'}";
    }
}

---

十一、课后作业

必做题

1. 数组去重练习

   • 使用HashSet对数组去重
   • 使用LinkedHashSet保持顺序去重
   • 统计重复元素及其次数

2. Set集合操作

   • 实现交集、并集、差集
   • 实现对称差集

3. TreeSet排序练习

   • 创建自定义对象TreeSet
   • 实现自然排序和自定义排序

选做题

1. 通讯录去重

   • 使用HashSet对联系人去重
   • 保持插入顺序

2. 成绩排名系统

   • 使用TreeSet实现成绩排名
   • 支持查询前N名、后N名

---

十二、学习总结

今日要点

1. HashSet

   • 基于HashMap实现
   • 元素唯一，无序
   • 通过hashCode和equals去重

2. TreeSet

   • 基于TreeMap实现（红黑树）
   • 元素唯一，有序
   • 支持自然排序和自定义排序

3. LinkedHashSet

   • 基于LinkedHashMap实现
   • 元素唯一，保持插入顺序

4. Collections工具类

   • 排序、查找、同步控制、不可变集合

选择建议

• 需要唯一性 → HashSet
• 需要排序 → TreeSet
• 需要顺序 → LinkedHashSet

---

下一课预告：泛型机制

学习时间：建议2-3小时（理论1小时 + 实践1-2小时）