Hash Maps
What is a hashmap?
 A hash map is an implementation of associative array and supports
O(1)
time access to values.  Uses a hash function to
map
keys to values. A value can be found in theO(1)
time by hashing the key then mapping the hash result to a location in the structure where the value resides.
How to know when to use this data structure?
 Does the problem have repeated work?
 Do you do repeated passes over a linear structure you can rather query by key?
 Do you do dependent passes
O(n^2)
orO(n^3)
time complexity?  Can you cache the precomputed data that will be used later?
Rudimentary understanding
 Take a key, run a hash function on that key and map it to a
hash table
, this is done by runningmod
on the key and determining which index in a table a key should reside.
Collision
 Two keys have the same hash value. To avoid collisions we want hash functions to be uniformly distributed.
Collision reduction

Open addressing  No strict addressing, they can appear in multiple places in the hash table.

linear probing
 If there’s a collision, check the next index directly adjacent to the current key.
 Linearly traverse the hash map and try to find an open position.

quadratic probing
 Similar to linear probing but instead use a quadratic function to jump positions.


Closed addressing  Item is restricted to a certain index. Item must be at that index. What happens here is we start to rely on linked lists to nest keys at that collision in the hash table.
 bucketing
 chaining
Load factor
 When do we resize our hash table. When the load becomes to much thus rendering O(1) time moot.
 Load factor is calculated by
# of items/# of addresses
.
Hash Map signature
class HashMap:
# Initializes an emtpy hash map.
def __init__(self):
# Given a key, will return the value associated with that key if itâ€™s in the table.
# This function will return None if the key is not in the hash map.
# O(1) runtime.
def get(self, key):
# Inserts the keyvalue pair into the hashmap.
# If the key already exists it will overwrite the previous value with the new value.
# O(1) runtime.
def put(self, key, value):
# Returns true if it contains the key.
# O(1) runtime.
def contains(self, key):
# Private function to compute an integer hash value for a given key.
# O(1) runtime.
def _hash(self, key):