WOLFRAM

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

"OrderedHashSet" （数据结构）

"OrderedHashSet"

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

更多信息

  • 有序哈希集可在保留插入顺序很重要的情况下高效插入和删除以及进行成员测试：
  • CreateDataStructure["OrderedHashSet"]创建新的空 "OrderedHashSet"
    CreateDataStructure["OrderedHashSet",elems]创建一个包含 elems 的新 "OrderedHashSet"
    Typed[x,"OrderedHashSet"]指定 x 的类型为 "OrderedHashSet"
  • 对于类型为 "OrderedHashSet" 的数据结构，可进行以下操作：
  • 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["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 创建新的 "OrderedHashSet"：

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

插入集合中：

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["OrderedHashSet"]; Do[ds["Insert", i], {i, 100}]

可视化数据结构：

Wolfram Language code: ds["Visualization"]

保留插入元素的顺序：

Wolfram Language code: ds["Elements"]

范围  (16)

创建  (2)

创建一个空的 "OrderedHashSet"：

Wolfram Language code: CreateDataStructure["OrderedHashSet"]

创建一个带有初始元素的 "OrderedHashSet"：

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

信息  (1)

可用 CreateDataStructure 创建新的 "OrderedHashSet"：

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

关于数据结构 ds 的信息：

Wolfram Language code: Information[ds]

操作  (13)

"Complement"  (1)

创建一个带有初始元素的 "OrderedHashSet"：

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

创建一个新的集合，其中包含存在于原始 "OrderedHashSet" 中但不在给定列表中的元素：

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

验证新有序哈希集合中的元素：

Wolfram Language code: ds1["Elements"]

"Copy"  (1)

创建一个带有初始元素的 "OrderedHashSet"：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", 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)

创建一个带有初始元素的 "OrderedHashSet"：

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

将内容以列表形式返回：

Wolfram Language code: ds["Elements"]

Normal 返回相同的列表：

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

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

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

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

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

"Delete"  (1)

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

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

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

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

"DeleteAll"  (1)

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

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

该集合现在为空：

Wolfram Language code: ds["EmptyQ"]

"Insert"  (1)

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

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

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

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

"Intersection"  (1)

创建一个带有初始元素的 "OrderedHashSet"：

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

创建一个新集合，其中仅包含原始 "OrderedHashSet" 和给定列表中共同的元素：

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

验证新有序哈希集合中的元素：

Wolfram Language code: ds1["Elements"]

"Length"  (1)

创建一个带有初始元素的 "OrderedHashSet"：

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

获取集合中元素的数量：

Wolfram Language code: ds["Length"]

Length 给出相同的值：

Wolfram Language code: Length[ds]

"MemberQ"  (1)

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

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

"Pop"  (1)

创建一个带有初始元素的 "OrderedHashSet"：

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

移除集合中的一个元素：

Wolfram Language code: ds["Pop"]

"Union"  (1)

创建一个带有初始元素的 "OrderedHashSet"：

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

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

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

验证新哈希集合中的元素：

Wolfram Language code: ds1["Elements"]

"Visualization"  (1)

创建一个带有初始元素的 "OrderedHashSet"：

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

可视化哈希集合的内容：

Wolfram Language code: ds["Visualization"]

应用  (2)

稳定去重  (1)

创建一个随机元素列表：

Wolfram Language code: list = RandomChoice[{"A", "B", "C", "D"}, 20]

从列表中移除重复元素，同时保留首次出现的顺序：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; ds["Union", list];

获取集合中的元素：

Wolfram Language code: ds["Elements"]

与 DeleteDuplicates 进行比较：

Wolfram Language code: DeleteDuplicates[list]

有序共同元素  (1)

找出两个集合中的共同元素，同时保留第一个集合的顺序：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {a, b, c, d, e}]; ds["Intersection", {e, c, a, f}]//Normal

属性和关系  (5)

InputForm  (1)

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

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

此序列化形式可用于重新创建数据结构：

Wolfram Language code: DataStructure["OrderedHashSet", {"Data" -> Range[10]}]

Length  (1)

可以使用 Length 获取 "OrderedHashSet" 中的元素数量：

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

使用 "Length" 操作也可以实现同样的效果：

Wolfram Language code: ds["Length"]

Normal  (1)

Normal 可用于获取 "OrderedHashSet" 的元素：

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

也可以使用 "Elements" 操作来实现同样的效果：

Wolfram Language code: ds["Elements"]

SameQ  (1)

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

Wolfram Language code: ds1 = CreateDataStructure["OrderedHashSet", Range[10]]; ds2 = CreateDataStructure["OrderedHashSet", Range[10]]; ds1 === ds2

"HashSet"  (1)

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

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

巧妙范例  (1)

创建一个由第一个整数的所有因子组成的有序集合：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Divisors[45]]

通过与第二个整数的所有因子求交集，找出两个整数的公约数：

Wolfram Language code: ds["Intersection", Divisors[78]]//Normal

提取最后一个元素作为最大公约数：

Wolfram Language code: Last[%]

使用内置函数验证结果：

Wolfram Language code: GCD[45, 78]