HashMap Implementation from Scratch in DSA Javascript - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Initialize HashMap with fixed size array

↓

Hash function: key -> index

↓

Insert key-value pair at index

↓

If collision: use chaining (linked list) at index

↓

Search key: hash key -> index -> traverse chain

↓

Retrieve or update value

↓

Delete key: hash key -> index -> remove from chain

↓

Done

Shows how keys are hashed to array indices, stored with chaining for collisions, and accessed or removed.

Execution Sample

DSA Javascript

class HashMap {
  constructor(size = 5) {
    this.buckets = Array(size).fill(null).map(() => []);
  }
  _hash(key) {
    let hash = 0;
    for (let char of key) hash += char.charCodeAt(0);
    return hash % this.buckets.length;
  }
  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 [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }
  delete(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        return true;
      }
    }
    return false;
  }
}

This code creates a simple HashMap with fixed buckets, hashing keys to indices, handling collisions by chaining, and supports set, get, and delete.

Execution Table

Step	Operation	Key	Hashed Index	Bucket State	Pointer Changes	Visual State
1	Initialize HashMap	-	-	[[], [], [], [], []]	-	[[], [], [], [], []]
2	Set key-value	apple	0	[['apple', 10]]	Insert at bucket 0	[[['apple',10]], [], [], [], []]
3	Set key-value	lime	3	[['apple', 10], [], [], ['lime', 20], []]	Insert at bucket 3	[[['apple',10]], [], [], [['lime',20]], []]
4	Set key-value	fig	0	[['apple', 10], ['fig', 15], [], ['lime', 20], []]	Collision at bucket 0, append	[[['apple',10], ['fig',15]], [], [], [['lime',20]], []]
5	Get value	lime	3	[['apple', 10], ['fig', 15], [], ['lime', 20], []]	Traverse bucket 3, found 'lime'	[[['apple',10], ['fig',15]], [], [], [['lime',20]], []]
6	Delete key	apple	0	[['fig', 15], [], [], ['lime', 20], []]	Remove 'apple' from bucket 0	[[['fig',15]], [], [], [['lime',20]], []]
7	Get value	apple	0	[[['fig',15]], [], [], [['lime',20]], []]	Traverse bucket 0, 'apple' not found	[[['fig',15]], [], [], [['lime',20]], []]
8	Set key-value	lime	3	[[['fig',15]], [], [], [['lime', 25]], []]	Update 'lime' value in bucket 3	[[['fig',15]], [], [], [['lime',25]], []]
9	Get value	lime	3	[[['fig',15]], [], [], [['lime',25]], []]	Traverse bucket 3, found updated 'lime'	[[['fig',15]], [], [], [['lime',25]], []]
10	Delete key	orange	1	[[['fig',15]], [], [], [['lime',25]], []]	Bucket 1 empty, nothing to delete	[[['fig',15]], [], [], [['lime',25]], []]
11	End	-	-	-	-	No more operations

💡 All operations completed; HashMap buckets show final chained key-value pairs.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	Final
buckets	[[], [], [], [], []]	[[['apple',10]], [], [], [], []]	[[['apple',10]], [], [], [['lime',20]], []]	[[['apple',10], ['fig',15]], [], [], [['lime',20]], []]	[[['fig',15]], [], [], [['lime',20]], []]	[[['fig',15]], [], [], [['lime',25]], []]	[[['fig',15]], [], [], [['lime',25]], []]
key	-	apple	lime	fig	apple	lime	orange
hashedIndex	-	0	3	0	0	3	1

Key Moments - 3 Insights

Why do we need to check the bucket array at the hashed index before inserting?

Because multiple keys can hash to the same index (collision), so we must check the bucket (a list) to either update an existing key or add a new key-value pair, as shown in steps 4 and 8 in the execution_table.

What happens when we try to get a key that does not exist?

The get operation hashes the key to find the bucket, then traverses the bucket list. If the key is not found, it returns undefined, as shown in step 7 when 'apple' was deleted and then searched.

How does the delete operation remove a key from the HashMap?

It hashes the key to find the bucket, then traverses the bucket list to find the key and removes it using splice, as shown in step 6 where 'apple' was removed from bucket 0.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the bucket state after inserting 'fig'?

A [['apple', 10], ['fig', 15]] at bucket 0

B [['fig', 15]] at bucket 0

C [['fig', 15]] at bucket 3

D [['apple', 10], ['fig', 15]] at bucket 3

💡 Hint

Check the 'Bucket State' column at step 4 in the execution_table.

At which step does the value for key 'lime' get updated?

A Step 3

B Step 8

C Step 5

D Step 6

💡 Hint

Look for 'Update' operation on 'lime' in the execution_table.

If we try to delete a key not present in the HashMap, what happens to the buckets?

A Buckets become empty

B All keys are removed

C Buckets remain unchanged

D New empty bucket is added

💡 Hint

See step 10 in execution_table where 'orange' deletion is attempted.

Concept Snapshot

HashMap stores key-value pairs using an array of buckets.
Keys are hashed to an index using a hash function.
Collisions are handled by chaining: storing multiple pairs in a bucket list.
Operations: set (insert/update), get (retrieve), delete (remove).
Each operation hashes the key, then works within the bucket at that index.
Simple, fast average access with collision handling.

Full Transcript

This visual execution shows how a HashMap works internally. We start with an empty array of buckets. Each key is converted to an index by a hash function. When inserting, if the bucket is empty, the key-value pair is added. If not, we check for the key to update or append it to handle collisions. Getting a value means hashing the key and searching the bucket list. Deleting removes the key from the bucket list if found. The execution table tracks each step, showing how buckets change and how pointers move. This helps understand the chaining method for collisions and how keys are stored and retrieved efficiently.

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