HashMap Implementation from Scratch in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a HashMap?

A HashMap is a data structure that stores key-value pairs. It uses a hash function to convert keys into an index where the value is stored, allowing fast data retrieval.

beginner

Why do we use a hash function in a HashMap?

A hash function converts a key into an index number. This index tells where to store or find the value quickly in an array, making data access fast.

intermediate

What is a collision in a HashMap?

A collision happens when two different keys produce the same index from the hash function. We need special ways to handle collisions so data is not lost.

intermediate

Name one common method to handle collisions in a HashMap.

One common method is chaining, where each index holds a list of key-value pairs. If multiple keys map to the same index, they are stored in this list.

intermediate

What is the average time complexity for searching a value in a well-implemented HashMap?

The average time complexity is O(1), meaning it takes constant time to find a value using its key.

What does a hash function do in a HashMap?

A Sorts the keys alphabetically

B Converts a key into an index

C Deletes duplicate keys

D Stores values directly

A hash function converts a key into an index to store or find the value quickly.

What is a collision in a HashMap?

A When two keys have the same value

B When a key is missing

C When two keys produce the same index

D When the HashMap is empty

A collision happens when two different keys produce the same index from the hash function.

Which method stores multiple key-value pairs at the same index to handle collisions?

A Sorting

B Linear probing

C Rehashing

D Chaining

Chaining stores multiple key-value pairs in a list at the same index to handle collisions.

What is the average time complexity to find a value in a HashMap?

A O(1)

B O(log n)

C O(n)

D O(n log n)

In a well-implemented HashMap, searching takes constant time O(1) on average.

Which of these is NOT a typical operation of a HashMap?

A Sort all keys

B Delete key-value pair

C Find value by key

D Insert key-value pair

HashMaps do not sort keys; they store and retrieve key-value pairs efficiently.

Explain how a HashMap stores and retrieves data using a hash function and how collisions are handled.

Think about how you find a book in a library using a code and what happens if two books have the same code.

Describe the average time complexity of searching in a HashMap and why it is efficient.

Imagine looking up a phone number by name in a well-organized phone book.

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