HashMap Implementation from Scratch in DSA Typescript

Mental Model

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

Analogy: Imagine a big set of mailboxes where each mailbox number is found by turning a person's name into a number, so you can quickly find their letters without searching all mailboxes.

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

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 and insert (cat -> 5) there

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

Why: We convert 'cat' to a number and use modulo 5 to find bucket 2 to store its value

Step 2: Hash 'dog' to index 4 and insert (dog -> 7) there

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

Why: We convert 'dog' to a number and use modulo 5 to find bucket 4 to store its value

Step 3: Hash 'bird' to index 2, find 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' map to bucket 2, so we chain entries to handle collision

Result:

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

Annotated Code

DSA Typescript

class HashNode {
  key: string;
  value: number;
  next: HashNode | null;

  constructor(key: string, value: number) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

class HashMap {
  private buckets: Array<HashNode | null>;
  private size: number;

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

  private hash(key: string): number {
    let hashValue = 0;
    for (const char of key) {
      hashValue += char.charCodeAt(0);
    }
    return hashValue % this.size;
  }

  set(key: string, value: number): void {
    const index = this.hash(key); // get bucket index
    if (this.buckets[index] === null) {
      this.buckets[index] = new HashNode(key, value); // insert if empty
      return;
    }

    let current = this.buckets[index];
    while (current) {
      if (current.key === key) {
        current.value = value; // update existing key
        return;
      }
      if (current.next === null) break;
      current = current.next; // move to next node
    }

    current.next = new HashNode(key, value); // add new node at end
  }

  get(key: string): number | null {
    const index = this.hash(key); // find bucket
    let current = this.buckets[index];
    while (current) {
      if (current.key === key) return current.value; // found key
      current = current.next; // check next node
    }
    return null; // not found
  }

