CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Dictionaries
Learning Goal: represent and modify data using dictionaries. In particular:
- Create and access dictionaries and their keys and values
- Recognize the difference between indexing in lists and using keys in dictionaries.
- Understand why dictionaries are efficient
- Quick Example
- Creating Dictionaries
- Using Dictionaries
- Properties of Dictionaries
- Dictionaries Map Keys to Values
- Keys are Sets
- Values are Unrestricted
- Dictionaries are Very Efficient
- 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) - 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!
- Create an empty dictionary
- 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
- Properties of Dictionaries
- 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]) - 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'
- Keys are unordered
- 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' - 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!
- Dictionaries Map Keys to Values
- Check 7.3
- Some Worked Examples Using Dictionaries
We'll go over these in class.