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
mapkeys to values. A value can be found in the
O(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
- Can you cache the precomputed data that will be used later?
- Take a key, run a hash function on that key and map it to a
hash table, this is done by running
modon the key and determining which index in a table a key should reside.
- Two keys have the same hash value. To avoid collisions we want hash functions to be uniformly distributed.
Open addressing - No strict addressing, they can appear in multiple places in the hash table.
- 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.
- 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.
- 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 key-value 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):