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

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

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

Understanding Time Complexity

We want to understand why hash maps are useful by looking at the time it takes to find data.

What problem does a hash map solve when searching or storing data?

Scenario Under Consideration

Analyze the time complexity of searching for a value in an array versus using a hash map.

// Searching in an array
function findInArray(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return true;
  }
  return false;
}

// Using a hash map
const map = new Map();
map.set('key', 'value');
const found = map.has('key');
    

The first function searches through each item one by one. The second uses a hash map to check quickly.

Identify Repeating Operations

Look at what repeats when searching for data.

• Primary operation: Looping through the array items one by one in findInArray.
• How many times: Up to n times, where n is the number of items.
• Hash map operation: Direct lookup using a hash function, no loop needed.

How Execution Grows With Input

As the list gets bigger, searching by checking each item takes longer.

Input Size (n)	Approx. Operations (Array Search)
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows directly with the number of items.

For hash maps, the lookup stays almost the same time regardless of size.

Final Time Complexity

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

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

Common Mistake

[X] Wrong: "Searching an array is always fast enough, so hash maps are not needed."

[OK] Correct: When the list is large, searching each item one by one becomes slow, making hash maps much faster for lookups.

Interview Connect

Understanding why hash maps exist shows you know how to choose the right tool for fast data access, a key skill in coding and problem solving.

Self-Check

"What if the array was sorted? How would the time complexity of searching change compared to using a hash map?"

Practice

1. Why do we use a hash map in programming?
hashMap = {}

easy

A. To store key-value pairs for fast data lookup

B. To store data in a sorted order automatically

C. To perform mathematical calculations faster

D. To create a list of items without duplicates

Solution

1. Step 1: Understand the purpose of a hash map

   A hash map stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike lists or arrays, hash maps provide faster lookup by key, not by position or order.

3. Final Answer:

   To store key-value pairs for fast data lookup -> Option A

4. Quick Check:

   Hash map = fast key-value lookup [OK]

Hint: Hash maps store data by keys for quick access [OK]

Common Mistakes:

• Thinking hash maps sort data automatically
• Confusing hash maps with arrays or lists
• Assuming hash maps are for math calculations

2. Which of the following is the correct way to create an empty hash map (object) in JavaScript?

easy

A. const map = []

B. const map = {}

C. const map = () => {}

D. const map = new Map[]

Solution

1. Step 1: Recall JavaScript syntax for objects

   In JavaScript, curly braces {} create an empty object, which can be used as a hash map.

2. Step 2: Check other options

   Square brackets [] create arrays, () => {} is a function, and new Map[] is invalid syntax.

3. Final Answer:

   const map = {} -> Option B

4. Quick Check:

   Empty object = {} [OK]

Hint: Use curly braces {} to create empty hash maps in JavaScript [OK]

Common Mistakes:

• Using [] which creates an array, not a hash map
• Trying to use function syntax for hash map
• Incorrect new Map[] syntax

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

const map = {};
map['apple'] = 5;
map['banana'] = 3;
console.log(map['apple']);

medium

A. 5

B. Error

C. 3

D. undefined

Solution

1. Step 1: Assign values to keys in the hash map

   The code sets map['apple'] = 5 and map['banana'] = 3, storing these key-value pairs.

2. Step 2: Access the value for key 'apple'

   console.log(map['apple']) prints the value 5 stored at key 'apple'.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   map['apple'] = 5, output = 5 [OK]

Hint: Access value by key to get stored number [OK]

Common Mistakes:

• Expecting output to be 'undefined' if key exists
• Confusing values of different keys
• Thinking it causes an error

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

const map = {};
map.apple = 10;
console.log(map['applee']);

medium

A. Syntax error in object creation

B. Using dot notation instead of brackets

C. Cannot assign values to an empty object

D. Accessing a key that does not exist

Solution

1. Step 1: Check key assignment

   map.apple = 10 correctly assigns value 10 to key 'apple'.

2. Step 2: Check key access

   console.log(map['applee']) tries to access key 'applee' which was never assigned, so it returns undefined.

3. Final Answer:

   Accessing a key that does not exist -> Option D

4. Quick Check:

   Wrong key access = undefined [OK]

Hint: Check spelling of keys when accessing hash map values [OK]

Common Mistakes:

• Thinking dot notation is wrong here
• Expecting error on accessing missing key
• Assuming empty object cannot store values

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

const words = ['cat', 'dog', 'cat', 'bird'];
const counts = {};
// Fill counts here
console.log(counts);

hard

A. for (const w of words) { counts[w] = 1; }

B. for (const w of words) { counts[w] = counts[w] + 1; }

C. for (const w of words) { counts[w] = (counts[w] || 0) + 1; }

D. for (const w of words) { counts[w] += 1; }

Solution

1. Step 1: Understand counting logic

   We need to add 1 to the count for each word. If the word is new, start from 0.

2. Step 2: Analyze each option

   for (const w of words) { counts[w] = 1; } sets count to 1 always, ignoring repeats. for (const w of words) { counts[w] = counts[w] + 1; } tries to add 1 but counts[w] is undefined initially causing NaN. for (const w of words) { counts[w] = (counts[w] || 0) + 1; } uses (counts[w] || 0) + 1 to handle undefined keys correctly. for (const w of words) { counts[w] += 1; } tries to add 1 without initialization, causing NaN.

3. Final Answer:

   for (const w of words) { counts[w] = (counts[w] || 0) + 1; } -> Option C

4. Quick Check:

   Initialize with 0 or use || 0 before adding [OK]

Hint: Use (counts[key] || 0) + 1 to count safely [OK]

Common Mistakes:

• Not initializing counts before adding
• Overwriting counts instead of incrementing
• Assuming counts[w] is always defined