Why HashMap Implementation from Scratch in DSA Typescript?

The Big Idea

What if you could find any item instantly, no matter how big your collection is?

The Scenario

Imagine you have a huge collection of books and you want to find a specific book quickly by its title. If you look through each book one by one, it will take a lot of time.

Now, think about writing down each book's title and its shelf number on a piece of paper. When you want a book, you check the paper instead of searching all shelves.

The Problem

Manually searching through all books one by one is very slow and tiring, especially when the collection grows.

Writing down all titles and shelf numbers on paper can get messy and hard to update when books are added or removed.

It's easy to make mistakes, lose track, or waste time flipping through pages.

The Solution

A HashMap is like a smart, organized notebook that uses a special formula (hash function) to quickly find where each book is stored.

It stores pairs of keys (like book titles) and values (like shelf numbers) so you can find, add, or remove books fast without searching everything.

Before vs After

✗ Before

let books = [['Harry Potter', 12], ['Lord of the Rings', 7]];
function findBook(title) {
  for (let i = 0; i < books.length; i++) {
    if (books[i][0] === title) return books[i][1];
  }
  return -1;
}

✓ After

class HashMap {
  private map: {[key: string]: number} = {};
  set(key: string, value: number) { this.map[key] = value; }
  get(key: string) { return this.map[key] ?? -1; }
}

What It Enables

HashMaps let you find, add, or remove data instantly, even in huge collections, making programs faster and easier to manage.

Real Life Example

Online stores use HashMaps to quickly find product details by product ID so customers see information instantly without waiting.

Key Takeaways

Manual searching is slow and error-prone for large data.

HashMaps use keys and a formula to store and find data fast.

This makes programs efficient and scalable.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store data in a sorted order

B. To store key-value pairs for fast data retrieval

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand HashMap functionality

   A HashMap stores data as key-value pairs, allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option B

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Thinking HashMap stores data in order
• Confusing HashMap with arrays
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap class property in TypeScript?

easy

A. private map: {[key: string]: any} = {};

B. map = new Map();

C. let map = [];

D. const map: Map = {};

Solution

1. Step 1: Identify TypeScript syntax for object property

   Declaring a private property with type {[key: string]: any} initializes an object for key-value storage.

2. Step 2: Check other options for correctness

   map = new Map(); uses built-in Map, not a plain object; C is an array; D has wrong Map type usage.

3. Final Answer:

   private map: {[key: string]: any} = {}; -> Option A

4. Quick Check:

   TypeScript object property syntax = private map: {[key: string]: any} = {}; [OK]

Hint: Use object type {[key: string]: any} for HashMap storage [OK]

Common Mistakes:

• Using array instead of object for map
• Incorrect Map type declaration
• Confusing built-in Map with plain object

3. What will be the output of this TypeScript code snippet implementing a simple HashMap?

class SimpleHashMap {
  private map: {[key: string]: string} = {};
  set(key: string, value: string) {
    this.map[key] = value;
  }
  get(key: string) {
    return this.map[key] || null;
  }
}
const h = new SimpleHashMap();
h.set('a', 'apple');
h.set('b', 'banana');
console.log(h.get('a'));
console.log(h.get('c'));

medium

A. "apple" followed by null

B. "apple" followed by undefined

C. undefined followed by null

D. Error at runtime

Solution

1. Step 1: Trace set method calls

   Keys 'a' and 'b' are set with values 'apple' and 'banana' respectively in the map object.

2. Step 2: Trace get method calls

   Getting 'a' returns 'apple'; getting 'c' returns undefined, so || null returns null.

3. Final Answer:

   "apple" followed by null -> Option A

4. Quick Check:

   Existing key returns value, missing key returns null [OK]

Hint: Missing keys return null due to || null fallback [OK]

Common Mistakes:

• Expecting undefined instead of null for missing keys
• Confusing set and get method effects
• Assuming runtime error on missing key

4. Identify the bug in this simple HashMap implementation and choose the correct fix:

class BuggyHashMap {
  private map: {[key: string]: number} = {};
  set(key: string, value: number) {
    this.map[key] = value;
  }
  get(key: string): number {
    return this.map[key];
  }
}
const h = new BuggyHashMap();
h.set('x', 10);
console.log(h.get('y'));

medium

A. map should be an array instead of object

B. set method should check if key exists before setting

C. get should return number | null and handle missing keys

D. No bug, code works fine

Solution

1. Step 1: Analyze get method return type

   get returns number but missing keys return undefined, causing type mismatch.

2. Step 2: Fix get method to handle missing keys

   Change return type to number | null and return null if key missing to avoid undefined.

3. Final Answer:

   get should return number | null and handle missing keys -> Option C

4. Quick Check:

   Handle missing keys in get method [OK]

Hint: Always handle missing keys in get method return type [OK]

Common Mistakes:

• Ignoring undefined return for missing keys
• Changing map to array incorrectly
• Thinking set method needs key existence check

5. You want to implement a HashMap from scratch in TypeScript that handles collisions using chaining (array of entries). Which approach correctly adds a new key-value pair to the map?

hard

A. Store keys in an array and values in a separate array without hashing

B. Compute hash, overwrite bucket with new entry ignoring existing keys

C. Use a single array for all entries without hashing

D. Compute hash, check bucket array; if key exists update value, else push new entry

Solution

1. Step 1: Understand collision handling by chaining

   Chaining stores multiple entries in a bucket array; new entries are added or updated if key exists.

2. Step 2: Analyze options for correct collision handling

   Compute hash, check bucket array; if key exists update value, else push new entry correctly checks bucket, updates existing key or adds new entry; others ignore collisions or do not hash.

3. Final Answer:

   Compute hash, check bucket array; if key exists update value, else push new entry -> Option D

4. Quick Check:

   Chaining = bucket array with update or add [OK]

Hint: Check bucket for key, update or add entry to handle collisions [OK]

Common Mistakes:

• Overwriting bucket ignoring existing keys
• Not using hashing for bucket selection
• Storing keys and values separately without hashing