Why HashMap Implementation from Scratch in DSA Javascript?

The Big Idea

What if you could find anything 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. Without any system, you would have to look through every book one by one, which takes a lot of time.

The Problem

Searching manually through a large list is slow and tiring. You might lose track or make mistakes, especially if the list keeps growing. It's like looking for a needle in a haystack every time.

The Solution

A HashMap acts like a smart organizer that uses a special code (hash) to place each book in a specific spot. This way, you can jump directly to the spot where the book should be, making search, add, and remove operations very fast and easy.

Before vs After

✗ Before

const books = ['BookA', 'BookB', 'BookC'];
function findBook(title) {
  for (let i = 0; i < books.length; i++) {
    if (books[i] === title) return i;
  }
  return -1;
}

✓ After

class HashMap {
  constructor() {
    this.map = {};
  }
  set(key, value) {
    this.map[key] = value;
  }
  get(key) {
    return this.map[key];
  }
}

What It Enables

With a HashMap, you can store and find data instantly, even when you have thousands or millions of items.

Real Life Example

Think of a phone book app on your phone. When you type a name, it quickly shows the number without searching every contact one by one, thanks to a HashMap-like system.

Key Takeaways

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

HashMaps use a hashing method to organize data for quick access.

This makes storing and retrieving data very fast and efficient.

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 data as a sequence of elements

C. To store data in a last-in-first-out order

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

Solution

1. Step 1: Understand what a HashMap stores

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike lists or stacks, HashMaps focus on fast lookup, not order or sequence.

3. Final Answer:

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

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMaps store pairs for quick lookup by key [OK]

Common Mistakes:

• Confusing HashMap with list or stack
• Thinking HashMap stores data in order
• Assuming HashMap stores only values without keys

2. Which of the following is the correct way to define a simple HashMap class constructor in JavaScript?

easy

A. class HashMap { constructor() { this.map = {}; } }

B. class HashMap { constructor() { map = []; } }

C. function HashMap() { this.map = new Map(); }

D. class HashMap { constructor() { this.map = null; } }

Solution

1. Step 1: Check class syntax and property initialization

   class HashMap { constructor() { this.map = {}; } } correctly defines a class with a constructor initializing an object property this.map.

2. Step 2: Identify errors in other options

   class HashMap { constructor() { map = []; } } misses this., so map is not a property. function HashMap() { this.map = new Map(); } uses function syntax, not class. class HashMap { constructor() { this.map = null; } } initializes this.map to null, which is not useful for storing pairs.

3. Final Answer:

   class HashMap { constructor() { this.map = {}; } } -> Option A

4. Quick Check:

   Proper class constructor uses this.property = value [OK]

Hint: Use this.property inside constructor for class fields [OK]

Common Mistakes:

• Forgetting 'this.' before property name
• Mixing function and class syntax
• Initializing property to null instead of object

3. Consider this simple HashMap implementation snippet:

class HashMap {
  constructor() {
    this.map = {};
  }
  set(key, value) {
    this.map[key] = value;
  }
  get(key) {
    return this.map[key] || null;
  }
}

const h = new HashMap();
h.set('a', 1);
h.set('b', 2);
h.set('a', 3);
console.log(h.get('a'));

What will be printed?

medium

A. 3

B. 2

C. 1

D. null

Solution

1. Step 1: Trace the set operations

   First, key 'a' is set to 1, then 'b' to 2, then 'a' is updated to 3, overwriting previous value.

2. Step 2: Check the get operation

   Calling get('a') returns the current value for 'a', which is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Last set value for 'a' = 3 [OK]

Hint: Last set value for a key overwrites previous [OK]

Common Mistakes:

• Assuming first set value remains
• Confusing keys and values
• Expecting null if key was set before

4. The following HashMap method is intended to remove a key-value pair but has a bug:

remove(key) {
  delete this.map.key;
}

What is the correct fix?

medium

A. Change to delete this.map->key;

B. Change to this.map.delete(key);

C. Change to delete this.map[key];

D. Change to this.map.remove(key);

Solution

1. Step 1: Understand property access in JavaScript objects

   Using dot notation with this.map.key looks for property literally named 'key', not the variable key.

2. Step 2: Use bracket notation for dynamic keys

   Bracket notation this.map[key] accesses the property named by the variable key. So delete this.map[key]; correctly deletes the key-value pair.

3. Final Answer:

   Change to delete this.map[key]; -> Option C

4. Quick Check:

   Use brackets for variable keys [OK]

Hint: Use brackets [] to delete dynamic keys [OK]

Common Mistakes:

• Using dot notation with variable keys
• Using non-existent methods like remove()
• Using wrong delete syntax

5. You want to implement a keys() method in your HashMap class that returns all keys stored. Which of these implementations correctly returns an array of keys?

hard

A. keys() { return Object.values(this.map); }

B. keys() { return Object.keys(this.map); }

C. keys() { return this.map.keys(); }

D. keys() { return this.map.getKeys(); }

Solution

1. Step 1: Identify how to get keys from a plain object

   JavaScript's Object.keys() returns an array of keys from an object.

2. Step 2: Check other options for correctness

   keys() { return this.map.keys(); } assumes this.map is a Map object, but here it's a plain object, so this.map.keys() is undefined. keys() { return Object.values(this.map); } returns values, not keys. keys() { return this.map.getKeys(); } uses a non-existent method.

3. Final Answer:

   keys() { return Object.keys(this.map); } -> Option B

4. Quick Check:

   Object.keys() returns keys array [OK]

Hint: Use Object.keys() to get keys from plain objects [OK]

Common Mistakes:

• Using Map methods on plain objects
• Returning values instead of keys
• Calling non-existent methods