Comprehensive Guide to Hashing
1. What is Hashing?
Hashing is a process used to convert data (like a string or number) into a fixed-size numerical value known as a hash value or hash code. This hash value is used as
an index to store and retrieve data in data structures like hash maps and hash sets.
Key Points:
Hashing allows us to quickly retrieve or store data using a unique hash value.
Hashing is used in many algorithms and data structures to improve efficiency.
2. How Does Hashing Work?
A hash function takes input data (a string, number, etc.) and returns a fixed-size hash value. This hash value is used as an index or address in the hash table or hash
map.
Example: Hashing a String
Let’s hash the string "Apple" :
Key = "Apple"
Hash("Apple") = 123456
Here, the hash function takes "Apple" and outputs a numerical value 123456 . This hash value can then be used as an index to store or retrieve the associated data
(e.g., "Apple").
3. Hash Map and Hash Set
What is a Hash Map?
A hash map (also called a dictionary or unordered_map ) is a data structure that stores key-value pairs. You can quickly access a value by using its key, thanks to the
hash function.
Example:
Key: "Apple"
Value: "100 calories"
The hash map maps the key "Apple" to its value "100 calories" . We use the hash value of the key "Apple" to store and access the associated value in
constant time.
What is a Hash Set?
A hash set is similar to a hash map, but it only stores keys and ensures that the keys are unique. You can use a hash set to check for the existence of an element
quickly.
Example:
Hash Set: {"Apple", "Banana", "Orange"}
You can quickly check if "Apple" exists in the set using its hash value.
4. Time Complexity of Hashing Operations
The main advantage of using hash maps and hash sets is their ability to perform operations like insert, lookup, and delete in constant time O(1) on average.
Average Time Worst Case Time
Operation
Complexity Complexity
Insert O(1) O(n)
Lookup O(1) O(n)
Average Time Worst Case Time
Operation
Complexity Complexity
Delete O(1) O(n)
Why Average Case vs Worst Case?
Average Case (O(1)) : This assumes that the hash function distributes the keys evenly across the hash table. This means that each key has a unique index, and
collisions are rare.
Worst Case (O(n)): If many keys hash to the same index (i.e., a collision), the hash map or hash set can degrade into a linked list, causing the operations to
take linear time O(n).
5. Handling Collisions
A collision occurs when two different keys hash to the same index. This is a natural problem in hashing and can be handled in a couple of ways.
Common Methods for Handling Collisions:
1. Chaining :
Store multiple elements at the same index using a secondary data structure (e.g., a linked list or another hash set).
Example: If both "Apple" and "Banana" hash to the same index, they will be stored in a linked list at that index.
2. Open Addressing:
If a collision occurs, the system finds the next available index and stores the element there (using probing ).
Example: If "Apple" hashes to index 5 , and a collision occurs, the system tries index 6 next, and so on.
6. Hashing in Practice: Use Cases
Example 1: Frequency Counter
Problem: Given an array of integers, find the frequency of each element.
Brute Force Solution:
for(int i = 0; i < n; i++) {
int count = 0;
for(int j = 0; j < n; j++) {
if(arr[i] == arr[j]) {
count++;
}
}
cout << arr[i] << ": " << count << endl;
}
Time Complexity : O(n²) , because we check each pair of elements.
Space Complexity : O(1), because we only use a few variables.
Optimized Solution (Using Hash Map):
unordered_map<int, int> freq;
for(int i = 0; i < n; i++) {
freq[arr[i]]++;
}
for(auto& pair : freq) {
cout << [Link] << ": " << [Link] << endl;
}
Time Complexity : O(n), because we only pass through the array once, and each hash map operation (insert) takes O(1).
Space Complexity : O(n), because we store the frequency of each element.
Example 2: Duplicate Detection
Problem: Check if an array contains duplicates.
Brute Force Solution:
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(arr[i] == arr[j]) {
return true; // Duplicate found
}
}
}
return false; // No duplicates
Time Complexity : O(n²) , because we compare each pair of elements.
Space Complexity : O(1).
Optimized Solution (Using Hash Set):
unordered_set<int> seen;
for(int i = 0; i < n; i++) {
if([Link](arr[i]) != [Link]()) {
return true; // Duplicate found
}
[Link](arr[i]);
}
return false; // No duplicates
Time Complexity : O(n), because we only pass through the array once, and each hash set operation (insert, lookup) takes O(1).
Space Complexity : O(n), because we store each element in the hash set.
7. Hash Map vs Tree Map
Hash Map (O(1)) : Uses a hash function to calculate the index for storing keys and values.
Time Complexity : O(1) on average, but O(n) in the worst case (due to collisions).
Provides fast lookups, but no guaranteed order of the keys.
Commonly used in unordered collections.
Tree Map (O(log n)) : Uses a balanced tree structure (like a Red-Black Tree) to maintain order.
Time Complexity : O(log n) for insertion, lookup, and deletion.
Sorted keys (keys are ordered).
Commonly used in ordered collections.
8. Red-Black Tree
A Red-Black Tree is a type of self-balancing binary search tree (BST) . It is used to maintain order in data structures like Tree Maps.
Key Properties of Red-Black Trees:
1. Every node is either red or black .
2. The root is always black .
3. Every leaf is black .
4. If a red node has children, they must be black .
5. The number of black nodes from the root to any leaf is the same.
Why Use Red-Black Trees?
Balanced structure ensures that operations (insertion, deletion, lookup) are done in O(log n) time.
They help maintain sorted data without sacrificing performance.
9. Time Complexity of Hashing in Practice
Average Case vs Worst Case
Average Case : In practice, hash functions are designed to distribute keys uniformly across the table, resulting in constant time operations O(1) for insertions,
lookups, and deletions.
Worst Case : The worst case happens when there are too many collisions, and the hash map degrades to a linked list (using chaining) or needs to probe a lot
of indices (using open addressing). This leads to O(n) time complexity for each operation.
Conclusion
Hashing allows us to access data in constant time, O(1), on average, by mapping data to indices.
Hash maps and hash sets are crucial data structures that provide fast lookups and can be optimized for performance.
Understanding collisions , handling them effectively, and knowing when to use hash maps vs other structures (like red-black trees) can significantly improve
the efficiency of your algorithms.