CITS2200 - Lecture 9

← Back to Home

CITS2200 - Lecture 8
Maps and Dictionaries - Slides

Maps

• A map is a searchable collection of items that are key-value pairs
  • e.g. student number: name → key: value
• Multiple items with the same key are not allowed

Main operations for a map:

• Searching
• Inserting
• Deletion of items

Dictionaries

• Implementation of maps in Python through the dict class
  • Most significant data structure in Python!
• Unique keys are mapped to associated values

Dictionary → refers to Python’s implementation of the abstract data type that is a map

Map ADT Using dict Syntax in Python

M = {} # create empty map
M[k] # return value v associated with key k
M[k] = v # assign/replace value v with key k 
del M[k] / M.pop(k, default) # remove item with key k
len(M) # return number of items in map M
iter(M): # generate sequence of keys in map M

More map operations:

k in M # return True if map contains item with key k
M.get(k, d=None) # return M[k] or d if k does not exist
M.setdefault(k, d) # set rule above for all get operations
M.pop(k, d=None) # remove item and return v if k exists or return d if k does not exist

Even more map operations:

M.popitem() # remove + return an arbitrary (k, v) pair  
M.clear() # remove all entries  
M.keys() # return view of all keys  
M.values() # return view of all values  
M.items() # return view of (key, value) pairs  
M.update(M2) # add/update entries from another map  
M == M2 # return True if same key-value pairs  
M != M2 # return True if maps differ

Simple List-Based Map

• Can efficiently implement a map using an unsorted list
• Used instead of dict class:

M = [("a", 1), ("b", 2), ("c", 3)]

• Every value is a (key, value) tuple

Performance:

• Inserting item takes $O(1)$ time $-$ can insert item at beginning or end
  • This is because the list is unsorted!
• Searching for or removing an item takes $O(n)$ time → in worst case

This unsorted list implementation is effective only for maps of small size or for maps in which insertions are the most common operations, while searches and removals are rarely performed

---

CITS2200 - Lecture 10