The HashMap Data Structure
Overview
- Use a hash function to map keys to values.
- Each keys is associated with a list of values
- These values, when hashed, give the key
- Implemented with an array of lists
- Each key corresponds to a slot in the array containing the list of its values
- Automatically resize themselves to maintain constant average insertion and lookup times
When to Use HashMaps
- When caching data
- When creating a dictionary of terms/values
- Keeping track of which nodes have been visited in a depth-first or breadth-first search of a graph.
Time Complexity & Space Complexity
| Operation | Average Time Complexity |
|---|---|
| Indexing | N/A |
| Search | O(1) |
| Insertion | O(1) |
| Deletion | O(1) |
The worst space complexity of a HashMap is O(n).
HashMap Concept Review
A useful summary of HashMap concepts to review can be found here.