Hash-Based Design

Hash-Based Design: Building Smart Storage Systems 🏗️

Imagine you have a magical library where books can teleport to your hands instantly. That’s what we’re building today!

The Story: The Library of Instant Answers

Once upon a time, there was a tiny village with a HUGE library. People would ask for books all day long. But the librarian had a problem—she couldn’t remember where every book was!

So she invented three magical tools:

1. A Magic Bookshelf (HashMap) - stores books with instant lookup
2. A Guest Book (HashSet) - remembers who visited, no duplicates
3. A “Recently Popular” Display (LRU Cache) - shows the books people asked for most recently

Let’s learn how to build each one!

1. Design HashMap: Your Magic Bookshelf 📚

What Is a HashMap?

Think of it like a coat check at a party:

• You give them your coat (the value)
• They give you a ticket number (the key)
• Later, you show your ticket and get your coat INSTANTLY!

# Simple HashMap Example
my_map = {}
my_map["apple"] = 5      # Store: key="apple", value=5
print(my_map["apple"])   # Get: returns 5 instantly!

How Does the Magic Work?

The secret is a hash function—it turns any key into a number (an index).

graph TD
    A["Key: 'apple'"] --> B["Hash Function"]
    B --> C["Index: 3"]
    C --> D["Store at position 3"]

Building Your Own HashMap

Here’s the recipe:

class MyHashMap:
    def __init__(self):
        # Create 1000 empty buckets
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key):
        # Turn key into bucket number
        return key % self.size

    def put(self, key, value):
        # Find the right bucket
        idx = self._hash(key)
        # Check if key exists, update it
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        # New key, add it
        self.buckets[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return -1  # Not found

    def remove(self, key):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                del self.buckets[idx][i]
                return

Why Buckets?

Sometimes two keys get the same hash (called a collision).

Example: Both “cat” and “act” might hash to index 7!

We solve this by making each position a list (bucket) that can hold multiple items.

Index 0: []
Index 1: [("dog", 10)]
Index 2: []
Index 3: [("cat", 5), ("act", 3)]  ← Both live here!

2. Design HashSet: The Guest Book 📝

What Is a HashSet?

It’s like a VIP list at a club:

• You can add a name
• You can check if someone’s on the list
• You can remove a name
• No duplicates allowed! (Can’t add the same person twice)

HashSet vs HashMap

Building Your Own HashSet

class MyHashSet:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key):
        return key % self.size

    def add(self, key):
        idx = self._hash(key)
        # Only add if not already there
        if key not in self.buckets[idx]:
            self.buckets[idx].append(key)

    def contains(self, key):
        idx = self._hash(key)
        return key in self.buckets[idx]

    def remove(self, key):
        idx = self._hash(key)
        if key in self.buckets[idx]:
            self.buckets[idx].remove(key)

Real-World Uses

• Checking if a username is taken
• Tracking which pages you’ve visited
• Finding unique words in a document

3. LRU Cache: The “Recently Popular” Display 🌟

What Is LRU Cache?

LRU = Least Recently Used

Imagine your desk can only hold 3 books. When you want a 4th book, you must remove one. Which one? The one you haven’t touched in the longest time!

graph TD
    A["Desk has: Book A, B, C"] --> B["Want Book D"]
    B --> C["Remove A #40;oldest#41;"]
    C --> D["Desk now: B, C, D"]

Why Do We Need This?

Your computer has limited fast memory. LRU Cache keeps the most useful stuff ready and throws away what you haven’t used.

Real examples:

• Browser history (recent pages load faster)
• Netflix (recently watched shows are ready)
• Your phone’s app switcher

The Secret Recipe

We need TWO ingredients:

1. HashMap - for instant lookup (O(1) access)
2. Doubly Linked List - to track order of use

graph LR
    subgraph "Order #40;Most → Least Recent#41;"
    HEAD --> D --> C --> B --> TAIL
    end
    subgraph "HashMap"
    KEY_D --> D
    KEY_C --> C
    KEY_B --> B
    end

Building Your Own LRU Cache

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # HashMap: key → Node

        # Dummy head and tail
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        # Remove node from list
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        # Add right after head
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # Move to front (most recent)
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            # Update existing
            self._remove(self.cache[key])

        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)

        if len(self.cache) > self.capacity:
            # Remove least recent (before tail)
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Let’s Walk Through an Example!

LRU Cache with capacity = 2

The Big Picture: How They Connect

graph TD
    subgraph "Hash-Based Structures"
    A["HashMap"] --> |"Stores key→value"| D["Instant Lookup O#40;1#41;"]
    B["HashSet"] --> |"Stores unique keys"| D
    C["LRU Cache"] --> |"HashMap + Linked List"| D
    end

    C --> E["Limited Capacity"]
    C --> F["Removes Least Used"]

Summary: Your New Superpowers! 🦸

Time Complexity Cheat Code

You Did It! 🎉

You now understand three powerful tools that real engineers use every day:

1. HashMap - Your instant-access dictionary
2. HashSet - Your no-duplicates list
3. LRU Cache - Your smart, limited-space storage

These are the building blocks of:

• Databases
• Web browsers
• Operating systems
• Every app on your phone!

Next time you search for something and it appears instantly—you’ll know a HashMap helped make that happen!

“The best data structure is the one that makes the impossible feel instant.”