DSA: Hashing
Learn hash function design, collision resolution strategies, and classic hashing algorithms for frequency counting, two-sum, anagrams, and more.
Hash Functions and Collision Resolution
A hash function maps a key to a bucket index. A good hash function distributes keys uniformly to minimise collisions. When two keys map to the same index, a collision resolution strategy handles the conflict.
Collision Resolution Strategies
Two families exist: chaining stores multiple keys per bucket via a linked list; open addressing finds the next available slot within the table.
- Chaining: each bucket holds a linked list of all colliding keys simple, allows load factor above 1
- Linear probing: on collision at i, try (i+1)%n, (i+2)%n, causes clustering
- Quadratic probing: try i+1², i+2², i+3², reduces primary clustering
- Double hashing: use a second hash function as the step size, best distribution of the three
| Strategy | Avg Lookup | Cache Friendly | Load Factor Limit |
|---|---|---|---|
| Chaining | O(1 + α) | No (linked list) | Any (typically < 1.0) |
| Linear Probing | O(1/(1-α)) | Yes (array) | < 0.7 |
| Quadratic Probing | O(1/(1-α)) | Moderate | < 0.5 |
| Double Hashing | O(1/(1-α)) | Moderate | < 0.7 |
Hash Map Implementation (Chaining)
A chaining hash map uses an array of linked lists. The hash function maps each key to a bucket; the linked list at that bucket stores all key-value pairs that collide there.
Chaining Hash Map
Lookup scans the linked list at the target bucket. With a good hash and low load factor, lists stay short and average lookup is O(1).
- put(key, val): hash key to bucket, scan list for key, update or prepend
- get(key): hash key, scan bucket list, return value or -1 if absent
- Load factor α = n / capacity. Rehash when α exceeds threshold (e.g. 0.75)
- Rehashing: double the capacity, reinsert all existing pairs
Chaining Hash Map
C++Keys 1 and 8 both hash to bucket 1 (mod 7). The bucket list holds both pairs and scans are O(chain length).
Open Addressing: Linear Probing
In linear probing, all entries live in the table array itself. On a collision at index i, try i+1, i+2, ... (mod capacity) until an empty slot is found.
Linear Probing
Simple and cache-friendly, but clusters of occupied slots form over time (primary clustering), increasing average probe length.
- Insert: probe forward from the hash index until an empty or deleted slot is found
- Lookup: probe forward until the key is found or an empty slot is reached
- Delete: mark as DELETED (tombstone) so probes skip it but do not stop
- Keep load factor below 0.7 to limit average probe length
Linear Probing Hash Map
C++Keys 5, 16, and 27 all hash to slot 5 (mod 11). Linear probing places them in consecutive slots 5, 6, 7.
Counting Frequencies
A hash map is the standard tool for counting how often each element appears in a collection. A single pass builds the frequency map in O(n) time.
Frequency Map with unordered_map
unordered_map provides O(1) average insert and lookup. Incrementing freq[key]++ automatically initialises missing keys to 0.
- Single pass: freq[element]++ for each element
- Default value for a missing key in unordered_map is 0 (zero-initialised)
- After building, iterate the map to find most/least frequent, check existence, etc.
- For character frequencies in a string, a fixed int[26] array is faster and simpler
Frequency Counting with unordered_map
C++One pass builds the map. A second pass finds the mode. Both are O(n), and the overall solution is O(n) time, O(n) space.
Two Sum Problem
Find two indices such that their values sum to a target. A hash map reduces the naive O(n²) solution to O(n) by storing each element and checking if its complement already exists.
Two Sum in One Pass
For each element, compute complement = target - element. If the complement is in the map, a valid pair is found. Otherwise, store the current element.
- Map stores: value as key, index as value
- Check complement = target - nums[i] before inserting nums[i]
- If complement found: indices are map[complement] and i
- Time: O(n), Space: O(n)
Two Sum in O(n)
C++Checking for the complement before storing means the map only contains elements seen before the current index.
Subarray with Sum K (Prefix Sum + Hash Map)
Count subarrays whose elements sum to k. A prefix sum hash map tracks how many times each prefix sum has appeared. If prefixSum - k exists in the map, those earlier prefixes form valid subarrays ending at the current index.
Prefix Sum Map
prefixSum[i] - prefixSum[j] = k means the subarray from j+1 to i has sum k. Checking for prefixSum - k in the map finds all such j values instantly.
- Initialise map with {0: 1} to handle subarrays starting from index 0
- At each index: count += map[prefixSum - k], then map[prefixSum]++
- Each map lookup and insert is O(1)
- Time: O(n), Space: O(n)
Subarray Sum Equals K
C++The initial {0:1} entry handles the case where a prefix sum itself equals k (subarray from index 0).
Longest Consecutive Sequence
Find the length of the longest sequence of consecutive integers in an unsorted array. A hash set enables O(1) membership tests, allowing each sequence to be extended in O(n) total.
Start-of-Sequence Detection
Only start counting a sequence from n if n-1 is NOT in the set. This ensures each sequence is counted exactly once from its smallest element.
- Insert all elements into an unordered_set in O(n)
- For each element n, check if n-1 is absent, if so, n is the start of a sequence
- Extend the sequence by checking n+1, n+2, ... until the chain breaks
- Each element is visited at most twice across all sequences: O(n) total
Longest Consecutive Sequence in O(n)
C++Skipping non-starts (where n-1 exists) ensures the inner while loop runs only once per sequence start, keeping total work O(n).
Group Anagrams
Group a list of strings so that all anagrams appear together. Two strings are anagrams when their sorted character sequences are identical, making the sorted string a perfect hash key.
Sorted String as Key
Sort each string's characters to produce a canonical key. All anagrams share the same canonical key and map to the same group.
- Sort each word alphabetically to get its canonical form
- Use an unordered_map keyed by the canonical form
- Append each original word to the vector at its canonical key
- Time: O(n * L log L) where n is the number of words and L is the max word length
Group Anagrams by Sorted Key
C++Sorting each word produces the same canonical string for all anagrams. The map groups them automatically.
First Repeating Element
Find the first element in an array that appears more than once. A hash set tracks seen elements, the first element already in the set when encountered is the answer.
Single-Pass with Hash Set
Traverse left to right and insert each element into a set. The first element already present in the set is the first repeating element.
- O(1) average insert and lookup with unordered_set
- First duplicate found during the single left-to-right pass
- If the array has no duplicates, return -1
- Time: O(n), Space: O(n)
First Repeating Element
C++A single left-to-right pass stops at the first element whose value is already in the seen set.
Knowledge Check
1. What is the average time complexity for lookup in a well-designed hash map?
2. Chaining handles collisions by:
3. In linear probing, a collision at index i is resolved by trying:
4. Rehashing is triggered when the load factor exceeds a threshold because:
5. The Two Sum problem is solved in O(n) using a hash map by:
6. Two strings are anagrams of each other when:
7. To find the longest consecutive sequence in O(n), you use a hash set because:
8. To find a subarray with sum equal to k, you use a prefix sum map where you check for: