Why Hash Map Exists and What Problem It Solves in DSA Typescript - Performance Analysis

Time Complexity: Why Hash Map Exists and What Problem It Solves

O(n) for array search, O(1) average for hash map lookup

Understanding Time Complexity

We want to understand why hash maps are useful by looking at how fast they let us find things.

The question is: How does using a hash map change the time it takes to find or store data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple search in an array
function findValue(arr: number[], target: number): boolean {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return true;
    }
  }
  return false;
}

// Using a hash map for quick lookup
function findValueWithMap(map: Map, target: number): boolean {
  return map.has(target);
}
    

This code shows two ways to check if a value exists: searching an array and using a hash map.

Identify Repeating Operations

• Primary operation: Checking each item in the array one by one.
• How many times: Up to n times, where n is the number of items in the array.
• Hash map operation: Directly checking if the key exists without looping.
• How many times: Just once, no matter how big the map is.

How Execution Grows With Input

As the list gets bigger, searching each item takes longer, but hash map lookup stays fast.

Input Size (n)	Array Search Operations	Hash Map Lookup Operations
10	Up to 10 checks	1 check
100	Up to 100 checks	1 check
1000	Up to 1000 checks	1 check

Pattern observation: Array search grows linearly with input size, hash map lookup stays constant.

Final Time Complexity

Time Complexity: O(n) for array search, O(1) average for hash map lookup

This means searching an array takes longer as it grows, but hash maps let us find things quickly no matter the size.

Common Mistake

[X] Wrong: "Hash maps always find items instantly without any cost."

[OK] Correct: Hash maps usually find items quickly, but sometimes collisions happen, making lookup slower. Still, on average, they are much faster than searching arrays.

Interview Connect

Understanding why hash maps exist helps you explain how to choose the right tool for fast data lookup, a key skill in many coding problems.

Self-Check

"What if the array was sorted? How would the time complexity change if we used binary search instead of linear search?"

Practice

1. Why do we use a Hash Map instead of a simple list to store key-value pairs?

easy

A. Because it allows fast lookup of values by keys

B. Because it stores data in sorted order automatically

C. Because it uses less memory than a list

D. Because it can only store numbers

Solution

1. Step 1: Understand the problem with lists

   Lists require checking each item one by one to find a value by key, which is slow for large data.

2. Step 2: How hash maps solve this

   Hash maps use a special function to find the exact place of a key quickly, making lookup fast.

3. Final Answer:

   Because it allows fast lookup of values by keys -> Option A

4. Quick Check:

   Fast key lookup = Because it allows fast lookup of values by keys [OK]

Hint: Hash maps speed up key-based searches [OK]

Common Mistakes:

• Thinking hash maps sort data automatically
• Believing hash maps use less memory always
• Assuming hash maps only store numbers

2. Which of the following is the correct way to create a hash map (Map) in TypeScript?

easy

A. const map = new Map();

B. const map = Map();

C. const map = new map();

D. const map = new Map(); string, number;

Solution

1. Step 1: Recall TypeScript Map syntax

   In TypeScript, a Map is created using new Map<KeyType, ValueType>().

2. Step 2: Check each option

   const map = new Map(); uses correct syntax with new Map<string, number>(). Others have syntax errors or wrong casing.

3. Final Answer:

   const map = new Map<string, number>(); -> Option A

4. Quick Check:

   Correct Map creation syntax = const map = new Map<string, number>(); [OK]

Hint: Use 'new Map<KeyType, ValueType>()' to create hash maps [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using lowercase 'map' instead of 'Map'
• Incorrect generic syntax

3. What will be the output of the following TypeScript code?

const map = new Map();
map.set('apple', 5);
map.set('banana', 3);
map.set('apple', 10);
console.log(map.get('apple'));

medium

A. Error

B. 5

C. undefined

D. 10

Solution

1. Step 1: Understand map.set behavior

   When setting a key that already exists, the value is updated to the new one.

2. Step 2: Trace the code

   First 'apple' is set to 5, then updated to 10. So map.get('apple') returns 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Updated value for 'apple' = 10 [OK]

Hint: Last set value for a key overwrites previous [OK]

Common Mistakes:

• Assuming first value remains
• Thinking get returns undefined if key repeated
• Expecting error on duplicate keys

4. Identify the error in this TypeScript code that tries to use a hash map:

const map = new Map();
map['key'] = 'value';
console.log(map.get('key'));

medium

A. map.get() cannot be used to retrieve values

B. Map constructor requires key and value types

C. Using bracket notation to add key-value pairs does not work with Map

D. Map keys must be numbers only

Solution

1. Step 1: Understand how to add entries to Map

   Map entries must be added using map.set(key, value), not bracket notation.

2. Step 2: Analyze the code behavior

   Using map['key'] = 'value' adds a property to the object, not a Map entry, so map.get('key') returns undefined.

3. Final Answer:

   Using bracket notation to add key-value pairs does not work with Map -> Option C

4. Quick Check:

   Use map.set() to add entries [OK]

Hint: Use map.set() to add entries, not bracket notation [OK]

Common Mistakes:

• Adding entries with bracket notation
• Expecting map.get() to find bracket-added keys
• Thinking Map keys must be numbers

5. You want to count how many times each word appears in a list of words using a hash map in TypeScript. Which approach correctly solves this problem?

hard

A. Use a Set to store words and count size for each word

B. Use a Map, for each word check if it exists, then increment or set to 1

C. Use a Map with word as value and count as key

D. Use an array and push words, then count duplicates manually later

Solution

1. Step 1: Understand the counting problem

   We need to store each word as a key and count as a value, so Map<string, number> fits well.

2. Step 2: How to update counts

   For each word, check if it exists in the map; if yes, increment count, else set count to 1.

3. Step 3: Why other options fail

   Use an array and push words, then count duplicates manually later is inefficient and manual. Use a Map with word as value and count as key swaps key and value wrongly. Use a Set to store words and count size for each word's Set only stores unique words without counts.

4. Final Answer:

   Use a Map<string, number>, for each word check if it exists, then increment or set to 1 -> Option B

5. Quick Check:

   Counting words = Map with word keys and number counts [OK]

Hint: Map keys = words, values = counts; increment or set 1 [OK]

Common Mistakes:

• Using Set which can't count duplicates
• Swapping key and value types in Map
• Counting manually with arrays inefficiently