"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 list	time: O(n)
ds["Copy"]	return a copy of ds	time: O(n)
ds["Elements"]	return a list of the elements of ds	time: O(n)
ds["EmptyQ"]	True, if ds has no elements	time: O(1)
ds["Delete",x]	delete x from ds, return True if x was actually an element	time: O(1)
ds["DeleteAll"]	delete all the elements from ds	time: O(n)
ds["Insert",x]	add x to the set and return True if addition succeeded	time: O(1)
ds["Intersection",list]	remove elements from ds that do not appear in list	time: O(n)
ds["Length"]	returns the number of elements stored in ds	time: O(1)
ds["MemberQ",x]	True, if x is an element of ds	time: O(1)
ds["Pop"]	remove an element from ds and return it	time: O(1)
ds["SubsetQ",ds₁]	return True if hash set ds₁ is a subset of ds	time: O(n)
ds["Union",list]	add elements to ds that appear in list	time: O(n)
ds["Visualization"]	return a visualization of ds	time: O(n)

The following functions are also supported:

	ds_i===ds_j	True, if ds_i equals ds_j
	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:

Top