Back to Study Material Data Structures and Algorithms

Hash Map

A hash map is an abstract data type that associates unique keys with values, providing average O(1) time complexity for insertion, deletion, and lookup. It...

Hash Map

The Key-Value Abstraction

A hash map is an abstract data type that associates unique keys with values, providing average O(1) time complexity for insertion, deletion, and lookup. It is implemented using a hash table internally, but the interface it exposes focuses on the semantic operation of mapping keys to values rather than on the underlying array mechanics.

The defining operations of a hash map are: put(key, value) to associate a value with a key (overwriting any existing value for that key), get(key) to retrieve the value associated with a key, remove(key) to delete the key-value association, containsKey(key) to test whether a key exists, and sometimes keySet() or entrySet() to iterate over all stored pairs.

The uniqueness constraint on keys distinguishes a hash map from a multimap. In a hash map, each key appears at most once. Calling put with an existing key replaces the old value rather than creating a second entry. This makes hash maps suitable for frequency counting, caching, and lookup tables.

A worked example: counting word frequencies in a document. For each word in the document, if the word is already a key in the map, increment its value by 1. Otherwise, insert the word with value 1. This runs in O(n) where n is the number of words, compared to O(n log n) if you sorted the words and counted runs.

Pseudocode: create an empty hash map. For each word w in the document, if map.containsKey(w), map.put(w, map.get(w) plus 1). Else map.put(w, 1). After processing, map.get(w) returns the frequency of word w.

Hash maps appear in the standard libraries of virtually every programming language: HashMap and LinkedHashMap in Java, dict in Python (which maintains insertion order since version 3.7), unordered_map in C++, and Dictionary in C# and Swift.

Time complexity: O(1) average for all operations. O(n) worst case. Space complexity: O(n).

Interview tip: word frequency counting is the canonical hash map example. Be prepared to code it from scratch and to discuss what happens if the document contains punctuation or mixed case, demonstrating attention to real-world details.

Hash Map vs Tree Map

The hash map and the tree map both implement the key-value mapping abstraction but offer fundamentally different performance profiles. Choosing between them correctly is an important practical skill.

A tree map (backed by a balanced binary search tree such as a red-black tree) maintains keys in sorted order and provides O(log n) time for all operations. A hash map provides O(1) average time but does not preserve order.

The ordered nature of a tree map enables operations that a hash map cannot support efficiently. These include: finding the minimum or maximum key in O(log n), finding all keys in a range in O(log n plus k) where k is the number of results, finding the successor or predecessor of a key in O(log n), and iterating over all keys in sorted order in O(n).

A hash map cannot support any of these operations efficiently. Iterating over all keys in a hash map in sorted order requires extracting all keys and sorting them, taking O(n log n). Finding all keys in a range requires examining every key, taking O(n).

Insertion order preservation is a middle ground offered by linked hash maps (Java's LinkedHashMap, Python's regular dict since 3.7). These maintain a doubly linked list connecting entries in insertion order, allowing O(1) iteration in insertion order while retaining O(1) hash map operations.

A worked example: an order-matching engine needs to find the best buy and sell prices (minimum sell and maximum buy) in constant time. A tree map of price to quantity immediately supports this via its minimum and maximum operations. A hash map would require scanning all entries to find these values.

Time complexity comparison: hash map O(1) average, tree map O(log n) guaranteed. Space complexity: both O(n), but tree maps have a larger constant factor due to pointer storage for tree structure.

Interview tip: when asked which data structure to use for a key-value store, ask whether the keys need to be retrieved in sorted order or whether range queries are needed. If yes, use a tree map. If only point lookups, insertions, and deletions are needed, use a hash map.

Practical Hash Map Patterns

Several recurring patterns in algorithm design use hash maps as their core data structure. Recognizing these patterns allows you to quickly identify the right approach when you encounter a new problem.

Two-sum pattern: given an array and a target sum, find two elements that add to the target. The naive O(n squared) solution checks every pair. The hash map solution scans the array once, and for each element x, checks whether (target minus x) is already in the map. If so, the pair is found. Otherwise, insert x into the map. This runs in O(n) time and O(n) space. This pattern generalizes to three-sum and k-sum with additional loops.

Frequency counting pattern: count how many times each element appears. Scan the array and increment the map entry for each element. Then answer queries like most frequent element, elements with frequency above a threshold, or anagram detection in O(1) or O(k) time.

Sliding window with hash map pattern: maintain a hash map of element frequencies within a sliding window. As the window slides, add the new right element and remove the departing left element. This enables O(n) solutions to problems like longest substring without repeating characters and minimum window substring.

Memoization with hash map pattern: use a hash map to cache the results of expensive recursive function calls, converting exponential recursion into polynomial time. This is the top-down dynamic programming approach. The key is the function arguments; the value is the computed result.

A worked example of two-sum: array is 2, 7, 11, 15, target is 9. Scan: process 2, check if 7 is in map (no), insert 2. Process 7, check if 2 is in map (yes), return the pair (2, 7). Total: 2 comparisons instead of up to 6 for brute force.

Time complexity for all patterns above: O(n). Space complexity: O(n).

Interview tip: when you see a problem about pairs, frequencies, or substrings, immediately consider whether a hash map enables an O(n) solution. In most cases it does, and identifying this quickly signals strong pattern recognition to the interviewer.