java-Set

每日一言

纵有疾风起，人生不言弃。

——宫崎骏《起风了》

HashSet

HashSet的特点：

• HashSet允许有null值。(最多一个)
• HashSet是无序的
• HashSet不是线程安全的，如果多个线程尝试同时修改 HashSet，则最终结果是不确定的。 您必须在多线程访问时显式同步对 HashSet 的并发访问。
• HashSet中的元素实际上是对象，一些常见的基本类型可以使用它的包装类。

低层数据结构：

• 基于 HashMap

  HashSet<E> 的内部真正存储是依托于一个 HashMap<E, Object>，其中所有的元素都成了这个地图的 key ，而 value 则是一个固定的哨兵对象（PRESENT）。

使用HashSet

主要方法：

方法签名	功能描述	时间复杂度
boolean add(E e)	如果集合中不存在则添加，返回 true	平均 O(1)
boolean remove(Object o)	删除指定元素，返回是否成功	平均 O(1)
boolean contains(Object o)	判定是否包含指定元素	平均 O(1)
void clear()	清空所有元素	O(n)
Iterator<E> iterator()	返回遍历所有元素的迭代器	O(n)；迭代时无序

LinkedHashSet

LinkedHashSet 继承自HashSet，但是在HashSet的基础上额外维护了一条双向链表，确保迭代时能够按照插入顺序访问元素。

插入过程：

• 计算 hash 并定位到桶；
• 在桶中和链表尾部同时插入新节点；

删除过程：

• 从桶链或树结构删除；
• 调整双向链表的前后指针；

方法签名	功能描述	返回值	时间复杂度	备注
boolean add(E e)	若集合中不存在，则添加元素	是否成功添加	平均 O(1)	重复元素返回 false
boolean remove(Object o)	删除指定元素	是否成功删除	平均 O(1)	不存在返回 false
boolean contains(Object o)	判断是否包含指定元素	包含返回 true	平均 O(1)
Iterator<E> iterator()	返回按维护顺序遍历的迭代器	迭代器对象	O(1)	每调用 next() 为 O(1)
int size()	返回集合元素个数	元素个数	O(1)
boolean isEmpty()	是否为空	空返回 true	O(1)
void clear()	清空所有元素	—	O(n)	链表与哈希表都需清空
boolean addAll(Collection<? extends E> c)	批量添加	是否改变集合	O(m)	m = 集合 c 的大小
boolean removeAll(Collection<?> c)	批量移除	是否改变集合	O(m)
boolean retainAll(Collection<?> c)	保留与 c 集合的交集	是否改变集合	O(n + m)	n = this.size(), m = c.size()

TreeSet

主要特性：

• 基于 红黑树 实现，元素按 自然顺序 或 自定义 Comparator 排序；
• 不允许 null（否则抛 NullPointerException）；
• 支持 导航方法（如 first()、last()、lower()、floor()、ceiling()、higher() 等）；
• 所有基本操作时间复杂度均为 O(log n)。

低层数据结构：

• 内部通过一个 TreeMap<E,Object> 来存储元素，TreeSet 中的每个元素都成为该 TreeMap 的 key，对应的 value 为固定哨兵 PRESENT。
• TreeMap 基于 红黑树（自平衡二叉搜索树）实现，保证在插入、删除和查找时的树高始终为 O(log n)。

实现原理：

1. 插入（add）

   • 先在红黑树中查找应插入的位置；
   • 若不存在，则插入新节点并进行红黑树平衡（旋转与变色）；

2. 删除（remove）

   • 在树中定位目标节点并删除，随后执行相应的红黑树调整；

3. 查找（contains、navigation）

   • 按二叉搜索树规则，从根节点比对 compare(key, node.key)，向左或向右递归查找；

常用方法

方法签名	功能描述	返回值	时间复杂度	备注
boolean add(E e)	插入元素，若已存在则不变	是否成功添加	O(log n)	元素必须实现 Comparable或提供 Comparator
boolean remove(Object o)	删除指定元素	是否成功删除	O(log n)
boolean contains(Object o)	判断是否包含	包含返回 true	O(log n)
Iterator<E> iterator()	返回按排序顺序遍历的迭代器	迭代器对象	O(1) / 每次 next()O(1)	首次 O(h)，后续 O(1)
int size()	返回元素个数	元素数量	O(1)
boolean isEmpty()	判断是否为空	空返回 true	O(1)
void clear()	清空所有元素	—	O(n)
E first()	返回最小（第一）元素	元素	O(log n)	可通过缓存叶子节点优化到 O(1)
E last()	返回最大（最后）元素	元素	O(log n)	同上
E lower(E e)	返回小于 e的最大元素	若无返回 null	O(log n)
E floor(E e)	返回 ≤e的最大元素	若无返回 null	O(log n)
E ceiling(E e)	返回 ≥e的最小元素	若无返回 null	O(log n)
E higher(E e)	返回大于 e的最小元素	若无返回 null	O(log n)
SortedSet<E> subSet(E fromElement, E toElement)	返回 [fromElement, toElement)范围视图	视图对象	O(log n)	视图中操作会映射回原集合
SortedSet<E> headSet(E toElement)	返回 < toElement范围视图	视图对象	O(log n)
SortedSet<E> tailSet(E fromElement)	返回 ≥ fromElement范围视图	视图对象	O(log n)
Comparator<? super E> comparator()	返回用于排序的比较器；若为 null则使用自然顺序	比较器或 null	O(1)

• 定制排序 ：如果不想（或不能）让类本身实现 Comparable，也可以在构造 TreeSet 时传入一个 Comparator：

Comparator<MyType> cmp = Comparator.comparing(/* keyExtractor */);
TreeSet<MyType> ts = new TreeSet<>(cmp);

• （强烈建议）保持 compareTo/Comparator 与 equals 一致性