WOLFRAM

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

"HashTable" （数据结构）

"HashTable"

表示一个哈希表，其中的键和值为普通表达式.

更多信息

  • 哈希表可用于存储通过键来获取的值：
  • CreateDataStructure["HashTable"]创建新的空 "HashTable"
    CreateDataStructure["HashTable",assoc]创建一个包含来自 assoc 的规则的新 "HashTable"
    Typed[x,"HashTable"]指定 x 的类型为 "HashTable"
  • 对于类型为 "HashTable" 的数据结构，可进行以下操作：
  • ds["Copy"]返回 ds 的副本时间: O(n)
    ds["Elements"]返回 ds 的参数列表时间: O(n)
    ds["EmptyQ"]如果 ds 中没有参数则返回 True时间: O(1)
    ds["Insert",keyvalue]将 key 及关联的 value 添加到 ds 中，如果添加成功则返回 True时间: O(1)
    ds["KeyDrop",key]删除 ds 中的 key 及其值时间: O(1)
    ds["KeyDropAll"]删除 ds 中所有的键及其值时间: O(n)
    ds["KeyExistsQ",key]如果 ds 中有 key 则返回 True时间: O(1)
    ds["Keys"]将 ds 的建返回为列表时间: O(n)
    ds["Length"]ds 中存储的 key-value 对的数量时间: O(1)
    ds["Lookup",key]返回 ds 中存储的 key 的值；如果没有找到该键则返回 Missing 对象时间: O(1)
    ds["Lookup",key,defFun]返回 ds 中存储的 key 的值；如果没有找到该键则返回 defFun[key]时间: O(1)
    ds["Values"]将 ds 的值返回为列表时间: O(n)
    ds["Visualization"]返回 ds 的可视化时间: O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换成普通表达式

范例

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

基本范例  (2)

可用 CreateDataStructure 创建新的 "HashTable"：

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

插入键与值：

Wolfram Language code: ds["Insert", f[1] -> g[2]]

只存储了一个键：

Wolfram Language code: ds["Length"]

测试是否有键：

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

查找值：

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

如果没有找到键，返回 Missing 对象：

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

返回表达式形式的 ds：

Wolfram Language code: Normal[ds]

可视化数据结构：

Wolfram Language code: ds = CreateDataStructure["HashTable"]; Do[ds["Insert", i -> True], {i, 30}] ds["Visualization"]

范围  (15)

创建  (2)

创建一个空的 "HashTable"：

Wolfram Language code: CreateDataStructure["HashTable"]

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

Wolfram Language code: CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

信息  (1)

可用 CreateDataStructure 创建新的 "HashTable"：

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

数据结构 ds 的信息：

Wolfram Language code: Information[ds]

操作  (12)

"Copy"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

获取该表的一个副本：

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

两个表的内容相同：

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

修改副本不会影响原始表：

Wolfram Language code: ds1["Insert", "d" -> 4]; {Normal[ds], Normal[ds1]}

"Elements"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

将内容作为规则列表返回：

Wolfram Language code: ds["Elements"]

Normal 将内容作为 Association 返回：

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

创建一个空的 "HashTable"：

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

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

Wolfram Language code: ds["Insert", "a" -> 1]; ds["EmptyQ"]

"Insert"  (1)

创建一个空的 "HashTable"：

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

向表中插入一个键值对，如果插入成功则返回 True：

Wolfram Language code: ds["Insert", "a" -> 1]

再次插入相同的键值对是不可能的，因此返回 False：

Wolfram Language code: ds["Insert", "a" -> 1]

"KeyDrop"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

使用键从表中删除一个键值对，如果删除成功则返回 True：

Wolfram Language code: ds["KeyDrop", "b"]

表的内容已更改：

Wolfram Language code: Normal[ds]

"KeyDropAll"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

从表中删除所有键值对：

Wolfram Language code: ds["KeyDropAll"]

现在表是空的：

Wolfram Language code: ds["Length"]

"KeyExistsQ"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

测试以下键是否存在于表中：

Wolfram Language code: {ds["KeyExistsQ", "b"], ds["KeyExistsQ", "d"]}

"Keys"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

将表中的键作为列表返回：

Wolfram Language code: ds["Keys"]

"Length"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

获取表中元素的数量：

Wolfram Language code: ds["Length"]

Length 给出相同的值：

Wolfram Language code: Length[ds]

"Lookup"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

检索表中与键关联的值：

Wolfram Language code: ds["Lookup", "a"]

如果表中不存在该键，则返回 Missing：

Wolfram Language code: ds["Lookup", "d"]

第三个参数可用于指定在未找到键时应该应用于该键的函数：

Wolfram Language code: ds["Lookup", "d", notfound]

"Values"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

将表中的值作为列表返回：

Wolfram Language code: ds["Values"]

"Visualization"  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]

可视化哈希表的内容：

Wolfram Language code: ds["Visualization"]

应用  (2)

记忆化  (1)

哈希表对于保存将被计算的值很有用，该过程称为记忆化. 此处给出了应用于斐波纳契计算的例子：

Wolfram Language code: Fib[n_] := iFib[CreateDataStructure["HashTable"], n]
Wolfram Language code: iFib[st_, n_] := Module[{res}, Which[ n ≤ 1, n, st["KeyExistsQ", n], st["Lookup", n], True, res = iFib[st, n - 2] + iFib[st, n - 1]; st["Insert", n -> res]; res ]]

计算 100 的值：

Wolfram Language code: Fib[100]

计算 1000 的值：

Wolfram Language code: Fib[1000]

频率计数  (1)

编写一个计算列表中元素频率的函数：

Wolfram Language code: counts[list_List] := Module[{ht, c}, ht = CreateDataStructure["HashTable"]; Do[ c = ht["Lookup", elem, (ht["Insert", elem -> 0];0)&]; ht["Insert", elem -> c + 1] , {elem, list} ]; Normal[ht] ]

计算列表中出现次数：

Wolfram Language code: counts[{a, b, c, a}]//KeySort

与内置的 Counts 函数进行比较：

Wolfram Language code: Counts[{a, b, c, a}]//KeySort

属性和关系  (5)

InputForm  (1)

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

Wolfram Language code: InputForm[CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]]

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

Wolfram Language code: DataStructure["HashTable", {"Data" -> {"c" -> 3, "a" -> 1, "b" -> 2}}]

Length  (1)

可以使用Length 获取 "HashTable" 中的元素个数：

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]; Length[ds]

通过 "Length" 操作也可以实现同样的效果：

Wolfram Language code: ds["Length"]

Normal  (1)

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

Wolfram Language code: ds = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]; Normal[ds]

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

Wolfram Language code: ds["Elements"]

SameQ  (1)

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

Wolfram Language code: ds1 = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]; ds2 = CreateDataStructure["HashTable", <|"a" -> 1, "b" -> 2, "c" -> 3|>]; ds1 === ds2

"OrderedHashTable"  (1)

许多适用于 "HashTable" 的算法也适用于 "OrderedHashTable".

与 "HashTable" 不同，插入到 "OrderedHashTable" 中的键值对的顺序会被保留.