HashMap Implementation from Scratch in DSA Javascript - Time & Space Complexity

Time Complexity: HashMap Implementation from Scratch

O(n / b)

Understanding Time Complexity

When building a HashMap from scratch, it's important to know how fast it can add, find, or remove items.

We want to understand how the time to do these actions changes as the number of stored items grows.

Scenario Under Consideration

Analyze the time complexity of the following simple HashMap methods.

class SimpleHashMap {
  constructor(size) {
    this.buckets = new 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;
  }
}
    

This code creates a simple HashMap with buckets as arrays and handles collisions by storing key-value pairs in each bucket.

Identify Repeating Operations

Look at the loops and repeated steps in the code.

• Primary operation: Looping through a bucket array to find a key.
• How many times: Depends on the number of items in that bucket, which varies with total items and bucket count.

How Execution Grows With Input

As more items are added, buckets may hold more pairs, making searches longer.

Input Size (n)	Approx. Operations per get/set
10	About 1 to 2 checks (if buckets are 5)
100	About 10 to 20 checks (if buckets are 10)
1000	About 50 to 100 checks (if buckets are 20)

Pattern observation: More items mean longer bucket lists, so operations grow roughly in proportion to items per bucket.

Final Time Complexity

Time Complexity: O(n / b) where n is items and b is bucket count.

This means the time depends on how many items share the same bucket; more buckets mean faster operations.

Common Mistake

[X] Wrong: "HashMap operations always take constant time no matter what."

[OK] Correct: If many keys end up in the same bucket, searching that bucket takes longer, so time grows with items per bucket.

Interview Connect

Understanding how collisions affect speed shows you know the real workings of HashMaps, a key skill for coding interviews.

Self-Check

"What if we increased the number of buckets as items grow? How would that change the time complexity?"

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