HashSet

HashSet 表示一个无序的唯一值集合，具有高效的查找、插入和删除操作。

Effect 库提供了此结构的两个版本：

• HashSet - 不可变
• MutableHashSet - 可变

两个版本平均都提供常数时间操作。主要区别在于它们如何处理更改：一个返回新集合，另一个修改原始集合。

为什么使用 HashSet？

HashSet 解决了维护每个值只出现一次的无序集合的问题，并提供了检查成员资格和添加/删除值的快速操作。

一些常见的用例包括：

• 跟踪唯一项目（例如，完成某个操作的用户）
• 高效测试集合中的成员资格
• 执行集合操作，如并集、交集和差集
• 从集合中消除重复项

何时使用 HashSet 而不是其他集合

在以下情况下选择 HashSet（任一变体）而不是其他集合：

• 您需要确保元素是唯一的
• 您经常需要检查元素是否存在于集合中
• 您需要执行集合操作，如并集、交集和差集
• 元素的顺序对您的用例不重要

在以下情况下选择其他集合：

• 您需要维护插入顺序（使用 List 或 Array）
• 您需要键值关联（使用 HashMap 或 MutableHashMap）
• 您需要频繁按索引访问元素（使用 Array）

在不可变和可变变体之间选择

Effect 提供不可变和可变版本以支持不同的编码风格和性能需求。

HashSet

此版本从不修改原始集合。相反，它为每次更改返回一个新集合。

特征：

• 操作返回新实例而不是修改原始实例
• 保留先前状态
• 设计上线程安全
• 适用于函数式编程模式
• 适合在应用程序的不同部分之间共享

MutableHashSet

此版本允许直接更新：添加和删除值会就地更改集合。

特征：

• 操作直接修改原始集合
• 在增量构建集合时更高效
• 需要小心处理以避免意外的副作用
• 在有许多修改的场景中性能更好
• 适用于变更不会在其他地方引起问题的局部使用

何时使用每个变体

在以下情况下使用 HashSet：

• 您需要没有副作用的可预测行为
• 您想要保留数据的先前状态
• 您在应用程序的不同部分之间共享集合
• 您偏好函数式编程模式
• 您在并发环境中需要纤程安全

在以下情况下使用 MutableHashSet：

• 性能至关重要，您需要避免创建新实例
• 您正在通过许多添加/删除操作增量构建集合
• 您在受控范围内工作，变更是安全的
• 您需要在性能关键代码中优化内存使用

混合方法

您可以使用 HashSet.mutate 在临时可变上下文中对 HashSet 应用多个更新。这允许您一次执行多个更改而不修改原始集合。

示例（批量更改而不变更原始集合）

import { HashSet } from "effect"

// 创建一个不可变的 HashSet
const original = HashSet.make(1, 2, 3)

// 在临时可变草稿内应用多个更新
const modified = HashSet.mutate(original, (draft) => {
  HashSet.add(draft, 4)
  HashSet.add(draft, 5)
  HashSet.remove(draft, 1)
})

console.log(HashSet.toValues(original))
// 输出: [1, 2, 3] - 原始集合保持不变

console.log(HashSet.toValues(modified))
// 输出: [2, 3, 4, 5] - 更改应用到新版本

性能特征

HashSet 和 MutableHashSet 都为核心操作提供类似的平均时间性能：

操作	HashSet	MutableHashSet	描述
查找	O(1) 平均	O(1) 平均	检查值是否存在
插入	O(1) 平均	O(1) 平均	添加值
删除	O(1) 平均	O(1) 平均	删除值
迭代	O(n)	O(n)	迭代所有值
集合操作	O(n)	O(n)	并集、交集、差集

主要区别在于如何处理更新：

• HashSet 为每次更改返回一个新集合。如果连续进行许多更改，这可能会较慢。
• MutableHashSet 就地更新同一个集合。在执行许多更改时，这通常更快。

等价性和唯一性

HashSet 和 MutableHashSet 都使用 Effect 的 Equal 特征来确定两个元素是否相同。这确保每个值在集合中只出现一次。

• 原始值（如数字或字符串）按值比较，类似于 === 操作符。
• 对象和自定义类型必须实现 Equal 接口来定义两个实例相等的含义。如果没有提供实现，等价性会回退到引用比较。

示例（使用自定义等价性和哈希）

