What we often refer to as a HashMap is actually called a HashTable, but feel free to use them interchangeably. This is a data structure that associates a Value with a Key. Hash Tables use a hash function to compute the index, this is known as a HashCode, and the input for the hash function is the key. So when you use the key for lookup, it reproduces the same hash and returns the same index thus returning the requested value.
Hashing is a common space-time tradeoff, because it saves time by avoiding a linear search through the table like we would with an array, but that comes at the cost of space…
Collision handling
In the case of HashCollisions, when different keys produce the same hash, there are a number of collision resolution techniques that can be used.
- Separate chaining: uses a LinkedLists for each value, so that it stores all the collided items.
- Open addressing: All entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found. // We covered this in COMP3760
Implementations
| Language | API |
|---|---|
| C++ | std::unordered_map |
| Java | java.util.Map. Use java.util.HashMap |
| Python | dict |
| JavaScript | Object or Map |
Time complexity
| Operation | Big-O | Note |
|---|---|---|
| Access | N/A | Accessing not possible as the hash code is not known |
| Search | O(1)* | |
| Insert | O(1)* | |
| Remove | O(1)* | |
| *This is the average case, there are “freak” cases but these are uncommon and often unprioritized in contexts such as interviews. |
Common problems
These are problems you may be asked where using a hash table is key.
- Describing the implementation of a Least-Used cache, and its Big-O.
- A question involving an API’s integration with hash map where the buckets of hash map are made up of linked lists. //unsure about this one
Essential questions
Recommended practice questions
Try these after you complete the essentials.