Hash Map vs Array vs Linked List for Lookup in DSA C++ - Visual Comparison

Concept Flow - Hash Map vs Array vs Linked List for Lookup

Start Lookup

↓

Choose Data Structure

↓

Array

↓

Index Access

↓

Compare Value

↓

Found?

↓

Return Not Found

Lookup starts by choosing the data structure, then performs the specific search method: direct index for array, node traversal for linked list, or hash computation and bucket access for hash map.

Execution Sample

DSA C++

int lookupArray(int arr[], int size, int key) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == key) return i;
  }
  return -1;
}

This code searches for a key in an array by checking each element one by one.

Execution Table

Step	Operation	Data Structure	Pointer/Index	Action	Visual State
1	Start lookup for key=3	Array	i=0	Compare arr[0]=5 with 3	[5, 3, 7, 1, 9]
2	Compare next element	Array	i=1	Compare arr[1]=3 with 3	[5, 3, 7, 1, 9]
3	Key found	Array	i=1	Return index 1	[5, 3, 7, 1, 9]
4	Start lookup for key=3	Linked List	head	Compare node(5) with 3	5 -> 3 -> 7 -> 1 -> 9 -> null
5	Move to next node	Linked List	node(3)	Compare node(3) with 3	5 -> 3 -> 7 -> 1 -> 9 -> null
6	Key found	Linked List	node(3)	Return node with value 3	5 -> 3 -> 7 -> 1 -> 9 -> null
7	Start lookup for key=3	Hash Map	hash=3 % 5=3	Access bucket 3	[Bucket0:5] [Bucket1:3] [Bucket2:7] [Bucket3:1,9] [Bucket4:]
8	Traverse bucket 3	Hash Map	node(1)	Compare 1 with 3	[Bucket0:5] [Bucket1:3] [Bucket2:7] [Bucket3:1,9] [Bucket4:]
9	Traverse bucket 3	Hash Map	node(9)	Compare 9 with 3	[Bucket0:5] [Bucket1:3] [Bucket2:7] [Bucket3:1,9] [Bucket4:]
10	Key not found in bucket	Hash Map	bucket 3 end	Return not found	[Bucket0:5] [Bucket1:3] [Bucket2:7] [Bucket3:1,9] [Bucket4:]
11	Start lookup for key=3	Hash Map	hash=3 % 5=1	Access bucket 1	[Bucket0:5] [Bucket1:3] [Bucket2:7] [Bucket3:1,9] [Bucket4:]
12	Traverse bucket 1	Hash Map	node(3)	Compare 3 with 3	[Bucket0:5] [Bucket1:3] [Bucket2:7] [Bucket3:1,9] [Bucket4:]
13	Key found in bucket	Hash Map	node(3)	Return node with value 3	[Bucket0:5] [Bucket1:3] [Bucket2:7] [Bucket3:1,9] [Bucket4:]
14	End lookup	-	-	-	-

💡 Lookup ends when key is found or all elements checked without success.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	Final
i (Array index)	undefined	0	1	1	undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	1
currentNode (Linked List)	head (5)	5	3	3	undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	3
hash (Hash Map)	undefined	undefined	undefined	undefined	3	3	3	3	3	3	3	1	1	1	1
bucketNode (Hash Map bucket traversal)	undefined	undefined	undefined	undefined	node(1)	node(1)	node(9)	node(9)	end	end	node(3)	node(3)	node(3)	node(3)	node(3)

Key Moments - 3 Insights

Why does array lookup stop immediately when the key is found?

Because the array lookup uses direct index access and linear search; once the key matches at index i (see Step 3 in execution_table), it returns immediately without checking further.

Why does linked list lookup require traversal through nodes?

Linked list nodes are connected one after another without direct index access, so each node must be checked in order (see Steps 4-6) until the key is found or list ends.

Why might hash map lookup check multiple nodes in a bucket?

Because multiple keys can hash to the same bucket (collision), so the lookup traverses the bucket's linked nodes (see Steps 7-13) to find the key or conclude it's not present.

Visual Quiz - 3 Questions

Look at the execution_table, at which step does the array lookup find the key 3?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check the 'Operation' and 'Action' columns for array lookup steps in execution_table.

In the variable_tracker, what is the value of 'currentNode' after Step 5 during linked list lookup?

A 7

B 5

C 3

D null

💡 Hint

Look at the 'currentNode (Linked List)' row and the column 'After Step 5' in variable_tracker.

If the hash function changed to 'key % 4' instead of 'key % 5', how would the hash value for key=3 change in the hash map lookup?

A It would be 3

B It would be 0

C It would be 1

D It would be 2

💡 Hint

Calculate 3 % 4 and compare with the hash values in execution_table steps 7 and 11.

Concept Snapshot

Hash Map vs Array vs Linked List Lookup:
- Array: direct index access, linear search O(n)
- Linked List: node-by-node traversal O(n)
- Hash Map: compute hash, access bucket, traverse bucket O(1) average
- Hash collisions cause bucket traversal
- Lookup stops when key found or all checked

Full Transcript

This visual execution compares lookup in three data structures: array, linked list, and hash map. Lookup starts by choosing the data structure. For array, it checks each element by index until the key is found or array ends. For linked list, it traverses nodes one by one comparing values. For hash map, it computes a hash to find the bucket, then traverses nodes in that bucket to find the key. The execution table shows each step, operation, pointer or index used, and the visual state of the data structure. Variable tracker shows how indexes and pointers change over time. Key moments clarify why array lookup stops immediately on match, why linked list requires traversal, and why hash map may check multiple nodes due to collisions. The quiz tests understanding of lookup steps and hash function behavior. The snapshot summarizes lookup time and method differences for quick reference.

