Maps

Maps are a useful data structure that store (key, value) pairs in a way that lets you efficiently retrieve any pair if you know its key.

Creating a Map

Here is a map that stores the names of candidates for an election and the number of votes they received:

votes := map[string]int{"Raj":4, "Jones":2, "White":2}

On the right side of := is a map literal. Its type is map[string]int, and the map itself is specified using key:value pairs (similar to the notation used in languages like Python, JavaScript, and JSON).

You can also create a map using the make function, e.g.:

votes := make(map[string]int)  // creates an empty map
votes["Raj"] = 4
votes["Jones"] = 2
votes["White"] = 2

Accessing Elements of a Map

You access a particular value using a key, e.g. votes["yan"] evaluates to 4. If you want to add 1 vote for Jones, you can do it like this:

votes["Jones"]++  // add 1 to the value associated with "Jones"

To add a new item to the map, just assign it like this:

votes["Harper"] = 3

If the key "Harper" already happened to be in votes, then this statement would instead set its value to 3.

Missing Keys

If you try to access the value for a key that doesn’t exist, then the zero- value associated with the value’s type is returned. For example:

fmt.Println(votes["Kennedy"])   // prints 0, because "Kennedy" is not a key

This presents a problem: how can you distinguish between a key that doesn’t exist, and a key that is paired with 0? The solution Go provides is to return an optional flag indicating whether or not the key was found:

count, ok := votes["Kennedy"]
if ok {
        fmt.Printf("%v\n", count)
} else {
        fmt.Println("no candidate by that name")
}

It’s entirely up to the programmer to check the ok flag!

A common case is to test if a given key is in a map. For instance:

_, present := votes["Kennedy"]  // _ is the blank identifier; we use it
                                // here because we don't care about the
                                // associated value

If present is true, they "Kennedy" is a key in the list. If it’s false, then Kennedy is not in the list.

Deleting Items in a Map

To delete a key and its associated value from a map, use the built-in delete function:

delete(votes, "Raj")

If "Raj" happened to not be a key in votes, then this statement doesn’t modify the map.

Limitations on Keys

Not all data types are allowed to be keys in a map. Any data type that supports equality, such as integers, floats, strings, pointers, structs, and arrays can be used as a key. But, slices and other maps cannot be keys because they do not have equality defined for them.

Processing a Map with a For-loop

You can process every element of a map using a ranged for-loop:

for key, value := range votes {
        fmt.Printf("votes[\"%s\"] = %d\n", key, value)
}

Or if you just want the keys:

for key := range votes {
        fmt.Printf("votes[\"%s\"] = %d\n", key, votes[key])
}

Questions

1. What is the type of a map whose keys are integers and whose values are booleans?
2. What are two different data types that cannot be used as keys in a map?
3. Can nil be a key in a map? If no, why not? If yes, then what is the type for a map that can have nil as a key?
4. Write a function that takes a map of type map[string]int as input, and returns the key and value of the pair with the greatest value.
5. Write a function that takes a map of type map[string]int as input along with a target string val, and returns a slice containing all the keys whose value equals val.

Sample Program

The following program is based on an idea from the XKCD comic strip. It asks the user to type in some words, and then it checks to see which of those words are in xkcdWordlist.text, a file of the 3000 or so most common English words.

A map is a good data structure for this problem because testing if a word is in it can be done in O(1) time, on average. If, instead, you used a slice, then the retrieval would take O(n) time on average.

package main

import (
        "bufio"
        "fmt"
        "io/ioutil"
        "os"
        "strings"
)

func main() {
        //
        // load all the words into a map
        //
        var dictionary map[string]bool = make(map[string]bool)

        // read entire file into one slice of bytes
        allBytes, err := ioutil.ReadFile("xkcdWordlist.text")
        if err != nil {
                panic("no word file to read!")
        }

        // convert the byte slice to a string
        bigString := string(allBytes)

        // split the string into words
        words := strings.Split(bigString, " ")

        // add the words to the dictionary
        for _, w := range words {
                dictionary[w] = true
        }
        fmt.Printf("%v words in dictionary\n", len(dictionary))

        //
        // check words typed by the user
        //
        console := bufio.NewReader(os.Stdin)
        for {
                // print a prompt
                fmt.Print("--> ")

                // read, as a slice of bytes, the entire line of text entered by the user
                lineBytes, _, _ := console.ReadLine()
                // fmt.Printf("(input=\"%v\")\n", lineBytes)

                // convert the line to a string
                line := string(lineBytes)

                // split the string into words
                userWords := strings.Split(line, " ")
                // fmt.Printf("(%v)\n", userWords)

                // check each word to see if it is in the dictionary
                for _, w := range userWords {
                        if _, exists := dictionary[w]; !exists {
                                fmt.Printf("\"%v\" is too complex!\n", w)
                        }
                }
        } // for
} // main