What is Hashing? | DSA in C++ - Software Development PDF Download

Introduction

Hashing is a fundamental concept in computer science and is widely used in various applications. It is a technique that allows for efficient data storage and retrieval. In this article, we will explore what hashing is, how it works, and how it can be implemented in the C++ programming language.

What is Hashing?

Hashing is a process of converting data into a fixed-size numerical value called a hash code or hash value. The hash code represents the original data and is used to index and retrieve the data in a data structure called a hash table. It provides fast access to data by mapping it to a unique index within the table.

How Hashing Works

The basic idea behind hashing is to transform the input data using a hash function, which takes an input and produces a hash code. The hash code is typically a fixed-size integer. The hash code is then used as an index to store the data in the hash table.

Hash Functions

A hash function is responsible for generating the hash code. It takes the input data and applies a series of computations to produce a hash value. Ideally, a good hash function should have the following properties:

• Deterministic: Given the same input, the hash function should always produce the same hash value.
• Uniform Distribution: The hash values should be evenly distributed across the hash table to minimize collisions.
• Fixed Output Size: The hash function should generate a hash code of a fixed size.

Example:

// Hash function example

unsigned int hashFunction(const std::string& key, int tableSize) {

    unsigned int hash = 0;

    for (char ch : key) {

        hash += ch;

    }

    return hash % tableSize;

}

Collision Resolution Techniques

Collisions occur when two different inputs produce the same hash code. There are several collision resolution techniques to handle such situations:

• Separate Chaining: Each hash table entry contains a linked list of elements that share the same hash code.
• Open Addressing: If a collision occurs, the algorithm probes for the next available slot in the hash table.
• Linear Probing: The algorithm looks for the next available slot by linearly probing the subsequent indices.
• Quadratic Probing: The algorithm probes for the next slot by using quadratic equations.
• Double Hashing: The algorithm uses a secondary hash function to determine the next slot to probe.

Implementing Hashing in C++

The C++ Standard Template Library (STL) provides a built-in hash table implementation called 'std::unordered_map'. Here's a simple example:

#include <iostream>

#include <unordered_map>

int main() {

    std::unordered_map<std::string, int> scores;

    scores["Alice"] = 85;

    scores["Bob"] = 92;

    scores["Charlie"] = 78;

    std::cout << "Bob's score: " << scores["Bob"] << std::endl;

    return 0;

}

Output:

Bob's score: 92

Sample Problems and Solutions:

Problem 1: Given an array of integers, find the first repeating element.

#include <iostream>

#include <unordered_map>

#include <vector>

int findFirstRepeating(const std::vector<int>& arr) {

    std::unordered_map<int, int> countMap;

    for (int num : arr) {

        countMap[num]++;

        if (countMap[num] > 1) {

            return num;

        }

    }

    return -1; // No repeating element found

}

int main() {

    std::vector<int> arr = {3, 1, 4, 2, 3, 5, 4};

    int result = findFirstRepeating(arr);

    if (result != -1) {

        std::cout << "First repeating element: " << result << std::endl;

    } else {

        std::cout << "No repeating element found." << std::endl;

    }

    return 0;

}

Output:

First repeating element: 3

Problem 2: Implement a hash table from scratch using an array.

(Code and explanation)

Conclusion

Hashing is a powerful technique used for efficient data storage and retrieval. By understanding the concepts of hash functions, collision resolution techniques, and implementing hash tables, you can leverage this technique to solve various problems efficiently.