CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Maps

1. Quick Example
2. Creating Maps
3. Using Maps
4. Properties of Maps
   1. Dictionaries Map Keys to Values
   2. Keys are Sets
   3. Values are Unrestricted
   4. Maps are Very Efficient
5. Some Worked Examples Using Maps

1. Quick Example
   /* A dictionary is a data structure that maps keys to values in the same way that a list maps indexes to values. However, keys can be any immutable value! */ package main import "fmt" func getState(city string) string { stateMap := map[string]string{ "Pittsburgh":"PA", "Chicago":"IL", "Seattle":"WA" } state, ok := stateMap[city] if ok { return state } else { return "Sorry, never heard of it." } } func main() { fmt.Println(getState("Pittsburgh")) fmt.Println(getState("Boston")) }
   
   Another Example:
   package main import "fmt" func main() { counts := make(map[int]int) for _, n := range []int{1,2,3,4,1,1,2,2} { _, ok := counts[n] if ok { counts[n] += 1 } else { counts[n] = 1 } fmt.Println("I have seen", n, "a total of", counts[n], "time(s)") } fmt.Println("Done, counts:", counts) }


2. Creating Maps
   • Create an empty map
     package main import "fmt" func main() { d := make(map[int]int) // maps [integer keys] to integer values fmt.Println(d) }
   
   
   • Statically-allocate a map
     package main import "fmt" func main() { d := map[int]string{1: "a", 2: "b"} fmt.Println(d) }


3. Using Dictionaries
   package main import "fmt" func main() { // We can interact with dictionaries in a similar way to lists/sets d := map[string]string{ "a" : "z", "b" : "y", "c" : "x" } fmt.Println(len(d)) // prints 3, the number of key-value pairs _, ok := d["a"] fmt.Println(ok) // prints True because "a" is a key in d _, ok = d["z"] fmt.Println(ok) // prints False - we check the keys, not the values v, _ := d["a"] // finds the value associated with the given key fmt.Println(v) v, _ = d["z"] fmt.Println(v) // Prints an empty string, the default value of a string d["e"] = "wow" // adds a new key-value pair to the dictionary, or updates the value of a current key delete(d, "a") // removes the key-value pair specified from the dictionary. Crashes if the key is not in d for key, value := range d { fmt.Println(key, ":", value) } }


4. Properties of Maps
   1. Maps Map Keys to Values
      
      package main import "fmt" func main() { ages := make(map[string]int) key := "fred" value := 38 ages[key] = value // "fred" is the key, 38 is the value fmt.Println(ages[key]) }
   
   
   2. Keys are Sets
      
      • Keys are unordered
        package main import "fmt" func main() { d := make(map[int]int) d[2] = 100 d[4] = 200 d[8] = 300 fmt.Println(d) // unpredictable order }
      
      
      • Keys are unique
        package main import "fmt" func main() { d := make(map[int]int) d[2] = 100 d[2] = 200 d[2] = 300 fmt.Println(d) // map[2:300] }
      
      
      • Keys must be immutable
        package main func main() { d := make(map[[]int]int) // Error: invalid map key type []int }
   
   
   3. Values are Unrestricted
      
      package main import "fmt" func main () { // values may be mutable d := make(map[string][]int) a := []int{1,2} d["fred"] = a fmt.Println(d["fred"]) a[1] = 4 fmt.Println(d["fred"]) // sees change in a! }
   
   
   4. Dictionaries are Very Efficient
      As mentioned above, a dictionary's keys are stored as a set. This means that finding where a key is stored takes constant time. This lets us look up a dictionary's value based on a key in constant time too!


5. Some Worked Examples Using Dictionaries
   
   • mostFrequent(L)
     package main import "fmt" func mostFrequent(L []int) int { // Return most frequent element in L, resolving ties arbitrarily maxValue := 0 maxCount := 0 counts := make(map[int]int) for _, elem := range L { _, ok := counts[elem] if !ok { counts[elem] = 1 } else { counts[elem] += 1 } count, _ := counts[elem] if (count > maxCount) { maxCount = count maxValue = elem } } return maxValue } func assert(b bool) {if !b {panic("Assertion Error") }} func main() { fmt.Print("Testing mostFrequent()...") assert(mostFrequent([]int{2,5,3,4,6,4,2,4,5}) == 4) assert(mostFrequent([]int{2,3,4,3,5,3,6,3,7}) == 3) assert(mostFrequent([]int{42}) == 42) fmt.Println("Passed!") }