Hash-Based Design

🏪 Hash-Based Design: Building Smart Storage Systems

Imagine you’re the manager of a magical library. Not just any library—one where books can appear, disappear, and you need to remember which ones people read most recently. Today, we’ll learn how to build three amazing storage systems using the power of hash tables!

🌟 Our Everyday Metaphor: The Smart Locker System

Think of a hash table like a wall of smart lockers at a gym:

• Each locker has a number (the key)
• Inside is your stuff (the value)
• A special robot helper (hash function) tells you exactly which locker to use

Now let’s build three incredible systems!

📦 1. Design HashMap: Your Personal Locker Wall

What is a HashMap?

A HashMap is like having your own wall of lockers where:

• You pick a name for each locker (key)
• You put anything you want inside (value)
• The robot instantly knows which locker matches which name

Simple Example:

🔑 "apple" → 🗄️ Locker #3 → 🍎 Price: $2
🔑 "banana" → 🗄️ Locker #7 → 🍌 Price: $1
🔑 "orange" → 🗄️ Locker #3 → 💥 Collision!

The Collision Problem 💥

Sometimes two keys want the same locker! This is called a collision.

Solution: Chaining 🔗 Each locker can hold a small chain of items:

Locker #3: [apple→$2] → [orange→$3]

Building Our HashMap

class MyHashMap {
  constructor() {
    this.size = 1000;
    this.buckets = new Array(this.size)
      .fill(null)
      .map(() => []);
  }

  // Robot helper picks locker
  _hash(key) {
    return key % this.size;
  }

  // Put item in locker
  put(key, value) {
    const idx = this._hash(key);
    const bucket = this.buckets[idx];

    for (let pair of bucket) {
      if (pair[0] === key) {
        pair[1] = value; // Update
        return;
      }
    }
    bucket.push([key, value]); // New
  }

  // Find item in locker
  get(key) {
    const idx = this._hash(key);
    for (let pair of this.buckets[idx]) {
      if (pair[0] === key) return pair[1];
    }
    return -1; // Not found
  }

  // Remove from locker
  remove(key) {
    const idx = this._hash(key);
    const bucket = this.buckets[idx];
    const i = bucket.findIndex(p => p[0] === key);
    if (i !== -1) bucket.splice(i, 1);
  }
}

Real Life Example 🎮

const prices = new MyHashMap();
prices.put(1, 100);  // Item #1 costs $100
prices.put(2, 200);  // Item #2 costs $200
prices.get(1);       // Returns 100
prices.remove(2);    // Bye bye item #2
prices.get(2);       // Returns -1 (gone!)

🎯 2. Design HashSet: The Guest List

What is a HashSet?

A HashSet is like a bouncer’s guest list at a party:

• Names only—no extra info
• Each name appears only once
• Quick check: “Is this person on the list?”

Simple Example:

Guest List: { "Alice", "Bob", "Charlie" }

✅ "Is Alice invited?" → YES!
❌ "Is Dave invited?" → NO!

Building Our HashSet

class MyHashSet {
  constructor() {
    this.size = 1000;
    this.buckets = new Array(this.size)
      .fill(null)
      .map(() => []);
  }

  _hash(key) {
    return key % this.size;
  }

  // Add guest to list
  add(key) {
    if (!this.contains(key)) {
      this.buckets[this._hash(key)].push(key);
    }
  }

  // Remove guest
  remove(key) {
    const bucket = this.buckets[this._hash(key)];
    const idx = bucket.indexOf(key);
    if (idx !== -1) bucket.splice(idx, 1);
  }

  // Check if invited
  contains(key) {
    return this.buckets[this._hash(key)]
      .includes(key);
  }
}

Real Life Example 🎉

const guests = new MyHashSet();
guests.add(1);        // Guest #1 invited
guests.add(2);        // Guest #2 invited
guests.contains(1);   // true - welcome!
guests.remove(2);     // Guest #2 uninvited
guests.contains(2);   // false - sorry!

🏆 3. LRU Cache: The VIP Memory System

What is an LRU Cache?

LRU = Least Recently Used

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

Simple Example:

Memory capacity: 3 items

Add "Mom"    → [Mom]
Add "Dad"    → [Dad, Mom]
Add "Friend" → [Friend, Dad, Mom]
Add "Boss"   → [Boss, Friend, Dad] 💨 Mom forgotten!

Use "Dad"    → [Dad, Boss, Friend]
              (Dad moves to front!)

The Magic Combo 🪄

LRU Cache uses two data structures together:

graph TD
    A["HashMap"] -->|O 1 lookup| B["Find item instantly"]
    C["Doubly Linked List"] -->|O 1 reorder| D["Move items easily"]
    B --> E["🏆 Fast cache!"]
    D --> E

• HashMap: Find any item in O(1)
• Doubly Linked List: Move items around in O(1)

Building Our LRU Cache

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // HashMap!
    // Map keeps insertion order
    // in JavaScript
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    // Move to "recently used"
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    // If exists, remove first
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }

    // Add as most recent
    this.cache.set(key, value);

    // Too full? Remove oldest
    if (this.cache.size > this.capacity) {
      // First key = oldest
      const oldest = this.cache.keys().next().value;
      this.cache.delete(oldest);
    }
  }
}

Real Life Example 🧠

const browser = new LRUCache(3);

browser.put(1, "google.com");
browser.put(2, "youtube.com");
browser.put(3, "github.com");
// Cache: [1, 2, 3]

browser.get(1); // Returns "google.com"
// Cache: [2, 3, 1] - google moved to end!

browser.put(4, "twitter.com");
// Cache: [3, 1, 4] - youtube evicted!

browser.get(2); // Returns -1 (evicted!)

🎨 The Big Picture

graph LR
    H["Hash Table Magic"] --> A["HashMap"]
    H --> B["HashSet"]
    H --> C["LRU Cache"]

    A --> A1["Key→Value pairs"]
    A --> A2["put/get/remove"]

    B --> B1["Keys only"]
    B --> B2["add/contains/remove"]

    C --> C1["Limited memory"]
    C --> C2["Evicts least used"]

💡 Why Does This Matter?

🚀 Key Takeaways

1. HashMap = Lockers with names + stuff inside
2. HashSet = Guest list (names only, no duplicates)
3. LRU Cache = Smart brain that forgets old stuff
4. Hash function = Robot that picks the right locker
5. Collisions = When two keys want same locker (use chaining!)

🌈 You Did It!

You now understand three powerful hash-based designs:

✅ HashMap: Store anything with instant lookup ✅ HashSet: Track unique items efficiently ✅ LRU Cache: Smart memory that keeps recent items

These patterns power everything from databases to web browsers. You’re thinking like a real engineer now! 🎉