Hash Map vs Array vs Linked List for Lookup in DSA C++ - Trade-offs & Analysis

Mental Model

Lookup means finding if a value or key exists quickly. Arrays check one by one, linked lists do the same but slower, hash maps jump directly to the spot.

Analogy: Imagine looking for a book in a shelf: array is like checking each book in order, linked list is like a chain of books you follow one by one, hash map is like having a map that tells you exactly where the book is.

Array: [1] -> [2] -> [3] -> [4] -> null
Linked List: 1 -> 2 -> 3 -> 4 -> null
Hash Map: buckets -> [key:value] -> ... (direct access)

Dry Run Walkthrough

Input: Lookup value 3 in array [1, 2, 3, 4], linked list 1->2->3->4, and hash map {1:val, 2:val, 3:val, 4:val}

Goal: Show how each structure finds the value 3 and compare steps

Step 1: Check first element in array

[1] -> [2] -> [3] -> [4]

Why: Start from beginning to find value 3

Step 2: Check second element in array

[1] -> [2] -> [3] -> [4]

Why: Value not found yet, move to next

Step 3: Check third element in array, found 3

[1] -> [2] -> [3] -> [4]

Why: Found the value at index 2

Step 4: Start at head of linked list

1 -> 2 -> 3 -> 4 -> null ↑

Why: Begin traversal to find value 3

Step 5: Move to next node with value 2

1 -> 2 -> 3 -> 4 -> null ↑

Why: Value not found, move forward

Step 6: Move to next node with value 3, found it

1 -> 2 -> 3 -> 4 -> null ↑

Why: Found the value in linked list

Step 7: Use hash function to find bucket for key 3

buckets -> [3:val]

Why: Hash map jumps directly to bucket

Step 8: Check bucket and find value 3 immediately

buckets -> [3:val]

Why: Direct access avoids traversal

Result:

Array: found 3 after checking 3 elements
Linked List: found 3 after traversing 3 nodes
Hash Map: found 3 immediately via hash

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <vector>

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

bool lookupArray(const std::vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target) return true; // check each element
    }
    return false;
}

bool lookupLinkedList(Node* head, int target) {
    Node* curr = head;
    while (curr != nullptr) {
        if (curr->val == target) return true; // check current node
        curr = curr->next; // move to next node
    }
    return false;
}

bool lookupHashMap(const std::unordered_map<int, int>& map, int target) {
    return map.find(target) != map.end(); // direct lookup
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4};
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);

    std::unordered_map<int, int> map = {{1, 10}, {2, 20}, {3, 30}, {4, 40}};

    int target = 3;

    std::cout << "Array lookup: " << (lookupArray(arr, target) ? "Found" : "Not Found") << "\n";
    std::cout << "Linked List lookup: " << (lookupLinkedList(head, target) ? "Found" : "Not Found") << "\n";
    std::cout << "Hash Map lookup: " << (lookupHashMap(map, target) ? "Found" : "Not Found") << "\n";

    // Clean up linked list
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

if (arr[i] == target) return true; // check each element

check each array element until target found

if (curr->val == target) return true; // check current node

check current linked list node for target

curr = curr->next; // move to next node

advance to next node in linked list

return map.find(target) != map.end(); // direct lookup

directly check if target key exists in hash map

Output

Array lookup: Found

Linked List lookup: Found

Hash Map lookup: Found

Complexity Analysis

Time: Array and Linked List: O(n) because they check elements one by one; Hash Map: O(1) average because it jumps directly to the key's bucket

Space: Array and Linked List: O(n) to store elements; Hash Map: O(n) plus extra space for buckets and hashing overhead

vs Alternative: Hash Map is faster for lookup than array or linked list but uses more memory and has overhead for hashing

Edge Cases

Empty array, linked list, and hash map

Lookup returns false immediately as no elements exist

DSA C++

if (arr[i] == target) return true;

Target not present in any structure

Lookup returns false after full traversal or hash check

DSA C++

return false;

Single element structures with target present

Lookup returns true immediately on first check

DSA C++

if (curr->val == target) return true;

When to Use This Pattern

When a problem asks for fast lookup by key or value, consider hash maps for O(1) average time; arrays or linked lists are simpler but slower for large data.

Common Mistakes

Mistake: Assuming linked list lookup is as fast as hash map
Fix: Remember linked list lookup is O(n), hash map is O(1) average

Mistake: Using array lookup without considering size and performance
Fix: Use hash map if frequent lookups on large data are needed

Summary

Compares lookup speed in hash map, array, and linked list.

Use hash map for fast key-based lookup; arrays or linked lists for simple or small data.

Hash maps jump directly to data, arrays and linked lists check one by one.

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