WOLFRAM

Wolfram 语言与系统参考资料中心

"HashSet" （数据结构）

"HashSet"

表示一个集合，其中的成员为普通表达式，成员资格则是用哈希函数计算的.

更多信息

  • 哈希集合适用于存储一组唯一元素，并能提供高效的成员测试、插入和删除操作.
  • CreateDataStructure["HashSet"]创建新的空 "HashSet"
    CreateDataStructure["HashSet",elems]创建一个包含 elems 的新 "HashSet"
    Typed[x,"HashSet"]指定 x 的类型为 "HashSet"
  • 对于类型为 "HashSet" 的数据结构，可进行以下操作：
  • ds["Complement",list]从 ds 中删除出现在 list 中的元素用时：O(n)
    ds["Copy"]返回 ds 的副本用时：O(n)
    ds["Elements"]返回 ds 中的参数列表用时：O(n)
    ds["EmptyQ"]如果 ds 中没有元素则返回 True用时：O(1)
    ds["Delete",x]从 ds 中删除 x，如果 x 是元素，返回 True 用时：O(1)
    ds["DeleteAll"]删除 ds 的所有元素用时：O(n)
    ds["Insert",x]将 x 添加到集合中，如果插入成功则返回 True用时：O(1)
    ds["Intersection",list]从 ds 中删除没有出现在 list 中的元素用时: O(n)
    ds["Length"]返回存储在 ds 中的元素的数量用时: O(1)
    ds["MemberQ",x]如果 x 是 ds 的元素则返回 True用时: O(1)
    ds["Pop"]从 ds 删除一个参数并复原用时: O(1)
    ds["SubsetQ",ds1]如果哈希集合 ds1 是 ds 的子集，则返回 True 用时: O(n)
    ds["Union",list]将 list 中出现的元素添加到 ds 中用时: O(n)
    ds["Visualization"]返回 ds 的可视化用时: O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds
    InputForm[ds]ds 的输入形式
    Length[ds]ds 的长度
    Normal[ds]将 ds 转换成普通表达式

范例

打开所有单元 关闭所有单元

基本范例  (2)

可用 CreateDataStructure 创建新的 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet"]

向集合中插入一个元素：

Wolfram Language code: ds["Insert", f[1]]

集合中有一个元素：

Wolfram Language code: ds["Length"]

测试是否存储的是表达式：

Wolfram Language code: ds["MemberQ", f[1]]

如果存储的不是表达式，则返回 False：

Wolfram Language code: ds["MemberQ", f[2]]

从集合中移除一个元素，如果元素被成功移除则返回 True：

Wolfram Language code: ds["Delete", f[1]]

返回表达式形式的 ds：

Wolfram Language code: Normal[ds]

快速插入元素：

Wolfram Language code: ds = CreateDataStructure["HashSet"]; Do[ds["Insert", i], {i, 1000}]

可视化数据结构：

Wolfram Language code: ds["Visualization"]

范围  (17)

信息  (1)

可用 CreateDataStructure 创建新的 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet"]

数据结构 ds 的信息：

Wolfram Language code: Information[ds]

创建  (2)

创建一个空的 "HashSet"：

Wolfram Language code: CreateDataStructure["HashSet"]

用初始元素创建 "HashSet"：

Wolfram Language code: CreateDataStructure["HashSet", {x, y, z}]

运算  (14)

"Complement"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[100]]

创建一个新集合，其元素属于原 "HashSet" 但不属于给定列表：

Wolfram Language code: ds1 = ds["Complement", Range[50]]

检验新哈希集合的元素：

Wolfram Language code: ds1["Elements"]

"Copy"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[4]]

复制该集合：

Wolfram Language code: ds1 = ds["Copy"]

两个数组的内容是相同的：

Wolfram Language code: {Normal[ds], Normal[ds1]}

修改副本不会影响原始集合：

Wolfram Language code: ds1["Insert", 42]; {Normal[ds], Normal[ds1]}

"Elements"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[10]]

以列表显示给出内容：

Wolfram Language code: ds["Elements"]

Normal 返回同样的列表：

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

测试一个 "HashSet" 是否为空：

Wolfram Language code: ds = CreateDataStructure["HashSet"]; ds["EmptyQ"]

插入元素后，集合不再为空：

Wolfram Language code: ds["Insert", f[x]]; ds["EmptyQ"]

"Delete"  (1)

从 "HashSet" 中删除一个元素，如果删除成功则返回 True：

Wolfram Language code: ds = CreateDataStructure["HashSet", {f[x], f[y], f[z]}]; ds["Delete", f[x]]

不可能删除集合中不存在的元素，因此返回 False：

Wolfram Language code: ds["Delete", f[w]]

"DeleteAll"  (1)

删除 "HashSet" 中的所有元素：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[300]]; ds["DeleteAll"]

集合现在为空：

Wolfram Language code: ds["EmptyQ"]

"Insert"  (1)

向 "HashSet" 中插入一个元素，如果插入成功则返回 True：

Wolfram Language code: ds = CreateDataStructure["HashSet"]; ds["Insert", f[x]]

由于无法再次插入相同元素，因此返回 False：

Wolfram Language code: ds["Insert", f[x]]

"Intersection"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[100]]

创建一个新的集合，仅包含原始 "HashSet" 与给定列表中共有的元素：

Wolfram Language code: ds1 = ds["Intersection", Range[50]]

查看新哈希集合的元素：