import { Equal, Hash, HashSet } from "effect"

// 定义一个实现 Equal 接口的自定义类
class Person implements Equal.Equal {
  constructor(
    readonly id: number,
    readonly name: string,
    readonly age: number
  ) {}

  // 如果两个 Person 实例的 id、name 和 age 匹配，则它们相等
  [Equal.symbol](that: Equal.Equal): boolean {
    if (that instanceof Person) {
      return (
        Equal.equals(this.id, that.id) &&
        Equal.equals(this.name, that.name) &&
        Equal.equals(this.age, that.age)
      )
    }
    return false
  }

  // 哈希码基于 id（必须与等价逻辑匹配）
  [Hash.symbol](): number {
    return Hash.hash(this.id)
  }
}

// 添加两个具有相同内容的不同实例
const set = HashSet.empty().pipe(
  HashSet.add(new Person(1, "Alice", 30)),
  HashSet.add(new Person(1, "Alice", 30))
)

// 只保留一个实例
console.log(HashSet.size(set))
// 输出: 1

使用 Data 和 Schema 简化等价性

Effect 的 Data 和 Schema.Data 模块基于结构等价性自动为您实现 Equal。

示例（使用 Data.struct）

import { Data, Equal, HashSet, pipe } from "effect"

// 定义两个具有相同内容的记录
const person1 = Data.struct({ id: 1, name: "Alice", age: 30 })
const person2 = Data.struct({ id: 1, name: "Alice", age: 30 })

// 它们是不同的对象引用
console.log(Object.is(person1, person2))
// 输出: false

// 但它们在值上相等（基于内容）
console.log(Equal.equals(person1, person2))
// 输出: true

// 将两者都添加到 HashSet — 只会存储一个
const set = pipe(
  HashSet.empty(),
  HashSet.add(person1),
  HashSet.add(person2)
)

console.log(HashSet.size(set))
// 输出: 1

示例（使用 Schema.Data）

import { Equal, MutableHashSet, Schema } from "effect"

// 定义一个描述 Person 结构的 schema
const PersonSchema = Schema.Data(
  Schema.Struct({
    id: Schema.Number,
    name: Schema.String,
    age: Schema.Number
  })
)

// 从普通对象解码值
const Person = Schema.decodeSync(PersonSchema)

const person1 = Person({ id: 1, name: "Alice", age: 30 })
const person2 = Person({ id: 1, name: "Alice", age: 30 })

// person1 和 person2 是不同的实例但在值上相等
console.log(Equal.equals(person1, person2))
// 输出: true

// 将两者都添加到 MutableHashSet — 只会存储一个
const set = MutableHashSet.empty().pipe(
  MutableHashSet.add(person1),
  MutableHashSet.add(person2)
)

console.log(MutableHashSet.size(set))
// 输出: 1

HashSet

HashSet<A> 是一个不可变、无序的唯一值集合。 它保证每个值只出现一次，并支持查找、插入和删除等快速操作。

任何会修改集合的操作（如添加或删除值）都会返回一个新的 HashSet，保持原始集合不变。

操作

类别	操作	描述	时间复杂度
构造器	empty	创建空的 HashSet	O(1)
构造器	fromIterable	从可迭代对象创建 HashSet	O(n)
构造器	make	从多个值创建 HashSet	O(n)
元素	has	检查值是否存在于集合中	O(1) 平均
元素	some	检查是否有元素满足谓词	O(n)
元素	every	检查是否所有元素满足谓词	O(n)
元素	isSubset	检查集合是否为另一个的子集	O(n)
获取器	values	获取所有值的 Iterator	O(1)
获取器	toValues	获取所有值的 Array	O(n)
获取器	size	获取元素数量	O(1)
变更	add	向集合添加值	O(1) 平均
变更	remove	从集合中删除值	O(1) 平均
变更	toggle	切换值的存在状态	O(1) 平均
操作	difference	计算集合差集 (A - B)	O(n)
操作	intersection	计算集合交集 (A ∩ B)	O(n)
操作	union	计算集合并集 (A ∪ B)	O(n)
映射	map	转换每个元素	O(n)
序列化	flatMap	转换并展平元素	O(n)
遍历	forEach	对每个元素应用函数	O(n)
折叠	reduce	将集合归约为单个值	O(n)
过滤	filter	保留满足谓词的元素	O(n)
分区	partition	按谓词将集合分为两个	O(n)

