Hash-Based Design

Hash-Based Design: Building Smart Memory Systems 🧠

The Story of the Magical Library

Imagine you’re a librarian in a HUGE library with millions of books. Every day, hundreds of people ask you:

“Where is the book about dragons?”

If you had to walk through every shelf to find it… you’d never finish! 😫

But what if you had a magic filing system? You whisper “dragons” and instantly know: Shelf 42, Row 3!

That’s exactly what Hash Tables do for computers. They’re the magic filing system that finds things INSTANTLY!

What We’ll Build Together

graph TD
    A["Hash-Based Design"] --> B["HashMap"]
    A --> C["HashSet"]
    A --> D["LRU Cache"]
    B --> E["Store Key-Value Pairs"]
    C --> F["Store Unique Items"]
    D --> G["Remember Recent Things"]

Today, we’ll design THREE powerful tools:

1. HashMap - A dictionary that finds words instantly
2. HashSet - A guest list that never has duplicates
3. LRU Cache - A smart brain that remembers important stuff

Part 1: Design HashMap 📚

What is a HashMap?

Think of a HashMap like a magical address book.

The Magic: You don’t search page by page. You ask for “Emma” and BOOM - you get her number!

How Does the Magic Work?

Step 1: The Hash Function (The Magic Spell ✨)

Every name gets turned into a NUMBER using a special spell:

// Simple hash function
int hash(String key) {
    int number = 0;
    for (char c : key.toCharArray()) {
        number += c;  // Add letter values
    }
    return number % arraySize;
}

Example:

• “CAT” → C(67) + A(65) + T(84) = 216
• If array size is 10: 216 % 10 = 6
• So “CAT” lives at position 6!

Step 2: The Buckets (Storage Boxes 📦)

graph TD
    subgraph HashMap
    B0["Bucket 0"]
    B1["Bucket 1"]
    B2["Bucket 2"]
    B3["Bucket 3"]
    end
    B0 --> N1["apple→red"]
    B2 --> N2["cat→meow"]
    B2 --> N3["act→play"]

Sometimes two keys get the same number (like “cat” and “act”). That’s called a collision. We solve it by chaining items together!

Let’s Build It! 🔨

The Blueprint

class MyHashMap {
    // Our storage: array of linked lists
    LinkedList<int[]>[] buckets;
    int size = 1000; // 1000 buckets

    public MyHashMap() {
        buckets = new LinkedList[size];
    }
}

The Three Main Powers

Power 1: PUT (Store something)

void put(int key, int value) {
    int index = key % size;

    // Create bucket if empty
    if (buckets[index] == null) {
        buckets[index] = new LinkedList<>();
    }

    // Update if key exists
    for (int[] pair : buckets[index]) {
        if (pair[0] == key) {
            pair[1] = value;
            return;
        }
    }

    // Add new pair
    buckets[index].add(new int[]{key, value});
}

Power 2: GET (Find something)

int get(int key) {
    int index = key % size;

    if (buckets[index] == null) {
        return -1; // Not found!
    }

    for (int[] pair : buckets[index]) {
        if (pair[0] == key) {
            return pair[1]; // Found it!
        }
    }

    return -1; // Not in this bucket
}

Power 3: REMOVE (Delete something)

void remove(int key) {
    int index = key % size;

    if (buckets[index] == null) return;

    buckets[index].removeIf(
        pair -> pair[0] == key
    );
}

Real-Life Example 🌟

MyHashMap phonebook = new MyHashMap();

// Store contacts
phonebook.put(101, 5551234);  // ID 101
phonebook.put(102, 5555678);  // ID 102

// Find Emma's number
int emmaNumber = phonebook.get(101);
// Returns: 5551234

// Emma changed her number
phonebook.put(101, 5559999);

// Remove old contact
phonebook.remove(102);

Part 2: Design HashSet 🎯

What is a HashSet?

A HashSet is like a VIP guest list at a party.

Rules:

• Each person can only be on the list ONCE
• You can quickly check if someone is invited
• You can add or remove guests

graph LR
    A["Guest List"] --> B{Is Emma here?}
    B -->|Yes| C["Already invited!"]
    B -->|No| D["Add her name"]

The Secret: It’s Just a HashMap… Without Values!

Think about it:

• HashMap stores: key → value
• HashSet stores: key → (nothing)

We only care about the KEY existing!

Let’s Build It! 🔧

class MyHashSet {
    LinkedList<Integer>[] buckets;
    int size = 1000;

    public MyHashSet() {
        buckets = new LinkedList[size];
    }

    // Add a guest (if not already there)
    void add(int key) {
        int index = key % size;

        if (buckets[index] == null) {
            buckets[index] = new LinkedList<>();
        }

        if (!buckets[index].contains(key)) {
            buckets[index].add(key);
        }
    }

