HashMap Implementation from Scratch in DSA Typescript - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Initialize buckets array

↓

Hash key to index

↓

Check bucket at index

↓

Traverse bucket linked list

↓

Key found?

↓

Update value

Shows how a key is hashed to an index, bucket checked, and either updated or inserted.

Execution Sample

DSA Typescript

interface Node {
  key: string;
  value: any;
  next: Node | null;
}

class HashMap {
  private buckets: Array<Node | null>;
  constructor(size: number = 3) {
    this.buckets = new Array(size).fill(null);
  }
  private hash(key: string): number {
    let hash = 0;
    for (const char of key) hash += char.charCodeAt(0);
    return hash % this.buckets.length;
  }
  set(key: string, value: any): void {
    const index = this.hash(key);
    let node = this.buckets[index];
    while (node) {
      if (node.key === key) {
        node.value = value;
        return;
      }
      node = node.next;
    }
    const newNode: Node = { key, value, next: this.buckets[index] };
    this.buckets[index] = newNode;
  }
}

This code creates a simple HashMap with set method that inserts or updates key-value pairs. Node interface added for completeness.

Execution Table

Step	Operation	Bucket Index	Nodes in Bucket	Pointer Changes	Visual State
1	Initialize buckets array	-	[]	buckets = [null, null, null]	[null, null, null]
2	Set key='cat', value=5	0	[]	Insert new node at buckets[0]	[{cat:5}->null, null, null]
3	Set key='dog', value=7	1	[]	Insert new node at buckets[1]	[{cat:5}->null, {dog:7}->null, null]
4	Set key='cat', value=10	0	[{cat:5}->null]	Update node value at buckets[0]	[{cat:10}->null, {dog:7}->null, null]
5	Set key='tac', value=3	0	[{cat:10}->null]	Insert new node at buckets[0] head	[{tac:3}->{cat:10}->null, {dog:7}->null, null]
6	Set key='god', value=8	1	[{dog:7}->null]	Insert new node at buckets[1] head	[{tac:3}->{cat:10}->null, {god:8}->{dog:7}->null, null]
7	Set key='bird', value=4	2	[]	Insert new node at buckets[2]	[{tac:3}->{cat:10}->null, {god:8}->{dog:7}->null, {bird:4}->null]
8	End of operations	-	-	-	Final buckets state as above

💡 All keys inserted or updated; no more operations.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
buckets	[null, null, null]	[{cat:5}->null, null, null]	[{cat:5}->null, {dog:7}->null, null]	[{cat:10}->null, {dog:7}->null, null]	[{tac:3}->{cat:10}->null, {dog:7}->null, null]	[{tac:3}->{cat:10}->null, {god:8}->{dog:7}->null, null]	[{tac:3}->{cat:10}->null, {god:8}->{dog:7}->null, {bird:4}->null]	[{tac:3}->{cat:10}->null, {god:8}->{dog:7}->null, {bird:4}->null]	[{tac:3}->{cat:10}->null, {god:8}->{dog:7}->null, {bird:4}->null]
index	-	0	1	0	0	1	2	-	-
node	-	null	null	{cat:5}	null	{dog:7}	null	-	-

Key Moments - 3 Insights

Why do we insert new nodes at the head of the bucket linked list instead of the tail?

Inserting at the head is O(1) time, no traversal needed. See steps 5 and 6 in execution_table.

How does the hash function decide the bucket index?

Sums char codes of key, modulo bucket length. E.g., 'cat' -> 0, 'dog'->1. See 'Bucket Index' column.

What happens when inserting a duplicate key?

Traverses list, updates value if found. See step 4: 'cat' from 5 to 10.

Visual Quiz - 3 Questions

Look at execution_table step 5, what is the visual state of buckets?

A [{cat:10}->null, {dog:7}->null, null]

B [{tac:3}->{cat:10}->null, {dog:7}->null, null]

C [{tac:3}->null, {dog:7}->null, null]

D [null, null, null]

💡 Hint

Check 'Visual State' at step 5.

Which step inserts new node for 'god' at head of bucket 1?

A Step 6

B Step 3

C Step 4

D Step 7

💡 Hint

Look for 'god' in 'Operation', bucket 1.

If bucket size increased to 5, how would indices change?

A Stay the same

B All zero

C Recalculated: hash % 5

D Negative

💡 Hint

Hash uses modulo buckets.length.

Concept Snapshot

HashMap: key-value in buckets array. Hash(key) % size -> index. Bucket: linked list for collisions. set(): traverse/update or prepend new node. O(1) avg insert/lookup.

Full Transcript

Visual trace of HashMap set operations. Buckets init empty. Hash key to index. Empty bucket? New node. Occupied? Traverse for key: update value or prepend new. Head insert: fast O(1). Tables track changes step-by-step. Moments explain choices. Quiz verifies states, hashing.

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