  print(): void {
    for (let i = 0; i < this.size; i++) {
      let current = this.buckets[i];
      let bucketStr = `[${i}] -> `;
      while (current) {
        bucketStr += `(${current.key} -> ${current.value}) -> `;
        current = current.next;
      }
      bucketStr += '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();

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

compute bucket index by hashing key

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

insert new node if bucket empty

while (current) { if (current.key === key) { current.value = value; return; } if (current.next === null) break; current = current.next; }

traverse linked list to update existing key or find end

current.next = new HashNode(key, value);

append new node at end to handle collision

const index = this.hash(key); let current = this.buckets[index]; while (current) { if (current.key === key) return current.value; current = current.next; } return null;

search linked list in bucket for key and return value or null

Output

[0] -> null

[1] -> null

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

[3] -> null

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

Complexity Analysis

Time: O(n/k) on average, where n is number of keys and k is bucket count, because each bucket holds a short linked list; worst case O(n) if all keys collide

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

vs Alternative: Compared to a simple array search O(n), hashing reduces average search and insert to near O(1) by direct indexing

Edge Cases

Inserting a key that already exists

The value for that key is updated instead of adding a duplicate

DSA Typescript

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

Getting a key that does not exist

Returns null indicating key not found

DSA Typescript

return null;

Handling collisions when multiple keys hash to same bucket

Keys are stored in a linked list at that bucket

DSA Typescript

current.next = new HashNode(key, value);

When to Use This Pattern

When you need fast key-value storage and retrieval with average constant time, and must handle collisions, reach for the HashMap pattern using hashing and chaining.

Common Mistakes

Mistake: Not handling collisions, causing overwriting or lost data
Fix: Use a linked list or another structure at each bucket to store multiple entries

Mistake: Not updating existing keys and instead adding duplicates
Fix: Check for existing key in bucket and update its value before adding new node

Mistake: Using a poor hash function causing many collisions
Fix: Use a simple but effective hash function like summing char codes modulo bucket size

Summary

Stores key-value pairs using a hash function to find buckets and linked lists to handle collisions.

Use when you want fast insert and lookup by key without scanning all data.

The key insight is turning keys into bucket indexes and chaining entries to handle collisions 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 key-value pairs for fast data retrieval

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand HashMap functionality

   A HashMap stores data as key-value pairs, allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

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

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Thinking HashMap stores data in order
• Confusing HashMap with arrays
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap class property in TypeScript?

easy

A. private map: {[key: string]: any} = {};

B. map = new Map();

C. let map = [];

D. const map: Map = {};

Solution

1. Step 1: Identify TypeScript syntax for object property

   Declaring a private property with type {[key: string]: any} initializes an object for key-value storage.

2. Step 2: Check other options for correctness

   map = new Map(); uses built-in Map, not a plain object; C is an array; D has wrong Map type usage.

3. Final Answer:

   private map: {[key: string]: any} = {}; -> Option A

4. Quick Check:

   TypeScript object property syntax = private map: {[key: string]: any} = {}; [OK]

Hint: Use object type {[key: string]: any} for HashMap storage [OK]

Common Mistakes:

• Using array instead of object for map
• Incorrect Map type declaration
• Confusing built-in Map with plain object

3. What will be the output of this TypeScript code snippet implementing a simple HashMap?

class SimpleHashMap {
  private map: {[key: string]: string} = {};
  set(key: string, value: string) {
    this.map[key] = value;
  }
  get(key: string) {
    return this.map[key] || null;
  }
}
const h = new SimpleHashMap();
h.set('a', 'apple');
h.set('b', 'banana');
console.log(h.get('a'));
console.log(h.get('c'));

medium

A. "apple" followed by null

B. "apple" followed by undefined

C. undefined followed by null

D. Error at runtime

Solution

1. Step 1: Trace set method calls

   Keys 'a' and 'b' are set with values 'apple' and 'banana' respectively in the map object.

2. Step 2: Trace get method calls

   Getting 'a' returns 'apple'; getting 'c' returns undefined, so || null returns null.

3. Final Answer:

   "apple" followed by null -> Option A

4. Quick Check:

   Existing key returns value, missing key returns null [OK]

Hint: Missing keys return null due to || null fallback [OK]

Common Mistakes:

• Expecting undefined instead of null for missing keys
• Confusing set and get method effects
• Assuming runtime error on missing key

4. Identify the bug in this simple HashMap implementation and choose the correct fix:

class BuggyHashMap {
  private map: {[key: string]: number} = {};
  set(key: string, value: number) {
    this.map[key] = value;
  }
  get(key: string): number {
    return this.map[key];
  }
}
const h = new BuggyHashMap();
h.set('x', 10);
console.log(h.get('y'));

medium

A. map should be an array instead of object

B. set method should check if key exists before setting

C. get should return number | null and handle missing keys

D. No bug, code works fine

Solution

1. Step 1: Analyze get method return type

   get returns number but missing keys return undefined, causing type mismatch.

2. Step 2: Fix get method to handle missing keys

   Change return type to number | null and return null if key missing to avoid undefined.

3. Final Answer:

   get should return number | null and handle missing keys -> Option C

4. Quick Check:

   Handle missing keys in get method [OK]

Hint: Always handle missing keys in get method return type [OK]

Common Mistakes:

• Ignoring undefined return for missing keys
• Changing map to array incorrectly
• Thinking set method needs key existence check

5. You want to implement a HashMap from scratch in TypeScript that handles collisions using chaining (array of entries). Which approach correctly adds a new key-value pair to the map?

hard

A. Store keys in an array and values in a separate array without hashing

B. Compute hash, overwrite bucket with new entry ignoring existing keys

C. Use a single array for all entries without hashing

D. Compute hash, check bucket array; if key exists update value, else push new entry

Solution

1. Step 1: Understand collision handling by chaining

   Chaining stores multiple entries in a bucket array; new entries are added or updated if key exists.

2. Step 2: Analyze options for correct collision handling

   Compute hash, check bucket array; if key exists update value, else push new entry correctly checks bucket, updates existing key or adds new entry; others ignore collisions or do not hash.

3. Final Answer:

   Compute hash, check bucket array; if key exists update value, else push new entry -> Option D

4. Quick Check:

   Chaining = bucket array with update or add [OK]

Hint: Check bucket for key, update or add entry to handle collisions [OK]

Common Mistakes:

• Overwriting bucket ignoring existing keys
• Not using hashing for bucket selection
• Storing keys and values separately without hashing