Hashing

In C++, hashing is a technique used to map a large amount of data to a smaller set of values. It is used to efficiently store and retrieve data in separate data structures as well. Hashing is a way to convert a large input into a small output by using a hash function. In this implementation of hashing, we will use an array to store the data, with each array index representing a unique key.

Implementation: Here’s an example of implementing hashing in C++. In this implementation, we will create a simple hash table that stores strings as keys and the associated integer as the value.


#include <iostream>
#include <cstring>
using namespace std;

const int TABLE_SIZE = 128;

class HashTable {
   private:
    struct item {
        int value;
        string key;
        item(string k, int v) : key(k), value(v) {}
    };

    item** table;

   public:
    HashTable() {
        table = new item*[TABLE_SIZE]();
    }

    int hash(string key) {
        unsigned long hash = 5381;
        int c;

        for(int i = 0; i < key.length(); i++) {
            c = key[i];
            hash = ((hash << 5) + hash) + c;
        }

        return hash % TABLE_SIZE;
    }

    void insert(string key, int value) {
        int index = hash(key);

        if(table[index] == NULL) {
            table[index] = new item(key, value);
        }
        else {
            item* ptr = table[index];
            while(ptr->key != key && ptr->value != value) {
                ptr = ptr->next;
                if(ptr == NULL) {
                    ptr = new item(key, value);
                }
            }
        }
    }

    void search(string key) {
        int index = hash(key);

        if(table[index] == NULL) {
            cout << "Key not found" << endl;
        }
        else {
            item* ptr = table[index];
            while(ptr != NULL && ptr->key != key) {
                ptr = ptr->next;
            }

            if(ptr != NULL) {
                cout << "Value: " << ptr->value << endl;
            }
            else {
                cout << "Key not found" << endl;
            }
        }
    }

    ~HashTable() {
        for(int i = 0; i < TABLE_SIZE; i++) {
            if(table[i] != NULL) {
                delete table[i];
            }
        }
        delete[] table;
    }
};

int main() {
    HashTable ht;

    ht.insert("John", 10);
    ht.insert("Chris", 20);
    ht.insert("Bob", 30);

    ht.search("John");
    ht.search("Chris");
    ht.search("Bob");
    ht.search("Mike");

    return 0;
}

In this implementation, we start by declaring the HashTable class, which contains a struct called item. item contains a string key and an integer value, which is the data we want to store in the hash table. We then declare the table array, which contains pointers to the item struct.

The hash function uses a simple hash algorithm to convert the input string key into a hash value that corresponds to an index in the table array.

The insert function inserts a new item into the hash table by calling hash to get the index and then either storing the new item in the table array if the index is empty or searching through the linked list at the index to find the right spot to insert the new item.

The search function searches for an item by calling hash to get the index and then searching through the linked list at the index.

Finally, the ~HashTable destructor deletes all the items in the table array.

Hashing has numerous real-life applications across various domains. Here are some examples:

Data Retrieval: Hashing is commonly used in data structures like hash tables or hash maps. It enables efficient retrieval of data by mapping keys to corresponding hash values. This is utilized in databases, caches, and indexing systems for fast data access.

Password Storage: When storing user passwords, it is crucial to protect them. Hash functions help secure passwords by converting them into hash values before storage. The actual passwords are not stored, only their hash values. During authentication, the entered password is hashed, and the resulting hash value is compared to the stored hash value to verify correctness.

Cryptographic Algorithms: Hash functions play a vital role in various cryptographic algorithms. For example, in digital signatures, hash functions are used to create a condensed representation (hash) of the data being signed. This hash is then encrypted with the private key of the signer to generate the signature.

Data Integrity: Hashing is employed to verify the integrity of data during transmission or storage. By generating a hash value of the original data and comparing it with the computed hash value of received or retrieved data, any changes or corruption can be detected. This technique is commonly used in checksums, message digests, and file verification.

Content Addressing: Content addressing systems, such as the InterPlanetary File System (IPFS), utilize hashing to provide unique identifiers to files or content. The hash of the content is used as an address to retrieve and distribute the data in a decentralized manner.

Deduplication: Hashing can help identify and eliminate duplicate data in storage systems. By hashing the data blocks or chunks, duplicate chunks can be easily identified, allowing for efficient storage and reduction of storage space.

Caching: Hashing is often used in caching systems to quickly determine if a particular data item is present in the cache. The hash value of the data acts as a key for cache lookup, providing fast access to frequently accessed data.

These are just a few examples of how hashing is applied in real-life scenarios. Hash functions and hashing algorithms have broad applicability and are foundational to various areas of computer science and information systems.

PRACTICE PROBLEMS :

Smallest Range Covering Elements from K Lists

Hand of Straights