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

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

1. Quick Example
   stateMap = { 'pittsburgh':'PA', 'chicago':'IL', 'seattle':'WA', 'boston':'MA' } city = input("Enter a city name --> ").lower() if (city in stateMap): print(city.title(), "is in", stateMap[city]) else: print("Sorry, never heard of it.")
   
   Another Example:
   counts = dict() while True: n = int(input("Enter an integer (0 to end) --> ")) if (n == 0): break if (n in counts): counts[n] += 1 else: counts[n] = 1 print("I have seen", n, "a total of", counts[n], "time(s)") print("Done, counts:", counts)


2. Creating Dictionaries
   • Create an empty dictionary
     d = dict() print(d) # prints {}
   
   
   • Create an empty dictionary using braces syntax
     d = { } print(d) # prints {}
   
   
   • Create a dictionary from a list of (key, value) pairs
     pairs = [("cow", 5), ("dog", 98), ("cat", 1)] d = dict(pairs) print(d) # unpredictable order!
   
   
   • Statically-allocate a dictionary
     d = { "cow":5, "dog":98, "cat":1 } print(d) # ditto!


3. Properties of Dictionaries
   1. Dictionaries Map Keys to Values
      
      ages = dict() key = "fred" value = 38 ages[key] = value # "fred" is the key, 38 is the value print(ages[key])
   
   
   2. Keys are Sets
      
      • Keys are unordered
        d = dict() d[2] = 100 d[4] = 200 d[8] = 300 print(d) # unpredictable order
      
      
      • Keys are unique
        d = dict() d[2] = 100 d[2] = 200 d[2] = 400 print(d) # { 2:400 }
      
      
      • Keys must be immutable
        d = dict() a = [1] # lists are mutable, so... d[a] = 42 # Error: unhashable type: 'list'
   
   
   3. Values are Unrestricted
      
      # values may be mutable d = dict() a = [1,2] d["fred"] = a print(d["fred"]) a += [3] print(d["fred"]) # sees change in a! # but keys may not be mutable d[a] = 42 # TypeError: unhashable type: 'list'
   
   
   4. Dictionaries are Very Efficient
      Similar to sets, for the same reasons, dictionaries are very efficient.


4. Dictionary Operations
   Dictionary operations are provided via operators, functions, and methods in Python as follows (this is a partial list, for a full list, see here):
   
   
   1. Operations on a dictionary
      
      

      Operation	Result	Example
      len(d)	the number of items (key-value pairs) in dictionary d	d = { 1:[1,2,3,4,5], 2:"abcd" } print(len(d))
      d.copy()	new dictionary with a shallow copy of d	d1 = { 1:"a" } d2 = d1.copy() d1[2] = "b" print(d1) print(d2)
      d.popitem()	remove and return an arbitrary (key,value) pair from d; raises KeyError if empty	d = { 1:"a", 2:"b" } print(d.popitem()) # unpredictable! print(d)
      d.clear()	remove all items from dictionary d	d = { 1:"a", 2:"b" } d.clear() print(d, len(d))
      for key in d	Iterate over all keys in d.	d = { 1:"a", 2:"b" } for key in d: print(key, d[key])

   
   
   2. Operations on a dictionary and a key [and value]
      
      

      Operation	Result	Example
      key in d	test if d has the given key	d = { 1:"a", 2:"b" } print(0 in d) print(1 in d) print("a" in d) # surprised?
      key not in d	test if d does not have the given key	d = { 1:"a", 2:"b" } print(0 not in d) print(1 not in d) print("a" not in d)
      d[key]	the item of d with the given key. Raises a KeyError if key is not in the map.	d = { 1:"a", 2:"b" } print(d[1]) print(d[3]) # crash!
      d[key] = value	set d[key] to value.	d = { 1:"a", 2:"b" } print(d[1]) d[1] = 42 print(d[1])
      get(key[,default])	the value for key if key is in the dictionary, else default (or None if no default is provided).	d = { 1:"a", 2:"b" } print(d.get(1)) # works like d[1] here print(d.get(1, 42)) # default is ignored print(d.get(0)) # doesn't crash! print(d.get(0, 42)) # default is used
      del d[key]	remove d[key] from d. Raises KeyError if key not in d.	d = { 1:"a", 2:"b" } print(1 in d) del d[1] print(1 in d) del d[1] # crash!

   
   
   3. Operations on two dictionaries (or a dictionary and an iterable)
      
      

      Operation	Result	Example
      d1.update(d2)	update the dictionary with the key/value pairs from other, overwriting existing keys.	d1 = { 1:"a", 2:"b" } d2 = { 2:"c", 3:"d" } d1.update(d2) d2[4] = "e" print(d1) print(d2)



5. Some Worked Examples Using Dictionaries
   
   • mostFrequent(L)
   • isAnagram(s1, s2)