CMU 15-110: Principles of Computing
Maps (Dictionaries)

1. Motivating Examples
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. Example: isAnagram with a Dictionary

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


2. Creating Dictionaries
   • Create an empty dictionary
     d = dict() print(d)
   
   
   • Create a dictionary with some values in it
     d = { 'cow':5, 'dog':98, 'cat':1 } print(d['cow']) print(d)


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 must be immutable
      
      d = dict() a = [1] # lists are mutable, so... d[a] = 42 # Error: unhashable type: 'list'
   
   
   3. Values may be mutable
      
      d = dict() s = 'fred' a = [1,2] # This works with a mutable value because the key is immutable: d[s] = a print('We get to here') # But this fails because the key is mutable: d[a] = s print('But not to here')
   
   
   4. Dictionaries are Very Efficient
      As with sets, dictionaries are very efficient.


4. Dictionary Operations
   

   Operation	Result
   len(d)	the number of keys in d
   for key in d	loop over each key in d
   key in d	test if d has the given key
   key not in d	test if d does not have the given key
   d[key]	get the value that is associated with the given key. Raises a KeyError if key is not in d.
   d[key] = value	set d[key] to value (replace old value if there was one)



5. Example: isAnagram with a Dictionary
   Compare this solution to our earlier version here:
   def letterCounts(s): # improved version now returns a dictionary instead of a list, # and now uses the character as the key, instead of (ord(c) - ord('A') counts = dict() for c in s.upper(): if ((c >= 'A') and (c <= 'Z')): if (c in counts): counts[c] += 1 else: counts[c] = 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()