Using Maps as Sets

Many languages include a set in their standard library. A set is a data type that ensures there is at most one of a value, but doesn’t guarantee that the values are in any particular order. Checking to see if an element is in a set is fast, no matter how many elements are in the set. (Checking to see if an element is in a slice takes longer, as you add more elements to the slice.)

Go doesn’t include a set, but you can use a map to simulate some of its features. Use the key of the map for the type that you want to put into the set and use a bool for the value. The code in Example 2-11 demonstrates the concept. You can run it on The Go Playground.

Example 2-11. Using a map as a set

intSet := map[int]bool{}
vals := []int{5, 10, 2, 5, 8, 7, 3, 9, 1, 2, 10}
for _, v := range vals {
    intSet[v] = true
}
fmt.Println(len(vals), len(intSet))
fmt.Println(intSet[5])
fmt.Println(intSet[500])
if intSet[100] {
    fmt.Println("100 is in the set")
}

You want a set of ints, so you create a map where the keys are of int type and the values are of bool type. You iterate over the values in vals using a for-range loop (which I discuss in “The versatile for-range Statement”) to place them into intSet, associating each int with the boolean value true.

We wrote 11 values into intSet, but the length of intSet is 8, because you cannot have duplicate keys in a map. If you look for 5 in intSet, it returns true, because there is a key with the value 5. However, if you look for 500 or 100 in intSet, it returns false. This is because you haven’t put either value into intSet, which causes the map to return the zero value for the map value, and the zero value for a bool is false.

If you need sets that provide operations like union, intersection, and subtraction, you can either write one yourself or use one of the many third-party libraries that provide the functionality. The most popular one is https://github.com/deckarep/golang-set.

Note

Some people prefer to use struct{} for the value when a map is being used to implement a set. (I’ll discuss structs in the next section.) There are two advantages. One is that an empty struct uses zero bytes, while a boolean uses one byte. The other is that intention is slightly clearer. If there’s a key with the value struct{}, the element exists in the set, but it is unclear what it means when someone writes a key with a false value. It might be a bug or a misguided way to indicate that an element is not in the set.

The disadvantage is that using a struct{} makes your code clumsier. You have a less obvious assignment, and you need to use the comma ok idiom to check if a value is in the set:

intSet := map[int]struct{}{}
vals := []int{5, 10, 2, 5, 8, 7, 3, 9, 1, 2, 10}
for _, v := range vals {
    intSet[v] = struct{}{}
}
if _, ok := intSet[5]; ok {
    fmt.Println("5 is in the set")
}

Unless you have very large sets, the difference in memory usage will not likely be significant. As for the meaning of a false value for a set element, review code to make sure it never happens.