深入解析 Cangjie std.collection 之 HashSet\＜T＞：基于 HashMap 的高效哈希集合实战指南

• 人工智能
• AI 技能
• 文档
• 开发工具

HashSet 是 Cangjie 标准库std.collection中基于哈希表实现的集合数据结构，提供无序存储与自动去重能力，其插入、删除、查找均具备较高的时间效率，适合需要快速判断"元素是否存在"以及维护唯一性集合的场景。本文以 HashSet 类文档 为主体，结合包内 API 文档、接口定义 与 可运行示例，系统讲解 HashSet 的构造方式、全部成员函数、运算符重载与实战用法，读完即可在 Cangjie 项目中正确、高效地使用 HashSet。

一、HashSet 是什么：基于 HashMap 实现的 Set 实例

在 std.collection 包 中，HashSet 的类声明如下（见 collection_package_class.md）：

public class HashSet<T> <: Set<T> where T <: Hashable & Equatable<T> { public init() public init(elements: Collection<T>) public init(elements: Array<T>) public init(capacity: Int64) public init(size: Int64, initElement: (Int64) -> T) }

围绕该声明，有几点关键语义需要理解：

• 基于 HashMap 实现：HashSet 是 Set<T> 接口的实例，其内部直接复用 HashMap 的存储机制。官方文档明确指出，HashSet 的容量、内存布局、时间性能都和 HashMap 相同。也就是说，理解 HashMap 的哈希表行为，就等于理解了 HashSet 的底层运行原理。
• 元素无序：HashSet 中的元素没有固定顺序，不可以通过索引访问，也不保证元素的插入顺序。这是因为元素在哈希表中的位置由元素的哈希值决定，而非插入先后。
• 不允许重复元素：向 HashSet 中添加元素时，集合会根据元素的哈希值定位其在哈希表中的位置；若元素已存在，则添加失败，从而保证唯一性。
• 类型约束：泛型参数T必须同时满足Hashable（可哈希）与Equatable<T>（可判等）两个约束。其中Hashable用于计算哈希值、确定存储位置，Equatable<T>用于在哈希冲突时判断元素是否真正相等。这是使用 HashSet 前必须满足的前提条件。

从接口继承关系看，Set<T>继承自 ReadOnlySet<T>，后者只提供contains、subsetOf等只读操作，而Set<T>在只读基础上追加了add、remove、removeIf、clear、retain等可写操作（见 collection_package_interface.md）。

注意：与std.collection中其他集合类型一样，HashSet 不支持并发安全。若需要并发场景下的集合，应使用 collection.concurrent 包 提供的类型（见 collection_package_overview.md）。

二、构造 HashSet：五种构造函数详解

HashSet 共提供 5 种构造函数（见 HashSet 类文档），覆盖"空集合、指定容量、由数组/集合导入、函数批量初始化"等常见场景：

各构造函数的细节与约束（见 collection_package_class.md）：

• init()：构造空的 HashSet，初始容量为 16。这是最常用的构造方式，适合无法预估元素数量的场景，之后可通过add动态插入元素。
• init(capacity: Int64)：按指定容量预分配内部数组。若capacity小于 0，会抛出 IllegalArgumentException（见 init(Int64)）。预先指定合理容量可减少后续扩容带来的开销。
• init(elements: Array<T>)/init(elements: Collection<T>)：将已有数组或集合中的元素一次性装入新 HashSet，容量由入参的size决定；过程中自动完成去重。
• init(size: Int64, initElement: (Int64) -> T)：通过一个下标到元素的映射函数批量生成元素，size为元素个数，initElement为初始化函数规则。若size小于 0，同样抛出IllegalArgumentException。适合按规则生成一组连续数据的场景，例如(i) => i快速生成 0..N-1 的整数集合。

容量 vs 元素个数：HashSet 提供了capacity与size两个属性，其中capacity返回内部数组的容量大小，size返回实际元素个数。文档特别提醒：容量大小不一定等于 size。哈希表为了降低冲突概率，通常会让容量大于已存元素数量。

