Hash Tables

🗄️ Hash Tables: The Magic Library of Instant Answers

The Story of the Magical Library 📚

Imagine you walk into a HUGE library with a million books. You need to find one specific book: “The Adventures of Captain Code.”

The Slow Way: You start at the first shelf and check every single book. One by one. This could take FOREVER! 😩

The Smart Way: What if the librarian had a magical system? You whisper the book’s name, and POOF—the librarian instantly knows: “Shelf 42, third book from the left!” ✨

That magical system is a Hash Table!

A Hash Table is like having a super-smart librarian who can find ANY book instantly, no matter how big the library is.

🎯 What is a Hash Table?

A Hash Table is a special way to store things so you can find them SUPER FAST.

Think of it like a set of numbered boxes:

Box 0: [empty]
Box 1: ["apple" → "red fruit"]
Box 2: [empty]
Box 3: ["banana" → "yellow fruit"]
Box 4: ["grape" → "purple fruit"]

How it works:

1. You have a key (like “apple”)
2. A magic formula turns the key into a box number
3. You put your item in that exact box
4. When you need it back? Same formula = same box!

Real Life Example 🍕

Pizza shop phone numbers:

• “Joe’s Pizza” → goes to box 7
• “Tony’s Slice” → goes to box 3
• “Mama Mia’s” → goes to box 7 (uh oh! same box!)

🔮 Hash Functions: The Magic Formula

The hash function is the secret sauce. It’s a recipe that takes any word and turns it into a number.

Simple Example

Let’s make a baby hash function:

int hash(char* word) {
    int sum = 0;
    for (int i = 0; word[i]; i++) {
        sum = sum + word[i];
    }
    return sum % 10;  // box 0-9
}

What happens:

• Each letter has a number (a=97, b=98, c=99…)
• Add all the letter numbers together
• Divide by 10 and keep the remainder

Try it:

• “cat” → 99+97+116 = 312 → 312 % 10 = box 2
• “dog” → 100+111+103 = 314 → 314 % 10 = box 4

🌟 A Good Hash Function Should:

Popular Hash Functions

graph TD
    A["Input: Any Key"] --> B["Hash Function"]
    B --> C["Output: Number"]
    C --> D["Box/Bucket Index"]
    style B fill:#4ECDC4,stroke:#333

💥 Collision Handling: When Two Items Want the Same Box

PROBLEM: What happens when “cat” and “act” both want box 2?

This is called a COLLISION. It’s like two people trying to park in the same spot!

Solution 1: Chaining (The Linked List Way) 🔗

Each box can hold a little LIST of items instead of just one.

Box 2: ["cat"] → ["act"] → ["tac"]
         ↓
       All three words share box 2!

In C:

struct Node {
    char* key;
    int value;
    struct Node* next;  // link!
};

struct Node* table[10];  // 10 boxes

Pros: Simple! Never runs out of space. Cons: If one box gets too crowded, it slows down.

Solution 2: Open Addressing (Find Another Spot) 🏃

If your spot is taken, look for the next empty one!

"cat" wants box 2 → box 2 empty → PLACED!
"act" wants box 2 → box 2 full → try box 3 → PLACED!

Types of Open Addressing:

graph TD
    A["Collision at Box i"] --> B{Open Addressing}
    B --> C["Linear: Try i+1, i+2..."]
    B --> D["Quadratic: Try i+1, i+4, i+9..."]
    B --> E["Double Hash: Use 2nd formula"]
    style B fill:#FF6B6B,stroke:#333

Linear Probing Example

int find_spot(int start, int attempt) {
    return (start + attempt) % TABLE_SIZE;
}

Problem: Items bunch up together (clustering) 🫤

Quadratic Probing

Jumps further each time: 1, 4, 9, 16…

int find_spot(int start, int attempt) {
    return (start + attempt*attempt) % SIZE;
}

Better spreading! Less bunching. ✅

🏗️ Building a Hash Table in C

Step 1: Define the Structure

#define SIZE 100

struct Item {
    char* key;
    int value;
};

struct Item* hashTable[SIZE];

Step 2: The Hash Function

int hashCode(char* key) {
    int hash = 0;
    for (int i = 0; key[i]; i++) {
        hash = hash * 31 + key[i];
    }
    return hash % SIZE;
}

Step 3: Insert an Item

void insert(char* key, int value) {
    int index = hashCode(key);

    // Handle collision with linear probe
    while (hashTable[index] != NULL) {
        index = (index + 1) % SIZE;
    }

    hashTable[index] = malloc(sizeof(struct Item));
    hashTable[index]->key = key;
    hashTable[index]->value = value;
}

Step 4: Find an Item

int search(char* key) {
    int index = hashCode(key);

    while (hashTable[index] != NULL) {
        if (strcmp(hashTable[index]->key, key) == 0) {
            return hashTable[index]->value;
        }
        index = (index + 1) % SIZE;
    }
    return -1;  // Not found
}

⚡ Why Hash Tables are AMAZING

O(1) means: No matter if you have 10 items or 10 million, finding something takes the SAME time!

🎮 Where Do We Use Hash Tables?

1. Phone Contacts 📱

   • Name → Phone number (instant lookup!)

2. Spell Checkers ✍️

   • Is “teh” a word? Check instantly!

3. Game High Scores 🎯

   • Player name → Their score

4. Website Logins 🔐

   • Username → Password (hashed for safety!)

5. Caching 💾

   • Already calculated this? Here’s the answer!

🧠 Quick Summary

graph TD
    A["Hash Table"] --> B["Hash Function"]
    A --> C["Array of Buckets"]
    A --> D["Collision Handler"]

    B --> B1["Converts key to index"]
    C --> C1["Stores key-value pairs"]
    D --> D1["Chaining"]
    D --> D2["Open Addressing"]

    style A fill:#667eea,stroke:#333,color:#fff
    style B fill:#4ECDC4,stroke:#333
    style C fill:#FF6B6B,stroke:#333
    style D fill:#95E1D3,stroke:#333

The Three Big Ideas:

1. Hash Table = Magic numbered boxes for instant lookup
2. Hash Function = The spell that turns any key into a box number
3. Collision Handling = The backup plan when two keys want the same box

🌟 You Did It!

Now you understand how computers can find anything in the blink of an eye. Hash tables power everything from your contacts app to Google’s search engine.

Remember the magic library? You ARE the librarian now. You know the secret system! 🧙‍♂️

“With a good hash function, finding a needle in a haystack takes the same time as finding an elephant in an empty room.”

Happy Coding! 🚀