"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を使って作成できる：

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

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

キーがあるかどうかを検証する：

値を調べる：

キーが見付からない場合には，Missingオブジェクトが返される：

式バージョンの ds を返す：

データ構造の可視化を生成することができる：

スコープ  (1)

情報  (1)

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

データ構造 ds についての情報：

アプリケーション  (1)

メモ化  (1)

ハッシュテーブルは，計算に使える値を保存するのに便利である．これはメモ化として知られるプロセスである．ここでは，フィボナッチ計算に適用する例を示す：

100に対する値を計算する：

1000に対する値を計算する：