三、核心成员函数：完整 API 与参数说明

HashSet 的全部成员函数如下（原型与说明取自 HashSet 类文档，异常与返回值细节见 collection_package_class.md）：

3.1 元素定位与判等：contains / add / remove

contains(element: T)判断集合是否包含指定元素，是哈希集合最核心的查询能力——得益于哈希表结构，该操作的平均时间复杂度较低，无需遍历全部元素。add与remove都返回Bool表示操作是否真正生效：

• add返回true表示新元素成功加入；若元素已存在，返回false且集合不变（见 func add(T)）。
• remove返回true表示移除成功；元素不存在时返回false（见 func remove(T)）。

3.2 批量操作：add(Collection) / remove(Collection) / retain

• add(all!: Collection<T>)：将集合中所有元素并入当前 HashSet，重复元素自动跳过。
• remove(all!: Collection<T>)：删除当前 HashSet 中那些同样出现在给定 Collection 里的元素，等价于"差集"的原地版本。
• retain(all!: Set<T>)：保留当前 HashSet 与给定 Set 的交集部分，其余元素全部删除（见func retain(Set )）。

3.3 条件删除：removeIf 与并发修改异常

removeIf(predicate: (T) -> Bool)接受一个 lambda 判断条件，凡是满足true的元素都会被删除，非常适合按规则批量清理数据，例如删除所有偶数或空字符串。

需要特别注意的是：当predicate内部对 HashSet 本身执行了增、删、改操作时，会抛出 ConcurrentModificationException（见 func removeIf((T) -> Bool)）。也就是说，谓词函数只能做"判断"而不能顺带修改集合，否则遍历与修改并发进行会破坏迭代状态。

3.4 扩容策略：reserve 的完整规则

reserve(additional: Int64)用于预先扩容，其完整决策规则如下（见 func reserve(Int64)）：

1. 当additional小于等于零时，不发生扩容；
2. 当 HashSet 的剩余容量大于等于additional时，不发生扩容（容量充足则无需动作）；
3. 当 HashSet 的剩余容量小于additional时，取（原始容量的 1.5 倍向下取整）与（additional + 已使用容量）中的最大值进行扩容。

此外，若additional + 已使用容量超过Int64.Max，会抛出 OverflowException。对于能够预估元素数量的场景，提前调用reserve或使用指定容量的构造函数，可以避免插入过程中反复触发扩容，从而提升批量写入性能。

3.5 其他常用能力：clone / clear / toArray / isEmpty / iterator / subsetOf

• clone()：返回一个内容相同但彼此独立的新 HashSet，修改克隆体不影响原集合。
• clear()：清空全部元素，集合变为空。
• toArray()：将集合内所有元素拷贝到Array<T>返回，便于与数组 API 交互。
• isEmpty()：判断集合是否为空，等价于size == 0。
• iterator()：返回Iterator<T>，用于遍历集合。由于集合无序，遍历顺序不代表插入顺序。
• subsetOf(other: ReadOnlySet<T>)：判断当前集合是否为other的子集，即当前集合的每个元素都出现在other中时返回true。

四、运算符重载与扩展接口：集合运算一步到位

HashSet 不仅提供方法形式的操作，还通过运算符重载支持直观的集合代数运算（见 HashSet 类文档 与 collection_package_class.md）：

三者都接受任意ReadOnlySet<T>（包括 HashSet、TreeSet 等），并返回一个新的HashSet<T>，不修改参与运算的原始集合。例如setA & setB得到两者公共元素组成的新集合。

同时，HashSet 通过两个扩展接口获得额外能力：

• extend<T> HashSet<T> <: Equatable<HashSet<T>>：为 HashSet 扩展 Equatable 接口，提供==与!=运算符：
  • operator func ==(that: HashSet<T>): Bool：判断两个 HashSet 是否相等。两个 HashSet 相等指的是其中包含的元素完全相等，与插入顺序、内部布局无关（见 operator func ==）。
  • operator func !=(that: HashSet<T>): Bool：判不等，逻辑上等价于!(this == that)。
