03_Set接口规范与实现类深度分析
约 4463 字大约 15 分钟
2025-11-17
概述
Set接口是Java集合框架中的一个重要接口,继承自Collection接口,代表一个无序、不重复的集合。它的核心特性是元素的唯一性,不允许存储重复的元素。
核心特征
- 无序性:元素不保证按照特定顺序排列(
LinkedHashSet除外) - 唯一性:不允许存储重复的元素,依赖
equals()和hashCode()方法 - 高效查找:提供高效的元素查找功能
- 接口继承:继承自
Collection接口,拥有Collection的所有基本操作
Set接口定义
public interface Set<E> extends Collection<E> {
// 基本操作
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
// 修改操作
boolean add(E e);
boolean remove(Object o);
// 批量操作
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
// 相等性和哈希码
boolean equals(Object o);
int hashCode();
// Java 8+ 方法
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT);
}
// Java 9+ 方法
static <E> Set<E> of() {
return ImmutableCollections.emptySet();
}
static <E> Set<E> of(E e1) {
return new ImmutableCollections.Set12<>(e1);
}
// 其他of方法重载...
}主要实现类对比
HashSet/LinkedHashSet/TreeSet特性对比表
| 特性 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底层实现 | HashMap | LinkedHashMap | TreeMap |
| 存储结构 | 哈希表 | 哈希表 + 链表 | 红黑树 |
| 插入顺序 | 不保证 | 保证 | 不保证(按排序) |
| 元素排序 | 无序 | 插入顺序 | 自然排序或自定义排序 |
| 查找性能 | O(1) 平均 | O(1) 平均 | O(log n) |
| 插入性能 | O(1) 平均 | O(1) 平均 | O(log n) |
| 删除性能 | O(1) 平均 | O(1) 平均 | O(log n) |
| 线程安全 | 否 | 否 | 否 |
| 允许null值 | 是(仅一个) | 是(仅一个) | 否(非Comparable类型) |
| 内存占用 | 中等 | 较高 | 较高 |
| 适用场景 | 快速查找、去重 | 需要保留插入顺序的去重 | 需要排序的去重 |
HashSet底层实现原理
HashSet入门级使用示例
下面是一个简单的HashSet使用示例,展示最基础的创建、添加、遍历等操作:
public class HashSetBasicExample {
public static void main(String[] args) {
// 创建一个HashSet集合
HashSet<String> colors = new HashSet<>();
// 添加元素
colors.add("红色");
colors.add("蓝色");
colors.add("绿色");
colors.add("黄色");
System.out.println("添加元素后: " + colors);
// 输出类似: [红色, 蓝色, 绿色, 黄色] (注意:HashSet不保证顺序)
// 尝试添加重复元素(不会成功,且不会抛出异常)
boolean added = colors.add("红色");
System.out.println("添加重复元素成功? " + added); // 输出: false
System.out.println("Set中的元素: " + colors); // 仍然是4个元素
// 判断是否包含某个元素
boolean hasRed = colors.contains("红色");
System.out.println("包含红色: " + hasRed); // 输出: true
boolean hasBlack = colors.contains("黑色");
System.out.println("包含黑色: " + hasBlack); // 输出: false
// 遍历HashSet的三种方式
// 1. 使用增强for循环(foreach)遍历
System.out.println("\n使用foreach遍历:");
for (String color : colors) {
System.out.println("颜色: " + color);
}
// 2. 使用迭代器遍历
System.out.println("\n使用迭代器遍历:");
Iterator<String> iterator = colors.iterator();
while (iterator.hasNext()) {
String color = iterator.next();
System.out.println("颜色: " + color);
}
// 3. 使用Lambda表达式遍历(Java 8及以上)
System.out.println("\n使用Lambda表达式遍历:");
colors.forEach(color -> {
System.out.println("颜色: " + color);
});
// 删除元素
boolean removed = colors.remove("绿色");
System.out.println("\n删除绿色成功? " + removed); // 输出: true
System.out.println("删除后: " + colors); // 输出类似: [红色, 蓝色, 黄色]
// 获取集合大小
System.out.println("集合大小: " + colors.size()); // 输出: 3
// 清空集合
colors.clear();
System.out.println("清空后: " + colors); // 输出: []
System.out.println("集合是否为空: " + colors.isEmpty()); // 输出: true
// 实际应用场景:去重
System.out.println("\n去重示例:");
String[] duplicateArray = {"苹果", "香蕉", "苹果", "橙子", "香蕉", "葡萄"};
HashSet<String> uniqueFruits = new HashSet<>();
// 添加数组中的所有元素,自动去除重复
for (String fruit : duplicateArray) {
uniqueFruits.add(fruit);
}
System.out.println("去重前数组: " + Arrays.toString(duplicateArray));
System.out.println("去重后集合: " + uniqueFruits);
// 如果需要保持原来的数组形式
String[] uniqueArray = uniqueFruits.toArray(new String[0]);
System.out.println("去重后数组: " + Arrays.toString(uniqueArray));
}
}基本结构
HashSet底层基于HashMap实现,利用HashMap的key不允许重复的特性来保证Set的元素唯一性。
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
// 底层使用HashMap存储
private transient HashMap<E, Object> map;
// 所有元素对应的value,一个虚拟对象
private static final Object PRESENT = new Object();
// 构造函数
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// 包访问权限的构造函数,供LinkedHashSet使用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
}核心方法实现
// 添加元素
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
// 移除元素
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
// 检查元素是否存在
public boolean contains(Object o) {
return map.containsKey(o);
}
// 获取大小
public int size() {
return map.size();
}
// 清空集合
public void clear() {
map.clear();
}hashCode()和equals()正确实现
HashSet依赖元素的hashCode()和equals()方法来确保元素的唯一性。为了正确使用HashSet,元素类必须正确实现这两个方法。
实现流程图:
正确实现示例:
public class CorrectStudent {
private String id;
private String name;
private int age;
public CorrectStudent(String id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
CorrectStudent student = (CorrectStudent) o;
return age == student.age &&
Objects.equals(id, student.id) &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(id, name, age);
}
@Override
public String toString() {
return "Student{" +
"id='" + id + '\'' +
", name='" + name + '\'' +
", age=" + age +
'}';
}
// 测试HashSet使用
public static void main(String[] args) {
Set<CorrectStudent> students = new HashSet<>();
students.add(new CorrectStudent("001", "张三", 20));
students.add(new CorrectStudent("002", "李四", 21));
students.add(new CorrectStudent("001", "张三", 20)); // 重复元素
System.out.println("集合大小: " + students.size()); // 应该是2
for (CorrectStudent student : students) {
System.out.println(student);
}
}
}错误实现示例:
public class BadStudent {
private String id;
private String name;
private int age;
public BadStudent(String id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
}
// 只重写了equals,没有重写hashCode
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
BadStudent student = (BadStudent) o;
return age == student.age &&
Objects.equals(id, student.id) &&
Objects.equals(name, student.name);
}
// 没有重写hashCode,使用Object的默认实现
@Override
public String toString() {
return "BadStudent{" +
"id='" + id + '\'' +
", name='" + name + '\'' +
", age=" + age +
'}';
}
// 测试
public static void main(String[] args) {
Set<BadStudent> students = new HashSet<>();
BadStudent s1 = new BadStudent("001", "张三", 20);
BadStudent s2 = new BadStudent("001", "张三", 20); // 逻辑上相等
students.add(s1);
students.add(s2);
System.out.println("s1.equals(s2): " + s1.equals(s2)); // true
System.out.println("s1.hashCode() == s2.hashCode(): " +
(s1.hashCode() == s2.hashCode())); // false
System.out.println("集合大小: " + students.size()); // 2,错误地允许了重复元素
}
}LinkedHashSet实现原理
基本结构
LinkedHashSet继承自HashSet,底层使用LinkedHashMap来维护元素的插入顺序。
public class LinkedHashSet<E> extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true); // 调用HashSet的特殊构造函数
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
}底层机制
LinkedHashSet通过调用HashSet中包访问权限的构造函数,传入dummy参数为true,来创建一个LinkedHashMap实例:
// HashSet中的特殊构造函数
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}LinkedHashMap在HashMap的基础上,通过维护一个双向链表来记录元素的插入顺序。每个节点除了保存键值对信息外,还保存了前后节点的引用。
使用场景示例
public class LinkedHashSetExample {
public static void main(String[] args) {
// 创建LinkedHashSet
Set<String> set = new LinkedHashSet<>();
// 添加元素
set.add("Apple");
set.add("Banana");
set.add("Orange");
set.add("Grape");
set.add("Apple"); // 重复元素,不会被添加
// 遍历 - 保持插入顺序
System.out.println("LinkedHashSet遍历(保持插入顺序):");
for (String fruit : set) {
System.out.println(fruit);
}
// 输出: Apple, Banana, Orange, Grape
// 与HashSet对比
Set<String> hashSet = new HashSet<>(set);
System.out.println("\nHashSet遍历(不保证顺序):");
for (String fruit : hashSet) {
System.out.println(fruit);
}
// 输出顺序可能不同
// 应用场景:需要去重且保持插入顺序的场景
// 例如:记录用户操作历史,不允许重复操作且需要按时间顺序展示
// 另一个示例:缓存最近访问的不重复元素
LinkedHashSet<String> recentVisits = new LinkedHashSet<>(100);
String[] pages = {"首页", "产品页", "详情页", "首页", "联系我们"};
for (String page : pages) {
recentVisits.add(page);
}
System.out.println("\n最近访问(去重并保持顺序):" + recentVisits);
// 输出: [首页, 产品页, 详情页, 联系我们]
}
}TreeSet实现原理
基本结构
TreeSet底层基于TreeMap实现,利用TreeMap的有序性来保证Set元素的排序。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
// 底层使用NavigableMap(TreeMap的子接口)
private transient NavigableMap<E, Object> m;
// 所有元素对应的value,一个虚拟对象
private static final Object PRESENT = new Object();
// 构造函数
public TreeSet() {
this(new TreeMap<>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
TreeSet(NavigableMap<E, Object> m) {
this.m = m;
}
}核心方法实现
// 添加元素
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
// 移除元素
public boolean remove(Object o) {
return m.remove(o) == PRESENT;
}
// 获取第一个(最小)元素
public E first() {
return m.firstKey();
}
// 获取最后一个(最大)元素
public E last() {
return m.lastKey();
}
// 获取小于e的最大元素
public E lower(E e) {
return m.lowerKey(e);
}
// 获取小于等于e的最大元素
public E floor(E e) {
return m.floorKey(e);
}
// 获取大于等于e的最小元素
public E ceiling(E e) {
return m.ceilingKey(e);
}
// 获取大于e的最小元素
public E higher(E e) {
return m.higherKey(e);
}排序机制
TreeSet支持两种排序方式:
- 自然排序:元素类实现
Comparable接口,并重写compareTo()方法 - 自定义排序:在构造
TreeSet时传入Comparator接口的实现
自然排序示例:
public class NaturalOrderingExample {
public static void main(String[] args) {
// 使用自然排序(String实现了Comparable)
Set<String> treeSet = new TreeSet<>();
treeSet.add("Banana");
treeSet.add("Apple");
treeSet.add("Orange");
treeSet.add("Grape");
// 输出按自然顺序(字典序)排序的元素
System.out.println("自然排序结果:" + treeSet);
// 输出: [Apple, Banana, Grape, Orange]
// 自定义类实现Comparable
class Student implements Comparable<Student> {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student o) {
// 按分数从高到低排序
return Integer.compare(o.score, this.score);
}
@Override
public String toString() {
return name + "(" + score + ")";
}
}
Set<Student> students = new TreeSet<>();
students.add(new Student("张三", 85));
students.add(new Student("李四", 92));
students.add(new Student("王五", 78));
System.out.println("\n学生按分数排序:");
for (Student student : students) {
System.out.println(student);
}
// 输出: 李四(92), 张三(85), 王五(78)
}
}自定义比较器示例:
public class CustomComparatorExample {
public static void main(String[] args) {
// 自定义比较器:按字符串长度排序
Comparator<String> lengthComparator = Comparator.comparingInt(String::length);
Set<String> treeSet = new TreeSet<>(lengthComparator);
treeSet.add("Java");
treeSet.add("Python");
treeSet.add("C");
treeSet.add("JavaScript");
System.out.println("按长度排序结果:" + treeSet);
// 输出: [C, Java, Python, JavaScript]
// 复合比较器:先按长度,长度相同按字典序
Comparator<String> complexComparator =
Comparator.comparingInt(String::length)
.thenComparing(Comparator.naturalOrder());
Set<String> complexSet = new TreeSet<>(complexComparator);
complexSet.add("bat");
complexSet.add("cat");
complexSet.add("apple");
complexSet.add("dog");
System.out.println("\n复合排序结果:" + complexSet);
// 输出: [bat, cat, dog, apple]
}
}范围操作方法
TreeSet提供了丰富的范围操作方法,这是其他Set实现所不具备的:
public class RangeOperationsExample {
public static void main(String[] args) {
NavigableSet<Integer> set = new TreeSet<>();
// 添加元素
for (int i = 1; i <= 10; i++) {
set.add(i);
}
System.out.println("原始集合: " + set);
// 范围查询
System.out.println("小于5的元素: " + set.headSet(5)); // [1, 2, 3, 4]
System.out.println("大于等于5的元素: " + set.tailSet(5)); // [5, 6, 7, 8, 9, 10]
System.out.println("2到7之间的元素: " + set.subSet(2, 8)); // [2, 3, 4, 5, 6, 7]
// 导航方法
System.out.println("小于5的最大元素: " + set.lower(5)); // 4
System.out.println("小于等于5的最大元素: " + set.floor(5)); // 5
System.out.println("大于等于5的最小元素: " + set.ceiling(5)); // 5
System.out.println("大于5的最小元素: " + set.higher(5)); // 6
// 取首尾元素并移除
System.out.println("移除最小元素: " + set.pollFirst()); // 1
System.out.println("移除最大元素: " + set.pollLast()); // 10
System.out.println("移除后集合: " + set); // [2, 3, 4, 5, 6, 7, 8, 9]
// 降序视图
NavigableSet<Integer> descendingSet = set.descendingSet();
System.out.println("降序视图: " + descendingSet); // [9, 8, 7, 6, 5, 4, 3, 2]
}
}常见陷阱
- 元素必须可比较:如果没有提供比较器,元素类必须实现
Comparable接口,否则会抛出ClassCastException - 比较器与
equals一致性:比较器的比较结果应该与equals()方法保持一致,否则可能导致Set中存在equals()返回true的多个元素
public class InconsistentComparisonExample {
public static void main(String[] args) {
// 自定义比较器只比较name,忽略age
Comparator<Person> nameComparator = Comparator.comparing(Person::getName);
Set<Person> treeSet = new TreeSet<>(nameComparator);
treeSet.add(new Person("张三", 20));
treeSet.add(new Person("张三", 21)); // 不会被添加,因为name相同
// 但两个对象的equals()可能返回false
Person p1 = new Person("张三", 20);
Person p2 = new Person("张三", 21);
System.out.println("p1.equals(p2): " + p1.equals(p2)); // false
System.out.println("集合大小: " + treeSet.size()); // 1
}
static class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() { return name; }
public int getAge() { return age; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age && Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public String toString() {
return name + "(" + age + ")";
}
}
}- 性能考量:
TreeSet的操作时间复杂度为O(log n),比HashSet的O(1)平均复杂度要高,这是因为TreeSet需要维护元素的有序性
Set接口小结
Set接口核心总结(零基础友好版)
Set集合的核心特点
Set是一种无序、不可重复的集合,就像数学中的集合概念,或者现实生活中的标签系统。主要特点:
- 不可重复性:同一个Set中不能存储相同的元素,会自动去重
- 无序性:元素的存储顺序不固定,不能通过索引访问
- 高效查找:对于
HashSet,查找元素的时间复杂度为O(1)
HashSet vs TreeSet vs LinkedHashSet 选择指南
| 集合类型 | 主要特点 | 适用场景 |
|---|---|---|
| HashSet | 无序,查询速度快 | 主要用于去重,不关心元素顺序 |
| TreeSet | 有序,实现了SortedSet接口 | 需要元素按照自然顺序或自定义顺序排列 |
| LinkedHashSet | 维护插入顺序 | 需要保持元素插入顺序的同时又要去重 |
实际应用中的小技巧
- 去重操作:最常见的应用场景就是去除重复元素
// 快速去重数组中的重复元素
String[] array = {"A", "B", "A", "C", "B"};
Set<String> uniqueSet = new HashSet<>(Arrays.asList(array));- 判断元素存在:利用Set高效的查找特性来判断元素是否存在
- 元素相等判断:
- 向Set中添加自定义对象时,必须正确实现
equals()和hashCode()方法 - 这两个方法的实现必须保持一致:如果两个对象
equals()返回true,它们的hashCode()必须相同
- 向Set中添加自定义对象时,必须正确实现
- 遍历方式:
Set只能使用增强for循环(foreach)或迭代器遍历,不能通过索引访问 - 线程安全问题:
HashSet不是线程安全的,多线程环境下可以使用Collections.synchronizedSet()或CopyOnWriteArraySet
学习建议
- 先理解
Set的基本特性:无序和不可重复 - 掌握
Set的基本操作:添加、删除、遍历、判断元素存在 - 学会根据需求选择合适的
Set实现类 - 理解自定义对象作为
Set元素时需要注意的事项
面试知识点
- 元素唯一性保证机制:
HashSet:基于HashMap,依赖hashCode()和equals()LinkedHashSet:基于LinkedHashMap,同时保证插入顺序TreeSet:基于TreeMap,依赖Comparable或Comparator
- 性能特征:
HashSet:查找、插入、删除O(1)平均LinkedHashSet:略高于HashSet,但保持插入顺序TreeSet:所有操作O(log n),但提供排序和范围查询
- 适用场景选择:
- 快速去重:
HashSet - 去重并保持插入顺序:
LinkedHashSet - 去重并排序:
TreeSet
- 快速去重:
- 实现细节:
- 都不是线程安全的
HashSet允许一个null元素(如果元素类型允许)TreeSet在使用自然排序时,元素不能为null(除非Comparable实现允许)
最佳实践
- 正确实现hashCode()和equals():使用
HashSet或LinkedHashSet时,确保元素类正确实现这两个方法,以确保元素的唯一性 - 选择合适的实现类:根据是否需要排序、是否需要保持插入顺序选择合适的
Set实现 - 预估初始容量:对于
HashSet和LinkedHashSet,可以设置合适的初始容量和负载因子
Set<String> set = new HashSet<>(100, 0.75f); // 预设容量和负载因子- 线程安全处理:
// 方式1:使用同步包装器
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
// 方式2:使用CopyOnWriteArraySet(读多写少场景)
Set<String> concurrentSet = new CopyOnWriteArraySet<>();- 利用Java 8+特性:
// 使用Stream API处理Set
Set<String> filteredSet = set.stream()
.filter(s -> s.length() > 5)
.collect(Collectors.toSet());- TreeSet排序注意事项:
// 确保比较器与equals()方法一致
Set<Person> consistentSet = new TreeSet<>((p1, p2) -> {
int cmp = p1.getName().compareTo(p2.getName());
if (cmp != 0) return cmp;
return Integer.compare(p1.getAge(), p2.getAge());
});小结
Set接口是Java集合框架中用于存储不重复元素的重要接口。通过本章节的学习,我们深入理解了Set接口的主要实现类(HashSet、LinkedHashSet、TreeSet)的底层原理、性能特征和适用场景。在实际开发中,我们需要根据具体需求选择合适的Set实现,并注意正确实现元素类的hashCode()和equals()方法(对于HashSet和LinkedHashSet)或提供合适的比较机制(对于TreeSet)。
