WOLFRAM

Wolfram Language & System Documentation Center

"OrderedHashSet" (Data Structure)

"OrderedHashSet"

represents a set where the members are general expressions, membership is computed by using a hash function and the order in which members are inserted is preserved.

Details

  • An ordered hash set is useful for efficient insertion and removal as well as membership testing where it is important to preserve the order of insertion:
  • CreateDataStructure["OrderedHashSet"]create a new empty "OrderedHashSet"
    CreateDataStructure["OrderedHashSet",elems]create a new "OrderedHashSet" containing elems
    Typed[x,"OrderedHashSet"]give x the type "OrderedHashSet"
  • For a data structure of type "OrderedHashSet", the following operations can be used:
  • ds["Complement",list]remove elements from ds that appear in listtime: O(n)
    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["Delete",x]delete x from ds; return True if x was actually an elementtime: O(1)
    ds["DeleteAll"]delete all the elements from dstime: O(n)
    ds["Insert",x]add x to the set and return True if addition succeededtime: O(1)
    ds["Intersection",list]remove elements from ds that do not appear in listtime: O(n)
    ds["Length"]returns the number of elements stored in dstime: O(1)
    ds["MemberQ",x]True, if x is an element of dstime: O(1)
    ds["Pop"]remove an element from ds and return ittime: O(1)
    ds["Union",list]add elements to ds that appear in 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
    Length[ds]the length of ds
    Normal[ds]convert ds to a normal expression

Examples

open all close all

Basic Examples  (2)

A new "OrderedHashSet" can be created with CreateDataStructure:

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

Insert an element into the set:

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

There is one element in the set:

Wolfram Language code: ds["Length"]

Test if an expression is stored:

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

If an expression is not stored, False is returned:

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

Remove an element from the set, returning True if the element was successfully removed:

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

Return an expression version of ds:

Wolfram Language code: Normal[ds]

It is fast to insert elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; Do[ds["Insert", i], {i, 100}]

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

The order in which elements are inserted is preserved:

Wolfram Language code: ds["Elements"]

Scope  (16)

Creation  (2)

Create an empty "OrderedHashSet":

Wolfram Language code: CreateDataStructure["OrderedHashSet"]

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: CreateDataStructure["OrderedHashSet", {x, y, z}]

Information  (1)

A new "OrderedHashSet" can be created with CreateDataStructure:

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

Information about the data structure ds:

Wolfram Language code: Information[ds]

Operations  (13)

"Complement"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[100]]

Create a new set containing elements that are members of the original "OrderedHashSet" but not members of the given list:

Wolfram Language code: ds1 = ds["Complement", Range[50]]

Verify the elements of the new ordered hash set:

Wolfram Language code: ds1["Elements"]

"Copy"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[4]]

Get a copy of the set:

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

The contents of both arrays are the same:

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

Modifying the copy will not affect the original set:

Wolfram Language code: ds1["Insert", 42]; {Normal[ds], Normal[ds1]}

"Elements"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]

Get the contents as a list:

Wolfram Language code: ds["Elements"]

Normal returns the same list:

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

Test whether a "OrderedHashSet" is empty or not:

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

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

Wolfram Language code: ds["Insert", f[x]]; ds["EmptyQ"]

"Delete"  (1)

Delete an element from a "OrderedHashSet", returning True if deletion succeeded:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {f[x], f[y], f[z]}]; ds["Delete", f[x]]

Deleting an element not present in the set is not possible, so False is returned:

Wolfram Language code: ds["Delete", f[w]]

"DeleteAll"  (1)

Delete all elements in a "OrderedHashSet":

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[300]]; ds["DeleteAll"]

The set is now empty:

Wolfram Language code: ds["EmptyQ"]

"Insert"  (1)

Insert an element into a "OrderedHashSet", returning True if the insertion succeeded:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; ds["Insert", f[x]]

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

Wolfram Language code: ds["Insert", f[x]]

"Intersection"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[100]]

Create a new set containing only those elements common to both the original "OrderedHashSet" and a given list:

Wolfram Language code: ds1 = ds["Intersection", Range[50]]

Verify the elements of the new ordered hash set:

Wolfram Language code: ds1["Elements"]

"Length"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[100]]

Get the number of elements in the set:

Wolfram Language code: ds["Length"]

Length gives the same value:

Wolfram Language code: Length[ds]

"MemberQ"  (1)

Test whether an element is present in a "OrderedHashSet":

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {f[x], f[y], f[z]}]
Wolfram Language code: {ds["MemberQ", f[x]], ds["MemberQ", f[w]]}

"Pop"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {f[x], f[y], f[z]}]; ds["Elements"]

Remove an element of the set:

Wolfram Language code: ds["Pop"]

"Union"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]

Create a new set containing elements present both in the original "OrderedHashSet" and a given list:

Wolfram Language code: ds1 = ds["Union", Range[10, 20]]

Verify the elements of the new hash set:

Wolfram Language code: ds1["Elements"]

"Visualization"  (1)

Create a "OrderedHashSet" with initial elements:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[300]]

Visualize the contents of the hash set:

Wolfram Language code: ds["Visualization"]

Applications  (2)

Stable Deduplication  (1)

Create a list of random elements:

Wolfram Language code: list = RandomChoice[{"A", "B", "C", "D"}, 20]

Remove duplicate elements from the list while preserving the order of first occurrence:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; ds["Union", list];

Get the elements of the set:

Wolfram Language code: ds["Elements"]

Compare with DeleteDuplicates:

Wolfram Language code: DeleteDuplicates[list]

Ordered Common Elements  (1)

Find common elements of two collections while preserving the order of the first:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {a, b, c, d, e}]; ds["Intersection", {e, c, a, f}]//Normal

Properties & Relations  (5)

InputForm  (1)

InputForm returns the serialized contents of the "OrderedHashSet":

Wolfram Language code: InputForm[CreateDataStructure["OrderedHashSet", Range[10]]]

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

Wolfram Language code: DataStructure["OrderedHashSet", {"Data" -> Range[10]}]

Length  (1)

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

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]; 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 "OrderedHashSet":

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]; 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 sets contain identical elements in the same order:

Wolfram Language code: ds1 = CreateDataStructure["OrderedHashSet", Range[10]]; ds2 = CreateDataStructure["OrderedHashSet", Range[10]]; ds1 === ds2

"HashSet"  (1)

Many algorithms that work for "HashSet" also work for "OrderedHashSet".

Unlike "HashSet", the order in which elements are inserted into an "OrderedHashSet" is preserved.

Neat Examples  (1)

Create an ordered set of divisors of the first integer:

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Divisors[45]]

Find the common divisors of two integers by intersecting with the divisors of the second:

Wolfram Language code: ds["Intersection", Divisors[78]]//Normal

Extract the greatest common divisor as the last element:

Wolfram Language code: Last[%]

Verify the result using the built-in function:

Wolfram Language code: GCD[45, 78]