"HashTable" (Data Structure)

"HashTable"

represents a hash table where the keys and values are general expressions.

Details

  • A hash table is useful for storing individual values that can be retrieved by use of a key:
  • CreateDataStructure["HashTable"]create a new empty "HashTable"
    CreateDataStructure["HashTable",assoc]create a new "HashTable" containing the rules from assoc
    Typed[x,"HashTable"]give x the type "HashTable"
  • For a data structure of type "HashTable", the following operations can be used:
  • ds["Copy"]return a copy of dstime: O(n)
    ds["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if ds has no elementstime: O(1)
    ds["Insert",keyvalue]add key to ds with the associated value and return True if the addition succeededtime: O(1)
    ds["KeyDrop",key]drop key and its value from ds time: O(1)
    ds["KeyDropAll"]drop all the keys and their values from ds time: O(n)
    ds["KeyExistsQ",key]True, if the key exists in dstime: O(1)
    ds["Keys"]return the keys in ds as a listtime: O(n)
    ds["Length"]the number of key-value pairs stored in dstime: O(1)
    ds["Lookup",key]return the value stored with key in ds; if the key is not found return a Missing objecttime: O(1)
    ds["Lookup",key,defFun]return the value stored with key in ds; if the key is not found return defFun[key]time: O(1)
    ds["Values"]return the values in ds as a listtime: O(n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression

Examples

open allclose all

Basic Examples  (2)

A new "HashTable" can be created with CreateDataStructure:

Insert a key with a value:

There is one key stored:

Test if a key is present:

Look up a value:

When a key is not found, a Missing object is returned:

Return an expression version of ds:

A visualization of the data structure can be generated:

Scope  (1)

Information  (1)

A new "HashTable" can be created with CreateDataStructure:

Information about the data structure ds:

Applications  (1)

Memoization  (1)

Hash tables are useful for saving values that may be computed, a process known as memoization. An example applied to a Fibonacci computation is given here:

Compute the value for 100:

Compute the value for 1000: