# Hashing Search Algorithm

Hashing is a search algorithm used to quickly find the location of a data record in a table or database. It works by taking a value (known as the key) and using a hash function to compute an index into an array of buckets or slots, where the corresponding record can be found.

The hash function takes the key and performs some mathematical operations to convert it into a numerical value that can be used as an index. The resulting index is used to access the appropriate bucket or slot, where the desired record can be found.

## How Algorithm of Hashing Search works?

The algorithm for hashing search typically involves the following steps:

1. First, a hash function is chosen. The hash function takes the key as input and returns an index into the array of buckets.
2. The key-value pair is inserted into the appropriate bucket, based on the hash value.
3. When searching for a key, the hash function is used again to compute the index of the bucket where the key might be located.
4. If the key is found in the bucket, the corresponding value is returned.
5. If the key is not found in the bucket, the search algorithm may need to search other buckets or perform additional steps to resolve collisions.
6. When deleting a key-value pair, the hash function is used to locate the bucket, and the pair is removed from the bucket.

The efficiency of the algorithm depends on the quality of the hash function and the number of collisions that occur. If the hash function produces a good distribution of hash values and collisions are rare, then the search algorithm can be very efficient. However, if the hash function is poorly designed or collisions are frequent, then the search algorithm can become slow and inefficient. To mitigate the impact of collisions, various techniques can be used, such as open addressing or chaining.

Here’s a pseudocode implementation of hashing search:

``````function hashingSearch(key, hashTable):
// Compute hash value
hashValue = hashFunction(key)

// Search for key in bucket
if hashTable[hashValue] is not null:
for pair in hashTable[hashValue]:
if pair.key == key:
return pair.value

return null
``````

In this implementation, `key` is the key that we are searching for, and `hashTable` is the table or array of buckets where the key-value pairs are stored. The `hashFunction` is a user-defined function that takes the key as input and returns a hash value, which is used to index into the hash table.

### Example Code

Here’s an example of a C++ program that performs hashing search:

```#include <iostream>
#include <vector>

using namespace std;

// Define a key-value pair struct
struct Pair
{
int key;
string value;
};

// Define a hash table class
class HashTable
{
public:
// Constructor with table size as input
HashTable(int tableSize)
{
this->tableSize = tableSize;
table.resize(tableSize);
}

// Hash function to compute index from key
int hashFunction(int key)
{
return key % tableSize;
}

// Insert key-value pair into hash table
void insert(int key, string value)
{
int index = hashFunction(key);
table[index].push_back({key, value});
}

// Search for key in hash table
string search(int key)
{
int index = hashFunction(key);
for (auto pair : table[index])
{
if (pair.key == key)
{
return pair.value;
}
}
}

private:
int tableSize;
vector<vector<Pair>> table;
};

int main()
{
HashTable table(5);

table.insert(1, "apple");
table.insert(2, "banana");
table.insert(3, "orange");

cout << table.search(2) << endl; // Output: "banana"

return 0;
}
```

The above program will output:

``````banana

In this program, the `Pair` struct represents a key-value pair. The `HashTable` class contains a vector of vectors to represent the hash table, where each inner vector contains a list of `Pair` objects that have the same hash value.

The `HashTable` class contains a constructor that takes the size of the hash table as input, a `hashFunction` method to compute the index from the key, an `insert` method to insert key-value pairs into the hash table, and a `search` method to search for a key in the hash table.

In the `main` function, we create a `HashTable` object with a size of 5, insert some key-value pairs, and then search for a couple of keys using the `search` method. The program outputs the corresponding values for the keys, or “Key not found” if the key is not present in the hash table.

## Complexity Analysis of Hashing Search

The time complexity of hashing search depends on the quality of the hash function and the number of collisions that occur.

In the best-case scenario, where there are no collisions and the hash function produces a unique index for each key, the time complexity of hashing search is O(1). This is because the search algorithm can compute the index of the bucket that contains the key in constant time, and then retrieve the value from the bucket in constant time as well.

In the worst-case scenario, where all keys have the same hash value and are stored in the same bucket, the time complexity of hashing search becomes O(n), where n is the number of keys in the bucket. In this case, the search algorithm must examine each key-value pair in the bucket to find the key that we are searching for.

In practice, the quality of the hash function and the number of collisions depend on the size of the hash table, the number of keys, and the distribution of the keys. By choosing a good hash function and an appropriate hash table size, we can minimize the number of collisions and achieve an average-case time complexity of O(1) or close to it. Additionally, techniques like chaining or open addressing can be used to handle collisions and further improve the efficiency of the algorithm.

## When is the Hashing Search algorithm used?

Hashing search is used when we need to search for a key in a large collection of data that can be represented as key-value pairs. This algorithm is particularly useful when we need to perform frequent search operations and when the size of the data set is large.

Hashing search is often used in databases and information retrieval systems, where we need to quickly search for data based on a unique key. For example, a database management system may use hashing search to quickly retrieve records based on a primary key. Information retrieval systems may use hashing search to retrieve documents based on a unique identifier or keyword.

1. Fast search time: Hashing search provides constant time complexity for searching in the best case scenario. This makes it ideal for large data sets where search time is a critical factor.
2. Efficient storage: Hashing search requires less memory space compared to other search algorithms like linear search or binary search. This is because it stores only the key-value pairs in the hash table, rather than the entire data set.
3. Good performance on average: Hashing search provides good performance on average for a wide range of data sets when the hash function is chosen carefully.
4. Easy implementation: Hashing search is easy to implement and understand, and many programming languages provide built-in hash table data structures.