🔑 Hashing – Comprehensive Study Guide

**Hashing** is a **data storage and retrieval technique** that maps **keys to values using a hash function**. It allows for **fast search, insert, and delete operations** in O(1) time (on average).

⚡ Why Use Hashing?

• ✅ **Fast retrieval in O(1) time (on average).**
• 🚀 **Used in databases, caches, and encryption.**
• 🔍 **Efficient for dictionary & set operations.**
• 📡 **Avoids O(n) linear searches in arrays.**

📌 Types of Hashing Techniques

📥 **1. Direct Addressing (O(1) Space & Time Complexity)**

When keys are small and **distinct**, they can be stored directly in an array.

                int directAddressTable[1000]; // Array of size 1000
                void insert(int key, int value) {
                    directAddressTable[key] = value;
                }
                int search(int key) {
                    return directAddressTable[key];
                }
                

📥 **2. Hashing with Hash Functions**

Instead of direct mapping, a **hash function** converts a key into an **index**.

                int hashFunction(int key, int tableSize) {
                    return key % tableSize; // Modulo division method
                }
                

📌 Collision Handling Techniques

🔗 **1. Separate Chaining (Using Linked Lists)**

Multiple values **map to the same index**, stored as a **linked list**.

                struct HashNode {
                    int key, value;
                    HashNode* next;
                };
            
                class HashTable {
                    vector table;
                    int size;
            
                public:
                    HashTable(int s) : size(s), table(s, nullptr) {}
            
                    int hashFunction(int key) {
                        return key % size;
                    }
            
                    void insert(int key, int value) {
                        int index = hashFunction(key);
                        HashNode* newNode = new HashNode{key, value, table[index]};
                        table[index] = newNode;
                    }
            
                    int search(int key) {
                        int index = hashFunction(key);
                        HashNode* node = table[index];
                        while (node) {
                            if (node->key == key) return node->value;
                            node = node->next;
                        }
                        return -1; // Not found
                    }
                };
                

📤 **2. Open Addressing (Linear & Quadratic Probing)**

🔄 **Linear Probing (O(1) Average Time Complexity)**

Finds the **next available slot** if a collision occurs.

                int table[1000];
                int tableSize = 1000;
            
                int hashFunction(int key) {
                    return key % tableSize;
                }
            
                void insert(int key, int value) {
                    int index = hashFunction(key);
                    while (table[index] != -1) { // Find next available slot
                        index = (index + 1) % tableSize;
                    }
                    table[index] = value;
                }
                

🔄 **Quadratic Probing (O(1) Average Time Complexity, Avoids Clustering)**

Uses a quadratic function **(index + i²) % tableSize** to resolve collisions.

⚖️ Comparison of Collision Handling Techniques

🔍 Common Applications of Hashing

📌 **1. Hash Tables (O(1) Average Time Complexity for Lookup)**

                unordered_map hashTable;
                hashTable[1] = "Alice";
                hashTable[2] = "Bob";
                cout << hashTable[1]; // Output: Alice
                

📌 **2. Password Storage (Hashing in Cryptography)**

Passwords are stored using **secure hash functions like SHA-256.**

📌 **3. Caching in Web Browsers**

Browsers store **frequently accessed data** in a hash-based cache.

📌 **4. Detecting Duplicate Elements (Using HashSet)**

Find duplicate elements in O(n) time.

                unordered_set seen;
                for (int num : arr) {
                    if (seen.count(num)) {
                        cout << "Duplicate found: " << num;
                    }
                    seen.insert(num);
                }
                

⏳ Time Complexity Analysis

• ✅ **Best Case:** O(1) – No collisions.
• ⚡ **Worst Case:** O(n) – All elements map to the same index (bad hash function).

🌍 Real-World Applications of Hashing

• 📡 **Database Indexing** – Fast key-value storage.
• 🔑 **Cryptography** – Password hashing & blockchain.
• 📊 **Data Caching** – Faster retrieval in web apps.
• 🎭 **Compiler Design** – Storing variables efficiently.

🔗 Next Topics

• 📚 Trie Data Structure
• 🌲 Binary Search Trees
• 🔐 Cryptographic Hashing