Computer Science 15-112, Spring 2012
Class Notes:  Dictionaries (Maps)

1. Required Reading
2. Quick Example
3. Properties of Dictionaries
   1. Dictionaries Map Keys to Values
   2. Keys are Sets
   3. Values are Unrestricted
4. Create a Dictionary
5. Dictionary Operations
6. Example Using Dictionaries

1. Required Reading
   1. The Python Tutorial, Ch 5.5 (Dictionaries)
   2. The Python Standard Library, Ch 5.8 (Mapping Types -- dict)
       
2. Quick Example

   d = dict()
   d["fred"] = "555-1212"
   d["wilma"] = "555-3456"
   print d["fred"]
   # now fred and wilma get married, so...
   d["fred"] = d["wilma"]
   print d["fred"]

3. Properties of Dictionaries
   1. Dictionaries Map Keys to Values
       
   2. Keys are Sets
      Thus...
      1. Keys are unordered, unique, immutable
      2. Dictionaries are efficient
          
   3. Values are Unrestricted
      Thus...  values may be mutable

      # 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. Create a Dictionary

   # 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    # prints {'dog': 98, 'cow': 5, 'cat': 1}
   
   # Create a dictionary from a list of (key, value) pairs with braces syntax
   d = { "cow":5, "dog":98, "cat":1 }
   print d    # prints {'dog': 98, 'cow': 5, 'cat': 1}

5. Dictionary Operations
   This is a partial list.  For the full list, see here.
    
   1. Operations on a dictionary
       

      Operation	Result
      len(d)	Return the number of items (key-value pairs) in the dictionary d.
      d.clear()	Remove all items from the dictionary d.
      d.copy()	Return a shallow copy of the dictionary d.
      d.popitem()	Remove and return an arbitrary (key, value) pair from the dictionary.  If the dictionary is empty, calling popitem() raises a KeyError.
      for key in d	Iterate over all keys in d.  For example: d = { "cow":5, "dog":98, "cat":1 } for key in d:     print key, d[key]

       

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

      Operation	Result
      key in d	Return True if d has a key key, else False.
      key not in d	Equivalent to not key in d.
      d[key]	Return the item of d with key key. Raises a KeyError if key is not in the map.
      get(key[, default])	Return the value for key if key is in the dictionary, else default. If default is not given, it defaults to None, so that this method never raises a KeyError.
      d[key] = value	Set d[key] to value.
      del d[key]	Remove d[key] from d. Raises a KeyError if key is not in the map.

       

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

      Operation	Result
      update([other])	Update the dictionary with the key/value pairs from other, overwriting existing keys. Return None.

       

6. Example Using Dictionaries

   def mostFrequent(a):
       maxValue = None
       maxCount = 0
       counts = dict()
       for element in a:
           count = counts[element] if (element in counts) else 0
           count += 1
           counts[element] = count
           if (count > maxCount):
               maxCount = count
               maxValue = element
       return maxValue
   
   print mostFrequent([2,5,3,4,6,4,2,4,5])  # prints 4
   
   # once again, using get() with default value
   
   def mostFrequent(a):
       maxValue = None
       maxCount = 0
       counts = dict()
       for element in a:
           count = 1 + counts.get(element, 0)
           counts[element] = count
           if (count > maxCount):
               maxCount = count
               maxValue = element
       return maxValue
   
   print mostFrequent([2,5,3,4,6,4,2,4,5])  # prints 4

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem