## 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.