Hash Map vs Array vs Linked List for Lookup in DSA Rust - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Lookup time complexity in different data structures

Consider these three data structures holding 1 million integers: a hash map, an array, and a linked list. Which one will generally provide the fastest lookup for a specific value?

A Hash map, because it uses hashing to find elements in near constant time.

B Array, because it stores elements contiguously and supports binary search.

C Linked list, because it allows sequential access to elements.

D All have the same lookup speed since they store the same data.

💡 Hint

Think about how each data structure finds an element and the time it takes.

Hash maps use hashing to jump directly to the element's location, giving near constant time lookup. Arrays require searching (linear or binary if sorted), and linked lists require sequential traversal, which is slower.

❓ Predict Output

intermediate

Output of lookup simulation in Rust

What will be the output of this Rust code simulating lookup in different data structures?

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    let array = [10, 20, 30, 40, 50];
    let linked_list = vec![10, 20, 30, 40, 50]; // simulate linked list with Vec

    map.insert(1, 10);
    map.insert(2, 20);
    map.insert(3, 30);
    map.insert(4, 40);
    map.insert(5, 50);

    let key = 3;
    let map_lookup = map.get(&key);
    let array_lookup = array.iter().find(|&&x| x == 30);
    let list_lookup = linked_list.iter().find(|&&x| x == 30);

    println!("Map lookup: {:?}", map_lookup);
    println!("Array lookup: {:?}", array_lookup);
    println!("Linked list lookup: {:?}", list_lookup);
}

A

Map lookup: None
Array lookup: Some(30)
Linked list lookup: None

B

Map lookup: Some(30)
Array lookup: None
Linked list lookup: Some(30)

C

Map lookup: Some(30)
Array lookup: Some(30)
Linked list lookup: Some(30)

D

Map lookup: None
Array lookup: None
Linked list lookup: None

💡 Hint

Check how the key and values are matched in each lookup.

The map lookup uses key 3 which maps to value 30, so Some(30). The array and linked list searches for value 30, which exists, so both return Some(30).

🧠 Conceptual

advanced

Why linked lists have slower lookup than arrays

Why does a linked list generally have slower lookup times compared to an array?

A Because linked lists use hashing internally which is slower than arrays.

B Because linked lists use binary search which is slower than linear search.

C Because linked lists store elements contiguously, causing cache misses.

D Because linked lists store elements non-contiguously, requiring traversal from the head to find an element.

💡 Hint

Think about how memory layout affects access speed.

Linked lists store elements scattered in memory, so to find an element you must start at the head and follow links one by one, which is slower than direct index access in arrays.

❓ Predict Output

advanced

Output of Rust code comparing lookup times

What is the output of this Rust code that measures lookup times in a vector and a hash map?

DSA Rust

use std::collections::HashMap;
use std::time::Instant;

fn main() {
    let size = 1000000;
    let mut vec = Vec::new();
    let mut map = HashMap::new();

    for i in 0..size {
        vec.push(i);
        map.insert(i, i);
    }

    let target = size - 1;

    let start_vec = Instant::now();
    let found_vec = vec.iter().find(|&&x| x == target);
    let duration_vec = start_vec.elapsed();

    let start_map = Instant::now();
    let found_map = map.get(&target);
    let duration_map = start_map.elapsed();

    println!("Vector lookup found: {:?} in {:?}", found_vec, duration_vec);
    println!("HashMap lookup found: {:?} in {:?}", found_map, duration_map);
}

A

Vector lookup found: Some(999999) in longer time
HashMap lookup found: Some(999999) in shorter time

B

Vector lookup found: Some(999999) in shorter time
HashMap lookup found: Some(999999) in longer time

C

Vector lookup found: None
HashMap lookup found: Some(999999)

D

Vector lookup found: Some(999999)
HashMap lookup found: None

💡 Hint

Consider the time complexity of searching in a vector vs a hash map.

Vector lookup uses linear search, which takes longer especially near the end. Hash map lookup uses hashing for near constant time, so it is faster.

🧠 Conceptual

expert

Choosing data structure for frequent lookups and insertions

You need a data structure for a program that does frequent lookups and insertions of unique keys. Which data structure is best and why?

A Binary tree, because it guarantees constant time lookups and insertions.

B Hash map, because it offers average constant time for both lookups and insertions.

C Array, because it stores elements contiguously and allows fast insertions at the end.

D Linked list, because it allows fast insertions anywhere and constant time lookups.

💡 Hint

Think about average time complexity for lookup and insertion in each data structure.

Hash maps provide average O(1) time for both lookup and insertion. Arrays have slow insertions except at the end and slow lookups unless sorted. Linked lists have slow lookups. Binary trees have O(log n) time, not constant.

Practice

1. Which data structure provides the fastest average lookup time for a key-value pair in Rust?

easy

A. Array

B. Vector