Wolfram Language code: ds1["Elements"]

"Length"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[100]]

获取集合中元素的数量：

Wolfram Language code: ds["Length"]

Length 给出同样的结果：

Wolfram Language code: Length[ds]

"MemberQ"  (1)

测试一个元素是否存在于 "HashSet" 中：

Wolfram Language code: ds = CreateDataStructure["HashSet", {f[x], f[y], f[z]}]; {ds["MemberQ", f[x]], ds["MemberQ", f[w]]}

"Pop"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", {f[x], f[y], f[z]}]; ds["Elements"]

删除集合中的元素：

Wolfram Language code: ds["Pop"]

"SubsetQ"  (1)

测试一个集合的所有元素是否都包含在另一个集合中：

Wolfram Language code: ds1 = CreateDataStructure["HashSet", {1, 3, 5}]; ds2 = CreateDataStructure["HashSet", {1, 2, 3, 4, 5}]; ds1["SubsetQ", ds2]

检查较小的集合是否为较大集合的子集：

Wolfram Language code: ds2["SubsetQ", ds1]

"Union"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[10]]

创建一个新的集合，其中包含原始 "HashSet" 与给定列表中均存在的元素：

Wolfram Language code: ds1 = ds["Union", Range[10, 20]]

查看新哈希集合的元素：

Wolfram Language code: ds1["Elements"]

"Visualization"  (1)

用初始元素创建 "HashSet"：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[300]]

可视化哈希集合的内容：

Wolfram Language code: ds["Visualization"]

应用  (2)

多组字符串  (1)

内置集合运算非常适合处理机器数组成的矩形数组. 数据结构运算非常适合处理多组诸如字符串之类的非数字数据. 创建 1000000 个由字符串组成的列表：

Wolfram Language code: list1 = Table[ StringJoin[RandomChoice[ {"A", "B", "C"}, 4]], 1000000];
Wolfram Language code: ds = CreateDataStructure["HashSet"]; ds["Union", list1];//AbsoluteTiming
Wolfram Language code: Union[list1];//AbsoluteTiming

类似的例子则显示出 "Complement" 的优势：

Wolfram Language code: list1 = Table[ StringJoin[ RandomChoice[ {"A", "B", "C"}, 10]], 100000]; listC = Table[ StringJoin[{"A", RandomChoice[ {"A", "B", "C"}, 9]}], 50];
Wolfram Language code: ds = CreateDataStructure["HashSet"]; ds["Union", list1];//AbsoluteTiming
Wolfram Language code: listI = Union[list1];//AbsoluteTiming
Wolfram Language code: ds["Complement", listC];//AbsoluteTiming
Wolfram Language code: Complement[listI, listC];//AbsoluteTiming

在图中检测环  (1)

用 "HashSet" 在深度优先搜索遍历过程中跟踪已访问的节点，检测有向图是否包含环：

Wolfram Language code: hasCycle[graph_ ? GraphQ] := Module[{ visited = CreateDataStructure["HashSet"], recursionStack = CreateDataStructure["HashSet"], dfs}, dfs[node_] := If[!visited["MemberQ", node], visited["Insert", node]; recursionStack["Insert", node]; Do[ If[recursionStack["MemberQ", neighbor], Return[True, Module] , dfs[neighbor] ], {neighbor, VertexOutComponent[graph, node, {1}]} ]; recursionStack["Delete", node]; ]; Scan[dfs, VertexList[graph]]; False ]

检查下图是否含有非自环：

Wolfram Language code: hasCycle /@ {[image], [image], [image]}

属性和关系  (5)

InputForm  (1)

InputForm 返回 "HashSet" 的序列化内容：

Wolfram Language code: InputForm[CreateDataStructure["HashSet", Range[10]]]

该序列化形式可用于重建数据结构：

Wolfram Language code: DataStructure["HashSet", {"Data" -> {3, 4, 2, 1, 7, 6, 10, 9, 5, 8}}]

Length  (1)

Length 可用于获取 "HashSet" 中元素的数量：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[10]]; Length[ds]

用 "Length" 运算可得到同样的结果：

Wolfram Language code: ds["Length"]

Normal  (1)

Normal 可用于获取 "HashSet" 中的元素：

Wolfram Language code: ds = CreateDataStructure["HashSet", Range[10]]; Normal[ds]

用 "Elements" 运算可得到同样的结果：

Wolfram Language code: ds["Elements"]

SameQ  (1)

SameQ 可用于测试两个哈希集合是否包含相同的元素，与顺序无关：

Wolfram Language code: ds1 = CreateDataStructure["HashSet", Range[10]]; ds2 = CreateDataStructure["HashSet", Reverse@Range[10]]; ds1 === ds2

如果移除其中一个元素，则集合就不再相同：

Wolfram Language code: ds1["Pop"]; ds1 === ds2

"OrderedHashSet"  (1)

许多适用于 "OrderedHashSet" 的算法也适用于 "HashSet".

与 "OrderedHashSet" 不同，插入到 "HashSet" 中的元素顺序不会被保留.

巧妙范例  (1)

计算 GCD  (1)

找到两个因子集合的交集有助于找到最大的公因子：

Wolfram Language code: ds = CreateDataStructure["HashSet", Divisors[45]]; ds["Intersection", Divisors[78]]//Normal

最大值为 3：

Wolfram Language code: Max[%]

该结果即为 GCD：

Wolfram Language code: GCD[45, 78]