WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"HashTable" (データ構造)

"HashTable"

キーと値が一般式であるハッシュテーブルを表す．

詳細

  • ハッシュテーブルは，キーの使用によって取り出すことができる個々の値を保存するのに役立つ．
  • CreateDataStructure["HashTable"]新しい空の"HashTable"を作成する
    CreateDataStructure["HashTable",assoc]assoc からの規則を含む新しい"HashTable"を作成する
    Typed[x,"HashTable"]x に"HashTable"型を与える
  • "HashTable"型のデータ構造には，以下の演算が使える．
  • ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds が要素を持たない場合はTruetime: O(1)
    ds["Insert",keyvalue]関連付けられた value とともに key を ds に加え，追加が成功した場合にはTrueを返すtime: O(1)
    ds["KeyDrop",key]key とその値を ds から省くtime: O(1)
    ds["KeyDropAll"]すべてのキーとその値を ds から省くtime: O(n)
    ds["KeyExistsQ",key]key が ds 内にある場合はTruetime: O(1)
    ds["Keys"]ds のキーをリストとして返すtime: O(n)
    ds["Length"]ds に保存されるキーと値のペアの数time: O(1)
    ds["Lookup",key]ds 内に key と一緒に保存された値を返す．キーが見付からない場合はMissing オブジェクトを返すtime: O(1)
    ds["Lookup",key,defFun]ds 内に key と一緒に保存された値を返す．キーが見付からない場合は defFun[key]を返すtime: O(1)
    ds["Values"]ds の値をリストとして返すtime: O(n)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開く すべて閉じる

例  (2)

新しい"HashTable"は，CreateDataStructureを使って作成できる：

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

キーを値と一緒に挿入する：

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

保存されているキーは1個である：

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)

新しい"HashTable"は，CreateDataStructureを使って作成することができる：

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"]

キーが見付からない場合には，第3引数を使ってキーに適用されるべき関数を指定することができる：

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を使って，2つのハッシュテーブルに同じ要素が同じ順序で含まれるかどうかをテストすることができる：

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"にキーと値のペアが挿入される順序は保存される．