    // Is this guest on the list?
    boolean contains(int key) {
        int index = key % size;

        if (buckets[index] == null) {
            return false;
        }

        return buckets[index].contains(key);
    }

    // Remove a guest
    void remove(int key) {
        int index = key % size;

        if (buckets[index] != null) {
            buckets[index].remove(
                Integer.valueOf(key)
            );
        }
    }
}

Real-Life Example 🎉

MyHashSet vipList = new MyHashSet();

// Add guests
vipList.add(1);  // Emma joins
vipList.add(2);  // Tom joins
vipList.add(1);  // Emma tries again - ignored!

// Check the door
vipList.contains(1);  // true - Emma is VIP!
vipList.contains(3);  // false - stranger!

// Remove Tom (he was rude)
vipList.remove(2);

Part 3: LRU Cache 🧠

What is LRU Cache?

LRU = Least Recently Used

Imagine your brain can only remember 5 phone numbers. When you learn a 6th number, you forget the one you haven’t used the longest!

graph TD
    A["New Memory"] --> B{Brain Full?}
    B -->|No| C["Just add it!"]
    B -->|Yes| D["Forget oldest unused"]
    D --> C

The Two Superpowers Combined! 💪

To build LRU Cache, we need:

graph LR
    subgraph Linked List Order
    A["Most Recent"] --> B --> C --> D["Least Recent"]
    end
    subgraph HashMap Quick Access
    H["HashMap"] -.-> A
    H -.-> B
    H -.-> C
    H -.-> D
    end

The Clever Trick 🎩

Doubly Linked List = Each item knows its neighbors!

[HEAD] ↔ [Item A] ↔ [Item B] ↔ [Item C] ↔ [TAIL]

• HEAD: Fake start marker
• TAIL: Fake end marker
• New stuff goes after HEAD (most recent)
• Old stuff near TAIL gets removed

Let’s Build It! 🏗️

The Node (Each Memory Cell)

class Node {
    int key;
    int value;
    Node prev;
    Node next;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

The LRU Cache Class

class LRUCache {
    int capacity;
    Map<Integer, Node> map;
    Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();

        // Create dummy head and tail
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
}

The Helper Methods

// Add node right after HEAD (most recent)
void addToFront(Node node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
}

// Remove a node from anywhere
void removeNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

// Move existing node to front
void moveToFront(Node node) {
    removeNode(node);
    addToFront(node);
}

GET - Access a Memory

int get(int key) {
    if (!map.containsKey(key)) {
        return -1; // Don't remember this!
    }

    Node node = map.get(key);
    moveToFront(node); // I just used this!
    return node.value;
}

PUT - Store a Memory

void put(int key, int value) {
    // Already exists? Update it
    if (map.containsKey(key)) {
        Node node = map.get(key);
        node.value = value;
        moveToFront(node);
        return;
    }

    // Brain full? Forget oldest
    if (map.size() >= capacity) {
        Node oldest = tail.prev;
        removeNode(oldest);
        map.remove(oldest.key);
    }

    // Add new memory
    Node newNode = new Node(key, value);
    addToFront(newNode);
    map.put(key, newNode);
}

Real-Life Example 🌟

// Brain that remembers 3 things
LRUCache brain = new LRUCache(3);

brain.put(1, 100);  // Remember A
brain.put(2, 200);  // Remember B
brain.put(3, 300);  // Remember C
// Order: [3, 2, 1]

brain.get(1);       // Used A!
// Order: [1, 3, 2]

brain.put(4, 400);  // Remember D
// Brain full! Forget B (least recent)
// Order: [4, 1, 3]

brain.get(2);       // Returns -1
// "Who? I don't remember B!"

Why LRU Cache is AMAZING 🚀

Compare to searching through everything: O(n) - Slow! 🐢

Summary: Your New Superpowers! 💫

graph LR
    A["Hash-Based Design"] --> B["HashMap"]
    A --> C["HashSet"]
    A --> D["LRU Cache"]

    B --> B1["Fast key-value lookup"]
    B --> B2["O of 1 operations"]

    C --> C1["No duplicates"]
    C --> C2["Fast membership check"]

    D --> D1["Limited memory"]
    D --> D2["Forgets unused items"]
    D --> D3["HashMap + LinkedList"]

Key Takeaways

1. HashMap = Magic dictionary with instant lookup
2. HashSet = HashMap without values (just checking existence)
3. LRU Cache = Smart memory that forgets old unused things
4. Hash Function = Turns keys into array positions
5. Collision Handling = Chain items when positions collide

You Did It! 🎊

You now understand how to design:

• ✅ Your own HashMap
• ✅ Your own HashSet
• ✅ Your own LRU Cache

These are REAL interview questions at top tech companies. You just learned what many struggle to understand!

Remember: The magic isn’t in memorizing code. It’s in understanding WHY it works. Now you do! 🌟