Hashing

Hashing in C++

Hashing is a technique used to map data of arbitrary size (such as strings, integers, etc.) to fixed-size values using a hash function. It is widely used in various applications like hash tables, databases, caches, and encryption. The goal of hashing is to allow for efficient data retrieval, insertion, and deletion operations.

What is Hashing?

• Hash Function: A function that takes an input (or "key") and computes an integer value (called a hash value or hash code) based on that input. This value is used as an index in an array (or hash table) to store the data.
• Hash Table: A data structure that stores data in an array-like format where each data element is stored at an index generated by a hash function. The key is hashed to produce an index where the value is stored.

Components of Hashing

1. Key: The input data that is being hashed. It can be any data type (string, integer, etc.).
2. Hash Value: The integer value generated by the hash function that represents the key.
3. Bucket: An index or slot in the hash table where the value corresponding to the key is stored.
4. Collision: When two different keys produce the same hash value, causing both values to be stored in the same bucket. Collisions must be handled efficiently.

Hashing Techniques

1. Division Method
2. Multiplication Method
3. Universal Hashing

Handling Collisions

1. Chaining
2. Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)

1. Hash Function

A hash function takes an input (key) and computes an integer hash value. The function should have the following characteristics:

• Deterministic: The same input always produces the same hash value.
• Efficient: The function should be fast and easy to compute.
• Uniform: The hash values should be uniformly distributed to minimize collisions.

Example of a Simple Hash Function:

For simplicity, a basic hash function for integers could be:

int hashFunction(int key, int tableSize) {
    return key % tableSize;
}

In this example, the key is divided by the table size, and the remainder is the hash value. The remainder will be used as the index in the hash table.

2. Hashing Methods

(a) Division Method

The division method is one of the simplest hash functions, where the hash value is computed by dividing the key by the table size and using the remainder.

int hashFunction(int key, int tableSize) {
    return key % tableSize;
}

(b) Multiplication Method

In this method, the key is multiplied by a constant value and the result is then taken modulo the table size. A typical implementation might look like:

int hashFunction(int key, int tableSize) {
    float A = 0.6180339887;  // Constant between 0 and 1
    return int(tableSize * (key * A - int(key * A)));
}

(c) Universal Hashing

This method involves choosing a random hash function from a family of hash functions at runtime. The idea is to make it harder for an adversary to predict the hash function and cause a lot of collisions.

3. Handling Collisions

Since it's possible for multiple keys to produce the same hash value (a collision), collision resolution techniques are necessary to ensure efficient storage and retrieval.

(a) Chaining

In chaining, each bucket of the hash table stores a linked list (or another list structure) of elements. If multiple keys hash to the same bucket, they are added to the list at that bucket.

• Advantages:

  • Simple and easy to implement.
  • Allows for an unlimited number of elements per bucket.

• Disadvantages:

  • It can lead to inefficient performance if the chains are long (i.e., many collisions).

Code Example (Chaining):

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

class HashTable {
    int size;
    list<int> *table;

public:
    HashTable(int s) {
        size = s;
        table = new list<int>[size];
    }

    void insert(int key) {
        int index = key % size;
        table[index].push_back(key);  // Insert key into the linked list
    }

    void remove(int key) {
        int index = key % size;
        table[index].remove(key);  // Remove key from the linked list
    }

    bool search(int key) {
        int index = key % size;
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (*it == key)
                return true;
        }
        return false;  // Not found
    }
};

int main() {
    HashTable ht(10);
    ht.insert(15);
    ht.insert(25);
    ht.insert(35);

    if (ht.search(25)) {
        cout << "Found 25" << endl;
    } else {
        cout << "25 not found" << endl;
    }

    ht.remove(25);
    
    if (ht.search(25)) {
        cout << "Found 25" << endl;
    } else {
        cout << "25 not found" << endl;
    }

    return 0;
}

Output:

Found 25
25 not found

(b) Open Addressing

In open addressing, when a collision occurs, the algorithm searches for the next available bucket in the hash table according to a probe sequence. The most common probing techniques are:

• Linear Probing: If a collision occurs at index i, check index i+1, then i+2, and so on, until an empty slot is found.

• Quadratic Probing: Instead of checking the next index, check i+1^2, i+2^2, i+3^2, etc., to resolve collisions.

• Double Hashing: Use a second hash function to compute the probe sequence.

Code Example (Linear Probing):

#include <iostream>
using namespace std;

class HashTable {
    int size;
    int *table;

public:
    HashTable(int s) {
        size = s;
        table = new int[size];
        for (int i = 0; i < size; i++) {
            table[i] = -1;  // Initialize all elements as -1 (empty)
        }
    }

    void insert(int key) {
        int index = key % size;
        while (table[index] != -1) {
            index = (index + 1) % size;  // Linear probing
        }
        table[index] = key;
    }

    void remove(int key) {
        int index = key % size;
        while (table[index] != -1) {
            if (table[index] == key) {
                table[index] = -1;  // Mark the slot as empty
                return;
            }
            index = (index + 1) % size;
        }
    }

    bool search(int key) {
        int index = key % size;
        while (table[index] != -1) {
            if (table[index] == key) {
                return true;
            }
            index = (index + 1) % size;
        }
        return false;
    }
};

int main() {
    HashTable ht(10);
    ht.insert(15);
    ht.insert(25);
    ht.insert(35);

    if (ht.search(25)) {
        cout << "Found 25" << endl;
    } else {
        cout << "25 not found" << endl;
    }

    ht.remove(25);
    
    if (ht.search(25)) {
        cout << "Found 25" << endl;
    } else {
        cout << "25 not found" << endl;
    }

    return 0;
}

Output:

Found 25
25 not found

Time Complexity of Hashing Operations

• Insertion:

  • In chaining, the average time complexity is O(1), but in the worst case (if all keys hash to the same index), it can be O(n).
  • In open addressing, the average time complexity is O(1), but it can degrade to O(n) if the table becomes too full or too many collisions occur.

• Search:

  • In chaining, average time complexity is O(1), but it can be O(n) in the worst case.
  • In open addressing, average time complexity is O(1), but it can be O(n) in the worst case.

• Deletion:

  • In chaining, average time complexity is O(1), but in the worst case, it can be O(n).
  • In open addressing, average time complexity is O(1), but it can be O(n) in the worst case.

Applications of Hashing

• Hash Tables: Efficiently store and retrieve data.
• Database Indexing: Quickly find records in a database.
• Caches: Store previously computed results for quick retrieval.
• Cryptography: Hash functions are used in encryption algorithms and digital signatures.
• **Checksums and Hash