WOLFRAM

Wolfram Language & System Documentation Center

"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 all close all

Basic Examples  (2)

A new "HashTable" can be created with CreateDataStructure:

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

Insert a key with a value:

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

There is one key stored:

Wolfram Language code: ds["Length"]

Test if a key is present:

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

Look up a value:

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

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

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

Return an expression version of ds:

Wolfram Language code: Normal[ds]

A visualization of the data structure can be generated:

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

Scope  (15)

Creation  (2)

Create an empty "HashTable":

Wolfram Language code: CreateDataStructure["HashTable"]

Create a "HashTable" with initial elements:

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

Information  (1)

A new "HashTable" can be created with CreateDataStructure:

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

Information about the data structure ds:

Wolfram Language code: Information[ds]

Operations  (12)

"Copy"  (1)

Create a "HashTable" with initial elements:

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

Get a copy of the table:

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

The contents of both tables are the same:

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

Modifying the copy will not affect the original table:

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

"Elements"  (1)

Create a "HashTable" with initial elements:

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

Get the contents as a list of rules:

Wolfram Language code: ds["Elements"]

Normal returns the contents as an Association:

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

Create an empty "HashTable":

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

After inserting an element, the set is no longer empty:

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

"Insert"  (1)

Create an empty "HashTable":

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

Insert a key-value pair into the table, returning True if the insertion succeeded:

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

Inserting the same pair again is not possible, so False is returned:

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

"KeyDrop"  (1)

Create a "HashTable" with initial elements:

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

Drop a key-value pair from the table using its key, returning True if the deletion succeeded:

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

The contents of the table have changed:

Wolfram Language code: Normal[ds]

"KeyDropAll"  (1)

Create a "HashTable" with initial elements:

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

Drop all key-value pairs from the table:

Wolfram Language code: ds["KeyDropAll"]

The table is now empty:

Wolfram Language code: ds["Length"]

"KeyExistsQ"  (1)

Create a "HashTable" with initial elements:

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

Test whether the following keys are present in the table:

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

"Keys"  (1)

Create a "HashTable" with initial elements:

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

Get the keys in the table as a list:

Wolfram Language code: ds["Keys"]

"Length"  (1)

Create a "HashTable" with initial elements:

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

Get the number of elements in the table:

Wolfram Language code: ds["Length"]

Length gives the same value:

Wolfram Language code: Length[ds]

"Lookup"  (1)

Create a "HashTable" with initial elements:

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

Retrieve the value associated with a key in the table:

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

If the key is not present in the table, Missing is returned:

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

The third argument can be used to specify the function that should be applied to the key if it is not found:

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

"Values"  (1)

Create a "HashTable" with initial elements:

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

Get the values in the table as a list:

Wolfram Language code: ds["Values"]

"Visualization"  (1)

Create a "HashTable" with initial elements:

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

Visualize the contents of the hash table:

Wolfram Language code: ds["Visualization"]

Applications  (2)

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:

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

Compute the value for 100:

Wolfram Language code: Fib[100]

Compute the value for 1000:

Wolfram Language code: Fib[1000]

Frequency Counting  (1)

Write a function that counts the frequency of elements in a list:

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

Count occurrences in a list:

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

Compare with the built-in Counts function:

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

Properties & Relations  (5)

InputForm  (1)

InputForm returns the serialized contents of the "HashTable":

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

This serialized form can be used to recreate the data structure:

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

Length  (1)

Length can be used to get the number of elements in a "HashTable":

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

The same can be achieved with the "Length" operation:

Wolfram Language code: ds["Length"]

Normal  (1)

Normal can be used to get the elements of a "HashTable":

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

The same can be achieved with the "Elements" operation:

Wolfram Language code: ds["Elements"]

SameQ  (1)

SameQ can be used to test whether two hash tables contain identical elements in the same order:

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)

Many algorithms that work for "HashTable" also work for "OrderedHashTable".

Unlike "HashTable", the order in which key-value pairs are inserted into an "OrderedHashTable" is preserved.