CMPSC 122 Chapter Notes - Chapter 10: Lookup Table, Associative Array, Memory Stick
7 Nov 2016
School
Department
Course
Professor
● 10.1: Maps and Dictionaries
○ python's dict class represents a dictionary
○ dictionaries map keys to values
■ this is referred to as an associative array or map
■ keys are assumed unique but values may not be
■ syntax similar to arrays dict[key] = value
○ examples of dictionaries:
■ university ID system
■ DNS
■ social media
■ computer graphics color mapping
○ map ADT
■ M[k] should return the value associated with key k
■ M[k] = v should assign the value v to key k
■ del M[k] should remove the item whose key is k (use __delitem__)
■ len(M) should return number of items in M
■ iter(M) should produce a sequence of keys
■ should also support:
● k in M (returns true if M contains key k)
● M.get(k, d=None) returns default value d if key k is not in the map
● M.setdefault(k, d) sets default d
● M.pop(k, d=None) remove the item at key k and return its value
● M.popitem() pops an arbitrary key-value pair from the map and
returns them both in a tuple
● M.clear() clears the map
● M.keys() returns all keys
● M.values() returns all values
● M.items() returns all key-value pairs
● M.update(M2) copies assignments from M2 to M
● M == M2 returns true if M and M2 have identical associations
■ python provides Mapping and MutableMapping base classes that can be
extended to help in the creation of user-defined maps
● 10.2: Hash Tables
○ hash maps are used in the implementation of the python dictionary
○ keys as indices with syntax M[k]
○ lookup table: stores the conversion between a key and an array index
○ hash function used to convert keys to array indices
○ bucket arrays are used to allow multiple keys to assign to the same index in the
lookup table
○ hash functions
■ map each key k to an integer in range 0,N-1
■ if two or more keys hash to the same value, multiple items will be stored
in the bucket
● this is referred to as a collision
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Dictionaries map keys to values this is referred to as an associative array or map. Keys are assumed unique but values may not be. Syntax similar to arrays dict[key] = value. M[k] should return the value associated with key k. M[k] = v should assign the value v to key k. Del m[k] should remove the item whose key is k (use __delitem__) Should also support: len(m) should return number of items in m iter(m) should produce a sequence of keys. K in m (returns true if m contains key k) M. get(k, d=none) returns default value d if key k is not in the map. M. pop(k, d=none) remove the item at key k and return its value. M. popitem() pops an arbitrary key-value pair from the map and returns them both in a tuple. M. update(m2) copies assignments from m2 to m. M == m2 returns true if m and m2 have identical associations.