• extend<T> HashSet<T> <: ToString where T <: ToString：当元素类型T实现 ToString 接口时，HashSet 可转换为字符串，提供toString(): String成员。转换结果形如"[elem1, elem2, elem3]"，即方括号包裹、逗号分隔的格式，便于调试输出与日志打印（见 func toString()）。

五、实战：add / iterator / remove 完整示例

以下示例取自 sample_hashset_add_iterator_remove.md，展示 HashSet 最基本的"添加—遍历—删除"完整流程：

import std.collection.* /* 测试 */ main() { var set: HashSet<String> = HashSet<String>() // set: [] set.add("apple") // set: ["apple"] set.add("banana") // set: ["apple", "banana"], not in order set.add("orange") // set: ["apple", "banana", "orange"], not in order set.add("peach") // set: ["apple", "banana", "orange", "peach"], not in order var itset = set.iterator() while(true) { var value = itset.next() match(value) { case Some(v) => if (!set.contains(v)) { print("Operation failed") return 1 } else { println(v) } case None => break } } set.remove("apple") // set: ["banana", "orange", "peach"], not in order println(set) return 0 }

该示例值得注意的细节：

1. 去重验证：代码在遍历时对每个元素调用contains(v)反向校验，确保迭代器取出的元素确实存在于集合中，这是对哈希集合"增删一致性"的典型自检写法。
2. 迭代器语义：itset.next()返回Option<T>，用match匹配Some(v)/None分别处理"取到元素"与"遍历结束"，None时break退出循环。这是 Cangjie 中迭代Iterator<T>的标准模式。
3. 无序性：由于 Set 中的顺序不固定，运行结果可能如下（见原示例）：

apple banana orange peach [banana, orange, peach]

注意移除"apple"后打印集合，得到的是[banana, orange, peach]而非按插入顺序排列的内容，再次印证 HashSet 不保证顺序。

六、关联能力与选型建议

6.1 迭代器转换：collectHashSet

std.collection提供了便捷的转换函数 collectHashSet<T>(Iterable<T>)，可将任意迭代器直接转换成 HashSet：

public func collectHashSet<T>(it: Iterable<T>): HashSet<T> where T <: Hashable & Equatable<T>

传入实现了Iterable<T>的对象（如数组、ArrayList、另一个集合的迭代器），即可得到去重后的 HashSet。这在"对一批数据去重并建立快速查找集合"的场景中非常实用。

6.2 与 TreeSet 的选型对比

同为集合去重结构，HashSet 与 TreeSet 的区别本质在于底层实现与排序特性（见 collection_package_overview.md）：

若只关心"是否存在、是否唯一、插入删除快"，选 HashSet；若需要按自然顺序或自定义顺序遍历元素，则选 TreeSet。

6.3 使用注意事项小结

• 元素类型必须同时实现Hashable与Equatable<T>，否则无法编译；
• 集合无序且不支持索引访问，依赖顺序的算法请先toArray()后自行排序，或改用 TreeSet；
• 非并发安全，多线程共享同一 HashSet 时需要外部同步，或改用collection.concurrent包；
• removeIf的谓词内禁止修改集合本身，否则抛出ConcurrentModificationException；
• 预估到元素规模较大时，优先使用指定容量构造或reserve预扩容，减少哈希表重建开销。

结语

HashSet 是 Cangjiestd.collection中兼顾去重与查询效率的核心容器：它复用了 HashMap 的哈希表机制，以"无序 + 唯一"的语义覆盖了成员判断、批量去重、集合代数运算等高频需求，并通过运算符重载（&、|、-）与扩展接口（==、!=、toString）提供了接近原生语法的体验。掌握本文所述的构造方式、容量与扩容规则、迭代与条件删除的边界约束，即可在实战中正确驾驭这一数据结构。

• 人工智能
• AI 技能
• 文档
• 开发工具