Hash Sets in Go

Hash Sets are collections of unique items i.e no element can be repeated.

Hash Sets were designed to give us a way of adding and looking for unique values in a collection in a quick manner.

The values in a Hash Set can be either simple primitives like strings or integers as well as more complex object types like structs or arrays (but not slices, which can't be map keys).

In Go, Hash Sets are typically implemented using the built-in map type with empty struct values (map[T]struct{}); a map[T]bool works too, and the exercise uses it.

Creation:

To create a new empty set that holds strings, you use the following syntax:

mySet := map[string]struct{}{}

Creating an empty Set takes O(1) time.

Constructing from a slice

Go has no Set constructor, but you can build a set from a slice with a loop. All the unique elements of the slice will be added to the new set:

elements := []string{"b", "c", "c", "d"}
mySet := make(map[string]struct{})
for _, e := range elements {
    mySet[e] = struct{}{}
}

// mySet contains {"b", "c", "d"}

This takes O(n) time, where n is the number of elements in the slice.

Adding elements:

To add an element to the set, you assign it as a key with an empty struct value:

mySet := map[string]struct{}{"b": {}, "c": {}, "d": {}}

// Adding new elements
mySet["x"] = struct{}{}

// Adding an existing element
mySet["d"] = struct{}{} // nothing happens

// mySet contains {"b", "c", "d", "x"}

If the element already exists, assigning it again changes nothing and doesn't raise an error.

Adding an element to a Set takes O(1) time.

Checking if a value exists:

To check if a set has a specific element, you use the comma-ok idiom which returns true if the set contains the element, otherwise, it returns false.

mySet := map[string]struct{}{"b": {}, "c": {}, "d": {}}

_, ok := mySet["c"]
fmt.Println(ok) // prints true since 'c' exists (remember that set keeps unique values)

_, ok = mySet["x"]
fmt.Println(ok) // prints false since it does not exist in the set

Checking if a value exists in a Set takes O(1) time.

Removing elements:

To delete a specified element from a set, you use the delete() built-in function:

mySet := map[string]struct{}{"b": {}, "c": {}, "d": {}}

// Deleting elements
delete(mySet, "c")

// Deleting a non-existent element
delete(mySet, "z") // does nothing

// mySet contains {"b", "d"}

If the key doesn't exist, delete does nothing and doesn't raise an error, so it's safe to delete non-existing elements.

Removing an element from a Set takes O(1) time.

Iterating over the Set values:

If we want to iterate over values of the set, we can use the for loop along with the range keyword:

mySet := map[string]struct{}{"b": {}, "c": {}, "d": {}}

for val := range mySet {
    fmt.Println(val)
}

// This prints the three values in a random order, for example:
// d
// c
// b

Iterating over a map takes O(n) time.

Notice the order is not the same as we initiated. map keeps the data in random order

Space Complexity

A Set uses O(n) space, where n is the number of elements existing in the Set.

Assignment
Follow the Coding Tutorial and let's play with some Hash Sets.

Hint
Look at the examples above if you get stuck.