Why Hash Map Exists and What Problem It Solves in DSA C - See It Work

Why Hash Map Exists and What Problem It Solves

📖 Scenario: Imagine you have a big box of keys and you want to find the right key quickly to open a door. Searching one by one takes too long. A hash map is like a magic box that helps you find the right key fast.

🎯 Goal: You will create a simple program that stores and finds phone numbers by names using a hash map concept. This will show why hash maps exist and how they solve the problem of slow searching.

📋 What You'll Learn

Create an array of strings called names with these exact entries: "Alice", "Bob", "Charlie"

Create an array of integers called phone_numbers with these exact entries: 12345, 67890, 54321

Create an integer variable called size and set it to 3

Write a function called find_phone_number that takes char* name, char* names[], int phone_numbers[], and int size and returns the phone number for the given name or -1 if not found

Use a for loop with variable i to search through names inside find_phone_number

Print the phone number for "Bob" using find_phone_number

💡 Why This Matters

🌍 Real World

Hash maps help apps like phonebooks, contact lists, and databases find information fast without checking every item.

💼 Career

Understanding hash maps is key for software developers to write efficient code for searching and storing data.

1

Create the Data Setup

Create an array of strings called names with these exact entries: "Alice", "Bob", "Charlie". Also create an array of integers called phone_numbers with these exact entries: 12345, 67890, 54321.

DSA C

# Create arrays names and phone_numbers with given values
# Your code here

Hint

Use arrays to store the names and phone numbers exactly as shown.

2

Add Size Variable

Create an integer variable called size and set it to 3 to represent the number of entries.

DSA C

#include 

char* names[] = {"Alice", "Bob", "Charlie"};
int phone_numbers[] = {12345, 67890, 54321};

// Create size variable
# Your code here

Hint

Use an integer variable named size and assign it the value 3.

3

Write the Search Function

Write a function called find_phone_number that takes char* name, char* names[], int phone_numbers[], and int size. Use a for loop with variable i to search through names. If name matches names[i], return phone_numbers[i]. If not found, return -1.

DSA C

#include 
#include 

char* names[] = {"Alice", "Bob", "Charlie"};
int phone_numbers[] = {12345, 67890, 54321};

int size = 3;

// Write find_phone_number function
# Your code here

Hint

Use strcmp to compare strings inside the loop.

4

Print the Phone Number for Bob

Use printf to print the phone number for "Bob" by calling find_phone_number("Bob", names, phone_numbers, size).

DSA C

#include 
#include 

char* names[] = {"Alice", "Bob", "Charlie"};
int phone_numbers[] = {12345, 67890, 54321};

int size = 3;

int find_phone_number(char* name, char* names[], int phone_numbers[], int size) {
    for (int i = 0; i < size; i++) {
        if (strcmp(name, names[i]) == 0) {
            return phone_numbers[i];
        }
    }
    return -1;
}

int main() {
    // Print phone number for Bob
# Your code here
    return 0;
}

Hint

Use printf("%d\n", ...) to print the phone number.

Practice

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

easy

A. To quickly find values using keys without searching the entire list

B. To store values in sorted order automatically

C. To save memory by compressing data

D. To allow duplicate keys with different values

Solution

1. Step 1: Understand list search time

   In a simple list, finding a value by key requires checking each item one by one, which takes longer as the list grows.

2. Step 2: Understand hash map lookup

   A hash map uses a special function to jump directly to the value's location, making search very fast regardless of size.

3. Final Answer:

   To quickly find values using keys without searching the entire list -> Option A

4. Quick Check:

   Hash map = fast key lookup [OK]

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

Common Mistakes:

• Thinking hash maps store data sorted automatically
• Believing hash maps compress data to save memory
• Assuming hash maps allow duplicate keys

2. Which of the following is the correct syntax to declare a hash map in C using a struct and array?

easy

A. struct HashMap { int key; int value; } map[100];

B. HashMap map = new HashMap();

C. hash_map map;

D. map = {};

Solution

