WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

"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
    Normal[ds]convert ds to a normal expression

Examples

open allclose all

Basic Examples  (2)Summary of the most common use cases

A new "OrderedHashSet" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-ck3oom
Out[1]=1

Insert into the set:

In[2]:=2
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-84r1md
Out[2]=2

There is one element in the set:

In[3]:=3
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-tnm4iz
Out[3]=3

Test if an expression is stored:

In[4]:=4
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-kfcutb
Out[4]=4

If an expression is not stored, False is returned:

In[5]:=5
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-2ymbbr
Out[5]=5

Remove an element from the set. If something was actually removed, return True:

In[6]:=6
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-3dkxgf
Out[6]=6

Return an expression version of ds:

In[7]:=7
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-dbekgb
Out[7]=7

It is fast to insert elements:

In[1]:=1
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-mfljzp

A visualization of the data structure can be generated:

In[2]:=2
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-uvwa1b
Out[2]=2

The order in which elements are inserted is preserved:

In[3]:=3
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-53ezb4
Out[3]=3

Scope  (2)Survey of the scope of standard use cases

Information  (1)

A new "OrderedHashSet" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-wn7q0m
Out[1]=1

Information about the data structure ds:

In[2]:=2
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-5du3om
Out[2]=2

Set Operations  (1)

"OrderedHashSet" supports some core set operations. A new empty "OrderedHashSet" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-ubf2je
Out[1]=1

Insert an element into ds:

In[2]:=2
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-vyu2r7

The "Union" operation adds elements that were not originally in the data structure:

In[3]:=3
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-ma3q43
Out[3]=3

The "Complement" operation removes elements from the data structure:

In[4]:=4
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-gtty7m
Out[4]=4

The "Intersection" operation leaves common elements in the data structure:

In[5]:=5
✖
https://wolfram.com/xid/0ipeb3mtlox8s5rpy4mbnkwyhib-5omvlp
Out[5]=5