As you may know, there is no native implementation of sets in Go. This post describes how we can use the existing native data structures to implement sets (and hash-sets) in Go.

## What Is a Set?#

A set is a data structure that holds a distinct collection of items. It’s useful when you want to hold a non-repeating list of objects.

A good example of a set is describing the types of animals that are present in a zoo:

Unlike maps, a set does not have and key-value pairs.

Let’s see how we can implement this set in Go.

## Using Maps to Implement Sets#

Although Go doesn’t have sets natively, we can make use of maps to act the same way.

Since sets are just a collection of values, and not key-value pairs, we can represent them as maps with empty struct values. Let’s see how we would implement our zoo example:

``````package main

import (
"fmt"
)

func main() {
// Zoo acts as a set of strings
zoo := map[string]struct{}{}

// We can add members to the set
// by setting the value of each key to an
// empty struct
zoo["Walrus"] = struct{}{}
zoo["Parrot"] = struct{}{}
zoo["Lion"] = struct{}{}
zoo["Giraffe"] = struct{}{}

// Adding a new member to the set
zoo["Bear"] = struct{}{}

// Adding an existing to the set
zoo["Lion"] = struct{}{}

// Removing a member from the set
delete(zoo, "Parrot")

fmt.Println(zoo)
// map[Bear:{} Giraffe:{} Lion:{} Parrot:{} Walrus:{}]

}
``````

Try it here

We were able to execute all operations that are characteristic of a set, with the same time complexity of O(1) for adding and removing members from a set.

## Iterating Through Set Elements#

We can iterate through the set using the `range` operator:

``````for animal := range zoo {
fmt.Println(animal)
}
//Output:
// Lion
// Giraffe
// Bear
// Walrus
``````

This ranges through all the key-value pairs in the map (of which we are only interested in the keys).

## Adding Methods to the Set#

Although we were able to perform all of the operations characteristic of a set, it look a bit unwieldy.

In other language implementations, we have methods on our set such as `Add`, `Remove`, or `Has`.

In order to do this, we can make a new type and add methods to it.

``````// The animalSet type is a type alias of `map[string]struct{}`
type animalSet map[string]struct{}

// Adds an animal to the set
func (s animalSet) add(animal string) {
s[animal] = struct{}{}
}

// Removes an animal from the set
func (s animalSet) remove(animal string) {
delete(s, animal)
}

// Returns a boolean value describing if the animal exists in the set
func (s animalSet) has(animal string) bool {
_, ok := s[animal]
return ok
}
``````

We can use these methods in place of the barebones code used in the previous example:

``````func main() {
// Initializing zoo as a new set
zoo := animalSet{}

// Adding members to the set

// Adding an existing member to the set again

// Removing members from the set
zoo.remove("Parrot")

fmt.Println(zoo)
// map[Bear:{} Giraffe:{} Lion:{} Walrus:{}]

// Checking the presence of elements in a set
fmt.Println(zoo.has("Penguin"))
// false
fmt.Println(zoo.has("Bear"))
// true
}
``````

This looks much closer to a native implementation of sets.

## Compatibility and Performance#

Go does not have any language-native “set” data structure, however, using maps can achieve the same thing.

In terms of semantics, we were able to use the `add`, `remove` and `has` methods on our set implementation. The only downside, is that you’d need to write a custom implementation for any type of set.

We were able to achieve similar performance as well:

• Time complexity remains at O(1) for adding, removing, and verifying membership of elements.
• Space complexity also remains the same, since the `struct{}` type has a size of 0.

That about wraps it up! Let me know if I’ve missed anything, or if you have your own implementation in the comments below 👇