C. Linked List

D. Hash Map

Solution

1. Step 1: Understand lookup times for data structures

   Hash Map uses hashing to find keys quickly, usually in constant time O(1).

2. Step 2: Compare with Array and Linked List

   Array and Linked List require searching elements linearly, which is slower (O(n)).

3. Final Answer:

   Hash Map -> Option D

4. Quick Check:

   Fastest lookup = Hash Map [OK]

Hint: Hash Map uses hashing for O(1) lookup, arrays and lists are slower [OK]

Common Mistakes:

• Thinking arrays have O(1) lookup for keys (only for indices)
• Confusing linked list traversal with direct access
• Assuming vector is same as hash map for lookup

2. Which Rust syntax correctly declares a mutable HashMap named map with String keys and i32 values?

easy

A. let map: HashMap = HashMap::new();

B. let mut map: HashMap = HashMap::new();

C. let mut map = HashMap::new();

D. let map = HashMap::new();

Solution

1. Step 1: Check correct syntax for mutable HashMap declaration

   In Rust, let mut declares a mutable variable. The type is HashMap<String, i32>. The constructor is HashMap::new().

2. Step 2: Identify errors in other options

   let map = HashMap::new(); misses mut. let mut map = HashMap::new(); has wrong generic syntax. let map: HashMap = HashMap::new(); swaps key and value types.

3. Final Answer:

   let mut map: HashMap = HashMap::new(); -> Option B

4. Quick Check:

   Mutable HashMap syntax = let mut map: HashMap = HashMap::new(); [OK]

Hint: Use let mut with HashMap::new() and correct generics [OK]

Common Mistakes:

• Forgetting mut keyword for mutable map
• Wrong generic syntax with new()
• Swapping key and value types

3. What is the output of this Rust code snippet?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("orange", 5);

    let lookup = map.get("banana");
    println!("{:?}", lookup);
}

medium

A. None

B. 2

C. Some(2)

D. banana

Solution

1. Step 1: Understand HashMap get method return type

   The get method returns an Option type: Some(&value) if key exists, else None.

2. Step 2: Check if key "banana" exists and its value

   Key "banana" exists with value 2, so get("banana") returns Some(&2). Printing with {:?} shows Some(2).

3. Final Answer:

   Some(2) -> Option C

4. Quick Check:

   HashMap get returns Option = Some(2) [OK]

Hint: HashMap get returns Option; Some(value) if found, else None [OK]

Common Mistakes:

• Expecting direct value instead of Option
• Confusing None with Some
• Printing key instead of value

4. Identify the error in this Rust code that tries to find a value in a linked list:

struct Node {
    value: i32,
    next: Option,
}

fn find(head: &Option, target: i32) -> bool {
    let mut current = head;
    while current.is_some() {
        if current.as_ref().unwrap().value == target {
            return true;
        }
        current = current.unwrap().next;
    }
    false
}

medium

A. Using unwrap() twice causes ownership error

B. Missing mutable keyword for current

C. Incorrect comparison operator in if statement

D. next field should be a reference, not Box

Solution

1. Step 1: Analyze ownership in while loop

   Calling unwrap() on current moves ownership, so current cannot be used again.

2. Step 2: Identify why unwrap() causes error

   Using unwrap() twice consumes current, causing ownership error. Instead, use references or pattern matching.

3. Final Answer:

   Using unwrap() twice causes ownership error -> Option A

4. Quick Check:

   Ownership error due to unwrap() usage [OK]

Hint: unwrap() moves ownership; use references to avoid errors [OK]

Common Mistakes:

• Ignoring ownership rules with unwrap()
• Thinking mutable needed for current here
• Confusing Box with reference types

5. You need to store a large collection of user IDs (integers) and quickly check if a user ID exists. Which data structure is best and why? Choose the best option considering lookup speed and memory efficiency.

hard

A. Hash Map, because it offers average constant time lookup for keys

B. Array, because it provides constant time lookup for any integer key

C. Linked List, because it uses less memory and is easy to implement

D. Vector, because it automatically resizes and supports fast lookup

Solution

1. Step 1: Consider lookup speed for large collections

   Linked List has O(n) lookup, which is slow. Array lookup by index is O(1), but only if keys are indices, not arbitrary integers.

2. Step 2: Evaluate Hash Map and Vector

   Hash Map provides average O(1) lookup for arbitrary keys like user IDs. Vector lookup by index is O(1), but user IDs may not be continuous indices.

3. Final Answer:

   Hash Map, because it offers average constant time lookup for keys -> Option A

4. Quick Check:

   Best lookup for arbitrary keys = Hash Map [OK]

Hint: Use Hash Map for fast lookup of arbitrary keys like user IDs [OK]

Common Mistakes:

• Assuming array lookup works for arbitrary keys
• Choosing linked list for speed
• Confusing vector with hash map for key lookup