Implementing Sets (Hash-sets) in Golang

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 applications.

banner image

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:

usage of a set

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

Using Maps

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.

Iteration

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
	zoo.add("Walrus")
	zoo.add("Parrot")
	zoo.add("Lion")
	zoo.add("Giraffe")
	zoo.add("Bear")
	
	// Adding an existing member to the set again
	zoo.add("Lion")
	
	// 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 + 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 👇


Liked this article? Share it on: