"HashSet" (Data Structure)

"HashSet"

represents a set where the members are general expressions and membership is computed by using a hash function.

Details

  • A hash set is useful for efficient insertion and removal as well as membership testing:
  • CreateDataStructure["HashSet"]create a new empty "HashSet"
    CreateDataStructure["HashSet",elems]create a new "HashSet" containing elems
    Typed[x,"HashSet"]give x the type "HashSet"
  • For a data structure of type "HashSet", 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["SubsetQ",ds1]return True if hash set ds1 is a subset of dstime: O(n)
    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)

A new "HashSet" can be created with CreateDataStructure:

Insert into the set:

There is one element in the set:

Test if an expression is stored:

If an expression is not stored, False is returned:

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

Return an expression version of ds:

It is fast to insert elements:

A visualization of the data structure can be generated:

Scope  (2)

Information  (1)

A new "HashSet" can be created with CreateDataStructure:

Information about the data structure ds:

Set Operations  (1)

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

Insert an element into ds:

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

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

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

Applications  (1)

Sets of Strings  (1)

Built-in set operations are good for working with rectangular arrays of machine numbers. Data structure operations are good for working with sets of non-numeric data such as strings. Create a list of 1000000 strings:

A similar example shows benefits for "Complement":

Neat Examples  (1)

GCD Computation  (1)

Finding the intersection of two collections of divisors helps find the greatest:

The largest result is 3:

This is equal to the GCD: