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

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! 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 {} # We can also use empty braces 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. Using Dictionaries
# We can interact with dictionaries in a similar way to lists/sets d = { "a" : 1, "b" : 2, "c" : 3 } print(len(d)) # prints 3, the number of key-value pairs print("a" in d) # prints True print(2 in d) # prints False - we check the keys, not the values print(2 not in d) # prints True print("a" not in d) # prints False print(d["a"]) # finds the value associated with the given key. Crashes if the key is not in d print(d.get("z", 42)) # finds the value of the key if the key is in the dictionary, # or returns the second (default) value if the key is not in d d["e"] = "wow" # adds a new key-value pair to the dictionary, or updates the value of a current key del d["e"] # removes the key-value pair specified from the dictionary. Crashes if the key is not in d for key in d: print(key, d[key]) # we can iterate over the keys, then print out the keys or corresponding values

4. 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 = 100 d = 200 d = 300 print(d) # unpredictable order

• Keys are unique
d = dict() d = 100 d = 200 d = 400 print(d) # { 2:400 }

• Keys must be immutable
d = dict() a =  # 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 +=  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
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)
def mostFrequent(L): # Return most frequent element in L, resolving ties arbitrarily. maxValue = None maxCount = 0 counts = dict() for element in L: count = 1 + counts.get(element, 0) counts[element] = count if (count > maxCount): maxCount = count maxValue = element return maxValue def testMostFrequent(): print("Testing mostFrequent()... ", end="") assert(mostFrequent([2,5,3,4,6,4,2,4,5]) == 4) assert(mostFrequent([2,3,4,3,5,3,6,3,7]) == 3) assert(mostFrequent() == 42) assert(mostFrequent([]) == None) print("Passed!") testMostFrequent()

• isAnagram(s1, s2)
Here we rewrite the 1d-list isAnagram example only using a dictionary instead.
def letterCounts(s): counts = dict() for ch in s.upper(): if ((ch >= "A") and (ch <= "Z")): counts[ch] = counts.get(ch, 0) + 1 return counts def isAnagram(s1, s2): return (letterCounts(s1) == letterCounts(s2)) def testIsAnagram(): print("Testing isAnagram()...", end="") assert(isAnagram("", "") == True) assert(isAnagram("abCdabCd", "abcdabcd") == True) assert(isAnagram("abcdaBcD", "AAbbcddc") == True) assert(isAnagram("abcdaabcd", "aabbcddcb") == False) print("Passed!") testIsAnagram()