Set接口继承自Collection接口主要用于存储不重复的元素。本文将系统总结Set接口的基础操作、三大核心实现类HashSet、LinkedHashSet、TreeSet的底层原理以及多线程环境下的Set实现。一、 Set 接口核心特性不允许重复集合中任意两个元素e1和e2都满足e1.equals(e2) false。最多允许包含一个null元素取决于具体实现类。无索引Set不维护元素的索引无法通过get(int index)访问元素。无序性大部分除LinkedHashSet维护插入顺序和TreeSet维护自然或定制排序顺序外普通Set不保证遍历顺序与插入顺序一致。二、 通用方法与遍历方式Set继承了Collection的标准集合操作。add方法的返回值通常用于判断元素是否已存在或是否添加成功。SetString set new HashSet(); // 1. 添加元素 boolean isAdded1 set.add(Java); // 返回 true boolean isAdded2 set.add(Java); // 返回 false元素已存在 // 2. 删除元素 set.remove(Java); // 返回 boolean 表示是否成功移除 // 3. 判断与获取 set.contains(Python); // 是否包含指定元素 set.isEmpty(); // 是否为空 set.size(); // 获取元素数量 // 4. 集合运算 SetString set2 new HashSet(Arrays.asList(A, B)); set.addAll(set2); // 并集 set.retainAll(set2); // 交集 set.removeAll(set2); // 差集遍历方式由于没有索引Set只能通过以下三种方式遍历// 1. 增强 for 循环 for (String s : set) { System.out.println(s); } // 2. Iterator 迭代器 (遍历时安全删除元素的唯一推荐方式) IteratorString it set.iterator(); while (it.hasNext()) { String s it.next(); if (Java.equals(s)) { it.remove(); } } // 3. Lambda 表达式 (JDK 8) set.forEach(System.out::println);三、 HashSet 底层原理HashSet是最常用的Set实现类基于哈希表实现具备 O(1) 的增删查时间复杂度。1. 核心结构底层实现内部维护了一个HashMap实例。HashSet的元素被作为HashMap的key存储而value统一指向一个静态常量对象PRESENTprivate static final Object PRESENT new Object();。顺序完全无序。Null 值允许且仅允许存储一个null值。2. 去重与存储流程当调用add(Object o)时HashSet依赖对象的hashCode()和equals()方法判断重复调用对象的hashCode()方法计算哈希值。结合底层数组长度计算出存储索引。如果该位置为空直接存入。如果该位置已有元素哈希冲突则遍历该位置的链表或红黑树依次调用equals()比较若返回true则判定为重复元素拒绝存入。若所有equals()均返回false则将其追加到链表尾部或插入红黑树。3. 自定义对象去重必须重写 equals 和 hashCode若将自定义对象存入HashSet必须重写hashCode()和equals()否则默认继承自Object的方法会比较内存地址导致内容相同的对象无法去重。class Student { String name; int age; // 必须重写 equals 和 hashCode Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Student student (Student) o; return age student.age Objects.equals(name, student.name); } Override public int hashCode() { return Objects.hash(name, age); } }4. JDK 8 结构优化JDK 8 中HashSet底层结构为数组 链表 红黑树。当某个桶位置的链表长度 8且整个哈希表数组容量 64时链表会转化为红黑树使极端哈希冲突下的查询时间复杂度从 O(n) 优化为 O(log n)。四、 LinkedHashSet 底层原理LinkedHashSet直接继承自HashSet用于需要保证迭代顺序的场景。底层结构底层由LinkedHashMap支持。在哈希表的基础上额外维护了一个贯穿所有节点的双向链表。顺序迭代顺序严格等于插入顺序。节点结构每个节点除了常规的哈希值、数据、Next指针外额外包含before和after两个指针用于维护双向链表。五、 TreeSet 底层原理TreeSet不依赖哈希表用于需要对元素进行排序的场景。1. 核心特性底层结构内部维护了一个TreeMap实例底层数据结构为红黑树。顺序元素自动排序自然排序或比较器定制排序。Null 值不支持存储null存入null会抛出NullPointerException。2. 特有方法NavigableSet 接口TreeSet实现了NavigableSet接口支持边界查询和范围操作TreeSetInteger tree new TreeSet(Arrays.asList(10, 20, 30, 40, 50)); tree.first(); // 最小元素10 tree.last(); // 最大元素50 tree.lower(30); // 严格小于 30 的最大元素20 tree.higher(30); // 严格大于 30 的最小元素40 tree.floor(35); // 小于等于 35 的最大元素30 tree.ceiling(35); // 大于等于 35 的最小元素40 tree.subSet(20, 40);// 返回范围视图 [20, 40)3. 去重机制与排序规则TreeSet不依赖hashCode()和equals()它通过比较器判断元素是否重复只要比较方法compareTo或compare返回 0即判定为重复元素。方式一自然排序实现 Comparable 接口class User implements ComparableUser { int id; String name; Override public int compareTo(User o) { int res this.id - o.id; // 需补充多字段比较逻辑防止因单一字段相同如 id 相同但 name 不同被误判为重复元素并丢弃 return res 0 ? this.name.compareTo(o.name) : res; } }方式二定制排序传入 Comparator 比较器TreeSetString set new TreeSet((s1, s2) - { int lenDiff s1.length() - s2.length(); return lenDiff 0 ? s1.compareTo(s2) : lenDiff; });六、 核心实现类对比总结特性HashSetLinkedHashSetTreeSet底层数据结构哈希表 (数组链表红黑树)哈希表 双向链表红黑树 (二叉查找树)元素顺序无序插入顺序按大小排序允许 null 值允许 (最多 1 个)允许 (最多 1 个)不允许重复判定标准hashCode()equals()hashCode()equals()compareTo()或compare()返回 0时间复杂度增删查O(1)增删查O(1)增删查O(log n)七、 线程安全的 Set 实现上述HashSet、LinkedHashSet、TreeSet均非线程安全。多线程并发修改会抛出ConcurrentModificationException。并发场景下推荐使用以下方案Collections.synchronizedSet原理基于装饰器模式通过synchronized关键字为所有操作方法加排他锁。特点实现简单但锁粒度粗并发性能较低。SetString syncSet Collections.synchronizedSet(new HashSet());CopyOnWriteArraySet原理底层基于CopyOnWriteArrayList实现。写操作添加、删除时通过复制底层数组实现无锁读。特点读操作绝对线程安全且高效写操作开销大内存占用高。适用于“读多写少”场景如配置黑名单。SetString cowSet new CopyOnWriteArraySet();ConcurrentHashMap.newKeySet()原理底层利用ConcurrentHashMap通过 CAS 和局部锁保证高并发安全。特点性能最优适用于绝大多数高并发且需要去重的读写场景。SetString concurrentSet ConcurrentHashMap.newKeySet();
Set 集合系列
Set接口继承自Collection接口主要用于存储不重复的元素。本文将系统总结Set接口的基础操作、三大核心实现类HashSet、LinkedHashSet、TreeSet的底层原理以及多线程环境下的Set实现。一、 Set 接口核心特性不允许重复集合中任意两个元素e1和e2都满足e1.equals(e2) false。最多允许包含一个null元素取决于具体实现类。无索引Set不维护元素的索引无法通过get(int index)访问元素。无序性大部分除LinkedHashSet维护插入顺序和TreeSet维护自然或定制排序顺序外普通Set不保证遍历顺序与插入顺序一致。二、 通用方法与遍历方式Set继承了Collection的标准集合操作。add方法的返回值通常用于判断元素是否已存在或是否添加成功。SetString set new HashSet(); // 1. 添加元素 boolean isAdded1 set.add(Java); // 返回 true boolean isAdded2 set.add(Java); // 返回 false元素已存在 // 2. 删除元素 set.remove(Java); // 返回 boolean 表示是否成功移除 // 3. 判断与获取 set.contains(Python); // 是否包含指定元素 set.isEmpty(); // 是否为空 set.size(); // 获取元素数量 // 4. 集合运算 SetString set2 new HashSet(Arrays.asList(A, B)); set.addAll(set2); // 并集 set.retainAll(set2); // 交集 set.removeAll(set2); // 差集遍历方式由于没有索引Set只能通过以下三种方式遍历// 1. 增强 for 循环 for (String s : set) { System.out.println(s); } // 2. Iterator 迭代器 (遍历时安全删除元素的唯一推荐方式) IteratorString it set.iterator(); while (it.hasNext()) { String s it.next(); if (Java.equals(s)) { it.remove(); } } // 3. Lambda 表达式 (JDK 8) set.forEach(System.out::println);三、 HashSet 底层原理HashSet是最常用的Set实现类基于哈希表实现具备 O(1) 的增删查时间复杂度。1. 核心结构底层实现内部维护了一个HashMap实例。HashSet的元素被作为HashMap的key存储而value统一指向一个静态常量对象PRESENTprivate static final Object PRESENT new Object();。顺序完全无序。Null 值允许且仅允许存储一个null值。2. 去重与存储流程当调用add(Object o)时HashSet依赖对象的hashCode()和equals()方法判断重复调用对象的hashCode()方法计算哈希值。结合底层数组长度计算出存储索引。如果该位置为空直接存入。如果该位置已有元素哈希冲突则遍历该位置的链表或红黑树依次调用equals()比较若返回true则判定为重复元素拒绝存入。若所有equals()均返回false则将其追加到链表尾部或插入红黑树。3. 自定义对象去重必须重写 equals 和 hashCode若将自定义对象存入HashSet必须重写hashCode()和equals()否则默认继承自Object的方法会比较内存地址导致内容相同的对象无法去重。class Student { String name; int age; // 必须重写 equals 和 hashCode Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Student student (Student) o; return age student.age Objects.equals(name, student.name); } Override public int hashCode() { return Objects.hash(name, age); } }4. JDK 8 结构优化JDK 8 中HashSet底层结构为数组 链表 红黑树。当某个桶位置的链表长度 8且整个哈希表数组容量 64时链表会转化为红黑树使极端哈希冲突下的查询时间复杂度从 O(n) 优化为 O(log n)。四、 LinkedHashSet 底层原理LinkedHashSet直接继承自HashSet用于需要保证迭代顺序的场景。底层结构底层由LinkedHashMap支持。在哈希表的基础上额外维护了一个贯穿所有节点的双向链表。顺序迭代顺序严格等于插入顺序。节点结构每个节点除了常规的哈希值、数据、Next指针外额外包含before和after两个指针用于维护双向链表。五、 TreeSet 底层原理TreeSet不依赖哈希表用于需要对元素进行排序的场景。1. 核心特性底层结构内部维护了一个TreeMap实例底层数据结构为红黑树。顺序元素自动排序自然排序或比较器定制排序。Null 值不支持存储null存入null会抛出NullPointerException。2. 特有方法NavigableSet 接口TreeSet实现了NavigableSet接口支持边界查询和范围操作TreeSetInteger tree new TreeSet(Arrays.asList(10, 20, 30, 40, 50)); tree.first(); // 最小元素10 tree.last(); // 最大元素50 tree.lower(30); // 严格小于 30 的最大元素20 tree.higher(30); // 严格大于 30 的最小元素40 tree.floor(35); // 小于等于 35 的最大元素30 tree.ceiling(35); // 大于等于 35 的最小元素40 tree.subSet(20, 40);// 返回范围视图 [20, 40)3. 去重机制与排序规则TreeSet不依赖hashCode()和equals()它通过比较器判断元素是否重复只要比较方法compareTo或compare返回 0即判定为重复元素。方式一自然排序实现 Comparable 接口class User implements ComparableUser { int id; String name; Override public int compareTo(User o) { int res this.id - o.id; // 需补充多字段比较逻辑防止因单一字段相同如 id 相同但 name 不同被误判为重复元素并丢弃 return res 0 ? this.name.compareTo(o.name) : res; } }方式二定制排序传入 Comparator 比较器TreeSetString set new TreeSet((s1, s2) - { int lenDiff s1.length() - s2.length(); return lenDiff 0 ? s1.compareTo(s2) : lenDiff; });六、 核心实现类对比总结特性HashSetLinkedHashSetTreeSet底层数据结构哈希表 (数组链表红黑树)哈希表 双向链表红黑树 (二叉查找树)元素顺序无序插入顺序按大小排序允许 null 值允许 (最多 1 个)允许 (最多 1 个)不允许重复判定标准hashCode()equals()hashCode()equals()compareTo()或compare()返回 0时间复杂度增删查O(1)增删查O(1)增删查O(log n)七、 线程安全的 Set 实现上述HashSet、LinkedHashSet、TreeSet均非线程安全。多线程并发修改会抛出ConcurrentModificationException。并发场景下推荐使用以下方案Collections.synchronizedSet原理基于装饰器模式通过synchronized关键字为所有操作方法加排他锁。特点实现简单但锁粒度粗并发性能较低。SetString syncSet Collections.synchronizedSet(new HashSet());CopyOnWriteArraySet原理底层基于CopyOnWriteArrayList实现。写操作添加、删除时通过复制底层数组实现无锁读。特点读操作绝对线程安全且高效写操作开销大内存占用高。适用于“读多写少”场景如配置黑名单。SetString cowSet new CopyOnWriteArraySet();ConcurrentHashMap.newKeySet()原理底层利用ConcurrentHashMap通过 CAS 和局部锁保证高并发安全。特点性能最优适用于绝大多数高并发且需要去重的读写场景。SetString concurrentSet ConcurrentHashMap.newKeySet();
