Hashing Master | Algo Singh

The Power of Hashing

Hashing transforms a large key into a small index from 0 to m-1 to store data in a fixed-size table. It aims for O(1) search time.

1. Hash Functions

The core mechanism h(k) that maps a key to an index.

Division h(k) = k % m. Fast, but sensitive to m (prime is best).
Multiplication h(k) = ⌊m(kA mod 1)⌋. Good for any m.
Mid-Square Square k, take middle digits. Good distribution.
Folding Split key into parts and sum them (e.g., for phone numbers).

2. Collision Resolution

When h(k₁) = h(k₂), a collision occurs. We must handle it.

Open Addressing Find another empty slot in the table.

Linear Probing (+1, +2...)
Quadratic Probing (+1², +2²...)
Double Hashing (use h₂(k))

Separate Chaining Each slot stores a Linked List (or tree).

Can handle Load Factor α > 1.

3. Universal Hashing

To prevent attacks where an adversary chooses keys that all hash to the same slot, we can pick a hash function randomly at runtime from a carefully designed family of functions (H).

This makes the probability of collision low for any set of keys.

4. Perfect Hashing

For a static set of keys (that don't change), it's possible to create a hash function that guarantees zero collisions.

This is often done with a two-level hashing scheme, where a universal hash function is used at each level.

Advanced Hashing Techniques

Exploring mathematical transformations to map keys uniformly.

Division

h(k) = k % m. Fast but sensitive to patterns.

Basic

Multiplication

h(k) = ⌊m(kA mod 1)⌋. A ≈ 0.618. Good distribution.

Robust

Mid-Square

Square k, take middle r digits. Mixes all bits.

Statistical

Folding

Split key into parts, sum them up. Good for long numbers.

Strings/BigInt

Universal

Pick random h from a family H at runtime. Prevents attacks.

Security

Key Metrics

α

Load Factor

α = n/m. Keeps track of table fullness.

O(1)

Time Complexity

Average case for Search/Insert. Worst case O(n).

m

Table Size

Usually chosen as a Prime Number.

Configuration

Hash Function

Collision Resolution

Table Size (m)

Operations

Load Factor α 0.00

Collisions 0

Initializing...

Ready

Cryptographic Hash Playground

Input Text

MD5 (128-bit) Legacy, fast, broken

SHA-1 (160-bit) Git default, broken

SHA-256 (256-bit) Bitcoin standard, secure

hashing_logic.cpp

class HashTable {
    int size;
    int* table;
public:
    int hash(int key) {
        // Division Method
        return key % size;
    }

    void insertLinear(int key) {
        int idx = hash(key);
        int i = 0;
        
        // Linear Probing: (h(k) + i) % m
        while (table[(idx + i) % size] != -1) {
            i++;
            if (i == size) return; // Table Full
        }
        table[(idx + i) % size] = key;
    }

    void insertDoubleHash(int key) {
        int h1 = key % size;
        int h2 = 1 + (key % (size - 1)); // Secondary Hash
        int i = 0;

        while (table[(h1 + i * h2) % size] != -1) {
            i++;
        }
        table[(h1 + i * h2) % size] = key;
    }
};

// --- Separate Chaining Example ---
class ChainingHashTable {
    int size;
    std::vector<std::list<int>> table; // Vector of linked lists

public:
    ChainingHashTable(int s) : size(s), table(s) {}

    int hash(int key) { return key % size; }

    void insert(int key) {
        int idx = hash(key);
        table[idx].push_back(key); // Append to the list at the index
    }
};

// --- Open Addressing Example ---
class OpenAddressingHashTable {
    int size;
    std::vector<int> table;
    const int EMPTY = -1;

public:
    OpenAddressingHashTable(int s) : size(s), table(s, EMPTY) {}

    // --- Hash Functions ---
    int divisionHash(int key) { return key % size; }
    int multiplicationHash(int key) {
        double A = 0.6180339887; // Knuth's constant
        return floor(size * fmod(key * A, 1.0));
    }

    // --- Collision Resolution Methods ---
    void insertLinear(int key) {
        int idx = divisionHash(key);
        int i = 0;
        while (table[(idx + i) % size] != EMPTY) {
            i++;
            if (i == size) return; // Table full
        }
        table[(idx + i) % size] = key;
    }

    void insertQuadratic(int key) {
        int idx = divisionHash(key);
        int i = 0;
        while (table[(idx + i*i) % size] != EMPTY) {
            i++;
            if (i == size) return;
        }
        table[(idx + i*i) % size] = key;
    }

    void insertDoubleHash(int key) {
        int h1 = divisionHash(key);
        int h2 = 1 + (key % (size - 1)); // h2 must not be 0
        int i = 0;
        while (table[(h1 + i * h2) % size] != EMPTY) {
            i++;
            if (i == size) return;
        }
        table[(h1 + i * h2) % size] = key;
    }
};