Hash Table Fundamentals
A hash table, also known as a hash map, is a data structure that maps keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. This mechanism allows for highly efficient data retrieval and storage, often achieving average O(1) time complexity for insertions, deletions, and lookups.
The Essence of Hashing
The core principle behind a hash table is transforming a given key into an array index. This transformation is performed by a hash function. For example, if you want to store student records and quickly check if a student is enrolled, a hash function could take the student's name (the key) and convert it into a numerical index. This index then points directly to the location where the student's data might be stored in an underlying array.
A typical hash function first generates a hash code from the key, which is a numerical representation of the key. This hash code is then usually modulated by the size of the internal array to produce a valid index. Different data types require specific encoding methods to generate these unique hash codes.
Managing Hash Collisions
A critical challenge in hash table design arises when two distinct keys produce the same hash code and thus map to the same array index. This event is called a hash collision. For instance, if both "Alice Smith" and "Bob Jones" hash to index 1, a collision occurs. Efficient collision resolution strategies are vital for a hash table's performance. Two primary methods are:
Chaining
In the chaining method, each slot in the hash table array points to the head of a linked list. When a collision occurs, the new element is simply added to the linked list at the corresponding index. So, if "Alice Smith" and "Bob Jones" both map to index 1, they would both reside in the linked list associated with array slot 1.
Open Addressing (Linear Probing)
With open addressing, all elements are stored directly within the hash table array itself. When a collision occurs (i.e., the target index is already occupied), the algorithm searches for the next available empty slot in the array. Linear probing specifically checks the next sequential index (index + 1, index + 2, etc.) until an empty slot is found. A crucial requirement for open addressing schemes is that the table size must always be larger than the number of elements stored to ensure there are always available slots to resolve collisions.
Common Hash-Based Data Structures
When solving algorithmic problems, several data structures leverage hashing or provide similar key-based access patterns:
- Arrays: Can be used directly if keys are integers within a manageable range.
- Sets: Store unique elements and allow fast membership testing.
- Maps: Store key-value pairs and allow fast value retrieval based on a key.
C++ Standard Library Implementations: Sets and Maps
The C++ Standard Library offers different implementations for sets and maps, with varying underlying mechanisms and performance characteristics:
std::unordered_setandstd::unordered_map: These are implemented using hash tables. They offer average O(1) time complexity for insertions, deletions, and lookups. However, elements are not stored in any particular order.std::setandstd::map: These are implemented using self-balancing binary search trees, specifically red-black trees. They guarantee logarithmic O(log N) time complexity for operations, and critically, elements (or keys in a map) are always stored in sorted order. While not hash tables, their key-based access paradigm makes them suitable for many "hashing" style problems where order or specific tree properties are beneficial.
When selecting between these, prioritize unordered_set/unordered_map for optimal average-case performance if element order is not a concern. If sorted order is required, set/map are the appropriate choices. Similarly, std::multiset and std::multimap allow for duplicate elements/keys while maintaining sorted order via red-black trees.
Note that older C++ compilers or unofficial libraries might have provided hash_set and hash_map. However, unordered_set and unordered_map were standardized in C++11 and are the preferred, official way to use hash table functionality in modern C++.
Essential Functions for C++ Standard Library Sets
Below are some frequently used member functions for std::set and std::unordered_set (some functions like lower_bound/upper_bound are specific to ordered sets).
| Function | Description | Example Usage |
|---|---|---|
insert() |
Adds an element to the set. | mySet.insert(value); |
erase() |
Removes an element or a range of elements. | mySet.erase(value); or mySet.erase(iterator); |
find() |
Searches for an element and returns an iterator to it, or end() if not found. |
auto iter = mySet.find(value); |
count() |
Returns 1 if the element is present, 0 otherwise (for set/unordered_set). |
size_t cnt = mySet.count(value); |
size() |
Returns the number of elements in the set. | size_t currentSize = mySet.size(); |
empty() |
Checks if the set contains no elements. | bool isEmpty = mySet.empty(); |
clear() |
Removes all elements from the set. | mySet.clear(); |
begin() |
Returns an iterator to the first element. | auto iter = mySet.begin(); |
end() |
Returns an iterator to the element past the last element. | auto iter = mySet.end(); |
Essential Functions for C++ Standard Library Maps
Here are common member functions for std::map and std::unordered_map:
| Function | Description | Example Usage |
|---|---|---|
insert() |
Inserts a key-value pair. | myMap.insert({key, value}); |
erase() |
Removes a key-value pair based on key or iterator. | myMap.erase(key); or myMap.erase(iterator); |
find() |
Searches for a key and returns an iterator to its pair, or end() if not found. |
auto iter = myMap.find(key); |
count() |
Returns 1 if the key is present, 0 otherwise (for map/unordered_map). |
size_t cnt = myMap.count(key); |
size() |
Returns the number of key-value pairs. | size_t currentSize = myMap.size(); |
empty() |
Checks if the map is empty. | bool isEmpty = myMap.empty(); |
clear() |
Removes all key-value pairs. | myMap.clear(); |
begin() |
Returns an iterator to the first key-value pair. | auto iter = myMap.begin(); |
end() |
Returns an iterator to the element past the last key-value pair. | auto iter = myMap.end(); |
at() |
Returns a reference to the value associated with a key (throws if key not found). | int val = myMap.at(key); |
operator[] |
Returns a reference to the value associated with a key (inserts default-constructed value if key not found). | int val = myMap[key]; |
Practical Algorithm Problems with Hash Tables
- Valid Anagram
Problem: Given two strings s and t, determine if t is an anagram of s. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
#include <string>
#include <unordered_map>
class Solution {
public:
bool isAnagram(std::string s, std::string t) {
if (s.length() != t.length()) {
return false; // Anagrams must have the same length
}
std::unordered_map<char, int> charCounts;
// Count character frequencies in string s
for (char ch : s) {
charCounts[ch]++;
}
// Decrement counts for characters in string t
// If a character in t is not in s or its count drops below zero, it's not an anagram
for (char ch : t) {
if (charCounts.find(ch) == charCounts.end() || charCounts[ch] == 0) {
return false; // Character not found or already depleted
}
charCounts[ch]--;
}
// After processing both strings, all counts should be zero
// This check is actually redundant if the lengths are checked upfront and decrements are validated
// However, a final check for safety or if the decrement logic was simpler might be useful
// for (auto const& [key, val] : charCounts) {
// if (val != 0) {
// return false;
// }
// }
return true;
}
};
- Intersection of Two Arrays
Problem: Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique.
#include <vector>
#include <unordered_set>
class Solution {
public:
std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
// Store unique elements of nums1 in a hash set for efficient lookups
std::unordered_set<int> uniqueElements1(nums1.begin(), nums1.end());
std::vector<int> commonElements;
std::unordered_set<int> resultSet; // To ensure unique elements in the result
// Iterate through nums2 and check if elements exist in uniqueElements1
for (int val : nums2) {
if (uniqueElements1.count(val) > 0) { // Check if 'val' is in uniqueElements1
// Add to result set if not already present
resultSet.insert(val);
}
}
// Convert the result set to a vector
for (int val : resultSet) {
commonElements.push_back(val);
}
return commonElements;
}
};
- Intersection of Two Arrays II
Problem: Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result should appear as many times as it shows in both arrays. The result can be in any order.
#include <vector>
#include <unordered_map>
class Solution {
public:
std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
// Use a map to store counts of elements in the first array
std::unordered_map<int, int> elementFrequencies;
for (int numVal : nums1) {
elementFrequencies[numVal]++;
}
std::vector<int> intersectionResult;
// Iterate through the second array
for (int numVal : nums2) {
// If the element exists in the map and its count is greater than zero
if (elementFrequencies.count(numVal) > 0 && elementFrequencies[numVal] > 0) {
intersectionResult.push_back(numVal); // Add to the result
elementFrequencies[numVal]--; // Decrement its count
}
}
return intersectionResult;
}
};
- Happy Number
Problem: Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
#include <unordered_set>
class Solution {
private:
// Helper function to calculate the sum of squares of digits
int sumOfSquaredDigits(int number) {
int totalSum = 0;
while (number > 0) {
int digit = number % 10;
totalSum += digit * digit;
number /= 10;
}
return totalSum;
}
public:
bool isHappy(int n) {
std::unordered_set<int> seenNumbers; // To detect cycles
int currentNumber = n;
// Continue until the number is 1 or a cycle is detected
while (currentNumber != 1) {
// If we have seen this number before, it means we are in a cycle
if (seenNumbers.count(currentNumber) > 0) {
return false; // Not a happy number
}
// Add the current number to the set of seen numbers
seenNumbers.insert(currentNumber);
// Calculate the next number in the sequence
currentNumber = sumOfSquaredDigits(currentNumber);
}
return true; // The number eventually reached 1, so it's happy
}
};
- Two Sum
Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Assume that each input would have exactly one solution, and you may not use the same element twice.
#include <vector>
#include <unordered_map>
class Solution {
public:
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::unordered_map<int, int> complementMap; // Stores number -> its index
for (int i = 0; i < nums.size(); ++i) {
int currentNum = nums[i];
int requiredComplement = target - currentNum;
// Check if the required complement already exists in the map
if (complementMap.count(requiredComplement) > 0) {
// Found the pair! Return their indices
return {complementMap[requiredComplement], i};
}
// If not found, add the current number and its index to the map
complementMap[currentNum] = i;
}
// This part should not be reached based on problem constraints (exactly one solution)
return {};
}
};
- 4Sum II
Problem: Given four lists of integers nums1, nums2, nums3, and nums4, return the number of tuples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.
#include <vector>
#include <unordered_map>
class Solution {
public:
int fourSumCount(std::vector<int>& numsA, std::vector<int>& numsB, std::vector<int>& numsC, std::vector<int>& numsD) {
std::unordered_map<int, int> sumABCounts; // Stores sum (A[i]+B[j]) -> count
// Calculate all possible sums of elements from numsA and numsB
// and store their frequencies in the map
for (int valA : numsA) {
for (int valB : numsB) {
sumABCounts[valA + valB]++;
}
}
int totalTuples = 0;
// Iterate through numsC and numsD
// For each pair (valC, valD), calculate the required complement: -(valC + valD)
// Look up this complement in sumABCounts
for (int valC : numsC) {
for (int valD : numsD) {
int requiredSum = -(valC + valD);
// If the required sum exists in our map, add its frequency to the total count
if (sumABCounts.count(requiredSum) > 0) {
totalTuples += sumABCounts[requiredSum];
}
}
}
return totalTuples;
}
};
- Ransom Note
Problem: Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine, and false otherwise. Each letter in magazine can only be used once in ransomNote.
#include <string>
#include <unordered_map>
class Solution {
public:
bool canConstruct(std::string ransomNote, std::string magazine) {
// A simple frequency map for characters available in the magazine
std::unordered_map<char, int> magazineCharSupply;
// Populate the map with character counts from the magazine
for (char character : magazine) {
magazineCharSupply[character]++;
}
// Iterate through the ransom note
for (char characterNeeded : ransomNote) {
// Check if the character is available in the magazine and its count is positive
if (magazineCharSupply.find(characterNeeded) == magazineCharSupply.end() || magazineCharSupply[characterNeeded] == 0) {
return false; // Character not available or supply exhausted
} else {
magazineCharSupply[characterNeeded]--; // Consume one instance of the character
}
}
return true; // All characters for the ransom note were successfully found and used
}
};
- Three Sum
Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
#include <vector>
#include <algorithm> // For std::sort
class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& numbers) {
std::vector<std::vector<int>> resultTriplets;
int numSize = numbers.size();
if (numSize < 3) return resultTriplets;
// Sort the array to efficiently use the two-pointer approach and handle duplicates
std::sort(numbers.begin(), numbers.end());
// Iterate through each number as the first element of a potential triplet
for (int i = 0; i < numSize - 2; ++i) {
// Optimization: If current number is positive, sum cannot be zero with other non-negative numbers
if (numbers[i] > 0) break;
// Skip duplicate values for the first element
if (i > 0 && numbers[i] == numbers[i-1]) {
continue;
}
int targetSum = -numbers[i]; // We need two other numbers that sum to -numbers[i]
int leftPtr = i + 1;
int rightPtr = numSize - 1;
// Use two pointers for the remaining sub-array
while (leftPtr < rightPtr) {
int currentSum = numbers[leftPtr] + numbers[rightPtr];
if (currentSum < targetSum) {
leftPtr++; // Need a larger sum
} else if (currentSum > targetSum) {
rightPtr--; // Need a smaller sum
} else {
// Found a triplet!
resultTriplets.push_back({numbers[i], numbers[leftPtr], numbers[rightPtr]});
// Skip duplicate values for the second element
while (leftPtr < rightPtr && numbers[leftPtr] == numbers[leftPtr + 1]) {
leftPtr++;
}
// Skip duplicate values for the third element
while (leftPtr < rightPtr && numbers[rightPtr] == numbers[rightPtr - 1]) {
rightPtr--;
}
// Move pointers to search for next distinct triplet
leftPtr++;
rightPtr--;
}
}
}
return resultTriplets;
}
};
- Four Sum
Problem: Given an array nums of n integers, return an array of all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that 0 <= a, b, c, d < n, a, b, c, and d are distinct, and nums[a] + nums[b] + nums[c] + nums[d] == target. The solution set must not contain duplicate quadruplets.
#include <vector>
#include <algorithm> // For std::sort
class Solution {
public:
std::vector<std::vector<int>> fourSum(std::vector<int>& inputNums, int target) {
std::vector<std::vector<int>> foundQuadruplets;
int arrayLength = inputNums.size();
if (arrayLength < 4) return foundQuadruplets;
std::sort(inputNums.begin(), inputNums.end());
// Outer loop for the first element
for (int i = 0; i < arrayLength - 3; ++i) {
// Skip duplicate values for the first element
if (i > 0 && inputNums[i] == inputNums[i-1]) {
continue;
}
// Optimization to potentially break early if min possible sum is already too large
if ((long long)inputNums[i] + inputNums[i+1] + inputNums[i+2] + inputNums[i+3] > target) {
break;
}
// Optimization to skip if max possible sum with current inputNums[i] is too small
if ((long long)inputNums[i] + inputNums[arrayLength-1] + inputNums[arrayLength-2] + inputNums[arrayLength-3] < target) {
continue;
}
// Second loop for the second element
for (int j = i + 1; j < arrayLength - 2; ++j) {
// Skip duplicate values for the second element
if (j > i + 1 && inputNums[j] == inputNums[j-1]) {
continue;
}
// More optimizations
if ((long long)inputNums[i] + inputNums[j] + inputNums[j+1] + inputNums[j+2] > target) {
break;
}
if ((long long)inputNums[i] + inputNums[j] + inputNums[arrayLength-1] + inputNums[arrayLength-2] < target) {
continue;
}
long long remainingTarget = (long long)target - inputNums[i] - inputNums[j];
int leftPointer = j + 1;
int rightPointer = arrayLength - 1;
// Two-pointer approach for the third and fourth elements
while (leftPointer < rightPointer) {
long long currentTwoSum = (long long)inputNums[leftPointer] + inputNums[rightPointer];
if (currentTwoSum < remainingTarget) {
leftPointer++;
} else if (currentTwoSum > remainingTarget) {
rightPointer--;
} else {
// Found a quadruplet!
foundQuadruplets.push_back({inputNums[i], inputNums[j], inputNums[leftPointer], inputNums[rightPointer]});
// Skip duplicate values for the third element
while (leftPointer < rightPointer && inputNums[leftPointer] == inputNums[leftPointer + 1]) {
leftPointer++;
}
// Skip duplicate values for the fourth element
while (leftPointer < rightPointer && inputNums[rightPointer] == inputNums[rightPointer - 1]) {
rightPointer--;
}
// Move pointers for the next search
leftPointer++;
rightPointer--;
}
}
}
}
return foundQuadruplets;
}
};