示例（基本创建和操作）

import { HashSet } from "effect"

// 创建一个包含 3 个值的初始集合
const set1 = HashSet.make(1, 2, 3)

// 添加一个值（返回新集合）
const set2 = HashSet.add(set1, 4)

// 原始集合保持不变
console.log(HashSet.toValues(set1))
// 输出: [1, 2, 3]

console.log(HashSet.toValues(set2))
// 输出: [1, 2, 3, 4]

// 与另一个集合执行集合操作
const set3 = HashSet.make(3, 4, 5)

// 合并两个集合
const union = HashSet.union(set2, set3)

console.log(HashSet.toValues(union))
// 输出: [1, 2, 3, 4, 5]

// 共享值
const intersection = HashSet.intersection(set2, set3)

console.log(HashSet.toValues(intersection))
// 输出: [3, 4]

// 仅在 set2 中的值
const difference = HashSet.difference(set2, set3)

console.log(HashSet.toValues(difference))
// 输出: [1, 2]

示例（使用 pipe 链式操作）

import { HashSet, pipe } from "effect"

const result = pipe(
  // 重复项被忽略
  HashSet.make(1, 2, 2, 3, 4, 5, 5),
  // 保留偶数
  HashSet.filter((n) => n % 2 === 0),
  // 将每个值翻倍
  HashSet.map((n) => n * 2),
  // 转换为数组
  HashSet.toValues
)

console.log(result)
// 输出: [4, 8]

MutableHashSet

MutableHashSet<A> 是一个可变、无序的唯一值集合。 与 HashSet 不同，它允许直接修改，add、remove 和 clear 等操作会更新原始集合而不是返回新集合。

当您需要重复构建或更新集合时，这种可变性可以提高性能，特别是在局部或隔离的范围内。

操作

类别	操作	描述	复杂度
构造器	empty	创建空的 MutableHashSet	O(1)
构造器	fromIterable	从可迭代对象创建集合	O(n)
构造器	make	从多个值创建集合	O(n)
元素	has	检查值是否存在于集合中	O(1) 平均
元素	add	向集合添加值	O(1) 平均
元素	remove	从集合中删除值	O(1) 平均
获取器	size	获取元素数量	O(1)
变更	clear	从集合中删除所有值	O(1)

示例（使用可变集合）

import { MutableHashSet } from "effect"

// 创建一个带有初始值的可变集合
const set = MutableHashSet.make(1, 2, 3)

// 添加新元素（就地更新集合）
MutableHashSet.add(set, 4)

// 检查当前内容
console.log([...set])
// 输出: [1, 2, 3, 4]

// 删除元素（就地修改）
MutableHashSet.remove(set, 1)

console.log([...set])
// 输出: [2, 3, 4]

// 完全清空集合
MutableHashSet.clear(set)

console.log(MutableHashSet.size(set))
// 输出: 0

与 JavaScript 的互操作性

HashSet 和 MutableHashSet 都实现了 Iterable 接口，因此您可以将它们与 JavaScript 功能一起使用，例如：

• 展开操作符 (...)
• for...of 循环
• Array.from

您还可以使用 .toValues 将值提取为数组。

示例（以 JS 原生方式使用 HashSet 值）

import { HashSet, MutableHashSet } from "effect"

// 不可变 HashSet
const hashSet = HashSet.make(1, 2, 3)

// 可变变体
const mutableSet = MutableHashSet.make(4, 5, 6)

// 将 HashSet 转换为迭代器
//
//      ┌─── IterableIterator<number>
//      ▼
const iterable = HashSet.values(hashSet)

// 展开到 console.log
console.log(...iterable)
// 输出: 1 2 3

// 在 for...of 循环中使用
for (const value of mutableSet) {
  console.log(value)
}
// 输出: 4 5 6

// 使用 Array.from 转换为数组
console.log(Array.from(mutableSet))
// 输出: [ 4, 5, 6 ]

// 使用 toValues 将不可变 HashSet 转换为数组
//
//      ┌─── Array<number>
//      ▼
const array = HashSet.toValues(hashSet)

console.log(array)
// 输出: [ 1, 2, 3 ]

性能注意事项

避免在热路径或大型集合中重复在 HashSet 和 JavaScript 数组之间转换。这些操作涉及复制数据，可能会影响内存和速度。