Maps in Go

Learning objectives

In the previous code along, we discussed how to identify the occurrences of a substring within a larger text. We would like to return to the more general problem of finding the most frequent strings (of some fixed length) within the text, which we called the Frequent Words Problem.

To solve the Frequent Words Problem, we will need to build a frequency table associating each k-mer substring of a string with its number of occurrences. Recall the following example from the core text.

To implement the frequency table, we will need to build a dictionary, called a map in Go, that associates values (in this case integers) with keys (in this case strings). In this lesson, we will learn about how Go implements maps, which will prepare us to solve the Frequent Words Problem.

Setup

Create a folder called maps in your go/src directory and create a text file called main.go in the go/src/maps folder. We will edit main.go, which should have the following starter code.

package main

import (
    "fmt"
)

func main() {
    fmt.Println("Maps in Go.")
}

Code along video

Beneath the video, we provide a detailed summary of the topics and code covered in the code along.

Although we strongly suggest completing the code along on your own, you can find completed code from the code along in our course code repository.

Code along summary

Declaring maps

Recall that we used the following notation to declare a slice containing six integers.

func main() {
    fmt.Println("Maps in Go.")

    //recall slice declarations
    var a []int 
    a = make([]int, 6) // slices must be made

}

To declare a map, we use similar notation, except that we do not need to assign the map an initial length because Go automatically allocates memory for the map. For example, we will declare a map polls that associates a state name (a string) to the polling percentage for a candidate (a decimal). We will work more with this map in the next chapter.

func main() {
    fmt.Println("Maps in Go.")

    //recall slice declarations
    var a []int 
    a = make([]int, 6) // slices must be made

    var polls map[string]float64
    polls = make(map[string]float64) // maps must be made but have no set length

}

As we had a one-line declaration for slices, we will have an analogous shorthand declaration for maps.

func main() {
    fmt.Println("Maps in Go.")

    //recall slice shorthand declarations
    a := make([]int, 6) // slices must be made

    polls := make(map[string]float64) // maps must be made but have no set length

}

Accessing the value corresponding to a key in a map is similar to accessing the value corresponding to some index of an array or slice. With a slice, we need to ensure that the i-th element of the slice exists before setting it; in the case of a map, we can set the value corresponding to a key even if the map does not yet contain the key. We illustrate this below by setting a few values of polls.

func main() {
    fmt.Println("Maps in Go.")

    polls := make(map[string]float64) // maps are made but have no set length

    polls["Pennsylvania"] = 0.517
    polls["Ohio"] = 0.489
    polls["Texas"] = 0.378
    polls["Florida"] = 0.5
}

Although we can set the value of any key we choose, maps do have a length that is equal to the number of keys that we have been assigned values.

func main() {
    fmt.Println("Maps in Go.")

    polls := make(map[string]float64) // maps are made but have no set length

    polls["Pennsylvania"] = 0.517
    polls["Ohio"] = 0.489
    polls["Texas"] = 0.378
    polls["Florida"] = 0.5

    fmt.Println("The number of states in the map is", len(polls)) // prints 4
}

Removing an element from a map

Let’s do the world a favor and rid ourselves of Florida once and for all. We can do so using a built in delete() function that takes two inputs: the name of the map’s variable and the key that we wish to delete from the map.

func main() {
    fmt.Println("Maps in Go.")

    polls := make(map[string]float64) // maps are made but have no set length

    polls["Pennsylvania"] = 0.517
    polls["Ohio"] = 0.489
    polls["Texas"] = 0.378
    polls["Florida"] = 0.5

    fmt.Println("The number of states in the map is", len(polls)) // prints 4

    delete(polls, "FL") // Bugs_bunny_sawing_off_Florida.gif

    fmt.Println("The number of states in the map is now", len(polls)) // prints 3
}

Array, slice, and map literals

We can also set the values of arrays, slices, and maps when they are defined, which is helpful when the number of values is small or fixed. For example, we could declare the following array of four symbols.

func main() {
    fmt.Println("Maps in Go.")

    // ...

    symbols := [4]byte{'A', 'C', 'G', 'T'}
}

We might instead want to declare a short slice, in case we are planning to change the elements of the slice later.

func main() {
    fmt.Println("Maps in Go.")

    // ...

    symbols := [4]byte{'A', 'C', 'G', 'T'}

    primes := []int{2, 3, 5, 7, 11}
}

We can declare short maps too. For example, the following map associates states with their number of electoral votes (more on this in the next chapter).

func main() {
    fmt.Println("Maps in Go.")

    // ...

    electoralVotes := map[string]uint {
        "Pennsylvania": 20,
        "Ohio": 18,
        "Texas": 38, //Go demands this final comma for consistency
    }
}

These declarations are called array, slice, and map literals.

Maps are passed by reference