1. Step 1: Recognize C syntax for struct arrays

   In C, a hash map can be represented as an array of structs with key and value fields.

2. Step 2: Check options for valid C declaration

   struct HashMap { int key; int value; } map[100]; correctly declares a struct and an array of 100 elements. Other options use syntax from other languages or invalid C syntax.

3. Final Answer:

   struct HashMap { int key; int value; } map[100]; -> Option A

4. Quick Check:

   C struct array = struct HashMap { int key; int value; } map[100]; [OK]

Hint: C uses structs and arrays for hash maps [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Trying to declare hash maps without structs
• Using empty braces {} for initialization

3. Consider this simplified hash map code in C that stores keys and values:

struct Entry { int key; int value; };
struct Entry map[5] = {{1, 10}, {2, 20}, {3, 30}, {4, 40}, {5, 50}};

int findValue(int key) {
  for (int i = 0; i < 5; i++) {
    if (map[i].key == key) return map[i].value;
  }
  return -1;
}

int main() {
  printf("%d", findValue(3));
  return 0;
}

What is the output when this program runs?

medium

A. 3

B. -1

C. 30

D. Compilation error

Solution

1. Step 1: Understand the findValue function

   The function loops through the map array and returns the value where the key matches the input.

2. Step 2: Trace the call findValue(3)

   It finds key 3 at index 2 with value 30 and returns it. So printf prints 30.

3. Final Answer:

   30 -> Option C

4. Quick Check:

   Key 3 value = 30 [OK]

Hint: Loop finds key, returns matching value [OK]

Common Mistakes:

• Confusing key with value in output
• Assuming function returns key instead of value
• Expecting compilation error due to struct

4. This code tries to find a value by key in a hash map but has a bug:

struct Entry { int key; int value; };
struct Entry map[3] = {{1, 100}, {2, 200}, {3, 300}};

int findValue(int key) {
  for (int i = 0; i <= 3; i++) {
    if (map[i].key == key) return map[i].value;
  }
  return -1;
}

What is the bug and how to fix it?

medium

A. The key comparison uses '==' instead of '='; replace '==' with '='

B. The struct is missing a constructor; add one to fix it

C. The return type should be void; change int to void

D. The loop goes out of bounds; change 'i <= 3' to 'i < 3' to fix it

Solution

1. Step 1: Check loop bounds

   The array has 3 elements indexed 0,1,2. Loop with 'i <= 3' accesses map[3], which is out of bounds.

2. Step 2: Fix loop condition

   Change loop to 'i < 3' to stay within valid indices and avoid runtime errors.

3. Final Answer:

   The loop goes out of bounds; change 'i <= 3' to 'i < 3' to fix it -> Option D

4. Quick Check:

   Loop bounds must match array size [OK]

Hint: Array index must be less than size, not less or equal [OK]

Common Mistakes:

• Ignoring array bounds causing crashes
• Confusing assignment '=' with comparison '=='
• Changing return type unnecessarily

5. You want to store student IDs and their grades using a hash map in C. Which problem does using a hash map solve best compared to an array or list? A student ID is a large number and not continuous. Options: A) Allow multiple students to share the same ID B) Automatically sort students by their grades C) Save memory by storing only unique grades D) Quickly find a student's grade by their ID without searching all entries

hard

A. Allow multiple students to share the same ID

B. Quickly find a student's grade by their ID without searching all entries

C. Save memory by storing only unique grades

D. Automatically sort students by their grades

Solution

1. Step 1: Understand the problem with large, non-continuous keys

   Arrays or lists require searching or large memory if keys are large and sparse.

2. Step 2: How hash maps help

   Hash maps use a function to map large keys to storage locations, enabling fast lookup without scanning all data.

3. Final Answer:

   Quickly find a student's grade by their ID without searching all entries -> Option B

4. Quick Check:

   Hash map = fast lookup for large keys [OK]

Hint: Hash maps handle large keys efficiently [OK]

Common Mistakes:

• Thinking hash maps sort data automatically
• Believing hash maps compress data to save memory
• Assuming duplicate keys are allowed