HashMap Implementation from Scratch in DSA Javascript - Build from Scratch

HashMap Implementation from Scratch

📖 Scenario: Imagine you want to create a simple phone book app that stores names and phone numbers. To do this efficiently, you will build a basic HashMap from scratch in JavaScript. This will help you understand how data can be stored and found quickly.

🎯 Goal: Build a simple HashMap class with methods to add key-value pairs, retrieve values by key, and display all stored entries.

📋 What You'll Learn

Create a HashMap class with an internal array called buckets of size 10.

Add a hash method that converts a string key into an index between 0 and 9.

Add a set method to store a key-value pair in the correct bucket.

Add a get method to retrieve a value by its key.

Add a print method to display all key-value pairs in the HashMap.

💡 Why This Matters

🌍 Real World

HashMaps are used in many apps to store and find data quickly, like phone books, caches, and databases.

💼 Career

Understanding HashMaps helps in software development roles where efficient data storage and retrieval are important.

1

Create the HashMap class with buckets

Create a class called HashMap with a constructor that initializes a property called buckets as an array of length 10 filled with empty arrays.

DSA Javascript

class HashMap {
  constructor() {
    // Your code here
  }
}

Hint

Use Array(10).fill(null).map(() => []) to create an array of 10 empty arrays.

2

Add the hash function

Inside the HashMap class, add a method called hash that takes a string key and returns a number between 0 and 9 by summing the character codes of the key and taking the remainder when divided by 10.

DSA Javascript

class HashMap {
  constructor() {
    this.buckets = Array(10).fill(null).map(() => []);
  }

  // Your code here
}

Hint

Loop over each character in the key and add its code to sum. Then use sum % 10 to get the bucket index.

3

Add set and get methods

Add a set method that takes key and value, finds the correct bucket using hash(key), and stores the pair. If the key exists, update the value. Also add a get method that returns the value for a given key or undefined if not found.

DSA Javascript

class HashMap {
  constructor() {
    this.buckets = Array(10).fill(null).map(() => []);
  }

  hash(key) {
    let sum = 0;
    for (let i = 0; i < key.length; i++) {
      sum += key.charCodeAt(i);
    }
    return sum % 10;
  }

  // Your code here
}

Hint

Use the hash to find the bucket. Check if the key exists to update or add the pair. For get, search the bucket and return the value or undefined.

4

Add print method and test the HashMap

Add a print method that loops through all buckets and prints each key-value pair in the format key: value. Then create a HashMap instance, add these entries using set: 'Alice' : '1234', 'Bob' : '5678', 'Charlie' : '91011'. Finally, call print() to display all entries.

DSA Javascript

class HashMap {
  constructor() {
    this.buckets = Array(10).fill(null).map(() => []);
  }

  hash(key) {
    let sum = 0;
    for (let i = 0; i < key.length; i++) {
      sum += key.charCodeAt(i);
    }
    return sum % 10;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    bucket.push([key, value]);
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        return bucket[i][1];
      }
    }
    return undefined;
  }

  // Your code here
}

const phoneBook = new HashMap();
// Your code here

Hint

Loop through each bucket and each pair inside it to print all entries. Then add the three entries and call print().

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