Practice

1. Which data structure provides the fastest average lookup time for finding an element by key?

easy

A. Array

B. Stack

C. Linked List

D. Hash Map

Solution

1. Step 1: Understand lookup times for each data structure

   Hash Map uses hashing to find keys quickly, usually in constant time O(1). Arrays require searching elements, which is O(n) unless index is known. Linked Lists require traversal, also O(n).

2. Step 2: Compare average lookup times

   Hash Map average lookup is O(1), Array and Linked List average lookup is O(n). So Hash Map is fastest for key-based lookup.

3. Final Answer:

   Hash Map -> Option D

4. Quick Check:

   Fastest lookup = Hash Map [OK]

Hint: Hash Map lookup is usually O(1), faster than arrays or lists [OK]

Common Mistakes:

• Confusing array index access with key lookup
• Thinking linked list lookup is faster than array
• Assuming stack is good for key lookup

2. Which of the following is the correct way to declare a hash map in C++ using STL for integer keys and string values?

easy

A. std::unordered_map map;

B. std::map map;

C. std::hash_map map;

D. std::unordered_map map;

Solution

1. Step 1: Identify correct STL container for hash map

   In modern C++, std::unordered_map is the standard hash map container. std::hash_map is deprecated or non-standard.

2. Step 2: Check key and value types

   We want integer keys and string values, so std::unordered_map is correct. std::map map; uses std::map which is a balanced tree, not hash map. std::unordered_map map; swaps key and value types.

3. Final Answer:

   std::unordered_map map; -> Option A

4. Quick Check:

   Correct hash map syntax = std::unordered_map map; [OK]

Hint: Use std::unordered_map for hash maps in C++ [OK]

Common Mistakes:

• Using std::map instead of unordered_map for hash map
• Swapping key and value types
• Using deprecated std::hash_map

3. What will be the output of the following C++ code snippet?

#include <iostream>
#include <unordered_map>
int main() {
    std::unordered_map map = {{1, "one"}, {2, "two"}, {3, "three"}};
    if (map.find(2) != map.end()) {
        std::cout << map[2];
    } else {
        std::cout << "Not found";
    }
    return 0;
}

medium

A. three

B. Not found

C. two

D. Compilation error

Solution

1. Step 1: Understand the map initialization and lookup

   The unordered_map is initialized with keys 1, 2, 3 and their string values. The code checks if key 2 exists using find.

2. Step 2: Check the condition and output

   Since key 2 exists, map[2] returns "two" which is printed.

3. Final Answer:

   two -> Option C

4. Quick Check:

   Key 2 found, output = two [OK]

Hint: Check if key exists before accessing map to avoid errors [OK]

Common Mistakes:

• Assuming map[2] returns "Not found" if key missing
• Confusing find() return value
• Thinking unordered_map is ordered

4. The following code tries to find an element in a linked list but causes a runtime error. What is the main issue?

#include <iostream>
struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = nullptr;
    // No nodes added
    Node* current = head;
    while (current->data != 5) {
        current = current->next;
    }
    std::cout << "Found 5";
    return 0;
}

medium

A. Infinite loop because next is never updated

B. Dereferencing null pointer when list is empty

C. Missing return statement in main

D. Incorrect struct definition

Solution

1. Step 1: Analyze linked list initialization

   The list is empty (head is nullptr). The pointer current is set to nullptr.

2. Step 2: Identify cause of runtime error

   The code tries to access current->data without checking if current is nullptr, causing a null pointer dereference and runtime crash.

3. Final Answer:

   Dereferencing null pointer when list is empty -> Option B

4. Quick Check:

   Null pointer access causes runtime error [OK]

Hint: Always check pointer is not null before dereferencing [OK]

Common Mistakes:

• Ignoring null pointer checks
• Assuming list has elements without adding
• Confusing infinite loop with crash

5. You need to store a large dataset of user IDs (integers) and their names (strings) for fast lookup by ID. Which data structure is best and why? Choose the best option considering lookup speed, memory, and insertion time.

hard

A. Hash Map, because it offers average O(1) lookup and efficient insertion

B. Linked List, because it uses less memory and is easy to insert

C. Array, because it provides O(1) lookup by index

D. Binary Search Tree, because it keeps data sorted for fast lookup

Solution

1. Step 1: Evaluate array suitability

   Array lookup by index is O(1), but user IDs are keys, not indices, so array lookup is O(n) unless IDs are continuous and small, which is unlikely.

2. Step 2: Compare linked list and binary search tree

   Linked list lookup is O(n), slow for large data. Binary search tree lookup is O(log n), better but slower than hash map average O(1).

3. Step 3: Assess hash map advantages

   Hash map provides average O(1) lookup and insertion, ideal for large datasets with arbitrary keys like user IDs.

4. Final Answer:

   Hash Map, because it offers average O(1) lookup and efficient insertion -> Option A

5. Quick Check:

   Best for fast key lookup = Hash Map [OK]

Hint: Use hash map for fast key-based lookup and insertion [OK]

Common Mistakes:

• Assuming array is always fastest for lookup
• Ignoring hash map memory overhead
• Choosing linked list for fast lookup