The number of electoral votes that each state receives is a function of its population. The number of votes that we presented in the previous section are from 2020, but in 2024, the electoral votes changed as voters fled miserable rust belt states like Pennsylvania and Ohio for the uninhabitable heat, low taxes, and plentiful ammunition of Texas.

Let’s use this demographic fact to write a function updating the electoralVotes array to their appropriate 2024 values, in which Pennsylvania and Ohio each lost a vote and Texas gained two votes.

func UpdateVotes(electoralVotes map[string]uint) {
    electoralVotes["Pennsylvania"] = 19
    electoralVotes["Ohio"] = 17
    electoralVotes["Texas"] = 40
}

We give this example not to make a cute political point but rather to illustrate a fact about maps input to functions. After we call this function in func main(), we will print out the number of votes allocated to Pennsylvania.

func main() {
    fmt.Println("Maps in Go.")

    // ...

    electoralVotes := map[string]uint {
        "Pennsylvania": 20,
        "Ohio": 18,
        "Texas": 38, //Go demands this final comma for consistency in case we add more elements later
    }

    UpdateVotes(electoralVotes)

    fmt.Println("The number of electoral votes in Pennsylvania is", electoralVotes["Pennsylvania"])
}

When we compile and run our code, we see that the number of votes printed is 19, so that the map that we created in func main() has been changed by a function. This behavior is different from that of basic types like integers and strings, which we learned in a previous code along are passed by value to functions. In contrast, like slices, maps are passed by reference, which means that we can edit maps that are passed into functions.

Ranging over the keys of a map

Rather than printing only Pennsylvania’s electoral votes, let’s print the votes of all states. As we can range over the indices (and values) of an array, we can range over the keys (and values) of a map. In the code below, we range over polls and print each state’s name and its polling percentage.

func main() {
    fmt.Println("Maps in Go.")

    // ...

    electoralVotes := map[string]uint {
        "Pennsylvania": 20,
        "Ohio": 18,
        "Texas": 38, //Go demands this final comma for consistency in case we add more elements later
    }

    UpdateVotes(electoralVotes)

    for state, votes := range electoralVotes {
        fmt.Println("The number of votes in", state, "is", votes)
    }
}

One might imagine that the keys of polls (and their associated values) would be printed in alphabetical order, or the order in which keys were placed in the map. Yet for technical reasons, the order of the keys is random (or, to use a more precise term that we will introduce in the next chapter, pseudorandom).

Ranging over the keys of a map in alphabetical order

If we would instead like to range over and print out the keys of a map in alphabetical order, then we can first build a slice containing all the keys, sort the keys in alphabetical order, and range over this list of keys instead of the map. The following code, which calls a function to print the keys (and their associated values) of a map in alphabetical order, requires us to add "sort" to the package import list. Note that we do not have a collection of indices when ranging over a map, so we will declare a counter variable (i) that we will use to keep track of how many keys of the input map we have considered.

func main() {
    fmt.Println("Maps in Go.")

    // ...

    electoralVotes := map[string]uint {
        "Pennsylvania": 20,
        "Ohio": 18,
        "Texas": 38, //Go demands this final comma for consistency in case we add more elements later
    }

    UpdateVotes(electoralVotes)

    for state, votes := range electoralVotes {
        fmt.Println("The number of votes in", state, "is", votes)
    }

    PrintMapAlphabetical(polls)

}

//PrintMapAlphabetical takes as input a map of strings to unsigned integers.
//It prints each key-value pair on its own line, with keys printed in alphabetical order.
func PrintMapAlphabetical(dict map[string]uint) {
    //sort the keys of the map, then range over the sorted keys to print key-value pairs
    keys := make([]string, len(dict))
    i := 0

    for key := range dict {
        keys[i] = key
        i++
    }
    //sort the keys
    sort.Strings(keys)

    //let's range over keys and print the associated dictionary value
    for _, key := range keys {
        fmt.Println("The value associated with", key, "is", dict[key])
    }
}

Looking ahead to the next lesson

We are now ready to move on to the next lesson and find frequent words in a string. You may like to try implementing the following functions on your own before joining us in the code along.

FindFrequentWords(text, k)
    frequentPatterns ← an array of strings of length 0
    freqMap ← FrequencyTable(text, k)
    max ← MaxMapValue(freqMap)
    for all strings pattern in freqMap
        if freqMap[pattern] = max
            frequentPatterns ← append(frequentPatterns, pattern)
    return frequentPatterns

FrequencyTable(text, k)
    freqMap ← empty map
    n ← length(text)
    for every integer i between 0 and n − k
        pattern ← text[i, i + k]
        if freqMap[pattern] doesn't exist
            freqMap[pattern] = 1
        else
            freqMap[pattern]++
    return freqMap

MaxMapValue(dict)
    m ← 0
    firstTime = true
    for every key pattern in dict
        if firstTime = true or dict[pattern] > m
            firstTime= false
            m ← dict[pattern]
    return m