Computer Science 15-112, Fall 2011
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

 Dictionaries (Maps)
  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