Index Mapping
Introduction
The concept of hashing is utilized to perform faster search and retrieval operations. In hashing, we use a hash function to map a key to a value. Consider checking out this cool blog on hashing to learn about the fundamentals of hashing, its implementation techniques, and much more.
In this blog, we will discuss one of the most common and frequently used hashing techniques, i.e., Index Mapping, also known as Trivial Hashing. We will also look at how this technique can be extended to map negative numbers to an index.
What is Index Mapping?
In the index mapping technique, we use an array, and as the name suggests, every value is mapped to some index in the array.
Assume we have the following keys: 2, 5, 1, 6, 7, and we want to determine whether a specific element is present or not.
Let us first look at the naive idea to solve this problem.
Naive Approach
The brute force approach is to push all the elements in an array, and then for every query, we will traverse the array and see if the given element is present or not.
Given below is the C++ implementation of the above idea.
Program
#include <iostream>
#include <vector>
using namespace std;
// Function to check if 'elementToBeSearched' exist in the array, 'arr' or not.
bool find(vector<int> &arr, int elementToBeSearched) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == elementToBeSearched) {
return true;
}
}
return false;
}
int main() {
// Taking user input.
int n;
cout << "Enter the number of elements: ";
cin >> n;
vector<int> arr(n);
// Storing elements in array.
cout << "Enter " << n << " elements: ";
for (int &element : arr) {
cin >> element;
}
// Taking number of queries as input.
int q;
cout << "Enter the number of queries: ";
cin >> q;
while (q--) {
int elementToBeSearched;
cout << "Enter the element to be searched: ";
cin >> elementToBeSearched;
// Searching element in the array.
if (find(arr, elementToBeSearched)) {
cout << elementToBeSearched << " Found\n";
}
else {
cout << elementToBeSearched << " Not Found\n";
}
}
return 0;
}
Input
Enter the number of elements: 5
Enter 5 elements: 2 5 1 6 7
Enter the number of queries: 3
Enter the element to be searched: 1
Enter the element to be searched: 2
Enter the element to be searched: 3
Output
1 Found
2 Found
3 Not Found
Time Complexity of Search
O(N), where ‘N’ is the number of elements.
For every query, we have to traverse the entire array to determine whether an element is present or not. Hence, the time complexity of searching for an element becomes O(N).
Space Complexity
O(1).
Since no auxiliary space has been used in this case.
Index Mapping Approach
In this approach, we will use the values of elements as indices in a boolean array (say: HASHTABLE) to indicate their presence.
If element ‘E’ is present then HASHTABLE[E] = true, otherwise HASHTABLE[E] = false.
As a result, to search element 2, we just need to do a lookup at index 2. In this way, the search queries can be optimized to be performed in constant time.
The question now is, what big should the hash table be? Since we need to store all of the elements in the hash table, the hash table must be large enough to store the maximum element.
As a result, the size of the hash table should be ‘MAX_ELEMENT + 1’ to store the ‘MAX_ELEMENT’ at index ‘MAX_ELEMENT’, where ‘MAX_ELEMENT’ is the value of the maximum element.
Let us now see the C++ implementation of the above approach.
Program
#include <iostream>
#include <vector>
using namespace std;
// Function to check if 'elementToBeSearched' exist in the hash table, 'hashTable' or not.
bool find(vector<bool> &hashTable, int elementToBeSearched) {
return hashTable[elementToBeSearched];
}
void insert(vector<bool> &hashTable, vector<int> &arr) {
for (int &element : arr) {
hashTable[element] = true;
}
}
int main() {
// Taking user input.
int n;
cout << "Enter the number of elements: ";
cin >> n;
vector<int> arr(n);
// To keep track of the maximum element.
int maxElement = 0;
// Storing elements in array.
cout << "Enter " << n << " elements: ";
for (int &element : arr) {
cin >> element;
maxElement = max(element, maxElement);
}
// Creating a hash table of size 'maxElement + 1'.
vector<bool> hashTable(maxElement + 1, false);
// Marking the presence of elements in the hash table.
insert(hashTable, arr);
// Taking number of queries as input.
int q;
cout << "Enter the number of queries: ";
cin >> q;
while (q--) {
int elementToBeSearched;
cout << "Enter the element to be searched: ";
cin >> elementToBeSearched;
// Searching element in the array.
if (find(hashTable, elementToBeSearched)) {
cout << elementToBeSearched << " Found\n";
}
else {
cout << elementToBeSearched << " Not Found\n";
}
}
return 0;
}
Input
Enter the number of elements: 5
Enter 5 elements: 2 5 1 6 7
Enter the number of queries: 3
Enter the element to be searched: 1
Enter the element to be searched: 2
Enter the element to be searched: 3
Output
1 Found
2 Found
3 Not Found
Time Complexity of Search
O(1).
For every query, we simply have to perform a lookup in the hash table, which is a constant time operation. Hence, the time complexity of searching an element is O(1).
Space Complexity
O(MAX_ELEMENT + 1), where ‘MAX_ELEMENT’ is the maximum value of the element.
It is because the hash table used above is of size ‘MAX_ELEMENT + 1’.
Key Points about Index Mapping
It is worthwhile to mention that index mapping is useful for limited-range elements. If the elements are very far apart, index mapping might result in a significant amount of space wastage.
For example:
Suppose the elements are 1, 2, and 1000. Although there are three elements, we have to create an array of size 1001 to map the value 1000 at index 1000 in the array.
Also, index mapping should be employed when the universe of keys is small enough that creating an array with one place for every possible key is affordable.
Its effectiveness stems from the fact that we can examine an arbitrary location in an array in constant time.
What if Array also contains Negative Elements?
So far, we have been utilizing values of elements as indices in the hash table. However, this is valid only for non-negative elements as indices are always non-negative.
Now you must be wondering how we will indicate the presence of negative elements? That’s truly a very genuine doubt. Let us see how we are going to solve this problem.
Previously, we used a boolean hash table and marked true for elements that are present and false for those that are absent.
To take care of negative elements, we can use an integer hash table. For an element ‘E’, we can mark index ‘E’ with 0 if ‘E’ is not present, 1 if ‘E’ is present, -1 if ‘-E’ is present and 2 if ‘E’ as well as ‘-E’ are present.
Note: For element 0, we will always mark HASHTABLE[0] = 1.
For example:
Suppose we have an array with the following elements: 1, 2, 4, 0, -2, -6, 8, and we want to mark their presence in the hash table.
The first step is to choose the size of the hash table. If an array has both positive and negative elements, the size of the hash table will be the maximum of all the absolute values. Here it is 8. So, we will create an integer hash table of size 9 (8 + 1), initialized with zero. The HASHTABLE will look like this:
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
For element 1, we will mark HASHTABLE[1] = 1.
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
For element 2, we will mark HASHTABLE[2] = 1.
0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
For element 4, we will mark HASHTABLE[4] = 1.
0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
For element 0, we will mark HASHTABLE[0] = 1.
1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
For element -2, we will mark HASHTABLE[2] = 2 (as 2 and -2 both are present).
1 | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
For element -6, we will mark HASHTABLE[6] = -1.
1 | 1 | 2 | 0 | 1 | 0 | -1 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
For element 8, we will mark HASHTABLE[8] = 1.
1 | 1 | 2 | 0 | 1 | 0 | -1 | 0 | 1 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Now let us try searching few elements:
- Search 3: Since HASHTABLE[3] = 0, element 3 is not found.
- Search -2: Since HASHTABLE[2] = 2, it shows that elements 2 and -2 both are present. Hence, -2 found.
- Search 6: Since HASHTABLE[6] = -1, it shows that element -6 is present and not element 6. Hence, 6 is not found.
- Search 2: Since HASHTABLE[2] = 2, it shows that elements 2 and -2 both are present. Hence, 2 found.
Thus, we can conclude that:
- An element ‘E’ is present in the hash table only if HASHTABLE[E] = 1 or HASHTABLE[E] = 2.
- An element ‘-E’ is present in the hash table only if HASHTABLE[E] = -1 or HASHTABLE[E] = 2.
Based on this discussion, let us now see the implementation of the above idea.
Program
#include <iostream>
#include <vector>
using namespace std;
// Function to check if 'elementToBeSearched' exist in the hash table, 'hashTable' or not.
bool find(vector<int> &hashTable, int elementToBeSearched) {
int index = abs(elementToBeSearched);
if (elementToBeSearched < 0) {
return (hashTable[index] == -1 || hashTable[index] == 2);
}
else {
return (hashTable[index] == 1 || hashTable[index] == 2);
}
}
// Function to mark the presence of elements in the hash table.
void insert(vector<int> &hashTable, vector<int> &arr) {
for (int &element : arr) {
int index = abs(element);
if (element < 0) {
hashTable[index] = (hashTable[index] == 1 || hashTable[index] == 2) ? 2 : -1;
}
else {
hashTable[index] = (hashTable[index] == -1 || hashTable[index] == 2) ? 2 : 1;
}
}
}
int main() {
// Taking user input.
int n;
cout << "Enter the number of elements: ";
cin >> n;
vector<int> arr(n);
// To keep track of the maximum element.
int maxElement = 0;
// Storing elements in array.
cout << "Enter " << n << " elements: ";
for (int &element : arr) {
cin >> element;
maxElement = max(abs(element), maxElement);
}
// Creating a hash table of size 'maxElement + 1'.
vector<int> hashTable(maxElement + 1, 0);
// Marking the presence of elements in the hash table.
insert(hashTable, arr);
// Taking number of queries as input.
int q;
cout << "Enter the number of queries: ";
cin >> q;
while (q--) {
int elementToBeSearched;
cout << "Enter the element to be searched: ";
cin >> elementToBeSearched;
// Searching element in the array.
if (find(hashTable, elementToBeSearched)) {
cout << elementToBeSearched << " Found\n";
}
else {
cout << elementToBeSearched << " Not Found\n";
}
}
return 0;
}
Input
Enter the number of elements: 7
Enter 7 elements: 1 2 4 0 -2 -6 8
Enter the number of queries: 4
Enter the element to be searched: 3
Enter the element to be searched: -2
Enter the element to be searched: 6
Enter the element to be searched: 2
Output
3 Not Found
-2 Found
6 Not Found
2 Found
Time Complexity of Search
O(1).
For every query, we are still performing a lookup in the hash table, which is a constant time operation. Hence, the time complexity of searching an element is O(1).
Space Complexity
O(|MAX_ELEMENT| + 1), where ‘|MAX_ELEMENT|’ is the absolute maximum value of the element.
You can also read about the Longest Consecutive Sequence.
Frequently Asked Question
What is the time complexity of insertion in a hashmap?
The time complexity of the insertion of an element in a hashmap is constant which is O(1)
What is the difference between a map and an unordered_map in C++?
The data is stored in an ordered fashion in the map based on the ascending order of keys whereas the unordered_map stores the data in the fashion in that keys are inserted in.
Conclusion
With this discussion, this blog attempted to understand index mapping and its utility in performing a search in constant time. We also discussed the implementation of index mapping for arrays containing negative elements as well as the time and space complexities.
We hope you found this blog useful. Now move ahead and use this concept of index mapping to solve some interesting problems on CodeStudio.
Recommended Reading:
- Hash Function in Data Structure
- Internal Working of HashMap
- Hashmap
- Hashtable v/s STL Map
- Difference Between Hashmap and Hashtable in Java
- Separate Chaining and Open Addressing For Collision Addressing
- Practice Problems
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.
Feel free to let us know your thoughts in the comments section.