HashMap Implementation from Scratch in DSA Javascript

Mental Model

A HashMap stores key-value pairs by turning keys into numbers to find where to keep values quickly.

Analogy: Imagine a library where each book has a unique code. Instead of searching all books, you use the code to go directly to the shelf and find the book fast.

Buckets array:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
Each bucket can hold a linked list of key-value pairs.

Dry Run Walkthrough

Input: Insert keys 'cat', 'dog', 'bird' with values 5, 7, 3 into a HashMap of size 5

Goal: Store key-value pairs so we can find values by keys quickly using hashing and handle collisions

Step 1: Hash 'cat' to index 2, insert ('cat', 5) in bucket 2

[0] -> null
[1] -> null
[2] -> ('cat',5) -> null
[3] -> null
[4] -> null

Why: We convert 'cat' to a number to find bucket 2 and store the pair there

Step 2: Hash 'dog' to index 4, insert ('dog', 7) in bucket 4

[0] -> null
[1] -> null
[2] -> ('cat',5) -> null
[3] -> null
[4] -> ('dog',7) -> null

Why: Hashing 'dog' gives bucket 4, so we store the pair there

Step 3: Hash 'bird' to index 2, collision! Add ('bird', 3) to bucket 2 linked list

[0] -> null
[1] -> null
[2] -> ('cat',5) -> ('bird',3) -> null
[3] -> null
[4] -> ('dog',7) -> null

Why: Both 'cat' and 'bird' hash to bucket 2, so we chain them in a list

Step 4: Retrieve value for 'bird': hash to 2, search linked list in bucket 2

[0] -> null
[1] -> null
[2] -> ('cat',5) -> ('bird',3) -> null
[3] -> null
[4] -> ('dog',7) -> null

Why: We find 'bird' by checking each node in bucket 2's list

Result:

[0] -> null
[1] -> null
[2] -> ('cat',5) -> ('bird',3) -> null
[3] -> null
[4] -> ('dog',7) -> null
Value for 'bird' is 3

Annotated Code

DSA Javascript

class HashMap {
  constructor(size = 5) {
    this.buckets = new Array(size).fill(null);
    this.size = size;
  }

  // Simple hash function: sum char codes mod size
  hash(key) {
    let hashValue = 0;
    for (const char of key) {
      hashValue += char.charCodeAt(0);
    }
    return hashValue % this.size;
  }

  // Insert or update key-value pair
  set(key, value) {
    const index = this.hash(key); // find bucket
    if (this.buckets[index] === null) {
      this.buckets[index] = [{ key, value }]; // create list
    } else {
      // check if key exists, update
      for (const pair of this.buckets[index]) {
        if (pair.key === key) {
          pair.value = value; // update existing
          return;
        }
      }
      this.buckets[index].push({ key, value }); // add new pair
    }
  }

  // Retrieve value by key
  get(key) {
    const index = this.hash(key); // find bucket
    const bucket = this.buckets[index];
    if (bucket === null) return undefined; // no bucket
    for (const pair of bucket) {
      if (pair.key === key) {
        return pair.value; // found value
      }
    }
    return undefined; // not found
  }

  // Print all key-value pairs
  print() {
    for (let i = 0; i < this.size; i++) {
      const bucket = this.buckets[i];
      let bucketStr = `[${i}] -> `;
      if (bucket === null) {
        bucketStr += 'null';
      } else {
        bucketStr += bucket.map(p => `('${p.key}',${p.value})`).join(' -> ') + ' -> null';
      }
      console.log(bucketStr);
    }
  }
}

// Driver code
const map = new HashMap(5);
map.set('cat', 5);
map.set('dog', 7);
map.set('bird', 3);
map.print();
console.log('Value for bird is', map.get('bird'));

const index = this.hash(key); // find bucket

compute bucket index from key using hash function

if (this.buckets[index] === null) { this.buckets[index] = [{ key, value }]; }

if bucket empty, create new list with key-value pair

for (const pair of this.buckets[index]) { if (pair.key === key) { pair.value = value; return; } }

check for existing key in bucket to update value

this.buckets[index].push({ key, value });

add new key-value pair to bucket list on collision

const bucket = this.buckets[index]; if (bucket === null) return undefined;

return undefined if bucket empty when getting key

for (const pair of bucket) { if (pair.key === key) { return pair.value; } }

search bucket list for key to return value

Output

[0] -> null

[1] -> null

[2] -> ('cat',5) -> ('bird',3) -> null

[3] -> null

[4] -> ('dog',7) -> null

Value for bird is 3

Complexity Analysis

Time: O(1) average for insert and get because hashing finds bucket quickly; O(n) worst if many collisions in one bucket

Space: O(n) because we store all key-value pairs in buckets

vs Alternative: Compared to a simple list search O(n), hashing reduces average lookup to O(1) by direct indexing

Edge Cases

Insert duplicate key

Value updates instead of adding duplicate

DSA Javascript

if (pair.key === key) { pair.value = value; return; }

Get key not present

Returns undefined

DSA Javascript

if (bucket === null) return undefined;

Empty HashMap get

Returns undefined safely

DSA Javascript

if (bucket === null) return undefined;

When to Use This Pattern

When you need fast key-value storage and retrieval with average constant time, use a HashMap pattern with hashing and collision handling.

Common Mistakes

Mistake: Not handling collisions, overwriting existing bucket data
Fix: Use a list or chaining in each bucket to store multiple pairs

Mistake: Not updating value when inserting duplicate key
Fix: Check existing keys in bucket and update value if found

Mistake: Returning wrong value or error when key not found
Fix: Return undefined if bucket empty or key not found

Summary

Stores key-value pairs using a hash function to find buckets and handles collisions with chaining.

Use when you want fast average-time insert and lookup by key.

The key insight is turning keys into bucket indexes and handling collisions by storing multiple pairs in a bucket.

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